Artikel ini terutama memperkenalkan bagaimana Java mencapai delapan algoritma penyortiran yang umum digunakan: memasukkan penyortiran, menyortir yang menggelegak, memilih penyortiran, penyortiran bukit, penyortiran cepat, penyortiran merger, pesanan penumpukan, dan penyortiran basis LST.
Klasifikasi
1) Masukkan sortir (penyortiran langsung, penyortiran bukit)
2) Pertukaran penyortiran (penyortiran yang menggelegak, penyortiran cepat)
3) Pilih penyortiran (langsung pilih penyortiran, penyortiran bertumpuk)
4) Gabungkan penyortiran
5) Distribusi dan penyortiran (penyortiran basis)
Ruang tambahan yang diperlukan adalah yang paling: ruang paling tambahan untuk merger dan penyortiran: kecepatan theverage tercepat dari urutan penumpukan: penyortiran cepat
Tidak stabil: Sortir dengan cepat, Sortir bukit, penyortiran ditumpuk.
Mari kita lihat hubungan antara 8 penyortiran:
1. Langsung masukkan sortir
(1) Ide Dasar: Di antara set yang akan diurutkan, dengan asumsi (n-1) [n> = 2] Nomor sudah ada baris
Secara berurutan, sekarang nomor NN dimasukkan ke dalam urutan sebelumnya, sehingga nomor N ini
Itu juga berurutan. Ini berulang kali diedarkan sampai seluruh pesanan beres.
(2) Contoh
(3) Sadarilah dengan Java
paket com.njue; 17,18,23,34,15,35,25,53,51}; Temp = a [i]; untuk (; j> = 0 && temp <a [j]; j-) {a [j+1] = a [j]; test;} untuk (int i = 0; i <a.length; i ++) {System.out.println (a [i]);}}}}}2. Urutan bukit (penyortiran tambahan minimum)
(1) Ide -Ide Dasar: Jumlah kelompok yang akan diurutkan berdasarkan algoritma dibagi menjadi beberapa kelompok sesuai dengan jumlah peningkatan D (n/2, N sebagai jumlah yang akan diurutkan). dan diurutkan, dan kemudian gunakan peningkatan yang lebih kecil (D/2) untuk mengelompokkannya, dan kemudian langsung memasukkan Sort di setiap grup. Ketika kenaikan dikurangi menjadi 1, jenis dimasukkan secara langsung dan jenis selesai.
(2) Contoh:
(3) Sadarilah dengan Java
PublicClass Shellsort {publicShellsort () {int a [] = {1,54,3,78,34,12,45,56,100}; .Ceil (d1/2); ) {int j = id; j+d] = temp;}} if (d == 1) {break;} untuk (int i = 0; i <a.length; i ++) {System.out.println (a [i]);} }}3. Pilihan penyortiran sederhana
(1) Ide -Ide Dasar: Dalam kelompok yang akan diurutkan, pilih jumlah terkecil dari jumlah angka dan posisi pertama;
Kemudian temukan jumlah terkecil dari posisi kedua dalam angka yang tersisa, sehingga loop dibandingkan dengan jumlah terakhir dari angka terakhir dan angka terakhir.
(2) Contoh:
(3) Sadarilah dengan Java
PUBLIK SELEACTSORT {PUBLIK SELECTORT () {int a [] = {1,54,3,78,34,12,45}; ) {int j = i+1; j]; Saya] );}}4. Heap Sorting
(1) Ide -Ide Dasar: Pengepakan pengepakan adalah pilihan penyortiran yang berbentuk pohon, yang merupakan peningkatan yang efektif dari pemilihan penyortiran langsung.
Definisi heap adalah sebagai berikut: urutan (h1, h2, ..., hn) dengan n elemen, dan hanya sebagai puas (hai> = h2i, hai> = 2i+1) atau (hai <= h2i, hai <= 2i 2i) +1) (i = 1,2, ..., n/2) disebut tumpukan. Di sini kita hanya membahas tumpukan yang memenuhi persyaratan yang pertama. Dapat dilihat dari definisi tumpukan bahwa elemen teratas (yaitu, elemen pertama) harus menjadi item terbesar (tempat pembuangan atas besar). Pohon biner lengkap dapat secara intuitif mewakili struktur tumpukan. Bagian atas tumpukan berakar, dan yang lainnya adalah sub -trees kiri dan sub -trees kanan. Awalnya, urutan yang akan diurutkan dianggap sebagai pohon biner yang disimpan secara berurutan, menyesuaikan pesanan penyimpanan mereka sehingga mereka menjadi tumpukan. Kemudian bertukar simpul root dengan simpul terakhir dari heap. Kemudian menyesuaikan kembali angka sebelumnya (n-1) untuk membuatnya tumpukan. Menurut tipe ini, sampai hanya ada dua node, dan menukarnya, dan akhirnya mendapatkan urutan n node yang tertib. Dari perspektif deskripsi algoritma, urutan penumpukan membutuhkan dua proses. Oleh karena itu, ada dua fungsi komposisi penyortiran tumpukan. Salah satunya adalah fungsi penetrasi tumpukan, dan yang lainnya adalah berulang kali memanggil fungsi infiltrasi untuk mengimplementasikan fungsi penyortiran.
(2) Contoh:
Urutan awal: 46,79,56,38,40,84
Konstruksi:
Pertukaran, tendang angka maksimum dari tumpukan
Node yang tersisa dibangun lagi, dan angka maksimum dipertukarkan
Dorong dalam Orde: Dua node terakhir di tumpukan terakhir dari dua node terakhir dipertukarkan, satu ditendang keluar, dan jenisnya selesai.
(3) Sadarilah dengan Java
Impor java.util.arrays; , 15,35,25,53,51}; Panjang; 0, arraylength-i); Metode Goneralt Stub Int TMP = Data [i]; ) {// TODO Metode auto-gonement stub // simpul induk dari simpul (simpul terakhir) dari LastIndex Start untuk (int i = (lastIndex-); i> = 0; i-) {// k Simpan node Int k = i; // Jika sub-simpul dari node k saat ini ada (k*2+1 <= lastIndex) {// K Node Kiri Node Indeks int BiggerIndex = 2*K+1; BiggerIndex lebih kecil dari LastIndex, yaitu simpul kanan dari simpul K yang mewakili simpul K yang diwakili oleh BiggerIndex+1 ada jika (BiggerIndex <LastIndex) {// Jika nilai node yang tepat lebih besar, (data [lebih besarindex ] <Data [BigGerIndex+1]) {// BigGerIndex Selalu mencatat indeks BiggerIndex ++;} // Jika nilai node K kurang dari nilai node K if (data [data [data [data k ] <Data [BigGerIndex]) {// pertukaran swap mereka (data, k, BigGerIndex); dari nilai node kiri dan kanan.5. Penyortiran gelembung
(1) Gagasan Dasar: Dalam kelompok yang akan diurutkan, semua angka dalam ruang lingkup yang belum habis, perbandingan dan penyesuaian dua angka yang berdekatan dari atas ke bawah, sehingga yang lebih besar beberapa tenggelam, lebih kecil. Artinya: setiap kali dua angka yang berdekatan dibandingkan, mereka menemukan bahwa persyaratan penyortiran dan penyortiran mereka berlawanan, dan mereka akan bertukar.
(2) Contoh:
(3) Sadarilah dengan Java
Public Class Bubblesort {publicBbitsort () {inta [] = {49,38,65,97,76,13,49,78,34,5,4,62,98,54,54,56, 17,18,23 , 34,15,35,25,53,51}; Panjang-1-I; +1] = temp;}}} untuk (int i = 0; i <a.length; i ++) {System.out.println (a [i]);}}6. Urutkan dengan cepat
(1) Gagasan Dasar: Pilih elemen tolok ukur, biasanya pilih elemen pertama atau elemen terakhir. Elemen Benchmark.
(2) Contoh:
(3) Sadarilah dengan Java
PublicClass Quicksort {Inta [] = {49,38,65,97,76,13,27,78,34,264,5,4,99,98,54,56,17,18 23,34,15,35,25 , 53,51}; [] Daftar, int low) {int tmp = daftar [rendah]; High-;} Daftar [Low] = Daftar [Tinggi]; // Catatan yang lebih kecil dari poros tengah bergerak ke low-end sementara (Low <High && List [Low] <= TMP) {Low ++;} Daftar [Tinggi] = Daftar [Rendah]; int low, int tinggi) {if (rendah <tinggi) {int middle = getMiddle (daftar, rendah, tinggi); Penyortiran Tables Low -character_quicksort (Daftar, Tengah + 1, Tinggi); Array adalah kosong_quicksort (a2,0, a2.length -1);}}}7. Gabungkan penyortiran
(1) Penyortiran Dasar: Lampiran (gabungan) Metode penyortiran adalah untuk menggabungkan dua (atau lebih) atau lebih formulir menjadi orde baru, yaitu kata pengantar. Kemudian gabungkan urutan urutan ke dalam urutan keseluruhan.
(2) Contoh:
(3) Sadarilah dengan Java
Impor java.util.arrays; , 15,35,25,53,51}; (a [i]);} publicVoid sort (int [] data, int kiri, int right) {// tODO-GONERALTEDMethod Stub if (kiri <kanan) { / / / temukan indeks intermediate int center = (kiri+kanan) /2; ;}} PublicVoid merge (int [] data, int left, int center, int right) {// TODO-Goneorate int [data.length]; Proyek intray tengah = kiri; ]) {tmparr [ketiga ++] = data [kiri ++];} else {tmparr [ketiga ++] = data [mid ++]; ++];} while (kiri <= center) {tmparr [ketiga ++] = data [kiri ++]; println (arrays.tostring (data));8. Penyortiran dasar
(1) Gagasan Dasar: Seragam Semua nilai perbandingan (bilangan bulat positif) dengan panjang angka yang sama, dan jumlah digit pendek dibuat sebelum nol. Kemudian, mulai dari posisi terendah dan menyortir secara bergantian. Ini akan menjadi urutan tertib dari posisi terendah ke penyortiran bit tertinggi.
(2) Contoh:
(3) Sadarilah dengan Java
Impor Java.util.arraylist; , 54,101,56,17,18,23,34,15,35,25,53,51}; {System.out.println (a [i]);}} public void sort (int [] array) {// Pertama tentukan jumlah perjalanan penyortiran; <Array.length; Time ++;} // Buat 10 antrian; INS>); <array; int math.pow (10, i i 10, i); 0; = queue.get (k);Di atas adalah semua isi artikel ini.