Sắp xếp là một trong những loại hoạt động hoặc hành động cơ bản được thực hiện trên các đối tượng. Ngay từ khi còn nhỏ, trẻ đã được dạy cách sắp xếp, phát triển tư duy. Máy tính và các chương trình cũng không ngoại lệ. Có rất nhiều thuật toán. Tôi khuyên bạn nên xem chúng là gì và chúng hoạt động như thế nào. Ngoài ra, điều gì sẽ xảy ra nếu một ngày bạn được hỏi về một trong những điều này trong một cuộc phỏng vấn?
Giới thiệu
Sắp xếp các phần tử là một trong những loại thuật toán mà nhà phát triển phải làm quen. Nếu ngày xưa, khi tôi còn đi học, khoa học máy tính không được coi trọng lắm thì bây giờ ở trường các em có thể thực hiện các thuật toán sắp xếp và hiểu chúng. Các thuật toán cơ bản, đơn giản nhất, được triển khai bằng vòng lặp for. Đương nhiên, để sắp xếp một tập hợp các phần tử, chẳng hạn như một mảng, bạn cần phải duyệt qua bộ sưu tập này bằng cách nào đó. Ví dụ:
int[] array ={10,2,10,3,1,2,5};for(int i =0; i < array.length; i++){System.out.println(array[i]);}
Bạn có thể nói gì về đoạn mã này? Chúng ta có một vòng lặp trong đó chúng ta thay đổi giá trị chỉ mục ( int i) từ 0 thành phần tử cuối cùng trong mảng. Trên thực tế, chúng ta chỉ cần lấy từng phần tử trong mảng và in ra nội dung của nó. Càng nhiều phần tử trong mảng thì thời gian thực thi mã càng lâu. Nghĩa là, nếu n là số phần tử, với n=10, chương trình sẽ mất nhiều thời gian hơn để thực thi gấp 2 lần so với n=5. Khi chương trình của chúng ta có một vòng lặp, thời gian thực hiện tăng tuyến tính: càng nhiều phần tử thì thời gian thực thi càng lâu. Hóa ra thuật toán của đoạn mã trên hoạt động theo thời gian tuyến tính (n). Trong những trường hợp như vậy, “độ phức tạp của thuật toán” được gọi là O(n). Ký hiệu này còn được gọi là "big O" hoặc "hành vi tiệm cận". Nhưng bạn có thể chỉ cần nhớ “độ phức tạp của thuật toán”.
Cách sắp xếp đơn giản nhất (Sắp xếp bong bóng)
Vì vậy, chúng ta có một mảng và có thể lặp lại nó. Tuyệt vời. Bây giờ chúng ta hãy thử sắp xếp nó theo thứ tự tăng dần. Điều này có ý nghĩa gì với chúng ta? Điều này có nghĩa là cho hai phần tử (ví dụ: a=6, b=5), chúng ta phải hoán đổi a và b nếu a lớn hơn b (nếu a > b). Điều này có ý nghĩa gì đối với chúng ta khi làm việc với một bộ sưu tập theo chỉ mục (như trường hợp của một mảng)? Điều này có nghĩa là nếu phần tử có chỉ mục a lớn hơn phần tử có chỉ mục b, (mảng [a] > mảng [b]), thì các phần tử đó phải được hoán đổi. Thay đổi địa điểm thường được gọi là trao đổi. Có nhiều cách khác nhau để thay đổi địa điểm. Nhưng chúng tôi sử dụng mã đơn giản, rõ ràng và dễ nhớ:
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));
Như chúng ta có thể thấy, các yếu tố thực sự đã thay đổi vị trí. Chúng tôi bắt đầu với một yếu tố, bởi vì... nếu mảng chỉ bao gồm một phần tử, biểu thức 1 < 1 sẽ không trả về true và do đó chúng ta sẽ tự bảo vệ mình khỏi trường hợp mảng có một phần tử hoặc không có phần tử nào, và mã sẽ trông đẹp hơn. Nhưng dù sao thì mảng cuối cùng của chúng ta cũng không được sắp xếp, bởi vì... Không thể sắp xếp tất cả mọi người trong một lượt. Chúng ta sẽ phải thêm một vòng lặp khác, trong đó chúng ta sẽ thực hiện từng bước một cho đến khi nhận được một mảng được sắp xếp:
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));
Vậy là việc phân loại đầu tiên của chúng tôi đã thành công. Chúng tôi lặp lại ở vòng lặp bên ngoài ( while) cho đến khi chúng tôi quyết định rằng không cần lặp lại nữa. Theo mặc định, trước mỗi lần lặp mới, chúng tôi giả định rằng mảng của chúng tôi đã được sắp xếp và chúng tôi không muốn lặp lại nữa. Do đó, chúng tôi xem xét các phần tử một cách tuần tự và kiểm tra giả định này. Nhưng nếu các phần tử không theo thứ tự, chúng ta hoán đổi các phần tử và nhận ra rằng chúng ta không chắc chắn rằng các phần tử hiện tại đã theo đúng thứ tự. Vì vậy, chúng tôi muốn thực hiện thêm một lần lặp nữa. Ví dụ: [3, 5, 2]. 5 là nhiều hơn ba, mọi thứ đều ổn. Nhưng 2 nhỏ hơn 5. Tuy nhiên, [3, 2, 5] cần thêm một lần nữa, bởi vì 3 > 2 và chúng cần được đổi chỗ. Vì chúng ta sử dụng một vòng lặp trong một vòng lặp nên độ phức tạp của thuật toán của chúng ta sẽ tăng lên. Với n phần tử nó trở thành n * n, tức là O(n^2). Sự phức tạp này được gọi là bậc hai. Theo hiểu biết của chúng tôi, chúng tôi không thể biết chính xác sẽ cần bao nhiêu lần lặp. Chỉ báo độ phức tạp của thuật toán phục vụ mục đích thể hiện xu hướng tăng độ phức tạp, trường hợp xấu nhất. Thời gian chạy sẽ tăng bao nhiêu khi số phần tử n thay đổi. Sắp xếp bong bóng là một trong những cách sắp xếp đơn giản nhất và kém hiệu quả nhất. Nó đôi khi còn được gọi là "sắp xếp ngu ngốc". Tài liệu liên quan:
Một loại khác là sắp xếp lựa chọn. Nó cũng có độ phức tạp bậc hai, nhưng sẽ nói thêm về điều đó sau. Vì vậy, ý tưởng rất đơn giản. Mỗi lượt chọn phần tử nhỏ nhất và di chuyển nó về đầu. Trong trường hợp này, bắt đầu mỗi đường chuyền mới bằng cách di chuyển sang phải, nghĩa là đường chuyền đầu tiên - từ phần tử đầu tiên, đường chuyền thứ hai - từ phần tử thứ hai. Nó sẽ trông giống thế này:
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));
Cách sắp xếp này không ổn định vì các phần tử giống hệt nhau (theo quan điểm về đặc tính mà chúng ta sắp xếp các phần tử) có thể thay đổi vị trí của chúng. Một ví dụ điển hình được đưa ra trong bài viết Wikipedia: Sorting_by-selection . Tài liệu liên quan:
Sắp xếp chèn cũng có độ phức tạp bậc hai, vì chúng ta lại có một vòng lặp bên trong một vòng lặp. Nó khác với sắp xếp lựa chọn như thế nào? Sự sắp xếp này là "ổn định". Điều này có nghĩa là các phần tử giống hệt nhau sẽ không thay đổi thứ tự của chúng. Giống hệt nhau về các đặc điểm mà chúng tôi sắp xếp.
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));
Trong số các cách sắp xếp đơn giản, có một cách khác - sắp xếp con thoi. Nhưng tôi thích loại tàu con thoi hơn. Đối với tôi, có vẻ như chúng ta hiếm khi nói về tàu con thoi, và tàu con thoi thiên về chạy bộ hơn. Vì vậy, sẽ dễ hình dung hơn cách các tàu con thoi được phóng vào vũ trụ. Đây là một liên kết với thuật toán này. Bản chất của thuật toán là gì? Bản chất của thuật toán là chúng tôi lặp lại từ trái sang phải và khi hoán đổi các phần tử, chúng tôi kiểm tra tất cả các phần tử khác còn sót lại để xem liệu việc hoán đổi có cần phải lặp lại hay không.
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));
Một cách sắp xếp đơn giản khác là sắp xếp Shell. Bản chất của nó tương tự như sắp xếp bong bóng, nhưng mỗi lần lặp chúng ta có một khoảng cách khác nhau giữa các phần tử được so sánh. Mỗi lần lặp nó giảm đi một nửa. Đây là một ví dụ thực hiện:
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));
Ngoài những cách sắp xếp đơn giản đã nêu, còn có những cách sắp xếp phức tạp hơn. Ví dụ: sắp xếp hợp nhất. Đầu tiên, đệ quy sẽ hỗ trợ chúng ta. Thứ hai, độ phức tạp của chúng ta sẽ không còn là bậc hai như chúng ta đã quen. Độ phức tạp của thuật toán này là logarit. Viết là O (n log n). Vì vậy, hãy làm điều này. Đầu tiên, hãy viết một lệnh gọi đệ quy cho phương thức sắp xếp:
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);}}
Bây giờ, hãy thêm một hành động chính vào nó. Đây là một ví dụ về siêu phương thức của chúng tôi khi triển khai:
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);}
Hãy chạy ví dụ bằng cách gọi mergeSort(array, 0, array.length-1). Như bạn có thể thấy, bản chất bắt nguồn từ thực tế là chúng ta lấy đầu vào là một mảng cho biết phần đầu và phần cuối của phần cần sắp xếp. Khi bắt đầu sắp xếp, đây là phần đầu và phần cuối của mảng. Tiếp theo chúng ta tính toán dấu phân cách - vị trí của dải phân cách. Nếu bộ chia có thể chia mảng thành 2 phần thì ta gọi sắp xếp đệ quy cho các phần mà bộ chia đã chia mảng. Chúng tôi chuẩn bị một mảng đệm bổ sung trong đó chúng tôi chọn phần đã sắp xếp. Tiếp theo, chúng ta đặt con trỏ vào đầu vùng cần sắp xếp và bắt đầu đi qua từng phần tử của mảng trống mà chúng ta đã chuẩn bị và điền vào đó những phần tử nhỏ nhất. Nếu phần tử được con trỏ trỏ tới nhỏ hơn phần tử được trỏ đến bởi ước số, chúng ta đặt phần tử này vào mảng đệm và di chuyển con trỏ. Ngược lại, chúng ta đặt phần tử được trỏ đến bởi dấu phân cách vào mảng đệm và di chuyển dấu phân cách. Ngay khi dấu phân cách vượt ra ngoài ranh giới của vùng đã sắp xếp hoặc chúng ta lấp đầy toàn bộ mảng, phạm vi đã chỉ định sẽ được coi là đã sắp xếp. Tài liệu liên quan:
Một thuật toán sắp xếp thú vị khác là Counting Sort. Độ phức tạp thuật toán trong trường hợp này sẽ là O(n+k), trong đó n là số phần tử và k là giá trị lớn nhất của phần tử. Có một vấn đề với thuật toán: chúng ta cần biết giá trị tối thiểu và tối đa trong mảng. Dưới đây là một ví dụ thực hiện sắp xếp đếm:
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;}
Theo chúng tôi hiểu, sẽ rất bất tiện khi chúng ta phải biết trước giá trị tối thiểu và tối đa. Và sau đó có một thuật toán khác - Sắp xếp cơ số. Tôi sẽ trình bày thuật toán ở đây chỉ một cách trực quan. Để thực hiện, xem tài liệu:
Chà, đối với món tráng miệng - một trong những thuật toán nổi tiếng nhất: sắp xếp nhanh chóng. Nó có độ phức tạp về mặt thuật toán, nghĩa là chúng ta có O(n log n). Loại này còn được gọi là loại Hoare. Điều thú vị là thuật toán này được Hoare phát minh ra trong thời gian ông ở Liên Xô, nơi ông học dịch thuật máy tính tại Đại học Moscow và đang phát triển một cuốn sách hội thoại tiếng Nga-Anh. Thuật toán này cũng được sử dụng trong cách triển khai phức tạp hơn trong Arrays.sort trong Java. Còn Collections.sort thì sao? Tôi khuyên bạn nên tự mình xem chúng được sắp xếp như thế nào "dưới mui xe". Vì vậy, mã:
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);}}
Mọi thứ ở đây đều rất đáng sợ nên chúng ta sẽ tìm ra cách. Đối với nguồn mảng đầu vào int[], chúng ta đặt hai điểm đánh dấu là trái (L) và phải (R). Khi được gọi lần đầu tiên, chúng khớp với phần đầu và phần cuối của mảng. Tiếp theo, phần tử hỗ trợ được xác định, hay còn gọi là pivot. Sau đó, nhiệm vụ của chúng ta là di chuyển các giá trị nhỏ hơn pivot, sang trái pivotvà các giá trị lớn hơn sang phải. Để thực hiện việc này, trước tiên hãy di chuyển con trỏ Lcho đến khi chúng ta tìm thấy giá trị lớn hơn pivot. Nếu không tìm thấy giá trị nhỏ hơn thì
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