十大经典算法>排序算法

十大经典算法>排序算法可以分为比较排序和非比较排序:

• 前者包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序;

• 后者包括计数排序、桶排序、基数排序;

下面将详细介绍这些算法：

比较排序

1. 冒泡排序

• 基本思想：重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。
• 代码示例：

void bubbleSort(int arr[], int n) {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;}}}
}

python">def bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]return arr

解释：

• 该函数接受一个列表 arr 作为输入。

• 外层循环 for i in range(n) 控制排序的轮数，每一轮将最大元素 “浮” 到末尾。

• 内层循环 for j in range(0, n-i-1) 比较相邻元素，如果顺序错误则交换它们的位置。

• 时间复杂度：最好情况为 $O(n)$，最坏情况为 $O(n^2)$。

• 空间复杂度： $O(1)$。

2. 选择排序

• 基本思想：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
• 代码示例：

void selectionSort(int arr[], int n) {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[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}
}

python">def selection_sort(arr):for i in range(len(arr)):min_index = ifor j in range(i+1, len(arr)):if arr[j] < arr[min_index]:min_index = jarr[i], arr[min_index] = arr[min_index], arr[i]return arr

解释：

• 函数 selection_sort 对列表 arr 进行排序。

• 外层循环 for i in range(len(arr)) 确定当前要放置最小元素的位置。

• 内层循环 for j in range(i+1, len(arr)) 寻找未排序部分的最小元素索引。

• 时间复杂度： $O(n^2)$。

• 空间复杂度： $O(1)$。

3. 插入排序

• 基本思想：对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
• 代码示例：

void insertionSort(int arr[], int n) {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--;}arr[j + 1] = key;}
}

python">def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j -= 1arr[j + 1] = keyreturn arr

解释：

• 该函数接受列表 arr 并对其排序。

• 从第二个元素开始，将元素 key 与其前面已排序部分的元素比较并插入正确位置。

• 时间复杂度：最好情况为 $O(n)$，最坏情况为 $O(n^2)$。

• 空间复杂度： $O(1)$。

4. 希尔排序

• 基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行依次直接插入排序。
• 代码示例：

void shellSort(int arr[], int n) {for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}
}

python">def shell_sort(arr):n = len(arr)gap = n // 2while gap > 0:for i in range(gap, n):temp = arr[i]j = iwhile j >= gap and arr[j - gap] > temp:arr[j] = arr[j - gap]j -= gaparr[j] = tempgap //= 2return arr

• 函数 shell_sort 进行希尔排序。

• 初始 gap 为 n // 2，对相隔 gap 的元素进行插入排序，不断缩小 gap 直至为 1。

• 时间复杂度：$O(nlo{g}_{2}n)$ 到 $O(n^2)$ 之间。

• 空间复杂度：$O(1)$。

5. 归并排序

• 基本思想：将一个数组分成两个子数组，对每个子数组递归地进行排序，然后将排序好的子数组合并成一个有序的数组。
• 代码示例：

void merge(int arr[], int l, int m, int r) {int n1 = m - l + 1;int n2 = r - m;int L[n1], R[n2];for (int i = 0; i < n1; i++)L[i] = arr[l + i];for (int j = 0; j < n2; j++)R[j] = arr[m + 1 + j];int i = 0, j = 0, k = l;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++;}
}
void mergeSort(int arr[], int l, int r) {if (l < r) {int m = l + (r - l) / 2;mergeSort(arr, l, m);mergeSort(arr, m + 1, r);merge(arr, l, m, r);}
}

python">def merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2L = arr[:mid]R = arr[mid:]merge_sort(L)merge_sort(R)i = j = k = 0while i < len(L) and j < len(R):if L[i] <= R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1while i < len(L):arr[k] = L[i]i += 1k += 1while j < len(R):arr[k] = R[j]j += 1k += 1return arr

• merge_sort 函数将列表不断二分，分别对左右子列表排序，最后合并。

• 递归调用 merge_sort 对左右子列表排序。

• 时间复杂度：$O(nlogn)$。

• 空间复杂度：$O(n)$。

6. 快速排序

• 基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
• 代码示例：

int partition(int arr[], int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;
}
void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}

python">def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)

解释：

• 函数 quick_sort 选择一个基准元素 pivot。

• 元素被分成小于、等于、大于 pivot 的三个部分，对小于和大于部分递归排序。

• 时间复杂度：最好情况为$O(nlogn)$，最坏情况为$O(n^2)$。

• 空间复杂度：$O(logn)$到$O(n)$。

7. 堆排序

• 基本思想：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余个元素重新构造成一个堆，这样会得到个元素的次小值。如此反复执行，便能得到一个有序序列了。
• 代码示例：

void heapify(int arr[], int n, int i) {int largest = i;int l = 2 * i + 1;int r = 2 * i + 2;if (l < n && arr[l] > arr[largest])largest = l;if (r < n && arr[r] > arr[largest])largest = r;if (largest!= i) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;heapify(arr, n, largest);}
}
void heapSort(int arr[], int n) {for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);for (int i = n - 1; i >= 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapify(arr, i, 0);}
}

python">def heapify(arr, n, i):largest = il = 2 * i + 1r = 2 * i + 2if l < n and arr[i] < arr[l]:largest = lif r < n and arr[largest] < arr[r]:largest = rif largest!= i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heap_sort(arr):n = len(arr)for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)for i in range(n - 1, 0, -1):arr[i], arr[0] = arr[0], arr[i]heapify(arr, i, 0)return arr

解释：

• heapify 函数用于维护堆的性质。

• heap_sort 先将数组构建成最大堆，然后不断交换堆顶元素与末尾元素并调整堆。

• 时间复杂度：$O(nlogn)$。

• 空间复杂度：$O(1)$。

非比较排序

8. 计数排序

• 基本思想：通过统计每个元素出现的次数，然后根据统计结果将元素依次放入有序序列中。
• 代码示例：

void countSort(int arr[], int n) {int max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > max) {max = arr[i];}}int count[max + 1];for (int i = 0; i <= max; i++) {count[i] = 0;}for (int i = 0; i < n; i++) {count[arr[i]]++;}int j = 0;for (int i = 0; i <= max; i++) {while (count[i] > 0) {arr[j] = i;j++;count[i]--;}}
}

python">def count_sort(arr):max_val = max(arr)count = [0] * (max_val + 1)for i in arr:count[i] += 1output = []for i in range(len(count)):for j in range(count[i]):output.append(i)return output

解释：

• count_sort 先统计元素出现次数。

• 然后根据计数数组将元素按序添加到输出列表。

• 时间复杂度：$O(n+k)$，$k$其中是数据的范围。

• 空间复杂度：$O(k)$。

9. 桶排序

• 基本思想：将数据分到有限数量的桶子里，每个桶子再分别排序（有可能再使用别的算法>排序算法或是以递归方式继续使用桶排序进行排序）。
• 代码示例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void bucketSort(double arr[], int n) {vector<double> buckets[n];for (int i = 0; i < n; i++) {int bucketIndex = n * arr[i];buckets[bucketIndex].push_back(arr[i]);}for (int i = 0; i < n; i++) {sort(buckets[i].begin(), buckets[i].end());}int index = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < buckets[i].size(); j++) {arr[index] = buckets[i][j];index++;}}
}

python">def bucket_sort(arr):if len(arr) == 0:return arrmin_val, max_val = min(arr), max(arr)bucket_size = 5bucket_count = (max_val - min_val) // bucket_size + 1buckets = [[] for _ in range(bucket_count)]for i in arr:buckets[(i - min_val) // bucket_size].append(i)sorted_arr = []for bucket in buckets:insertion_sort(bucket)sorted_arr.extend(bucket)return sorted_arr

解释：

• 函数 bucket_sort 把元素分散到多个桶中。

• 对每个桶中的元素使用插入排序并合并。

• 时间复杂度：$O(n+k)$，其中 $k$ 是桶的数量。

• 空间复杂度：$O(n+k)$。

10. 基数排序

：

• 基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
• 代码示例：

void countSortForRadix(int arr[], int n, int exp) {int output[n];int count[10] = { 0 };for (int i = 0; i < n; i++) {count[(arr[i] / exp) % 10]++;}for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}for (int i = n - 1; i >= 0; i--) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}for (int i = 0; i < n; i++) {arr[i] = output[i];}
}
void radixSort(int arr[], int n) {int maxVal = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > maxVal) {maxVal = arr[i];}}for (int exp = 1; maxVal / exp > 0; exp *= 10) {countSortForRadix(arr, n, exp);}
}

python">def radix_sort(arr):def get_digit(num, digit):return (num // 10**digit) % 10max_val = max(arr)exp = 0while 10**exp <= max_val:buckets = [[] for _ in range(10)]for i in arr:digit = get_digit(i, exp)buckets[digit].append(i)arr = []for bucket in buckets:arr.extend(bucket)exp += 1return arr

解释：

• radix_sort 对元素按不同位数排序。
• 从最低位开始，将元素放入对应数字的桶中，再合并，逐位推进。

你可以使用以下方式调用这些函数：

python">arr = [12, 11, 13, 5, 6]
print(bubble_sort(arr.copy()))
print(selection_sort(arr.copy()))
print(insertion_sort(arr.copy()))
print(shell_sort(arr.copy()))
print(merge_sort(arr.copy()))
print(quick_sort(arr.copy()))
print(heap_sort(arr.copy()))
print(count_sort(arr.copy()))
print(bucket_sort(arr.copy()))
print(radix_sort(arr.copy()))

以上代码通过不同的算法>排序算法实现了对列表的排序，并且通过使用 copy 避免原始列表被修改。

注意：

• 在使用 bucket_sort 时，这里使用了 insertion_sort 对桶内元素排序，可以使用其他算法>排序算法。

• 在 radix_sort 中，根据不同位数将元素放入不同桶，按顺序取出实现排序。

• 时间复杂度：$O(d(n+k)$，其中 $d$ 是数字的位数，$k$ 是基数。

• 空间复杂度：$O(n+k)$。