Isih ialah salah satu jenis aktiviti atau tindakan asas yang dilakukan pada objek. Malah pada zaman kanak-kanak, kanak-kanak diajar untuk menyusun, mengembangkan pemikiran mereka. Komputer dan program juga tidak terkecuali. Terdapat pelbagai jenis algoritma. Saya cadangkan anda melihat apa itu dan bagaimana ia berfungsi. Selain itu, bagaimana jika suatu hari anda ditanya tentang salah satu daripada ini dalam temu bual?
pengenalan
Isih elemen ialah salah satu kategori algoritma yang mesti dibiasakan oleh pembangun. Jika suatu ketika dahulu, semasa saya belajar, sains komputer tidak dipandang serius, kini di sekolah mereka sepatutnya dapat melaksanakan algoritma pengisihan dan memahaminya. Algoritma asas, yang paling mudah, dilaksanakan menggunakan gelung for. Sememangnya, untuk mengisih koleksi elemen, sebagai contoh, tatasusunan, anda perlu merentasi koleksi ini. 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 anda boleh katakan tentang sekeping kod ini? Kami mempunyai gelung di mana kami menukar nilai 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 dilaksanakan. Iaitu, jika n ialah bilangan elemen, dengan n=10 program akan mengambil masa 2 kali lebih lama untuk dilaksanakan berbanding dengan n=5. Apabila program kami mempunyai satu gelung, masa pelaksanaan meningkat secara linear: lebih banyak elemen, lebih lama pelaksanaan. Ternyata algoritma kod di atas berfungsi dalam masa linear (n). Dalam kes sedemikian, "kerumitan algoritma" dikatakan sebagai O(n). Notasi ini juga dipanggil "O besar" atau "tingkah laku asimptotik". Tetapi anda hanya boleh mengingati "kerumitan algoritma."
Isihan paling mudah (Isih Buih)
Oleh itu, kami mempunyai tatasusunan dan boleh mengulanginya. Hebat. Sekarang mari kita cuba menyusunnya dalam tertib menaik. Apakah maknanya bagi kita? Ini bermakna diberikan dua elemen (contohnya, a=6, b=5), kita mesti menukar a dan b jika a lebih besar daripada b (jika a > b). Apakah maksud ini untuk kita apabila bekerja dengan koleksi mengikut indeks (seperti yang berlaku dengan tatasusunan)? Ini bermakna jika elemen dengan indeks a lebih besar daripada elemen dengan indeks b, (tatasusunan[a] > tatasusunan[b]), elemen tersebut mesti ditukar. Bertukar tempat selalunya dipanggil swap. Terdapat pelbagai cara untuk menukar tempat. Tetapi kami menggunakan kod yang ringkas, jelas dan mudah diingati:
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 kita dapat lihat, unsur-unsur sememangnya telah berubah tempat. Kami bermula dengan satu elemen, kerana... jika tatasusunan hanya terdiri daripada satu elemen, ungkapan 1 < 1 tidak akan kembali benar dan oleh itu kami akan melindungi diri kami daripada kes tatasusunan dengan satu elemen atau tanpa elemen itu sama sekali, dan kod itu akan kelihatan lebih baik. Tetapi tatasusunan terakhir kami tidak diisih, kerana... Tidak mungkin untuk mengisih semua orang dalam satu laluan. Kita perlu menambah satu lagi gelung di mana kita akan melakukan hantaran satu demi satu 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 pengisihan pertama kami berjaya. Kami lelaran dalam 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 mahu mengulang lagi. Oleh itu, kami meneliti elemen secara berurutan dan menyemak andaian ini. Tetapi jika unsur-unsur tidak teratur, kita menukar unsur-unsur dan menyedari bahawa kita tidak pasti bahawa unsur-unsur itu kini dalam susunan yang betul. Oleh itu, kami ingin melakukan satu lelaran lagi. Contohnya, [3, 5, 2]. 5 lebih daripada tiga, semuanya baik-baik saja. Tetapi 2 adalah kurang daripada 5. Walau bagaimanapun, [3, 2, 5] memerlukan satu pas lagi, kerana 3 > 2 dan mereka perlu ditukar. Memandangkan kami menggunakan gelung dalam gelung, ternyata kerumitan algoritma kami meningkat. Dengan n unsur ia menjadi n * n, iaitu O(n^2). Kerumitan ini dipanggil kuadratik. Seperti yang kita faham, kita tidak dapat mengetahui dengan tepat berapa banyak lelaran yang diperlukan. Penunjuk kerumitan algoritma berfungsi untuk menunjukkan trend peningkatan kerumitan, kes terburuk. Berapa banyak masa berjalan akan meningkat apabila bilangan elemen n berubah. Isih gelembung ialah salah satu jenis yang paling mudah dan tidak cekap. Ia juga kadang-kadang dipanggil "isihan bodoh". Bahan berkaitan:
Jenis lain ialah jenis pemilihan. Ia juga mempunyai kerumitan kuadratik, tetapi lebih lanjut mengenainya kemudian. Jadi ideanya mudah. Setiap pas memilih elemen terkecil dan mengalihkannya ke permulaan. Dalam kes ini, mulakan setiap hantaran baharu dengan bergerak ke kanan, iaitu hantaran pertama - dari elemen pertama, hantaran kedua - dari laluan kedua. 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));
Pengisihan ini tidak stabil, kerana unsur-unsur yang sama (dari sudut pandangan ciri yang mana kita menyusun unsur-unsur) boleh mengubah kedudukannya. Contoh yang baik diberikan dalam artikel Wikipedia: Sorting_by-selection . Bahan berkaitan:
Isihan sisipan juga mempunyai kerumitan kuadratik, kerana kita sekali lagi mempunyai gelung dalam gelung. Bagaimanakah ia berbeza daripada jenis pemilihan? Pengisihan ini "stabil". Ini bermakna elemen yang sama tidak akan mengubah susunannya. Sama dari segi ciri yang kita susun.
int[] array ={10,2,10,3,1,2,5};System.out.println(Arrays.toString(array));for(int left =0; left < array.length; left++){// Retrieve the value of the elementint value = array[left];// Move through the elements that are before the pulled elementint i = left -1;for(; i >=0; i--){// If a smaller value is pulled out, move the larger element furtherif(value < array[i]){
array[i +1]= array[i];}else{// If the pulled element is larger, stopbreak;}}// Insert the extracted value into the freed space
array[i +1]= value;}System.out.println(Arrays.toString(array));
Di antara jenis mudah, terdapat satu lagi - pengisihan ulang-alik. Tetapi saya lebih suka variasi ulang-alik. Nampaknya saya jarang bercakap tentang pesawat ulang-alik, dan ulang-alik lebih kepada larian. Oleh itu, lebih mudah untuk membayangkan bagaimana pengangkutan ulang-alik dilancarkan ke angkasa. Berikut ialah perkaitan dengan algoritma ini. Apakah intipati algoritma? Intipati algoritma adalah bahawa kita beralih dari kiri ke kanan, dan apabila menukar elemen, kita menyemak semua elemen lain yang tertinggal untuk melihat sama ada pertukaran itu perlu diulang.
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 jenis mudah ialah jenis Shell. Intipatinya adalah serupa dengan jenis gelembung, tetapi setiap lelaran kita mempunyai jurang yang berbeza antara elemen yang dibandingkan. Setiap lelaran dibelah dua. Berikut adalah contoh pelaksanaan:
int[] array ={10,2,10,3,1,2,5};System.out.println(Arrays.toString(array));// Calculate the gap between the checked elementsint gap = array.length /2;// As long as there is a difference between the elementswhile(gap >=1){for(int right =0; right < array.length; right++){// Shift the right pointer until we can find one that// there won't be enough space between it and the element before itfor(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));
Selain jenis ringkas yang ditunjukkan, terdapat jenis yang lebih kompleks. Contohnya, cantumkan jenis. Pertama, rekursi akan datang untuk membantu kami. Kedua, kerumitan kita tidak lagi kuadratik, seperti biasa. Kerumitan algoritma ini adalah logaritma. Ditulis sebagai O(n log n). Jadi mari kita lakukan ini. Mula-mula, mari kita tulis panggilan rekursif kepada kaedah pengisihan:
publicstaticvoidmergeSort(int[] source,int left,int right){// Choose a separator, i.e. split the input array in halfint delimiter = left +((right - left)/2)+1;// Execute this function recursively for the two halves (if we can split(if(delimiter >0&& right >(left +1)){mergeSort(source, left, delimiter -1);mergeSort(source, delimiter, right);}}
Sekarang, mari tambahkan tindakan utama padanya. Berikut ialah contoh kaedah super kami dengan pelaksanaan:
publicstaticvoidmergeSort(int[] source,int left,int right){// Choose a separator, i.e. split the input array in halfint delimiter = left +((right - left)/2)+1;// Execute this function recursively for the two halves (if we can split(if(delimiter >0&& right >(left +1)){mergeSort(source, left, delimiter -1);mergeSort(source, delimiter, right);}// Create a temporary array with the desired sizeint[] buffer =newint[right - left +1];// Starting from the specified left border, go through each elementint cursor = left;for(int i =0; i < buffer.length; i++){// We use the delimeter to point to the element from the right side// If delimeter > right, then there are no unadded elements left on the right sideif(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);}
Mari jalankan contoh dengan memanggil mergeSort(array, 0, array.length-1). Seperti yang anda lihat, intipatinya datang kepada fakta yang kami ambil sebagai input tatasusunan yang menunjukkan permulaan dan penghujung bahagian yang akan diisih. Apabila pengisihan bermula, ini adalah permulaan dan penghujung tatasusunan. Seterusnya kita mengira pembatas - kedudukan pembahagi. Jika pembahagi boleh membahagikan kepada 2 bahagian, maka kami memanggil pengisihan rekursif untuk bahagian di mana pembahagi membahagi tatasusunan. Kami menyediakan tatasusunan penimbal tambahan di mana kami memilih bahagian yang diisih. Seterusnya, kami meletakkan kursor pada permulaan kawasan yang hendak diisih dan mula melalui setiap elemen tatasusunan kosong yang telah kami sediakan dan mengisinya dengan elemen terkecil. Jika elemen yang ditunjuk oleh kursor adalah lebih kecil daripada elemen yang ditunjuk oleh pembahagi, kami meletakkan elemen ini dalam tatasusunan penimbal dan menggerakkan kursor. Jika tidak, kami meletakkan elemen yang ditunjuk oleh pemisah ke dalam tatasusunan penimbal dan memindahkan pemisah. Sebaik sahaja pemisah melangkaui sempadan kawasan yang diisih atau kami mengisi keseluruhan tatasusunan, julat yang ditentukan dianggap diisih. Bahan berkaitan:
Satu lagi algoritma pengisihan yang menarik ialah Isih Mengira. Kerumitan algoritma dalam kes ini ialah O(n+k), di mana n ialah bilangan elemen, dan k ialah nilai maksimum unsur. Terdapat satu masalah dengan algoritma: kita perlu mengetahui nilai minimum dan maksimum dalam tatasusunan. Berikut ialah contoh pelaksanaan jenis pengiraan:
publicstaticint[]countingSort(int[] theArray,int maxValue){// Array with "counters" ranging from 0 to the maximum valueint numCounts[]=newint[maxValue +1];// In the corresponding cell (index = value) we increase the counterfor(int num : theArray){
numCounts[num]++;}// Prepare array for sorted resultint[] sortedArray =newint[theArray.length];int currentSortedIndex =0;// go through the array with "counters"for(int n =0; n < numCounts.length; n++){int count = numCounts[n];// go by the number of valuesfor(int k =0; k < count; k++){
sortedArray[currentSortedIndex]= n;
currentSortedIndex++;}}return sortedArray;}
Seperti yang kita faham, adalah sangat menyusahkan apabila kita perlu mengetahui terlebih dahulu nilai minimum dan maksimum. Dan kemudian terdapat algoritma lain - Isih Radix. Saya akan membentangkan algoritma di sini hanya secara visual. Untuk pelaksanaan, lihat bahan:
Nah, untuk pencuci mulut - salah satu algoritma yang paling terkenal: jenis cepat. Ia mempunyai kerumitan algoritma, iaitu, kita mempunyai O(n log n). Jenis ini juga dipanggil jenis Hoare. Menariknya, algoritma itu dicipta oleh Hoare semasa tinggal di Kesatuan Soviet, di mana dia belajar terjemahan komputer di Universiti Moscow dan sedang membangunkan buku frasa Rusia-Inggeris. Algoritma ini juga digunakan dalam pelaksanaan yang lebih kompleks dalam Arrays.sort dalam Java. Bagaimana pula dengan Collections.sort? Saya cadangkan anda melihat sendiri bagaimana ia disusun "di bawah tudung". Jadi, kodnya:
publicstaticvoidquickSort(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 while element is less than pivotwhile(source[leftMarker]< pivot){
leftMarker++;}// Move the right marker until element is greater than pivotwhile(source[rightMarker]> pivot){
rightMarker--;}// Check if you don't need to swap elements pointed to by markersif(leftMarker <= rightMarker){// The left marker will only be less than the right marker if we have to swapif(leftMarker < rightMarker){int tmp = source[leftMarker];
source[leftMarker]= source[rightMarker];
source[rightMarker]= tmp;}// Move markers to get new borders
leftMarker++;
rightMarker--;}}while(leftMarker <= rightMarker);// Execute recursively for partsif(leftMarker < rightBorder){quickSort(source, leftMarker, rightBorder);}if(leftBorder < rightMarker){quickSort(source, leftBorder, rightMarker);}}
Segala-galanya di sini sangat menakutkan, jadi kami akan memikirkannya. Untuk sumber tatasusunan input int[], kami menetapkan dua penanda, kiri (L) dan kanan (R). Apabila dipanggil buat kali pertama, ia sepadan dengan permulaan dan penghujung tatasusunan. Seterusnya, elemen sokongan ditentukan, aka pivot. Selepas ini, tugas kami adalah untuk mengalihkan nilai kurang daripada pivot, ke kiri pivotdan yang lebih besar ke kanan. Untuk melakukan ini, mula-mula gerakkan penunjuk Lsehingga kita menemui nilai yang lebih besar daripada pivot. Jika nilai yang lebih kecil tidak dijumpai, maka
L совпадёт с
pivot. Потом двигаем указатель
R пока не найдём меньшее, чем
pivot meaning. Если меньшее meaning не нашли, то
R совпадёт с
pivot. Далее, если указатель
L находится до указателя
R or совпадает с ним, то пытаемся выполнить обмен элементов, если элемент
L меньше, чем
R. Далее
L сдвигаем вправо на 1 позицию,
R сдвигаем влево на одну позицию. Когда левый маркер
L окажется за правым маркером
R это будет означать, что обмен закончен, слева от
pivot меньшие значения, справа от
pivot — большие значения. После этого рекурсивно вызываем такую же сортировку для участков массива от начала сортируемого участка до правого маркера и от левого маркера до конца сортируемого участка. Почему от начала до правого? Потому что в конце итерации так и получится, что правый маркер сдвинется настолько, что станет границей части слева. Этот алгоритм более сложный, чем простая sorting, поэтому его лучше зарисовать. Возьмём белый лист бумаги, запишем: 4 2 6 7 3 , а
Pivot по центру, т.е. число 6. Обведём его в круг. Под 4 напишем
L, под 3 напишем
R. 4 меньше чем 6, 2 меньше чем 6. Total,
L переместился на положение
pivot, т.к. по условию
L не может уйти дальше, чем
pivot. Напишем снова 4 2 6 7 3 , обведём 6 вкруг (
pivot) и поставим под ним
L. Теперь двигаем указатель
R. 3 меньше чем 6, поэтому ставим маркер
R на цифру 3. Так How 3 меньше, чем
pivot 6 выполняем
swap, т.е. обмен. Запишем результат: 4 2 3 7 6 , обводим 6 вкруг, т.к. он по прежнему
pivot. Указатель
L на цифре 3, указатель
R на цифре 6. Мы помним, что двигаем указатели до тех пор, пока
L не зайдём за
R.
L двигаем на следующую цифру. Тут хочется разобрать два варианта: если бы предпоследняя цифра была 7 и если бы она была не 7, а 1.
Предпоследня цифра 1: Сдвинули указатель
L на цифру 1, т.к. мы можем двигать
L до тех пор, пока указатель
L указывает на цифру, меньшую чем
pivot. А вот
R мы не можем сдвинуть с 6, т.к. R не мы можем двигать только если указатель
R указывает на цифру, которая больше чем
pivot.
swap не делаем, т.к. 1 меньше 6. Записываем положение: 4 2 3 1 6, обводим
pivot 6.
L сдвигается на
pivot и больше не двигается.
R тоже не двигается. Обмен не производим. Сдвигаем
L и
R на одну позицию и подписываем цифру 1 маркером
R, а
L получается вне числа. Т.к.
L вне числа — ничего не делаем, а вот часть 4 2 3 1 выписываем снова, т.к. это наша левая часть, меньшая, чем
pivot 6. Выделяем новый
pivot и начинаем всё снова )
Предпоследняя цифра 7: Сдвинули указать
L на цифру 7, правый указатель не можем двигать, т.к. он уже указывает на pivot. т.к. 7 больше, чем
pivot, то делаем
swap. Запишем результат: 4 2 3 6 7, обводим 6 кружком, т.к. он
pivot. Указатель
L теперь сдвигается на цифру 7, а указатель
R сдвигается на цифру 3. Часть от
L до конца нет смысла сортировать, т.к. там всего 1 элемент, а вот часть от 4 до указателя
R отправляем на сортировку. Выбираем
pivot и начинаем всё снова ) Может на первый взгляд показаться, что если расставить много одинаковых с
pivot значений, это сломает алгоритм, но это не так. Можно напридумывать каверзных вариантов и на бумажке убедиться, что всё правильно и подивиться, How такие простые действия предоставляют такой надёжный механизм. Единственный минус — такая sorting не является стабильной. Т.к. при выполнении обмена одинаковые элементы могут поменять свой порядок, если один из них встретился до
pivot до того, How другой элемент попал в часть до
pivot при помощи обмена. Материал:
Выше мы рассмотрели "джентельменский" набор алгоритмов сортировки, реализованных на Java. Алгоритмы вообще штука полезная, How с прикладной точки зрения, так и с точки зрения развития мышления. Некоторые из них попроще, некоторые посложнее. По Howим-то умные люди защищали различные работы на степени, а по другим писали толстые-толстые книги. Надеюсь, приложенный к статье материал позволит вам узнать ещё больше, так How это обзорная статья, которая и так получилась увесистой. И цель её — дать небольшое вступление. Про введение в алгоритмы можно так же прочитать ознакомиться с книгой "
Грокаем Алгоримы". Также мне нравится плэйлист от Jack Brown —
AQA Decision 1 1.01 Tracing an Algorithm. Ради интереса можно посмотреть на визуализацию алгоритмов на
sorting.at и
visualgo.net. Ну и весь Youtube к вашим услугам.
GO TO FULL VERSION