Isih ialah salah satu operasi asas yang kami lakukan pada objek. Malah pada zaman kanak-kanak, kanak-kanak diajar untuk menyusun semasa mereka mengembangkan kemahiran berfikir mereka. Komputer dan perisian tidak terkecuali. Terdapat pelbagai jenis algoritma pengisihan dalam Java . Saya cadangkan anda menyemak apa itu dan cara ia berfungsi. Bagaimana jika anda ditanya tentang salah seorang daripada mereka pada temu duga suatu hari nanti?
pengenalan
Isih elemen adalah salah satu kategori algoritma yang mesti diketahui oleh pembangun. Jika sains komputer dahulu tidak diambil serius semasa saya di sekolah, pelajar hari ini mesti boleh melaksanakan dan memahami algoritma pengisihan. Algoritma asas, yang paling mudah, dilaksanakan menggunakan gelung for . Sememangnya, untuk mengisih koleksi elemen, seperti tatasusunan, anda perlu melalui koleksi tersebut. Sebagai contoh:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Apa yang boleh dikatakan tentang segmen kod ini? Kami mempunyai gelung di mana kami menukar indeks ( int i) daripada 0 kepada elemen terakhir dalam tatasusunan. Sebenarnya, kami hanya mengambil setiap elemen dalam tatasusunan dan mencetak kandungannya. Lebih banyak elemen dalam tatasusunan, lebih lama kod akan diambil untuk selesai. Iaitu, jika nialah bilangan elemen, apabila n = 10program akan mengambil masa dua kali lebih lama untuk dijalankan daripada apabila n = 5. Jika program kami mempunyai gelung tunggal, masa pelaksanaan berkembang secara linear: lebih banyak elemen terdapat, lebih lama masa pelaksanaan. Ternyata algoritma di atas berfungsi dalam masa linear (fungsi linear n). Dalam kes sedemikian, kami mengatakan bahawa kerumitan algoritma ialah "O(n)". Notasi ini juga dipanggil "O besar" atau "tingkah laku asimptotik". Tapi awak boleh ingat"
Algoritma pengisihan yang paling mudah (isih gelembung)
Katakan kita mempunyai tatasusunan dan kita boleh mengulanginya. Hebat. Sekarang mari kita cuba menyusunnya dalam tertib menaik. Apakah maksud ini? Ini bermakna bahawa diberikan dua elemen (contohnya, a = 6, b = 5), kita mesti menyusun semula adan bjika alebih besar daripada b(jika a > b). Apakah maksud ini apabila kita menggunakan indeks untuk bekerja dengan koleksi (seperti yang berlaku dengan tatasusunan)? Ini bermakna jika elemen dengan indeks a lebih besar daripada elemen dengan indeks b( array[a] > array[b]), maka elemen mesti ditukar. Terdapat pelbagai cara untuk menukar tempat. Tetapi kami akan menggunakan teknik yang mudah, mudah difahami dan mudah diingati:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Sekarang kita boleh menulis perkara berikut:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
Seperti yang anda lihat, unsur-unsur itu benar-benar ditukar. Kami bermula dengan indeks 1, kerana jika tatasusunan hanya mempunyai satu elemen, ungkapan itu array[i] < array[i-1]tidak sah untuk index 0. Melakukan ini juga melindungi kami daripada kes di mana tatasusunan tidak mempunyai unsur atau hanya satu elemen, dan ia menjadikan kod kelihatan lebih baik. Tetapi tatasusunan yang terhasil masih tidak diisih, kerana satu pas tidak mencukupi untuk melakukan pengisihan. Kita perlu menambah satu lagi gelung di mana kita akan melakukan hantaran berulang kali sehingga kita mendapat tatasusunan yang diisih:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
Jadi kami menyelesaikan algoritma pengisihan pertama kami. Kami mengulangi gelung luar ( while) sehingga kami memutuskan bahawa tiada lagi lelaran diperlukan. Secara lalai, sebelum setiap lelaran baharu, kami menganggap tatasusunan kami diisih dan kami tidak perlu mengulang lagi. Sehubungan itu, kami bergerak secara berurutan melalui unsur-unsur dan menyemak andaian ini. Tetapi jika elemen tidak teratur, maka kami menukar elemen dan memahami bahawa kami kini tidak mempunyai jaminan bahawa elemen berada dalam susunan yang betul. Ini bermakna kita perlu melakukan lelaran lain. Sebagai contoh, katakan kita mempunyai [3, 5, 2]. 5adalah lebih daripada 3— semuanya baik-baik saja. Tetapi 2kurang daripada 5. Walau bagaimanapun, [3, 2, 5]memerlukan pas lain, kerana3 > 2dan mereka perlu ditukar. Kerana kami menggunakan gelung dalam gelung, kerumitan algoritma kami meningkat. nElemen yang diberi , ia menjadi n * n, iaitu, O(n^2). Ini dipanggil kerumitan kuadratik. Secara umum, kita tidak dapat mengetahui dengan tepat berapa banyak lelaran yang diperlukan. Ungkapan kerumitan algoritma menunjukkan bagaimana kerumitan meningkat dalam kes terburuk. Iaitu, ia menunjukkan berapa banyak masa pelaksanaan akan meningkat apabila bilangan elemen nberubah. Isih gelembung ialah salah satu algoritma pengisihan yang paling mudah dan paling tidak cekap. Ia juga kadang-kadang dipanggil "jenis bodoh". Bahan mengenai topik ini:
Algoritma pengisihan lain ialah isihan pemilihan. Ia juga mempunyai kerumitan kuadratik, tetapi lebih lanjut mengenainya kemudian. Jadi ideanya mudah. Pada setiap pas, kami memilih elemen terkecil dan mengalihkannya ke permulaan. Selain itu, setiap hantaran bermula satu langkah ke kanan. Dalam erti kata lain, hantaran pertama bermula dari elemen sifar, hantaran kedua dari yang pertama, dll. Ia akan kelihatan seperti ini:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
Jenis ini tidak stabil, kerana unsur yang sama (dari segi apa jua ciri yang kita gunakan untuk mengisih unsur) boleh mengubah kedudukan relatifnya. Terdapat satu contoh yang baik ialah dalam artikel Wikipedia tentang jenis pemilihan . Bahan mengenai topik ini:
Isihan sisipan juga mempunyai kerumitan kuadratik, kerana kita sekali lagi mempunyai gelung dalam gelung. Apakah yang menjadikan jenis sisipan berbeza? Algoritma pengisihan ini adalah "stabil." Ini bermakna elemen yang sama tidak akan mengubah susunan relatifnya. Sekali lagi, kami maksudkan sama dari segi ciri yang kami susun mengikut.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
Jenis ulang-alik
Terdapat satu lagi algoritma pengisihan mudah: pengisihan ulang-alik. Ini juga dikenali sebagai jenis gelembung dua arah atau jenis shaker koktel. Nama ganti ini memberitahu kami bahawa jenis ulang-alik bukan mengenai pesawat ulang-alik. Ia mengenai sesuatu yang bergerak ke sana ke mari. Kini anda boleh memikirkannya apabila anda memikirkan algoritma ini. Apakah intipati algoritma? Intipati algoritma ialah kita beralih dari kiri ke kanan, menukar elemen dan menyemak sama ada mana-mana elemen yang tinggal ke arah lain perlu ditukar.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
Satu lagi algoritma pengisihan mudah ialah jenis shell. Intipatinya adalah serupa dengan jenis gelembung, tetapi dalam setiap lelaran kita mempunyai jurang yang berbeza antara elemen yang dibandingkan. Ia dipotong separuh dengan setiap lelaran. Berikut ialah pelaksanaan:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
Sebagai tambahan kepada algoritma pengisihan mudah ini, terdapat juga algoritma pengisihan yang lebih rumit. Contohnya, cantumkan jenis. Terdapat dua perkara yang perlu diperhatikan. Pertama, rekursi datang untuk menyelamatkan kami di sini. Kedua, kerumitan algoritma tidak lagi kuadratik, seperti yang biasa kita lakukan. Kerumitan algoritma ini adalah logaritma. Ini ditulis sebagai O(n log n). Jadi mari kita laksanakan. Pertama, kami akan menulis panggilan rekursif kepada kaedah isihan:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
Sekarang, mari kita tambahkan tindakan utama pada pelaksanaan kita. Inilah kaedah super kami:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
Kita boleh menjalankan contoh kita dengan memanggilmergeSort(array, 0, array.length-1). Seperti yang anda lihat, prosesnya bermula untuk menerima tatasusunan input bersama-sama dengan petunjuk permulaan dan akhir bahagian yang perlu diisih. Apabila pengisihan bermula, ini adalah permulaan dan penghujung tatasusunan. Kemudian kita mengira pembatas, iaitu indeks di mana kita akan membahagi tatasusunan. Jika tatasusunan boleh dibahagikan kepada 2 bahagian, maka kami memanggil kaedah isihan secara rekursif untuk dua bahagian tatasusunan. Kami menyediakan penimbal tambahan di mana kami akan memasukkan bahagian yang diisih. Seterusnya, tetapkan indeks pada permulaan bahagian untuk diisih dan mula berjalan melalui setiap elemen penimbal kosong, mengisinya dengan elemen terkecil. Jika elemen yang ditunjukkan oleh indeks adalah kurang daripada elemen yang ditunjukkan oleh pembatas, kami meletakkan elemen dalam penimbal dan mengalihkan indeks. Jika tidak, kami meletakkan elemen yang ditunjuk oleh pembatas ke dalam penimbal dan mengalihkan pembatas. Sebaik sahaja pembatas melangkaui sempadan bahagian yang sedang diisih atau kami mengisi keseluruhan tatasusunan, julat yang ditentukan dianggap diisih.Bahan mengenai topik ini:
Satu lagi algoritma pengisihan yang menarik ialah mengira jenis. Kerumitan algoritma di sini ialah O(n+k), di mana nialah bilangan elemen dan kmerupakan nilai maksimum bagi sesuatu elemen. Algoritma ini mempunyai satu kelemahan: kita perlu mengetahui nilai minimum dan maksimum dalam tatasusunan. Berikut ialah contoh jenis pengiraan:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
Anda boleh memahami bahawa ia sangat menyusahkan apabila kita perlu mengetahui terlebih dahulu nilai minimum dan maksimum. Dan kami mempunyai algoritma lain di sini: radix sort. Saya hanya akan membentangkan algoritma di sini secara visual. Lihat bahan tambahan untuk pelaksanaan: Bahan:
Nah, sudah tiba masanya untuk pencuci mulut — jenis cepat, salah satu algoritma pengisihan yang paling terkenal. Ia mempunyai kerumitan logaritma: O(n log n). Algoritma pengisihan ini dibangunkan oleh Tony Hoare. Menariknya, dia menciptanya semasa tinggal di Kesatuan Soviet, di mana dia belajar terjemahan mesin di Universiti Moscow dan membangunkan buku frasa Rusia-Inggeris. Lebih-lebih lagi, Java menggunakan versi yang lebih kompleks bagi algoritma ini dalam Arrays.sort. Bagaimana pula Collections.sort? Mengapa tidak melihat bagaimana perkara disusun "di bawah hud"? Inilah kodnya:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
Ini semua perkara yang sangat menakutkan, jadi mari kita mendalaminya. Untuk tatasusunan input ( int[]sumber), kami mencipta dua penanda: kiri ( L) dan kanan ( R). Semasa panggilan kaedah pertama, ia sepadan dengan permulaan dan penghujung tatasusunan. Kemudian kami mengenal pasti elemen pangsi, yang dinamakan dengan tepat pivot. Selepas ini, tugas kami adalah untuk mengalihkan nilai yang lebih kecil daripada pivotke kiri pivot, dan nilai yang lebih besar — ke kanan. Untuk melakukan ini, kami mula-mula mengalihkan Lpenanda sehingga kami menemui nilai yang lebih besar daripada pivot. Jika tiada nilai yang lebih kecil ditemui, maka
L menjadi sama dengan
pivot. Kemudian kita gerakkan
Rpenanda sehingga kita dapati nilai yang lebih kecil daripada
pivot. Jika tiada nilai yang lebih besar ditemui, maka
Rmenjadi sama dengan
pivot. Seterusnya, jika
Lpenanda berada sebelum
Rpenanda atau bertepatan dengannya, maka kita cuba menukar elemen jika
Lelemen itu kurang daripada
Relemen. Kemudian kita beralih
Lke kanan sebanyak 1, dan kita beralih
Rke kiri sebanyak 1. Apabila
Lpenanda bergerak melepasi
Rpenanda, ini bermakna pertukaran selesai: nilai yang lebih kecil berada di sebelah kiri
pivot, nilai yang lebih besar berada di sebelah kanan
pivot. Selepas ini, kami memanggil kaedah isihan yang sama secara rekursif pada subarrays — dari permulaan bahagian untuk diisih ke penanda kanan, dan dari penanda kiri ke penghujung bahagian untuk diisih. Kenapa dari awal ke penanda kanan? Kerana pada akhir lelaran, ternyata penanda kanan bergerak cukup untuk menjadi sempadan bahagian kiri. Algoritma ini lebih kompleks daripada pengisihan mudah, jadi sebaiknya lakarkannya. Ambil sehelai kertas putih dan tulis: 4 2 6 7 3. Kemudian tulis
pivotdi tengah, iaitu di bawah nombor 6. Bulatkan. Bawah 4, tulis
L, dan bawah 3, tulis
R. 4 kurang daripada 6, 2 kurang daripada 6. Kami akhirnya berpindah
Lke
pivotkedudukan, kerana
Ltidak boleh melepasi
pivot, mengikut syarat. Tulis semula 4 2 6 7 3. Bulatkan 6 (
pivot) dan letakkan
Ldi bawahnya. Sekarang gerakkan
Rpenanda. 3 adalah kurang daripada 6, jadi letakkan
Rpenanda pada 3. Oleh kerana 3 adalah kurang daripada 6 (
pivot), kita melakukan a
swap. Tulis keputusan: 4 2 3 7 6. Bulatan 6, kerana ia masih
pivot. Penanda
Ldihidupkan 3.
RPenanda dihidupkan 6. Ingat bahawa kita menggerakkan penanda sehingga
Lbergerak melepasi
R. Beralih
Lke nombor seterusnya. Di sini saya ingin meneroka dua kemungkinan: 1) kes di mana nombor kedua terakhir ialah 7 dan 2) kes di mana ia adalah 1, bukan 7.
Jika nombor kedua terakhir ialah 1: Pindahkan
Lpenanda kepada 1, kerana kita boleh bergerak
Lselagi itu
Lpenanda menunjuk kepada nombor yang lebih kecil daripada
pivot. Tetapi kita tidak boleh beralih
Rdaripada 6, kerana kita hanya boleh mengalihkan R jika
Rpenanda menunjuk kepada nombor yang lebih besar daripada
pivot. Kami tidak melakukan a
swap, kerana 1 kurang daripada 6. Tulis situasi semasa: 4 2 3 1 6. Bulatan 6 (
pivot).
Lberalih
pivotdan berhenti bergerak.
Rtidak bergerak. Kami tidak melakukan pertukaran. Shift
Ldan
Rdengan satu kedudukan. Tulis
Rpenanda di bawah 1.
LPenanda di luar sempadan. Kerana
Ldi luar batasan, kami tidak melakukan apa-apa. Tetapi, kami menulis 4 2 3 1 sekali lagi, kerana ini adalah bahagian kiri kami, iaitu kurang daripada
pivot(6). Pilih yang baharu
pivotdan mulakan semuanya semula :)
Jika nombor kedua terakhir ialah 7:Alihkan
Lpenanda ke 7. Kami tidak boleh mengalihkan penanda yang betul, kerana ia sudah menghala ke pangsi. 7 adalah lebih besar daripada
pivot, jadi kami melakukan
swap. Tulis keputusan: 4 2 3 6 7. Bulatan 6, kerana ia adalah
pivot. Penanda
Lkini dialihkan kepada 7, dan
Rpenanda dialihkan kepada 3. Tidak masuk akal untuk mengisih bahagian dari
Lke penghujung, kerana hanya terdapat 1 elemen. Walau bagaimanapun, kami menghantar bahagian dari 4 ke
Rpenanda untuk disusun. Kami memilih a
pivotdan bermula sekali lagi :) Pada pandangan pertama, nampaknya jika anda menambah banyak nilai yang sama dengan
pivot, maka anda akan memecahkan algoritma. Tetapi ini tidak berlaku. Anda boleh memikirkan kombinasi yang rumit dan di atas kertas meyakinkan diri anda bahawa semuanya betul dan kagum bahawa tindakan mudah itu melaksanakan mekanisme pengisihan yang boleh dipercayai. Satu-satunya kelemahan ialah algoritma pengisihan ini tidak stabil. Kerana pertukaran boleh mengubah susunan relatif elemen yang sama jika salah satu daripadanya ditemui sebelum
pivotelemen lain ditukar ke bahagian sebelumnya
pivot.
Garisan bawah
Di atas, kami melihat set algoritma pengisihan "gentleman" yang dilaksanakan di Java. Algoritma secara amnya berguna, baik dari perspektif yang diterapkan dan dari segi pembelajaran cara berfikir. Ada yang lebih mudah, ada yang lebih rumit. Orang pintar mempertahankan disertasi mereka untuk beberapa orang. Bagi yang lain, mereka menulis buku yang sangat tebal. Saya harap bahan tambahan akan membantu anda mempelajari lebih banyak lagi, kerana artikel ini hanyalah gambaran keseluruhan yang telah ternyata menjadi berat. Dan tujuannya adalah untuk memberikan pengenalan kecil. Anda juga boleh mendapatkan pengenalan kepada algoritma jika anda membaca
"Algoritma Grokking ". Saya juga suka senarai main daripada Jack Brown:
AQA Decision 1 1.01 Tracing an Algorithm . Untuk keseronokan, anda boleh melihat visualisasi algoritma semasa
pengisihan.visualgo.net .
GO TO FULL VERSION