程序員必須掌握這幾種排序算法的優(yōu)秀實踐，包會?。ê珿IF圖）
排序是計算機中常見且重要的操作，用于使數(shù)據(jù)按照某種規(guī)則或標(biāo)準進行有序化，便于后續(xù)的搜索、查找和處理。
為什么排序算法很重要？
由于排序通常有助于降低問題的算法復(fù)雜性，因此它在計算機科學(xué)中具有重要用途。百度搜索顯示，當(dāng)今計算世界中有 40 多種不同的排序算法。瘋狂吧？那你知道幾個呢！
現(xiàn)實世界中實現(xiàn)這一點的一些最佳示例是。
- 冒泡排序用于電視節(jié)目中，根據(jù)觀眾觀看時間對頻道進行排序！
- 數(shù)據(jù)庫使用外部合并排序?qū)μ蠖鵁o法完全加載到內(nèi)存中的數(shù)據(jù)集進行排序！
- 體育比分通過快速排序算法實時快速組織！
數(shù)據(jù)結(jié)構(gòu)中的排序類型
- 基于比較的排序：在基于比較的排序技術(shù)中，定義比較器來比較數(shù)據(jù)樣本的元素或項目。該比較器定義元素的順序。例子有：冒泡排序、歸并排序。
- 基于計數(shù)的排序：這些類型的排序算法中的元素之間不涉及比較，而是在執(zhí)行過程中進行計算假設(shè)。例如：計數(shù)排序、基數(shù)排序。
- 就地與非就地排序（In-Place vs Not-in-Place Sorting）：數(shù)據(jù)結(jié)構(gòu)中的就地排序技術(shù)會修改原始數(shù)組中數(shù)組元素的順序。另一方面，非就地排序技術(shù)使用輔助數(shù)據(jù)結(jié)構(gòu)對原始數(shù)組進行排序。就地排序技術(shù)的示例有：冒泡排序、選擇排序。非就地排序算法的一些示例包括：合并排序、快速排序。
PS：GIF圖較大，耐心等待打開，值得反復(fù)去看！
1、冒泡排序
冒泡排序的基本思想是，如果相鄰元素的順序不符合要求，則重復(fù)交換相鄰元素。是的，就是這么簡單。
如果給定的數(shù)組元素必須按升序排序，則冒泡排序?qū)⑹紫缺容^數(shù)組的第一個元素與第二個元素，如果結(jié)果大于第二個元素，則立即交換它們，然后繼續(xù)比較第二個和第三個元素，依此類推。
讓我們嘗試通過一個例子來理解冒泡排序背后的直觀方法：
冒泡排序算法解釋
Java 中的實現(xiàn)
import java.util.Arrays;
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {5, 3, 4, 2, 1};
bubbleSort(arr);
System.out.println("Sorted array: ");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}冒泡排序的實現(xiàn)
時間復(fù)雜度：
- 最壞情況： O(n^2)
- 平均情況：O(n*logn)
- 最好的情況：O(n*logn)
空間復(fù)雜度： O(1)。
2、選擇排序
選擇排序是一種排序算法，其中給定數(shù)組分為兩個子數(shù)組：已排序的左部分和未排序的右部分。
最初，已排序部分為空，未排序部分是整個列表。在每次迭代中，我們從未排序列表中獲取最小元素并將其推送到已排序列表的末尾，從而構(gòu)建已排序的數(shù)組。
讓我們嘗試用一個簡單的例子來理解選擇排序背后的直觀想法：
選擇排序算法解釋
Java 中的實現(xiàn)
import java.util.Arrays;
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {25, 22, 27, 15, 19};
selectionSort(arr);
System.out.println("Sorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}選擇排序的實現(xiàn)
時間復(fù)雜度：
- 最壞情況： O(n*n)
- 平均情況： O(n*logn)
- 最好情況： O(n*logn)
空間復(fù)雜度： O(1)。
3、插入排序
插入排序是一種將給定數(shù)組分為已排序部分和未排序部分的排序算法。在每次迭代中，要插入的元素必須在已排序的子序列中找到其最佳位置，然后插入，同時將剩余元素向右移動。
通過示例了解插入排序算法。
下面是一個例子，可以幫助更好地理解插入排序：
插入排序算法解釋
現(xiàn)在已經(jīng)了解了插入排序的實際工作原理，接下來看一下 Java的 實現(xiàn)。
import java.util.Arrays;
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {25, 22, 27, 15, 19};
insertionSort(arr);
System.out.println(Arrays.toString(arr));
}
}插入排序的實現(xiàn)
時間復(fù)雜度：
- 最壞情況： O(n*n)
- 平均情況： O(n*logn)
- 最好情況： O(n*logn)
空間復(fù)雜度： O(1)。
4、快速排序
快速排序是一種分而治之的算法?？焖倥判虮澈蟮闹庇^概念是，它從給定的元素數(shù)組中選擇一個元素作為主元，然后圍繞主元元素對數(shù)組進行分區(qū)。隨后，它遞歸地調(diào)用自身并隨后對兩個子數(shù)組進行分區(qū)。
通過可視化了解快速排序算法。
快速排序算法涉及的邏輯步驟如下：
- 樞軸選擇：選擇一個元素作為樞軸（這里，我們選擇最后一個元素作為樞軸）。
- 分區(qū)：數(shù)組的分區(qū)方式使得所有小于主元的元素都位于左子數(shù)組中，而所有嚴格大于主元的元素都存儲在右子數(shù)組中。
- 遞歸調(diào)用快速排序：對上面創(chuàng)建的兩個子數(shù)組再次調(diào)用快速排序函數(shù)，并重復(fù)步驟。
下面的實現(xiàn)中包含了注釋，以幫助更好地理解快速排序算法。
import java.util.Arrays;
public class QuickSort {
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int partitionIndex = partition(arr, low, high);
quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {14, 21, 5, 2, 3, 19};
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.print("Sorted array: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}快速排序的實現(xiàn)
時間復(fù)雜度：
- 最壞情況： O(n*n)
- 平均情況： O(n*logn)
- 最好情況： O(n*logn)
空間復(fù)雜度： O(1)。
5、隨機快速排序
隨機快速排序與快速排序的區(qū)別：
快速排序是一種分治算法，通過選擇一個基準元素（通常是數(shù)組中的一個元素），將數(shù)組劃分為兩個子數(shù)組，一個子數(shù)組中的所有元素都小于基準元素，另一個子數(shù)組中的所有元素都大于基準元素。然后遞歸地對這兩個子數(shù)組進行排序?？焖倥判虻钠骄鶗r間復(fù)雜度為O(nlogn)。
隨機快速排序與快速排序的不同之處在于選擇基準元素的方式。在快速排序中，通常選擇數(shù)組的第一個或最后一個元素作為基準元素。而在隨機快速排序中，首先從數(shù)組中隨機選擇一個元素作為基準元素，然后進行劃分。
隨機快速排序的主要優(yōu)點是減少了快速排序中最壞情況出現(xiàn)的概率。在快速排序中，如果選擇的基準元素是數(shù)組中的最小或最大元素，或者數(shù)組已經(jīng)是有序的，那么劃分結(jié)果可能會非常不平衡，導(dǎo)致算法的時間復(fù)雜度接近O(n^2)。通過隨機選擇基準元素，可以有效地降低這種情況發(fā)生的概率，提高算法的平均性能。
因此，隨機快速排序相對于快速排序來說，具有更好的性能保證，尤其是在面對特定情況下的輸入數(shù)據(jù)時。它在實踐中通常被認為是快速排序的一種優(yōu)化版本，可以提供更一致的性能，并減少最壞情況的發(fā)生概率。
時間復(fù)雜度：
- 最壞情況： O(n*n)
- 平均情況： O(n*logn)
- 最好情況： O(n*logn)
空間復(fù)雜度： O(logn)。
6、歸并排序
歸并排序是一種分而治之的算法。在每次迭代中，歸并排序?qū)⑤斎霐?shù)組劃分為兩個相等的子數(shù)組，為這兩個子數(shù)組遞歸地調(diào)用自身，最后合并已排序的兩半。
通過可視化了解合并排序算法。
歸并排序算法解釋
看一下它的實現(xiàn)。
import java.util.Arrays;
public class MergeSort {
public static void merge(long[] arr, long lt, long m, long rt) {
long n1 = m - lt + 1;
long n2 = rt - m;
long[] L = new long[(int) n1];
long[] R = new long[(int) n2];
for (int i = 0; i < n1; i++)
L[i] = arr[(int) (lt + i)];
for (int j = 0; j < n2; j++)
R[j] = arr[(int) (m + 1 + j)];
int i = 0, j = 0;
int k = (int) lt;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void mergeSort(long[] arr, long lt, long rt) {
if (lt >= rt)
return;
long m = lt + (rt - lt) / 2;
mergeSort(arr, lt, m);
mergeSort(arr, m + 1, rt);
merge(arr, lt, m, rt);
}
public static void printArray(long[] arr) {
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
public static void main(String[] args) {
long[] arr = {16, 19, 14, 20, 12, 13};
System.out.print("Unsorted array is: ");
printArray(arr);
mergeSort(arr, 0, arr.length - 1);
System.out.print("\nSorted array is: ");
printArray(arr);
}
}歸并排序的實現(xiàn)
時間復(fù)雜度：
- 最壞情況： O(n*logn)
- 平均情況： O(n*logn)
- 最好情況： O(n*logn)
空間復(fù)雜度： O(n)。
7、計數(shù)排序
計數(shù)排序是一種有趣的排序技術(shù)，主要是因為它關(guān)注特定范圍內(nèi)唯一元素的頻率（類似于散列）。
它的工作原理是計算具有不同鍵值的元素數(shù)量，然后在計算未排序序列中每個唯一元素的位置后構(gòu)建排序數(shù)組。
它與上面列出的算法不同，因為它實際上涉及輸入數(shù)據(jù)元素之間的零比較！
通過示例了解計數(shù)排序算法。
計數(shù)排序算法解釋
現(xiàn)在繼續(xù)看一下它在 Java 中的實現(xiàn)。
import java.util.Scanner;
public class CountSort {
public static void print(long[] vec, long n) {
for (long i = 1; i <= n; i++)
System.out.print(vec[(int) i] + " ");
System.out.println();
}
public static long getMax(long[] vec, long n) {
long max = vec[1];
for (long i = 2; i <= n; i++) {
if (vec[(int) i] > max)
max = vec[(int) i];
}
return max;
}
public static void countSort(long[] vec, long n) {
long[] output = new long[(int) (n + 1)];
long max = getMax(vec, n);
long[] count = new long[(int) (max + 1)];
for (int i = 0; i <= max; i++)
count[i] = 0;
for (long i = 1; i <= n; i++)
count[(int) vec[(int) i]]++;
for (int i = 1; i <= max; i++)
count[i] += count[i - 1];
for (long i = n; i >= 1; i--) {
output[(int) count[(int) vec[(int) i]]] = vec[(int) i];
count[(int) vec[(int) i]] -= 1;
}
for (long i = 1; i <= n; i++) {
vec[(int) i] = output[(int) i];
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the size of array: ");
long n = scanner.nextLong();
long[] arr = new long[(int) (n + 1)];
System.out.println("Enter elements:");
for (long i = 1; i <= n; i++)
arr[(int) i] = scanner.nextLong();
System.out.print("Unsorted array: ");
print(arr, n);
countSort(arr, n);
System.out.print("Sorted array: ");
print(arr, n);
scanner.close();
}
}計數(shù)排序?qū)崿F(xiàn)
時間復(fù)雜度：
- 最壞情況： O(n+k)，其中 n 是輸入數(shù)組的大小，k 是數(shù)組中唯一元素的數(shù)量。
空間復(fù)雜度： O(n+k)。
8、基數(shù)排序
正如之前所看到的，計數(shù)排序之所以與眾不同，是因為它不是像合并排序或冒泡排序那樣基于比較的排序算法，從而將其時間復(fù)雜度降低到線性時間。
但是，如果輸入數(shù)組的范圍從 1 到 n^2，計數(shù)排序就會失敗，在這種情況下，其時間復(fù)雜度會增加到 O(n^2)。
基數(shù)排序背后的基本思想是擴展計數(shù)排序的功能，以便在輸入數(shù)組元素范圍從 1 到 n^2 時獲得更好的時間復(fù)雜度。
通過示例了解基數(shù)排序。
算法：
對于每個數(shù)字 i，其中 i 從數(shù)字的最低有效數(shù)字到最高有效數(shù)字變化，根據(jù)第 i 個數(shù)字使用計數(shù)排序算法對輸入數(shù)組進行排序。請記住，我們使用計數(shù)排序，因為它是一種穩(wěn)定的排序算法。
例子：
基數(shù)排序算法解釋
因此，我們觀察到基數(shù)排序在整個執(zhí)行過程中使用計數(shù)排序作為其子例程。現(xiàn)在看一下它的 Java實現(xiàn)。
import java.util.Arrays;
public class RadixSort {
public static void getMax(long[] vec, int n) {
long maxval = vec[0];
for (int i = 1; i < n; i++) {
if (vec[i] > maxval) {
maxval = vec[i];
}
}
}
public static void countSort(long[] vec, int n, long x) {
long[] res = new long[n];
long[] count = new long[10];
Arrays.fill(count, 0);
for (int i = 0; i < n; i++) {
count[(int)((vec[i] / x) % 10)]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
res[(int)(count[(int)((vec[i] / x) % 10)] - 1)] = vec[i];
count[(int)((vec[i] / x) % 10)]--;
}
for (int i = 0; i < n; i++) {
vec[i] = res[i];
}
}
public static void radixSort(long[] vec, int n) {
long m = vec[0];
for (int i = 1; i < n; i++) {
if (vec[i] > m) {
m = vec[i];
}
}
for (long x = 1; m / x > 0; x *= 10) {
countSort(vec, n, x);
}
}
public static void main(String[] args) {
long[] vec = { 53, 89, 150, 36, 633, 233 };
int n = vec.length;
radixSort(vec, n);
for (int i = 0; i < n; i++) {
System.out.print(vec[i] + " ");
}
}
}基數(shù)排序?qū)崿F(xiàn)
時間復(fù)雜度： O(d(n+b))，其中b代表數(shù)組元素的基數(shù)（例如- 10代表十進制）
空間復(fù)雜度： O(n+d)，其中 d 是數(shù)組元素中的最大位數(shù)。
總結(jié)
排序算法總結(jié)
名詞解釋：
- n：數(shù)據(jù)規(guī)模
- k：“桶”的個數(shù)
- In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存
- Out-place：占用額外內(nèi)存
- 穩(wěn)定性：排序后 2 個相等鍵值的順序和排序之前它們的順序相同
