排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n2​) O(n) O(n2) O(1) 稳定
简单选择排序 O(n2) O(n2) O(n2) O(1) 稳定
直接插入排序 O(n2) O(n) O(n2) O(1) 稳定
希尔排序 O(nlogn)~O(n2) O(n1.3) O(n2) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(nlogn) O(n2) O(logn)~O(n) 不稳定

冒泡排序

1
2
3
4
5
6
void bubble_sort(int arr[], int len) {
	for (int i = 0; i < len - 1; i++)
		for (int j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}

直接插入排序

1
2
3
4
5
void insert_sort(int a[], int n) {
    for(int i = 1; i < n; i++)
        for(int j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)
            swap(a[j], a[j + 1]);
}

简单选择排序

1
2
3
4
5
6
7
8
void selection_sort(int a[], int n) {
    for(int i = 0; i < n - 1; i++) {
        int min = i;
        for(int j = i + 1; j < n; j++)
            if(a[j] < a[min]) min = j;
        swap(a[i], a[min]);
    }
}

希尔排序

1
2
3
4
5
6
7
8
9
void shell_sort(int a[], int n) {
    int gap = 1;	//步长
    while(gap < n / 3)
        gap = 3 * gap + 1;
    for(; gap > 0; gap /= 3)
        for(int i = gap; i < n; i++)
            for(int j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)	//每个元素与自己组内的数据进行直接插入排序
                swap(a[j], a[j + gap]);
}

具体步长选择方法可以参照：维基百科 or 大佬的简书

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void quick_sort(int a[], int l, int r) {
    if(l >= r)	return;
    
    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while(i < j) {
        do i++;	while(a[i] < x);	//while(a[++i] < x);
        do j--;	while(a[j] > x);	//while(a[--j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}
/*
	用i的话：
    x = a[l + r + 1 >> 1];
    quick_sort(a, l, i - 1);
    quick_sort(a, i, r);
    */

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void merge_sort(int a[], int l, int r) {
    if(l >= r)	return;
    
    int mid = l + r >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);
    
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
        if(a[i] < a[j]) tmp[k++] = a[i++];
    	else tmp[k++] = a[j++];
    
    while(i <= mid)	tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    
    for(i = l, j = 0; i <= r; i++, j++)
        a[i] = tmp[j];
}

堆排序

堆本质上是一棵完全二叉树。以小根堆为例，其每个点都是小于等于左右子节点的，根节点就是整个树的最小值。

堆的存储方式：用一维数组存储，heap[1]是整个堆的根节点，设某节点的下标是x，则左儿子是2x，右儿子是2x+1。

往下调整与往上调整：
如果某个数变大了，就要把它往下移,直到不能下移为止；反之，则要往上移。

堆的一些操作

1
2
3
4
5
heap[++size] = x;up(size); //插入一个数
heap[1]; //求最小值
heap[1] = heap[size];size--;down(1); //删除最小值
heap[k] = heap[size];size--;down(k);up(k); //删除任意一个元素
heap[k] = x;down(k);up[k]; //修改任意一个元素

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int h[N], size; //heap[]从1开始，size为数组长度(下标)

void down(int u) {
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    
    if (u != t) {
        swap(h[u], h[t]);
        down(t);
    }
}

void up(int u) {
    while (u / 2 && h[u / 2] > h[u]) {
        swap(h[u / 2], h[u]);
        u /= 2;
    }
}

void heap_sort() {  //先要建立小根堆，最终得到递减数列
    for (int i = size / 2; i; i--) //建立小根堆
        down(i);
    int t = size; //暂存size
    while(size) {
        swap(h[1], h[size--]);
        down(1);
    }
    size = t;
}