Penyortiran cepat telah membuat saya melihatnya sejak lama dan menyiksa saya untuk waktu yang lama, karena saya memiliki gambaran umum, tetapi berbagai masalah selalu muncul saat menulis kode. Masih sulit bagi saya pribadi untuk men-debugnya tingkat kesulitan tertentu, dan karena kerja keras dan kemalasan, kesalahan yang tidak dapat di-debug telah lama disingkirkan. Hari ini akhirnya keluar, dan saya masih sedikit bersemangat sedikit penjelasan.
Untuk mempelajari pengurutan cepat, Anda harus mempelajari metode bagi dan taklukkan terlebih dahulu. Ide dari membagi dan menaklukkan adalah dengan memberikan rangkaian angka yang tidak berurutan (angka tersebut asumsi, bisa juga objek lain. Tentu saja, parameter metode ini dapat ditentukan sendiri. Saya di sini Misalkan ada array bilangan bulat) dan kemudian memberikannya kepadanya Angka tengah, metode bagi dan taklukkan, akan membagi angka-angka tersebut menjadi dua bagian berdasarkan angka tengah yang diberikan padanya, satu bagian berada di sebelah kiri angka tengah, dan bagian lainnya berada di sebelah kanan titik pemisah, angka pada kedua sisinya masih urut, cara saya mendefinisikannya sebagai berikut:
//kiri adalah titik akhir kiri dari bagian bagi-dan-taklukkan dalam larik, dan kanan adalah total titik akhir dari bagian bagi-dan-taklukkan dalam larik Saya ingin membagi dan menaklukkan 5 bilangan bulat pertama, saya dapat memberikan 0 atau 4 sebagai public int signalFenZhi(int left,int right){ if(left<0||left>n-1||right<0||right> n-1){ kembali -1; } int temp = tes[kiri]; j=kanan; int i=kiri; sementara(i<j){ while(tes[j]>=tes[kiri]&&i<j){ j--; } while(tes[i]<=tes[kiri] &&i<j){ i++; } jika(i<j){ suhu = pengujian[i]; pengujian[i]=ujian[j]; pengujian[j]=temp; = tes[i]; tes[i]=tes[kiri]; tes[kiri]=temp; } for(int m=0;m<n;m++){ System.out.print(test[m]+" "); ;Tentu saja, Anda juga bisa memasukkan angka tengah sebagai parameter. Sekarang saya hanya menggunakan angka kiri yang dimasukkan sebagai angka pembagi.
Setelah memahami pembagian dan penaklukan, maka cara pengurutan cepat adalah dengan membagi dan menaklukan bilangan-bilangan yang sudah habis dibagi menjadi dua bagian, begitu seterusnya sampai semua bilangan tersebut berurutan.
public void quickSort(int kiri,int kanan){ if(kanan-kiri<1){ return ; }else{ int titik = this.signalFenZhi(kiri, kanan); titik!=kiri&&titik!=kanan){ quickSort(kiri,titik-1); quickSort(titik+1,kanan);Efisiensi pengurutan cepat sangat baik di antara banyak algoritma pengurutan. Kompleksitas waktunya adalah O(N*log2n). Namun, jika titik pembagian dan penaklukan tidak dipilih dengan baik, kompleksitas waktu akan berkurang menjadi (n kuadrat). ), karena jika array ini kebetulan diurutkan, dan kemudian kita mengambil angka paling kiri yang dilewati setiap kali, efisiensinya akan sangat rendah, jadi kita harus menghindari situasi ini. Jika semua opsi diuji, maka akan memakan banyak waktu waktu, jadi Cara komprominya adalah dengan menambahkan angka tengah pada angka paling kiri dan paling kanan, lalu mencari angka tengah di antara keduanya. Menggunakan ini sebagai nilai pemisah akan membuat segalanya lebih baik. tapi setelah saya selesaikan, pendekatan ini kurang bagus. Akan lebih baik jika meneruskan nilai pembagian sebagai metode membagi dan menaklukkan. Hati-hati teman-teman bisa mencobanya sendiri, tapi saya tidak akan mencobanya di sini, pada dasarnya sama saja!
paket com.jll; kelas publik FenZhi { int[] tes; int n=10; publik FenZhi(){ tes = new int[10]; untuk(int i=0;i<n;i++){ tes[i] =(int)(Matematika.acak()*100)+1; Sistem.keluar.cetak(uji[i]+" "); } Sistem.keluar.println(); } public FenZhi(int n){ if(n>0){ this.n=n; test = new int[n]; for(int i=0;i<n;i++){ test[i]=(int)(Matematika.acak ()*100)+1; } } } sinyal int publikFenZhiMajorizationFirst(int kiri,int kanan){ if(kiri<0||kiri>n-1||kanan<0||kanan>n-1||kiri>=kanan){ return -1; } if(kanan-kiri>=2){ int tengah = (kanan+kiri)/2; if(tes[kiri]>tes[tengah]){ int temp = tes[tengah]; tes[tengah] = tes[kiri]; if(tes[kiri]>tes[kanan]){ int temp = tes[kiri]; tes[kiri] = tes[kanan]; tes[kanan] = suhu; } if(tes[tengah]>tes[kanan] ){ int temp = uji[tengah]; uji[tengah] = uji[tengah] = uji[kiri]; = suhu; int j=kanan-1; int i=kiri+1; while(i<j){ while(tes[j]>=tes[kiri]&&i<j){ j--; ]<=ujian[kiri]&&i<j){ i++; } if(i<j){ suhu = uji[i]; uji[i]=ujian[j]; saya==j){ temp = uji[i]; uji[i]=uji[kiri]; uji[kiri]=temp; } /*if(i==j){ temp = uji[tengah]; ]; uji[i]=temp; }*/ /*untuk(int m=0;m<n;m++){ Sistem.keluar.cetak(uji[m]+" "); kalau tidak { if(tes[kanan]<tes[kiri]){ int temp = tes[kanan]; tes[kanan] = tes[kiri]; tes[kiri] = temp; } kembali ke kanan; ,int kanan){ if(kanan-kiri<1){ return ; }else{ int titik = this.signalFenZhiMajorizationFirst(kiri, kanan); adalah: "+titik); quickSortMajorizationFirst(kiri,titik-1); quickSortMajorizationFirst(titik+1,kanan); } } public static void main(String[] args) { FenZhi f = new FenZhi(); System.out. println(f.signalFenZhiMajorizationFirst(0, 9)); f.quickSortMajorizationFirst(0,fn-1); //f.quickSort(0,f.test.length-1); for(int i:f.test){ Sistem.out.print(i+" "); }}Kode berjalan sebagai berikut:
95 40 64 18 78 23 73 84 40 intinya adalah:4 intinya adalah:1intinya adalah:3intinya adalah:7intinya adalah:6intinya adalah:918 23 40 40 64 73 78 84 95
Di atas adalah apa yang saya pelajari, catat untuk referensi di masa mendatang.