冒泡排序
冒泡排序（Bubble Sort）是一种简单直观的排序算法。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
时间复杂度：$O(n^2)$
算法步骤
假设一个序列长度为n，m（m≤n）是已排序完成的在末尾的数。
-
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
-
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。对比结束后，最后的元素会是最大的数。
-
对接下来n-m个未排序的数重复步骤1和2，直到没有任何一对数字需要比较。
第一趟对序列中所有n个数进行比对，第二趟对序列中n-1个未排序完成的数进行比对，以此类推。每次比对的数为n-m。
动画演示：
代码实现
Python实现
1def bubbleSort(arr):
2 for i in range(len(arr)-1):
3 for j in range(len(arr)-1-i):
4 if arr[j] > arr[j+1]:
5 arr[j], arr[j + 1] = arr[j + 1], arr[j]
6 return arr
7
8if __name__ == '__main__':
9 arr = [
10 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 ]
11 bubbleSort(arr)
12 print(arr)
C实现
1#include <stdio.h>
2
3void bubbleSort(int arr[], int len)
4{
5 for (int i = 0; i < len - 1; i++)
6 for (int j = 0; j < len - 1 - i; j++)
7 if (arr[j] > arr[j + 1])
8 {
9 int tmp = arr[j];
10 arr[j] = arr[j + 1];
11 arr[j + 1] = tmp;
12 }
13}
14
15int main(void)
16{
17 int arr[] = {
18 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
19 int len = (int)sizeof(arr) / sizeof(*arr);
20 bubbleSort(arr, len);
21 for (int i = 0; i < len; i++)
22 printf("%d ", arr[i]);
23 return 0;
24}
优化算法
有序标志
冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。
-
Python实现：
1def bubbleSort(arr): 2 for i in range(len(arr)-1): 3 # 有序flag，初始为True 4 isSorted = True 5 for j in range(len(arr)-1-i): 6 if arr[j] > arr[j+1]: 7 arr[j], arr[j + 1] = arr[j + 1], arr[j] 8 # 发生交换，序列定为无序 9 isSorted = False 10 # 序列有序，停止循环 11 if isSorted: 12 break 13 return arr 14 15if __name__ == '__main__': 16 arr = [ 17 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 ] 18 bubbleSort(arr) 19 print(arr) -
C实现：
1#include <stdio.h> 2#include <stdbool.h> 3 4void bubbleSort(int arr[], int len) 5{ 6 for (int i = 0; i < len - 1; i++) 7 { 8 // 有序flag，初始为True 9 bool isSorted = true; 10 for (int j = 0; j < len - 1 - i; j++) 11 if (arr[j] > arr[j + 1]) 12 { 13 arr[j] = arr[j] ^ arr[j+1]; 14 arr[j+1] = arr[j] ^ arr[j+1]; 15 arr[j] = arr[j] ^ arr[j+1]; 16 // 发生交换，序列定为无序 17 isSorted = false; 18 } 19 // 序列有序，停止循环 20 if (isSorted) 21 break; 22 } 23} 24 25int main(void) 26{ 27 int arr[] = { 28 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 }; 29 int len = (int)sizeof(arr) / sizeof(*arr); 30 bubbleSort(arr, len); 31 for (int i = 0; i < len; i++) 32 printf("%d ", arr[i]); 33 return 0; 34}
数列有序区
通常，有序区的长度和排序的轮数是相等的。如，第一轮排序后的有序区长度是1，第二轮排序后是2 ……
但实际上，数列的有序区长度可能会大于这个长度，并且每轮增加的有序区长度也不一定仅为1。
该优化算法解决了这个问题，通过在每一轮排序的最后，记录下最后一次元素交换的位置（该位置也就是无序数列的边界，再往后就是有序区），而每轮的交换只要交换到无序区边界。
-
Python实现：
1def bubbleSort(arr): 2 # 无序数列的边界 3 sortBorder = len(arr) - 1 4 for i in range(len(arr)-1): 5 # 有序flag，初始为True 6 isSorted = True 7 # 每次仅需交换到无序区边界 8 for j in range(sortBorder): 9 if arr[j] > arr[j+1]: 10 arr[j], arr[j + 1] = arr[j + 1], arr[j] 11 # 把无序数列的边界更新为最后一次交换元素的位置 12 sortBorder = j 13 # 发生交换，序列定为无序 14 isSorted = False 15 # 序列有序，停止循环 16 if isSorted: 17 break 18 return arr 19 20if __name__ == '__main__': 21 arr = [ 22 22, 5, 50, 3, 32, 37, 34, 35, 9, 55, 64, 70, 82, 89 ] 23 bubbleSort(arr) 24 print(arr) -
C实现：
1#include <stdio.h> 2#include <stdbool.h> 3 4void bubbleSort(int arr[], int len) 5{ 6 int sortBorder = len - 1; 7 for (int i = 0; i < len - 1; i++) 8 { 9 // 有序flag，初始为True 10 bool isSorted = true; 11 for (int j = 0; j < len - 1 - i; j++) 12 if (arr[j] > arr[j + 1]) 13 { 14 arr[j] = arr[j] ^ arr[j+1]; 15 arr[j+1] = arr[j] ^ arr[j+1]; 16 arr[j] = arr[j] ^ arr[j+1]; 17 // 把无序数列的边界更新为最后一次交换元素的位置 18 sortBorder = j; 19 // 发生交换，序列定为无序 20 isSorted = false; 21 } 22 // 序列有序，停止循环 23 if (isSorted) 24 break; 25 } 26} 27 28int main(void) 29{ 30 int arr[] = { 31 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 }; 32 int len = (int)sizeof(arr) / sizeof(*arr); 33 bubbleSort(arr, len); 34 for (int i = 0; i < len; i++) 35 printf("%d ", arr[i]); 36 return 0; 37}
选择排序
选择排序（Selection Sort）是一种简单直观的排序算法，无论什么数据进去都是 $O(n²)$ 的时间复杂度。
算法步骤
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复步骤2，直到所有元素均排序完毕。
动画演示：
代码实现
Python实现
1def selectionSort(arr):
2 for i in range(len(arr) - 1):
3 # 记录最小数的索引
4 minIndex = i
5 for j in range(i + 1, len(arr)):
6 if arr[j] < arr[minIndex]:
7 minIndex = j
8 # i 不是最小数时，将 i 和最小数进行交换
9 if i != minIndex:
10 arr[i], arr[minIndex] = arr[minIndex], arr[i]
11 return arr
12
13if __name__ == '__main__':
14 arr = [
15 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 ]
16 arr = selectionSort(arr)
17 print(arr)
C实现
1#include <stdio.h>
2
3void selectionSort(int arr[], int len)
4{
5 for (int i = 0 ; i < len - 1 ; i++)
6 {
7 int min = i;
8 for (int j = i + 1; j < len; j++) // 走访未排序的元素
9 // 找到最小值
10 if (arr[j] < arr[min])
11 min = j;
12 // i 不是最小数时，将 i 和最小数进行交换
13 if (i != min)
14 {
15 int tmp = arr[i];
16 arr[i] = arr[min];
17 arr[min] = tmp;
18 }
19 }
20}
21
22int main(void)
23{
24 int arr[] = {
25 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
26 int len = (int)sizeof(arr) / sizeof(*arr);
27 selectionSort(arr, len);
28 for (int i = 0; i < len; i++)
29 printf("%d ", arr[i]);
30 return 0;
31}
插入排序
插入排序（Insertion Sort）是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序的有一种优化算法，叫做拆半插入。
算法步骤
假设序列的长度为$n$，其待排序序列第一个元素的位置为$m$（$1 \le m \le n$，元素位置从0开始）。
-
将元素$m$与已排序序列中的每个元素进行比较。如果已排序元素比元素$m$大，将元素$m$中比已排序序列大的元素往后移，直到前面没有比元素$m$大的元素（或前面已经没有元素）。将元素m插入。
如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。
-
从头到尾依次扫描未排序序列，直到没有未排序元素。
动画演示：
代码实现
Python实现
1def insertionSort(arr):
2 for i in range(len(arr) - 1):
3 preIndex = i
4 current = arr[i + 1]
5 # 找出要插入的位置
6 while preIndex >= 0 and arr[preIndex] > current:
7 # 将比current大的元素往后移
8 arr[preIndex + 1] = arr[preIndex]
9 preIndex -= 1
10 # 将current插入到适当的位置
11 arr[preIndex + 1] = current
12 return arr
13
14if __name__ == '__main__':
15 arr = [
16 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 ]
17 insertionSort(arr)
18 print(arr)
C实现
1#include <stdio.h>
2
3void insertionSort(int arr[], int len)
4{
5 for (int i = 0 ; i < len - 1 ; i++)
6 {
7 int current = arr[i + 1];
8 int j = i;
9 while (j >= 0 && arr[j] > current)
10 {
11 arr[j + 1] = arr[j];
12 j--;
13 }
14 arr[j + 1] = current;
15 }
16}
17
18int main(void)
19{
20 int arr[] = {
21 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
22 int len = (int)sizeof(arr) / sizeof(*arr);
23 insertionSort(arr, len);
24 for (int i = 0; i < len; i++)
25 printf("%d ", arr[i]);
26 return 0;
27}
希尔排序
算法步骤
希尔排序（Shell Sort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
希尔排序的基本思想是：先将整个待排序的增量序列根据增量分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
算法步骤
- 选择一个增量序列$t_1,t_2,…,t_k$，其中$t_i < t_{i-1}(1 \le i \le k),t_k = 1$；
- 按增量序列个数$k$，对序列进行$k$趟排序；
- 每趟排序，根据对应的增量$t_i$，将待排序列分割成若干长度为$t_i$的子序列，分别对各子表进行直接插入排序。仅增量因子为$1$时，整个序列作为一个表来处理，表长度即为整个序列的长度。
动画演示：
详细过程（引用自博客：一个很懒的人）：
代码实现
Python实现
1def shellSort(arr):
2 # 将增量d初始化为len(arr)//2
3 d = len(arr) // 2
4 while d > 0:
5 # 分别用插入排序排序每个以d为增量的分组
6 for i in range(d, len(arr)):
7 tmp = arr[i]
8 j = i - d
9 while j >= 0 and tmp < arr[j]:
10 arr[j + d] = arr[j]
11 j -= d
12 arr[j + d] = tmp
13 # 每次将增量d缩小1/2
14 d //= 2
15
16 return arr
17
18if __name__ == '__main__':
19 arr = [
20 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 ]
21 shellSort(arr)
22 print(arr)
C实现
1#include <stdio.h>
2
3void shellSort(int arr[], int len)
4{
5 // 将增量d初始化为len/2，每次将增量d缩小1/2
6 for (int d = len >> 1; d > 0; d >>= 1)
7 {
8 // 分别用插入排序排序每个以d为增量的分组
9 for (int i = d; i < len; i++)
10 {
11 int tmp = arr[i];
12 int j;
13 for (j = i - d; j >= 0 && tmp < arr[j]; j -= d)
14 arr[j + d] = arr[j];
15 arr[j + d] = tmp;
16 }
17 }
18}
19
20int main(void)
21{
22 int arr[] = {
23 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
24 int len = (int)sizeof(arr) / sizeof(*arr);
25 shellSort(arr, len);
26 for (int i = 0; i < len; i++)
27 printf("%d ", arr[i]);
28 return 0;
29}
归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
- 自上而下的递归；
- 自下而上的迭代。
算法步骤
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤 3 直到某一指针达到序列尾；将另一序列剩下的所有元素直接复制到合并序列尾。
动画演示：
图片演示：
-
递归演示：
-
合并演示：
代码实现
Python 实现
1def mergeSort(arr):
2 # 结束递归
3 if(len(arr) < 2):
4 return arr
5 # 计算中间位置下标
6 middle = len(arr) // 2
7 # 将序列切分为两半
8 left, right = arr[:middle], arr[middle:]
9 # 进行归并排序
10 return merge(mergeSort(left), mergeSort(right))
11
12def merge(left, right):
13 result = []
14 while left and right:
15 # 将较小的元素放在前面
16 if left[0] <= right[0]:
17 result.append(left.pop(0))
18 else:
19 result.append(right.pop(0))
20 # 将某一序列中剩下的元素全部放入
21 while left:
22 result.append(left.pop(0))
23 while right:
24 result.append(right.pop(0))
25 return result
26
27if __name__ == '__main__':
28 arr = [
29 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 ]
30 arr = mergeSort(arr)
31 print(arr)
C实现
非递归实现：
1#include <stdio.h>
2#include <stdlib.h>
3
4int min(int x, int y)
5{
6 return x < y ? x : y;
7}
8
9void mergeSort(int arr[], int len)
10{
11 int* a = arr;
12 int* b = (int*)malloc(len * sizeof(int));
13 if (!b)
14 return;
15 // 分为约log_2(len)次
16 for (int seg = 1; seg < len; seg += seg)
17 {
18 // 每次对下标区间为[low,high)的子序列进行归并排序
19 for (int start = 0; start < len; start += seg * 2)
20 {
21 // 当前排序区间：[low,high)
22 int low = start, mid = min(start + seg, len),
23 high = min(start + seg * 2, len);
24 // 第1段：[low,mid)
25 int start1 = low, end1 = mid;
26 // 第2段：[mid,high)
27 int start2 = mid, end2 = high;
28 // 对子序列进行归并排序
29 int i = low;
30 // 将两个序列中较小的放在前面
31 while (start1 < end1 && start2 < end2)
32 b[i++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
33 // 将某一序列中剩下的元素全部放入
34 while (start1 < end1)
35 b[i++] = a[start1++];
36 while (start2 < end2)
37 b[i++] = a[start2++];
38 }
39 int* tmp = a;
40 a = b;
41 b = tmp;
42 }
43 if (a != arr)
44 {
45 for (int i = 0; i < len; i++)
46 b[i] = a[i];
47 b = a;
48 }
49 free(b);
50}
51
52int main(void)
53{
54 int arr[] = {
55 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
56 int len = (int) sizeof(arr) / sizeof(*arr);
57 mergeSort(arr, len);
58 for (int i = 0; i < len; i++)
59 printf("%d ", arr[i]);
60 return 0;
61}
递归实现：
1#include <stdio.h>
2#include <stdlib.h>
3
4void merge_sort_recursive(int arr[], int reg[], int start, int end)
5{
6 // 结束递归
7 if (start >= end)
8 return;
9 // 当前排序区间：[start,end]
10 int len = end - start, mid = (len >> 1) + start;
11 // 第1段：[start,mid]
12 int start1 = start, end1 = mid;
13 // 第2段：[mid+1,end]
14 int start2 = mid + 1, end2 = end;
15 // 对第1段进行递归地排序
16 merge_sort_recursive(arr, reg, start1, end1);
17 // 对第2段进行递归地排序
18 merge_sort_recursive(arr, reg, start2, end2);
19 int i = start;
20 while (start1 <= end1 && start2 <= end2)
21 reg[i++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
22 while (start1 <= end1)
23 reg[i++] = arr[start1++];
24 while (start2 <= end2)
25 reg[i++] = arr[start2++];
26 for (int i = start; i <= end; i++)
27 arr[i] = reg[i];
28}
29
30void mergeSort(int arr[], int len)
31{
32 int* reg = (int*)malloc(len * sizeof(int));
33 merge_sort_recursive(arr, reg, 0, len - 1);
34}
35
36int main(void)
37{
38 int arr[] = {
39 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
40 int len = (int) sizeof(arr) / sizeof(*arr);
41 mergeSort(arr, len);
42 for (int i = 0; i < len; i++)
43 printf("%d ", arr[i]);
44 return 0;
45}
快速排序
快速排序在平均状况下，排序$n$个项目是$O(n\log {n})$。最坏运行情况是$O(n^2)$，但这种状况并不常见，比如说数列为顺序数列的情况下。一般，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
事实上，快速排序通常明显比其他$O(n\log {n})$算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
算法步骤
- 从序列中选择一个元素作为“基准”（pivot）。
- 将所有比基准数小的放在基准左边，所有比基准数大的放在基准右边（相同的数可以在任一边）。这个称为分区（partition）操作。
- 分区完成后，该基准就会归到序列中的相应位置，该位置是排序完成后的位置。
- 分别递归地把小于基准数的子序列（左边）和大于基准数的子序列（右边）执行1~3操作。
动画演示：
代码实现
Python实现
1def swap(arr, i, j):
2 arr[i], arr[j] = arr[j], arr[i]
3
4def partition(arr, left, right):
5 # 设置基准
6 pivot = left
7 # 索引从基准的下一个元素开始
8 index = pivot + 1
9 # 遍历:[index,right]
10 for i in range(index, right + 1):
11 # 将小于基准值的元素全部放到左边
12 if arr[i] < arr[pivot]:
13 swap(arr, i, index)
14 index += 1
15 i += 1
16 # 将基准归位
17 # 此时index位置上的是比基准值大的元素
18 # 或者等于right+1
19 # 即1<=index<=right+1
20 # 只有index-1才是基准真正的位置
21 swap(arr, pivot, index - 1)
22 return index - 1
23
24def quickSort(arr, left=None, right=None):
25 # 设定参数值
26 left = 0 if not isinstance(left, (int, float)) else left
27 right = len(arr) - 1 if not \
28 isinstance(right, (int, float)) else right
29 if left < right:
30 # 先进行“治”操作并取得分区索引
31 partitionIndex = partition(arr, left, right)
32 # 分别对左右两个分区递归地进行快速排序
33 quickSort(arr, left, partitionIndex - 1)
34 quickSort(arr, partitionIndex + 1, right)
35 return arr
36
37if __name__ == '__main__':
38 arr = [
39 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 ]
40 quickSort(arr)
41 print(arr)
C实现
递归实现：
1#include <stdio.h>
2
3void quick_sort_recursive(int arr[], int start, int end)
4{
5 if (start >= end)
6 return;
7 // 设置基准
8 int pivot = arr[start];
9 int left = start, right = end;
10 while (left < right)
11 {
12 // 先从右边起找出比基准小的
13 while (arr[right] >= pivot && left < right)
14 right--;
15 // 把比基准小的放到基准左边
16 arr[left] = arr[right];
17 // 再从左边起找出比基准大的
18 while (arr[left] <= pivot && left < right)
19 left++;
20 // 把比基准大的放到基准右边
21 arr[right] = arr[left];
22 }
23 // 将基准归位
24 arr[left] = pivot;
25 // 分别递归地排序左右两个分区
26 quick_sort_recursive(arr, start, left - 1);
27 quick_sort_recursive(arr, left + 1, end);
28}
29
30void quickSort(int arr[], const int len)
31{
32 quick_sort_recursive(arr, 0, len - 1);
33}
34
35int main(void)
36{
37 int arr[] = {
38 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
39 int len = (int)sizeof(arr) / sizeof(*arr);
40 quickSort(arr, len);
41 for (int i = 0; i < len; i++)
42 printf("%d ", arr[i]);
43 return 0;
44}
非递归实现：
1#include <stdio.h>
2#include <stdlib.h>
3
4// 范围
5typedef struct _stack
6{
7 int start, end;
8} Range;
9
10// 申请一个新的栈元素
11Range new_Range(int start, int end)
12{
13 Range s = {
14 .start = start,
15 .end = end
16 };
17 return s;
18}
19
20void quickSort(int arr[], const int len)
21{
22 if (len <= 1)
23 return;
24 // s模拟栈，p为数量，r[p++]为push，r[--p]为pop0
25 Range* s = (Range*)malloc(len * sizeof(Range));
26 int p = 0;
27 // 范围为[0,len-1]
28 s[p++] = new_Range(0, len - 1);
29 while (p)
30 {
31 // pop出当前要排序的范围
32 Range range = s[--p];
33 if (range.start >= range.end)
34 continue;
35 // 设置基准
36 int pivot = arr[range.start];
37 int left = range.start, right = range.end;
38 while (left < right)
39 {
40 // 先从右边起找出比基准小的
41 while (arr[right] >= pivot && left < right)
42 right--;
43 // 把比基准小的放到基准左边
44 arr[left] = arr[right];
45 // 再从左边起找出比基准大的
46 while (arr[left] <= pivot && left < right)
47 left++;
48 // 把比基准大的放到基准右边
49 arr[right] = arr[left];
50 }
51 // 将基准归位
52 arr[left] = pivot;
53 // 分别设置左右两个分区的范围
54 if (range.start < left)
55 s[p++] = new_Range(range.start, left - 1);
56 if (range.end > left)
57 s[p++] = new_Range(left + 1, range.end);
58 }
59 free(s);
60}
61
62int main(void)
63{
64 int arr[] = {
65 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
66 int len = (int)sizeof(arr) / sizeof(*arr);
67 quickSort(arr, len);
68 for (int i = 0; i < len; i++)
69 printf("%d ", arr[i]);
70 return 0;
71}
堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆积是一种近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
- 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
- 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。
堆排序是不稳定的。
算法步骤
-
将待排序的数组构造出一个堆
H[0……n-1]； -
把堆首（堆顶结点，即最大值）和堆尾（堆的最下层最右边的结点）互换；
此时不再对原堆顶（最大值）进行操作，即原堆顶已经被“移出”，堆的长度缩小1。
-
把新的数组顶端数据调整到相应位置；
-
重复步骤 2~3，直到堆的尺寸为 1。
动画演示：
代码实现
Python实现
1def swap(arr, i, j):
2 arr[i], arr[j] = arr[j], arr[i]
3
4def heapify(arr, len, i):
5 # 子结点
6 son = 2*i + 1
7 # 最大值元素位置
8 largest = i
9 # 将最大值置为堆顶结点
10 if son < len:
11 if son + 1 < len and arr[son + 1] > arr[son]:
12 son += 1
13 if arr[son] > arr[largest]:
14 largest = son
15 swap(arr, i, largest)
16 # 重新构造子堆
17 heapify(arr, len, largest)
18
19def buildMaxHeap(arr):
20 # int(len(arr)/2)递减至0
21 for i in range(int(len(arr)/2) - 1, -1, -1):
22 heapify(arr, len(arr), i)
23
24def heapSort(arr, left=None, right=None):
25 global arrLen
26 arrLen = len(arr)
27 # 构造堆
28 buildMaxHeap(arr)
29 # len(arr)-1递减至1
30 for i in range(len(arr)-1, 0, -1):
31 # 交换堆顶和最下层最右元素
32 swap(arr, 0, i)
33 # 将原堆顶移出并重新调整堆
34 heapify(arr, i, 0)
35 return arr
36
37if __name__ == '__main__':
38 arr = [
39 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 ]
40 heapSort(arr)
41 print(arr)
C实现
1#include <stdio.h>
2#include <stdlib.h>
3
4void swap(int* x, int* y)
5{
6 int tmp = *x;
7 *x = *y;
8 *y = tmp;
9}
10
11void heapify(int arr[], int len, int i)
12{
13 // 子节点
14 int son = i*2 + 1;
15 // 最大值元素位置
16 int largest = i;
17 // 将最大值置为堆顶结点
18 if (son < len)
19 {
20 if (son + 1 < len && arr[son + 1] > arr[son])
21 son++;
22 if (arr[son] > arr[largest])
23 {
24 largest = son;
25 swap(&arr[i], &arr[largest]);
26 // 重新构造子堆
27 heapify(arr, len, largest);
28 }
29 }
30}
31
32void buildMaxHeap(int arr[], int len)
33{
34 for (int i = len / 2 - 1; i >= 0; i--)
35 heapify(arr, len, i);
36}
37
38void heapSort(int arr[], int len)
39{
40 // 构造堆
41 buildMaxHeap(arr, len);
42 for (int i = len - 1; i > 0; i--)
43 {
44 // 交换堆顶和最下层最右元素
45 swap(&arr[0], &arr[i]);
46 // 将原堆顶移出并重新调整堆
47 heapify(arr, i, 0);
48 }
49}
50
51int main(void)
52{
53 int arr[] = {
54 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
55 int len = (int)sizeof(arr) / sizeof(*arr);
56 heapSort(arr, len);
57 for (int i = 0; i < len; i++)
58 printf("%d ", arr[i]);
59 return 0;
60}
计数排序
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是$Θ(n + k)$。计数排序不是比较排序，排序的速度快于任何比较排序算法。
由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。
算法步骤
- 找出待排序的数组中最大和最小的元素。
- 统计数组中每个值为
i的元素出现的次数，存入数组C的第i项。 - 对所有的计数累加（从
C中的第一个元素开始，每一项和前一项相加）。 - 反向填充目标数组：将每个元素
i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
动画演示：
代码实现
Python实现
1def countingSort(arr):
2 # 找出最大值
3 max = arr[0]
4 for i in range(1, len(arr)):
5 if arr[i] > max:
6 max = arr[i]
7 # 构建一个长度为max+1的数组
8 bucket = [0] * (max + 1)
9 # 计数
10 for i in range(len(arr)):
11 if not bucket[arr[i]]:
12 bucket[arr[i]] = 0
13 bucket[arr[i]] += 1
14 # 反向填充
15 index = 0
16 for i in range(len(bucket)):
17 while bucket[i] > 0:
18 arr[index] = i
19 bucket[i] -= 1
20 index += 1
21 return arr
22
23if __name__ == '__main__':
24 arr = [
25 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 ]
26 countingSort(arr)
27 print(arr)
C实现
1#include <stdio.h>
2#include <stdlib.h>
3
4void countingSort(int arr[], int len)
5{
6 // 找出最大值
7 int max = arr[0];
8 for (int i = 0; i < len; i++)
9 if (arr[i] > max)
10 max = arr[i];
11 // 构造和初始化
12 int bucketLen = max + 1;
13 int* bucket = (int*)malloc(bucketLen * sizeof(int));
14 for (int i = 0; i < bucketLen; i++)
15 bucket[i] = 0;
16
17 // 计数
18 for (int i = 0; i < len; i++)
19 if (arr[i] < bucketLen)
20 bucket[arr[i]]++;
21 // 反向填充
22 for (int i = 0, j = 0; i < bucketLen; i++)
23 while (bucket[i] > 0)
24 {
25 arr[j++] = i;
26 bucket[i]--;
27 }
28}
29
30int main(void)
31{
32 int arr[] = {
33 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
34 int len = (int)sizeof(arr) / sizeof(*arr);
35 countingSort(arr, len);
36 for (int i = 0; i < len; i++)
37 printf("%d ", arr[i]);
38 return 0;
39}
桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，需要做到两点：
- 在额外空间充足的情况下，尽量增大桶的数量
- 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
- 最快的情况：当输入的数据可以均匀的分配到每一个桶中。
- 最慢的情况：当输入的数据被分配到了同一个桶中。
算法步骤
-
将数列中的数均匀地分布到每个桶中（有时候并不是均匀分布）。
-
将每个桶中的数进行排序。
这里的排序可以使用桶排序也可以使用其它方法排序。
-
按照顺序将所有桶中的数据取出。
图片演示：
将元素分布在桶中：
元素在每个桶中排序：
代码实现
Python实现
1from quick_sort import quickSort
2
3def bucketSort(arr, bucketsize):
4 if len(arr) == 0 or bucketsize <= 0:
5 return arr
6 # 确定最大最小值
7 maxValue = minValue = arr[0]
8 for i in arr:
9 if i < minValue:
10 minValue = i
11 elif i > maxValue:
12 maxValue = i
13 # 桶数量
14 count = (maxValue - minValue) // bucketsize + 1
15 # 对应的桶
16 buckets = [[] for i in range(count + 1)]
17
18 # 把数据放入相应的桶
19 for i in arr:
20 index = (i - minValue) // bucketsize
21 buckets[index].append(i)
22
23 # 桶内排序并合并数据
24 arr.clear()
25 for j in buckets:
26 if len(j) != 0:
27 # 桶排序
28 # bucketSort(j, bucketsize-1)
29 # 快速排序
30 quickSort(j)
31 # 还可以换其它方法排序
32 arr.extend(j)
33 return arr
34
35if __name__ == "__main__" :
36 arr = [
37 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 ]
38 bucketSort(arr, 5)
39 print(arr)
C实现
1#include <stdio.h>
2#include <stdlib.h>
3
4extern void quickSort(int arr[], const int len);
5
6typedef struct _list
7{
8 int* bucket;
9 int len;
10} List;
11
12void append(List* pl, int num)
13{
14 if (!pl->len)
15 {
16 pl->bucket = (int*)malloc(sizeof(int));
17 pl->bucket[pl->len++] = num;
18 return;
19 }
20 int* tmp = (int*)malloc((pl->len + 1) * sizeof(int));
21 for (int i = 0; i < pl->len; i++)
22 tmp[i] = pl->bucket[i];
23 tmp[pl->len++] = num;
24 free(pl->bucket);
25 pl->bucket = tmp;
26}
27
28void bucketSort(int arr[], int len, int bucketsize)
29{
30 // 确定最大最小值
31 int max = arr[0], min = max;
32 for (int i = 0; i < len; i++)
33 if (arr[i] < min)
34 min = arr[i];
35 else if (arr[i] > max)
36 max = arr[i];
37
38 // 桶数量
39 int count = (max - min) / bucketsize + 1;
40 // 对应的桶
41 List* buckets = (List*)malloc(count * sizeof(List));
42 for (int i = 0; i < count; i++)
43 {
44 buckets[i].bucket = NULL;
45 buckets[i].len = 0;
46 }
47
48 // 方案一：动态数组
49 // 把数据放入相应的桶
50 for (int i = 0; i < len; i++)
51 {
52 int index = (arr[i] - min) / bucketsize;
53 append(&buckets[index], arr[i]);
54 }
55 // 方案二：二维数组
56 // int* size = (int*)malloc(count * sizeof(int));
57 // // 计算最大宽度
58 // for (int i = 0; i < count; i++)
59 // size[i] = 0;
60 // for (int i = 0; i < len; i++)
61 // size[(arr[i] - min) / bucketsize]++;
62 // int maxSize = 0;
63 // for (int i = 0; i < count; i++)
64 // if (size[i] > maxSize)
65 // maxSize = size[i];
66 // // 把数据放入相应的桶
67 // for (int i = 0; i < len; i++)
68 // {
69 // int index = (arr[i] - min) / bucketsize;
70 // if (!buckets[index].len)
71 // buckets[index].bucket = (int*)malloc(maxSize * sizeof(int));
72 // buckets[index].bucket[buckets[index].len++] = arr[i];
73 // }
74 // free(size);
75
76 // 桶内快排并合并数据
77 int index = 0;
78 for (int i = 0; i < count; i++)
79 if (buckets[i].len)
80 {
81 quickSort(buckets[i].bucket, buckets[i].len);
82 for (int j = 0; j < buckets[i].len; j++)
83 arr[index + j] = buckets[i].bucket[j];
84 index += buckets[i].len;
85 free(buckets[i].bucket);
86 buckets[i].bucket = NULL;
87 buckets[i].len = 0;
88 }
89
90 free(buckets);
91}
92
93int main(void)
94{
95 int arr[] = {
96 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
97 int len = (int)sizeof(arr) / sizeof(*arr);
98 bucketSort(arr, len, 5);
99 for (int i = 0; i < len; i++)
100 printf("%d ", arr[i]);
101 return 0;
102}
基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序还可以用于其它数据类型的排序（但其本质上还是整型，如字符型）。
基数排序用到了桶的概念，是桶排序的扩展，它是根据键值的每位数字来分配桶。
算法步骤
有两类基数排序：
- 最低位优先法，简称LSD法：先从最低位开始排序，再对次低位排序，直到对最高位排序后得到一个有序序列；
- 最高位优先法，简称MSD法：先从最高位开始排序，再逐个对各分组按次高位进行子排序，循环直到最低位。
📌如果位没有数的话，补0。
动画演示：
代码实现
Python实现
1def getBit(num, i):
2 return (num // i) % 10
3
4def getMax(arr):
5 max = arr[0]
6 for i in range(len(arr)):
7 if arr[i] > max:
8 max = arr[i]
9 return max
10
11def radixSort(arr):
12 if len(arr) <= 1:
13 return arr
14 # 获取最大值
15 max = getMax(arr)
16 # 根据最大位数排序
17 index = 1
18 while max // index:
19 # 桶排序
20 buckets = [[] for i in range(10)]
21 for x in arr:
22 bit_num = getBit(x, index)
23 buckets[bit_num].append(x)
24 arr.clear()
25 for x in buckets:
26 arr.extend(x)
27 index *= 10
28
29 return arr
30
31if __name__ == "__main__" :
32 arr = [
33 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 ]
34 radixSort(arr)
35 print(arr)
C实现
1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct _list
5{
6 int* bucket;
7 int len;
8} List;
9
10void append(List* pl, int num)
11{
12 if (!pl->len)
13 {
14 pl->bucket = (int*)malloc(sizeof(int));
15 pl->bucket[pl->len++] = num;
16 return;
17 }
18 int* tmp = (int*)malloc((pl->len + 1) * sizeof(int));
19 for (int i = 0; i < pl->len; i++)
20 tmp[i] = pl->bucket[i];
21 tmp[pl->len++] = num;
22 free(pl->bucket);
23 pl->bucket = tmp;
24}
25
26int getBit(int num, int i)
27{
28 return (num / i) % 10;
29}
30
31void radixSort(int arr[], int len)
32{
33 if (len <= 1)
34 return;
35 // 获取最大值
36 int max = arr[0];
37 for (int i = 1; i < len; i++)
38 if (arr[i] > max)
39 max = arr[i];
40 // 根据最大位数排序
41 // 方案一：动态数组
42 for (int i = 1; max / i; i *= 10)
43 {
44 // 桶排序
45 List buckets[10] = { {NULL, 0} };
46 for (int j = 0; j < len; j++)
47 append(&buckets[getBit(arr[j], i)], arr[j]);
48 int index = 0;
49 for (int j = 0; j < 10; j++)
50 if (buckets[j].len)
51 {
52 for (int k = 0; k < buckets[j].len; k++)
53 arr[index + k] = buckets[j].bucket[k];
54 index += buckets[j].len;
55 free(buckets[j].bucket);
56 buckets[j].bucket = NULL;
57 buckets[j].len = 0;
58 }
59 }
60 // 方案二：二维数组
61 // for (int i = 1; max / i; i *= 10)
62 // {
63 // // 计算最大宽度
64 // int size[10] = { 0 };
65 // for (int j = 0; j < len; j++)
66 // size[getBit(arr[j], i)]++;
67 // int maxSize = size[0];
68 // for (int j = 0; j < 10; j++)
69 // if (size[j] > maxSize)
70 // maxSize = size[j];
71 // // 桶排序
72 // List buckets[10] = { {NULL, 0} };
73 // for (int j = 0; j < len; j++)
74 // {
75 // int index = getBit(arr[j], i);
76 // if (!buckets[index].len)
77 // buckets[index].bucket = (int*)malloc(maxSize*sizeof(int));
78 // buckets[index].bucket[buckets[index].len++] = arr[j];
79 // }
80 // int index = 0;
81 // for (int j = 0; j < 10; j++)
82 // if (buckets[j].len)
83 // {
84 // for (int k = 0; k < buckets[j].len; k++)
85 // arr[index + k] = buckets[j].bucket[k];
86 // index += buckets[j].len;
87 // free(buckets[j].bucket);
88 // buckets[j].bucket = NULL;
89 // buckets[j].len = 0;
90 // }
91 // }
92}
93
94int main(void)
95{
96 int arr[] = {
97 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
98 int len = (int)sizeof(arr) / sizeof(*arr);
99 radixSort(arr, len);
100 for (int i = 0; i < len; i++)
101 printf("%d ", arr[i]);
102 return 0;
103}
评论