stabilitas (stabilitas)
Algoritme pengurutan stabil, yaitu ketika ada dua catatan yang sama dari kunci R dan S, dan R muncul sebelum S dalam daftar asli, R juga akan muncul sebelum S dalam daftar yang diurutkan.
Klasifikasi algoritma pengurutan
Yang umum termasuk penyisipan (insertion sort/Hill sort), pertukaran (bubble sort/quick sort), seleksi (selection sort), merge (merge sort), dll.
1. Sortir penyisipan
Pengurutan Penyisipan (Insertion Sort) bekerja dengan membuat urutan yang terurut. Untuk data yang tidak diurutkan, ia memindai dari belakang ke depan dalam urutan yang diurutkan untuk menemukan posisi yang sesuai dan menyisipkannya. Dalam pelaksanaan insertion sort biasanya digunakan in-place sorting (yaitu pengurutan yang hanya menggunakan O(1) spasi ekstra, oleh karena itu pada saat proses scanning dari belakang ke depan perlu dilakukan pergeseran secara berulang-ulang dan bertahap). mengurutkan elemen ke belakang, menyediakan ruang penyisipan untuk elemen terbaru.
Secara umum, pengurutan penyisipan diimplementasikan pada array menggunakan in-place. Algoritma spesifiknya dijelaskan sebagai berikut:
Dimulai dari elemen pertama, elemen-elemen tersebut dianggap telah terurut.
Dapatkan elemen berikutnya dan pindai dari belakang ke depan dalam urutan elemen yang diurutkan.
Jika elemen (yang diurutkan) lebih besar dari elemen baru, pindahkan elemen tersebut ke posisi berikutnya.
Ulangi langkah 3 hingga Anda menemukan posisi di mana elemen yang diurutkan lebih kecil atau sama dengan elemen baru.
Setelah memasukkan elemen baru pada posisi tersebut.
Ulangi langkah 2~5.
Copy kode kodenya sebagai berikut:
public static void insertionSort(int[] data) {
for (int indeks = 1; indeks < data.panjang; indeks++) {
int kunci = data[indeks];
int posisi = indeks;
// menggeser nilai yang lebih besar ke kanan
while (posisi > 0 && data[posisi - 1] > kunci) {
data[posisi] = data[posisi - 1];
posisi--;
}
data[posisi] = kunci;
}
}
2. Penyortiran bukit
Shell Sort adalah jenis penyisipan. Ini merupakan perbaikan pada algoritma pengurutan penyisipan langsung. Cara ini disebut juga dengan mengurangi penyortiran inkremental, karena DL. Nama Shell diambil dari usulannya pada tahun 1959.
Penyortiran bukit mengusulkan metode yang lebih baik berdasarkan dua properti penyisipan penyortiran berikut:
Pengurutan penyisipan sangat efisien ketika beroperasi pada data yang hampir terurut, yaitu dapat mencapai efisiensi penyortiran linier.
Namun penyisipan penyortiran umumnya tidak efisien karena penyisipan penyortiran hanya dapat memindahkan data satu bit pada suatu waktu.
Copy kode kodenya sebagai berikut:
statis <E meluas Sebanding<? super E>> void shellSort(Daftar<E> a) {
ke dalam h = 1;
sementara (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) oleh Knuth,1973>: 1, 4, 13, 40, 121, . ..
untuk (; jam >= 1; jam /= 3)
untuk (int i = h; i < a.size(); i++)
untuk (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Koleksi.swap(a, j, jh);
}
3. Penyortiran gelembung
Bubble Sort (Bubble Sort, diterjemahkan dari Taiwan sebagai: Bubble Sort atau Bubble Sort) adalah algoritma pengurutan sederhana. Ini berulang kali menelusuri urutan yang akan diurutkan, membandingkan dua elemen sekaligus dan menukarnya jika urutannya salah. Pekerjaan mengunjungi array diulangi sampai tidak diperlukan pertukaran lagi, yang berarti array telah diurutkan. Nama algoritma ini berasal dari fakta bahwa elemen yang lebih kecil akan perlahan-lahan "mengambang" ke bagian atas array melalui pertukaran.
Algoritma pengurutan gelembung bekerja sebagai berikut:
Bandingkan elemen yang berdekatan, dan jika elemen pertama lebih besar dari elemen kedua, tukar keduanya.
Lakukan hal yang sama untuk setiap pasangan elemen yang berdekatan, dimulai dengan pasangan pertama dan diakhiri dengan pasangan terakhir, di mana elemen terakhir harus menjadi bilangan terbesar.
Ulangi langkah di atas untuk semua elemen kecuali yang terakhir.
Ulangi terus langkah di atas untuk elemen yang semakin sedikit setiap kali hingga tidak ada lagi pasangan angka yang tersisa untuk dibandingkan.
Copy kode kodenya sebagai berikut:
public static void bubbleSort(int[] data) {
int suhu = 0;
for (int i = data.panjang - 1; i > 0; --i) {
boolean isSort = salah;
untuk (int j = 0; j < i; ++j) {
jika (data[j + 1] < data[j]) {
suhu = data[j];
data[j] = data[j + 1];
data[j + 1] = suhu;
isSort = benar;
}
}
// Jika pertukaran terjadi pada loop dalam, lanjutkan perbandingan; jika tidak ada pertukaran yang terjadi pada loop dalam, maka dianggap telah diurutkan.
jika (!isSort)
merusak;
}
}
4. Penyortiran cepat
Quicksort merupakan penyempurnaan dari bubble sort. Diusulkan oleh CAR Hoare pada tahun 1962. Ide dasarnya adalah membagi data yang akan diurutkan menjadi dua bagian independen melalui satu pengurutan. Semua data di satu bagian lebih kecil dari semua data di bagian lainnya, dan kemudian gunakan metode ini untuk memisahkan kedua bagian data dengan cepat. Sorting, seluruh proses pengurutan dapat dilakukan secara rekursif, sehingga seluruh data menjadi suatu urutan yang terurut.
Pengurutan cepat menggunakan strategi bagi dan taklukkan untuk membagi daftar menjadi dua sub-daftar.
Langkah-langkahnya adalah:
Memilih elemen dari urutan disebut "pivot".
Susun ulang larik sehingga semua elemen yang lebih kecil dari nilai dasar ditempatkan di depan nilai dasar, dan semua elemen yang lebih besar dari nilai dasar ditempatkan di belakang nilai dasar (angka yang sama dapat ditempatkan di kedua sisi). Setelah partisi ini keluar, basis berada di tengah-tengah urutan. Ini disebut operasi partisi.
Urutkan secara rekursif subarray elemen yang lebih kecil dari nilai dasar dan subarray elemen yang lebih besar dari nilai dasar.
Copy kode kodenya sebagai berikut:
/*
* implementasi yang lebih efisien untuk quicksort
* gunakan nilai median kiri, tengah dan kanan (@lihat #median()) untuk pivot, dan
* loop dalam yang lebih efisien untuk inti algoritma.
*/
Quicksort kelas publik {
int akhir statis publik CUTOFF = 11;
/**
* algoritma pengurutan cepat.<br />
*
* @param arr array item yang sebanding
*/
public static <T meluas Sebanding<? super T>> void quicksort(T[] arr) {
quickSort(arr, 0, arr.panjang - 1);
}
/**
* mendapatkan median kiri, tengah dan kanan
* urutkan ini dan sembunyikan pivot dengan meletakkannya di akhir array. <br />
*
* @param arr array item yang sebanding
* @param meninggalkan indeks paling kiri dari subarray
* @param di kanan indeks subarray paling kanan.<br />
* @kembalikan T
*/
public static <T meluas Sebanding<? super T>> T median(T[] arr, int kiri, int kanan) {
int tengah = (kiri + kanan) / 2;
jika (arr[kiri].bandingkanKe(arr[tengah]) > 0)
swapRef(arr, kiri, tengah);
jika (arr[kiri].bandingkanKe(arr[kanan]) > 0)
swapRef(arr, kiri, kanan);
jika (arr[tengah].bandingkanKe(arr[kanan]) > 0)
swapRef(arr, tengah, kanan);
swapRef(arr, tengah, kanan - 1);
kembali arr[kanan - 1];
}
/**
* metode internal untuk mengurutkan array dengan algoritma pengurutan cepat
*
* @param arr array Item Sebanding. <br />
* @param meninggalkan indeks paling kiri dari subarray
* @param di kanan indeks paling kanan dari subarray
*/
private static <T meluas Sebanding<? super T>> void quickSort(T[] arr, int kiri, int kanan) {
if (kiri + CUTOFF <= kanan) {
// temukan porosnya
T pivot = median(arr, kiri, kanan);
// mulai mempartisi
int i = kiri, j = kanan - 1;
untuk (;;) {
while (arr[++i].compareTo(pivot) < 0);
while (arr[--j].compareTo(pivot) > 0);
jika (saya <j)
swapRef(arr, saya, j);
kalau tidak
merusak;
}
// menukar referensi pivot kembali ke koleksi kecil.
swapRef(arr, i, kanan - 1);
quickSort(arr, left, i - 1); // mengurutkan koleksi kecil.
quickSort(arr, i + 1, kanan); // mengurutkan koleksi yang besar.
} kalau tidak {
// jika jumlah totalnya kurang dari CUTOFF kita menggunakan insertion sort
// sebagai gantinya (menyebabkan ini jauh lebih efisien).
Sortir(arr, sisipkan kiri, kanan);
}
}
/**
* metode untuk menukar referensi dalam array.<br />
*
* @param arr array Objek.<br />
* @param idx1 indeks elemen pertama
* @param idx2 indeks elemen kedua
*/
publik statis <T> batal swapRef(T[] arr, int idx1, int idx2) {
T tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* metode untuk mengurutkan subarray dari awal hingga akhir dengan penyisipan penyortiran
*algoritma.<br />
*
* @param arr array item yang sebanding
* @param memulai posisi awal
* @param mengakhiri posisi akhir
*/
public static <T meluas Sebanding<? super T>> void insertionSort(T[] arr, int start, int end) {
ke dalam aku;
untuk (int j = mulai + 1; j <= akhir; j++) {
T tmp = arr[j];
untuk (i = j; i > mulai && tmp.compareTo(arr[i - 1]) < 0; i--) {
arr[i] = arr[i - 1];
}
arr[i] = tmp;
}
}
private static void printArray(Bilangan Bulat[] c) {
untuk (int i = 0; i < c.panjang; i++)
Sistem.keluar.cetak(c[i] + ",");
Sistem.keluar.println();
}
public static void main(String[] args) {
Data bilangan bulat[] = {10, 4, 9, 23, 1, 45, 27, 5, 2};
System.out.println("bubbleSort...");
printArray(data);
penyortiran cepat(data);
printArray(data);
}
}
5. Penyortiran seleksi
Pengurutan pilihan adalah algoritma pengurutan yang sederhana dan intuitif. Begini cara kerjanya. Pertama, carilah elemen terkecil (besar) pada barisan yang belum diurutkan dan simpan di awal barisan yang telah diurutkan. Kemudian, lanjutkan mencari elemen terkecil (besar) dari sisa elemen yang belum diurutkan, lalu letakkan di akhir barisan. urutan yang diurutkan. Begitu seterusnya hingga semua elemen terurut.
Karena setiap proses penentuan elemen akan memiliki subproses pemilihan nilai minimum, maka orang dengan gamblang menyebutnya pengurutan seleksi.
Misalnya pada barisan 5 8 5 2 9, kita mengetahui bahwa elemen pertama 5 akan ditukar dengan 2 pada lintasan pertama. Kemudian urutan relatif dari kedua bilangan 5 pada barisan aslinya akan dimusnahkan, sehingga terjadilah pengurutan seleksi tidak stabil.
Copy kode kodenya sebagai berikut:
public static void selectSort(int[] data) {
int indeks minimum = 0;
int suhu = 0;
for (int i = 0; i < data.panjang; i++) {
minIndex = i; //Indeks array data minimum dari area tak berurutan
for (int j = i + 1; j < data.length; j++) { // Temukan data terkecil di area tak berurutan dan simpan subskrip arraynya
if (data[j] < data[minIndex]) {
indeks min = j;
}
}
if (minIndex != i) { // Jika posisi minimum dari area tak berurutan bukan data default pertama, tukarkan.
suhu = data[i];
data[i] = data[minIndeks];
data[Indeks min] = suhu;
}
}
}
6. Gabungkan pengurutan
Pengurutan gabungan adalah algoritme pengurutan yang efektif berdasarkan operasi penggabungan. Algoritma ini merupakan aplikasi yang sangat khas yang menggunakan metode membagi dan menaklukkan (Divide and Conquer).
Proses operasi penggabungan adalah sebagai berikut:
Gunakan spasi agar ukurannya merupakan jumlah dari dua barisan yang diurutkan. Ruang ini digunakan untuk menyimpan barisan yang digabungkan.
Tetapkan dua penunjuk, posisi awal adalah posisi awal dari dua urutan yang diurutkan.
Bandingkan elemen yang ditunjuk oleh dua penunjuk, pilih elemen yang relatif kecil dan masukkan ke dalam ruang gabungan, lalu pindahkan penunjuk ke posisi berikutnya.
Ulangi langkah 3 hingga penunjuk mencapai akhir urutan.
Menyalin semua elemen sisa dari urutan lainnya langsung ke akhir urutan yang digabungkan.
Copy kode kodenya sebagai berikut:
public static int[] mergeSort(int[] arr) {//Merge sort--rekursi
if (arr.panjang == 1) {
kembali arr;
}
int setengah = arr.panjang / 2;
int[] arr1 = int[setengah] baru;
int[] arr2 = int baru[arr.panjang - setengah];
Sistem.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, setengah, arr2, 0, arr2.panjang);
arr1 = penggabunganSort(arr1);
arr2 = penggabunganSort(arr2);
kembalikan mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {//Merge subrutin pengurutan
int[] hasil = baru int[arr1.length + arr2.length];
ke dalam saya = 0;
ke dalam j = 0;
ke dalam k = 0;
sementara (benar) {
jika (arr1[i] < arr2[j]) {
hasil[k] = arr1[i];
if (++i > arr1.panjang - 1) {
merusak;
}
} kalau tidak {
hasil[k] = arr2[j];
if (++j > arr2.panjang - 1) {
merusak;
}
}
k++;
}
untuk (; saya < arr1.panjang; i++) {
hasil[++k] = arr1[i];
}
untuk (; j < arr2.panjang; j++) {
hasil[++k] = arr2[j];
}
hasil pengembalian;
}
Kode lengkap (kecuali QuickSort)
Copy kode kodenya sebagai berikut:
paket com.clzhang.sample.thinking;
import java.util.*;
/**
* Implementasi Java dari beberapa algoritma pengurutan umum
* @penulis acer
*
*/
kelas publik CommonSort {
/**
* Algoritme spesifik penyisipan semacam dijelaskan sebagai berikut:
* 1. Dimulai dari elemen pertama, elemen tersebut dianggap telah terurut
* 2. Keluarkan elemen berikutnya dan pindai dari belakang ke depan dalam urutan elemen yang diurutkan
* 3. Jika elemen (yang diurutkan) lebih besar dari elemen baru, pindahkan elemen tersebut ke posisi berikutnya
* 4. Ulangi langkah 3 hingga Anda menemukan posisi elemen yang diurutkan lebih kecil atau sama dengan elemen baru
* 5. Setelah memasukkan elemen baru ke posisi ini
* 6. Ulangi langkah 2~5
*/
public static void insertionSort(int[] data) {
for (int indeks = 1; indeks < data.panjang; indeks++) {
int kunci = data[indeks];
int posisi = indeks;
// menggeser nilai yang lebih besar ke kanan
while (posisi > 0 && data[posisi - 1] > kunci) {
data[posisi] = data[posisi - 1];
posisi--;
}
data[posisi] = kunci;
}
}
/**
* Penyortiran bukit, silakan merujuk ke Wikipedia untuk ide implementasi algoritme yang cocok untuk operasi penyortiran dalam jumlah besar;
*/
statis <E meluas Sebanding<? super E>> void shellSort(Daftar<E> a) {
ke dalam h = 1;
sementara (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) oleh Knuth,1973>: 1, 4, 13, 40, 121, . ..
untuk (; jam >= 1; jam /= 3)
untuk (int i = h; i < a.size(); i++)
untuk (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Koleksi.swap(a, j, jh);
}
/**
* Pengoperasian algoritma bubble sort adalah sebagai berikut:
* 1. Bandingkan elemen yang berdekatan. Jika yang pertama lebih besar dari yang kedua, tukar keduanya.
* 2. Lakukan pekerjaan yang sama untuk setiap pasangan elemen yang berdekatan, dari pasangan pertama di awal hingga pasangan terakhir di akhir. Pada titik ini, elemen terakhir harus menjadi angka terbesar.
* 3. Ulangi langkah di atas untuk semua elemen kecuali yang terakhir.
* 4. Ulangi terus langkah di atas untuk elemen yang semakin sedikit setiap kali hingga tidak ada pasangan angka yang dapat dibandingkan. [1]
*/
public static void bubbleSort(int[] data) {
int suhu = 0;
for (int i = data.panjang - 1; i > 0; --i) {
boolean isSort = salah;
untuk (int j = 0; j < i; ++j) {
jika (data[j + 1] < data[j]) {
suhu = data[j];
data[j] = data[j + 1];
data[j + 1] = suhu;
isSort = benar;
}
}
// Jika pertukaran terjadi pada loop dalam, lanjutkan perbandingan; jika tidak ada pertukaran yang terjadi pada loop dalam, maka dianggap telah diurutkan.
jika (!isSort)
merusak;
}
}
/**
* Ide dasar pengurutan seleksi adalah:
* 1. Selama proses melintasi array, jika i mewakili nomor urut saat ini yang perlu diurutkan, Anda perlu mencari nilai minimum di antara sisa [i+1...n-1].
* 2.Kemudian tukarkan nilai minimum yang ditemukan dengan nilai yang ditunjukkan oleh i.
* Karena setiap proses penentuan elemen akan memiliki subproses pemilihan nilai minimum, maka orang dengan gamblang menyebutnya pengurutan seleksi.
* @paramdata
*/
public static void selectSort(int[] data) {
int indeks minimum = 0;
int suhu = 0;
for (int i = 0; i < data.panjang; i++) {
minIndex = i; //Indeks array data minimum dari area tak berurutan
for (int j = i + 1; j < data.length; j++) { // Temukan data terkecil di area tak berurutan dan simpan subskrip arraynya
if (data[j] < data[minIndex]) {
indeks min = j;
}
}
if (minIndex != i) { // Jika posisi minimum dari area tak berurutan bukan data default pertama, tukarkan.
suhu = data[i];
data[i] = data[minIndeks];
data[minIndex] = suhu;
}
}
}
/**
* Proses operasi penggabungan adalah sebagai berikut:
* 1. Gunakan spasi agar ukurannya merupakan jumlah dari dua barisan yang diurutkan.
* 2. Tetapkan dua penunjuk, posisi awal adalah posisi awal dari dua urutan yang diurutkan.
* 3. Bandingkan elemen yang ditunjuk oleh dua penunjuk, pilih elemen yang relatif kecil dan masukkan ke dalam ruang gabungan, lalu pindahkan penunjuk ke posisi berikutnya
* 4. Ulangi langkah 3 hingga penunjuk mencapai akhir urutan
* 5. Salin semua elemen sisa dari urutan lainnya langsung ke akhir urutan yang digabungkan
*/
public static int[] mergeSort(int[] arr) {//Merge sort--rekursi
if (arr.panjang == 1) {
kembali arr;
}
int setengah = arr.panjang / 2;
int[] arr1 = int[setengah] baru;
int[] arr2 = int baru[arr.panjang - setengah];
Sistem.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, setengah, arr2, 0, arr2.panjang);
arr1 = penggabunganSort(arr1);
arr2 = penggabunganSort(arr2);
kembalikan mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {//Merge subrutin pengurutan
int[] hasil = baru int[arr1.length + arr2.length];
ke dalam saya = 0;
ke dalam j = 0;
ke dalam k = 0;
sementara (benar) {
jika (arr1[i] < arr2[j]) {
hasil[k] = arr1[i];
if (++i > arr1.panjang - 1) {
merusak;
}
} kalau tidak {
hasil[k] = arr2[j];
if (++j > arr2.panjang - 1) {
merusak;
}
}
k++;
}
untuk (; saya < arr1.panjang; i++) {
hasil[++k] = arr1[i];
}
untuk (; j < arr2.panjang; j++) {
hasil[++k] = arr2[j];
}
hasil pengembalian;
}
pribadi statis kekosongan printArray(int[] c) {
untuk (int i = 0; i < c.panjang; i++)
Sistem.keluar.cetak(c[i] + ",");
Sistem.keluar.println();
}
public static void main(String []args){
int[] data = {10,4,9,23,1,45,27,5,2};
System.out.println("bubbleSort...");
int[] a = data.klon();
printArray(a);
bubbleSort(a);
printArray(a);
System.out.println("pilihSort...");
int[] b = data.klon();
printArray(b);
pilihUrutkan(b);
printArray(b);
System.out.println("insertionSort...");
int[] c = data.klon();
printArray(c);
penyisipanSort(c);
printArray(c);
System.out.println("shellSort...");
Daftar<Bilangan Bulat> daftar = Daftar Array baru<Bilangan Bulat>();
for(int i=0;i<data.panjang;i++)
daftar.tambahkan(data[i]);
System.out.println(daftar);
shellSort(daftar);
System.out.println(daftar);
System.out.println("mergeSort...");
int[] d = data.klon();
printArray(d);
printArray(mergeSort(d));
}
}