Noob
0%

排序算法总结

发表于 更新于 分类于 ，

插入排序

基本思想：维护一个已排好序的序列，每次从未排好序的序列中选择一个元素插入排好序的序列中。具体来说，初始已排序序列为第一个元素，从第二个元素开始，每次选择一个未排序元素，将已排序序列中所有大于该元素的元素向后移动一位，然后把该未排序元素放到排序序列的正确位置。该算法平均时间复杂度O(n^2),在元素已排好序的情况下，时间复杂度为O(n),空间复杂度O(1),是一种稳定排序算法。

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

希尔（Shell）排序

基本思想：希尔排序是对插入排序的优化，其依据如下。

  1. 当数据规模较小时，插入排序效率较高（n与n^2差距较小）
  2. 当元素基本有序时，插入排序效率较高

基于以上事实，希尔排序的过程为：

  1. 先将所有待排序元素划分为较小的子序列，子序列中相邻元素间的距离为增量值。
  2. 对划分的子序列进行插入排序。
  3. 重复1和2并不断减小增量值，当完成增量为1的排序后，所有元素完成排序
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void shell_sort(T arr[], int len) {
    	int gap, i, j;
    	T temp;
    	for (gap = len >> 1; gap > 0; gap >>= 1)
    		for (i = gap; i < len; i++) {
    			temp = arr[i];
    			for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
    				arr[j + gap] = arr[j];
    			arr[j + gap] = temp;
    		}
    }

选择排序

基本思想：每次从未排序序列中选择最小（大）元素放到已排序序列尾部。具体来说，初始时，所有元素都是未排序的，从第一个元素开始，向后扫描未排序序列，记录最小（大）元素下标，将该下标元素交换到扫描起始位置。由于交换过程中有可能把前面的相等元素交换到后面，所以选择排序算法是不稳定的（例如：5，5，2）。该算法时间复杂度O(n^2)，最好最坏都是O(n^2)，空间复杂度O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void select_sort(int a[], int n) {
    int pos, tmp;
    for(int i = 0; i < n - 1; ++i) {
        pos = i;
        for (int j = i + 1; j < n; ++j)
//如果for (int j = i + 1, pos = i; j < n; ++j)，pos作用域出现Bug
            if(a[j] < a[pos])
                pos = j;
        if(pos != i) {
            tmp = a[i];
            a[i] = a[pos];
            a[pos] = tmp;
        }
    }
}

冒泡排序

基本思想：元素两两交换，把大的元素交换到后面，每次冒泡都能把未排序序列中的最大元素放到正确的位置上。平均时间复杂度O(n^2)，空间复杂度O(1)，该排序算法是稳定排序算法。
改进一：设置一个标志，如果某轮冒泡没有发生元素交换，表示所有元素已完成排序，可提前退出循环。
改进二：用一个变量记录最后一次交换的位置坐标，该坐标之后的所有元素已完成排序，可以不再进行交换。

1
2
3
4
5
6
7
8
9
10
11
void insert_sort(int a[], int n) {
    int tmp;
    for(int i = 0; i < n - 1; ++i) {
        for(int j = 0; j < n - 1; ++j)
            if(a[j + 1] < a[j]) {
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
    }
}

快速排序

和归并排序一样是一种分治递归算法

基本思想：每次把一个元素放到正确位置上。具体来说，每次选择一个基准元素，所有大于该基准元素的元素放到前面，所有大于该基准元素的元素移动到该元素后面，然后把基准元素放到正确的位置上。重复该过程，直到所有元素都放到正确位置上。快速排序算法是一种不稳定的排序算法，平均时间复杂度O(NlongN),最坏时间复杂度O(N^2),空间复杂度O(longN)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int partation(int a[], int l, int r) {
    int p = a[l];
    while (l < r) {
        while (l < r && a[r] >= p) --r;
        a[l] = a[r];
        while (l < r && a[l] <= p) ++l;
        a[r] = a[l];
    }
    a[l] = p;
    return l;
}

void quick_sort(int a[], int l, int r) {
    if (l < r) {
        int p = partation(a, l, r);
        quick_sort(a, l, p - 1);
        quick_sort(a, p + 1, r);
    }
}

归并排序

基本思想：归并排序是典型的分治法，每次将两个排好序的序列归并成一个有序序列。初始时每个元素都是一个有序序列，然后每2个元素归并、每4个元素归并……直到归并成一个有序序列。可以采用递归的方法，平均、最好、最坏的时间复杂度都是O(NlongN)，空间复杂度O(N)+Olong(N)。

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
31
32
33
34
35
36
37
void merge(int a[], int start, int end, int tmp[]) {
    int mid = (start + end) >> 1;
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if(a[i] < a[j]) {
            tmp[k] = a[i];
            ++i;
        } else {
            tmp[k] = a[j];
            ++j;
        }
        ++k;
    }
    while (i <= mid) {
        tmp[k] = a[i];
        ++i;
        ++k;
    }
    while (j <= end) {
        tmp[k] = a[j];
        ++j;
        ++k;
    }
    for (i = start; i <= end; ++i) {
        a[i] = tmp[i];
    }
}


void merge_sort(int a[], int l, int r, int tmp[]) {
    if (l < r) {
        int mid = (l + r) >> 1;
        merge_sort(a, l, mid, tmp);
        merge_sort(a, mid + 1, r, tmp);
        merge(a, l, r, tmp);
    }
}

堆排序

基本思想：利用堆的性质，先将所有元素插入大顶堆，在插入的过程中调整堆。循环取出堆顶元素与堆的最后一个叶节点交换，得到最大元素、次大元素……放入有序序列。时间复杂度O(NlongN), 空间复杂度O(1).

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
void adjust(int a[], int x, int n) {
    int child = 2 * x + 1;
    while (child < n) {
        if (child + 1 < n && a[child + 1] > a[child])
            child = child + 1;
        if (a[child] > a[x]) {
            int tmp = a[x];
            a[x] = a[child];
            a[child] = tmp;
            x = child;
            child = 2 * child + 1;	
        } else {
            break;
        }
    }
}

void heap_sort(int a[], int n) {
    for(int i = n / 2 - 1; i >= 0; --i)
        adjust(a, i, n);
    for (int i = n - 1; i > 0; --i) {
        int tmp = a[i];
        a[i] = a[0];
        a[0] = tmp;
        adjust(a, 0, i);
    }
}

二叉树排序

基本思想：利用二叉搜索树（Binary Search Tree，BST）的中序遍历是一个非递减序列的性质。先将所有元素插入二叉搜索树，然后中序遍历该二叉树即可得到非递减序列。为了提高性能，在插入过程中需维持二叉树的平衡

上述的插入排序、选择排序、冒泡排序、快速排序、归并排序、堆排序、二叉树排序都是基于比较的排序，时间复杂度为O(N^2)或O(NlongN)。基于比较的排序时间复杂度下界为O(NlongN)。

非比较排序的时间复杂度可以达到O(N)，但是需要额外的空间，非比较排序有计数排序、桶排序、基数排序和希尔排序。

桶排序

基本思想：利用分治/Hash的思想，通过某种映射关系，将待排序元素放到若干个有序的桶中，使得待排序元素基本有序。然后对每个桶内的元素进行排序。最后把所有桶的元素合并到一起就可以得到有序序列。计数排序可以看做桶排序的特殊情况。

计数排序

基本思想：计数排序要求待排序元素是整数，首先找出待排序元素的最小值max和最大值min，开辟max - min + 1个数组元素，然后遍历待排序元素，对遍历元素值对应数组下标计数。最后扫描数组，通过计数值确定元素在排序序列中的位置。

计数排序适用于待排序元素的值包含在一个封闭区间的情况，例如对大量学生成绩排序[0, 100]。

基数排序

基本思想：基数排序也可以看做桶排序的一种，具体步骤如下。

  1. 初始化基数个桶（例如，对十进制整数排序时，初始化10个桶）
  2. 从最低位开始依次将元素放到该位数值对应的桶中
  3. 按照桶的顺序把元素放回
  4. 重复步骤2和3，直到遍历完所有位数