trudbot
0%

排序算法

发表于 更新于 分类于
本文字数： 4.5k 阅读时长 ≈ 8 分钟

没什么写， 突发奇想总结一下以前写过的排序算法， 权当复习。

以下皆以升序举例， a为默认数组名， n默认为数组长度

冒泡排序

大多数人学的第一个排序算法就算冒泡排序， 思想是每次比较相邻的两个数， 如果与升序不符合就进行交换； 从前到后一轮交换下来， 不难发现最大值会被交换到最后位， 因此下次只需要对前n-1个元素进行遍历即可。

每轮交换至少确定一个数的位置， 所以最多需要进行n - 1轮, 时间复杂度为

代码实现

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

选择排序

思想是每次都从剩余序列中选出一个最小值放到前面， 经过n-1次选择后数组即有序。

可以发现选择排序的过程其实和冒泡排序差不多， 但选择排序第i次选择只需要交换一次， 比较n - i + 1次， 而冒泡排序在比较次数相同的情况下， 还会有更多次交换。 因此选择排序的常数要比冒泡排序小。

代码实现

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

插入排序

插入排序是排序中表现最好的排序， 思想正如其名， 先将前i个元素排序， 在把第i + 1个元素插入前面已经有序的序列中。

插入排序的优势在于， 比较次数并不是死板的， 而是取决于元素应插入的位置。 特别的， 如果对有序序列进行插入排序， 那么每次插入只需要比较一次， 时间复杂度为。而对基本有序的序列， 插入排序效率也会更高。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
void Sort(int a[], int n) {
    for (int i = 1; i < n; i ++) {
        int x = a[i], j = i - 1;
        for (; j >= 0; j --) {
            if (a[j] > x) {
                a[j + 1] = a[j];
            } else {
                break;
            }
        }
        a[j + 1] = x;
    }
}

希尔排序

希尔排序基于对插入排序的优化， 是第一个出现的时间复杂度低于的排序。

前面提到， 当序列有序程度增大时， 插入排序的效率也会随之升高。希尔排序会先对数组的子数组进行插入排序， 直到数组有序程度较高， 再对整个数组进行插入排序。

在子数组的选择策略上， 我们选择从第一个元素开始的、下标间隔相同的所有元素， 如[3, 8, 3, 2, 4]， 若间隔为2， 子数组应该是[3, 3, 4]。

在实现上， 我们选择多组不同的间隔， 这里也叫做增量， 按增量从大到小的顺序依次对相应的子数组进行插入排序。 这里引入一个新的名词：增量序列， 增量序列是一个递增、初始项为1的正整数序列， 即为我们选择的间隔序列， 如[1, 2, 4, 8]， 如果我们要对长度为7的子数组使用该增量序列进行希尔排序， 则我们应该依次对增量为4, 2, 1的子数组进行插入排序， 显然增量为1的子数组即为原数组， 所以按增量序列依次进行插入排序最后肯定是能达到排序的效果的。

显然希尔排序的效率会受到增量序列的影响， 希尔排序的时间复杂度证明非常复杂， 受限于水平不在此说明。

比较常见的增量序列有发明者希尔推荐的希尔序列：[1, ..., len / 4, len / 2], 以及效率更高的Sedgewick序列

1
2
3
4
5
int Sedgewick[]={28,
    1,5,19,41,109,209,505,929,
    2161,3905,8929,16001,36289,64769,146305,260609,
    587521,1045505,2354689,4188161,9427969,16764929,37730305,67084289,
    150958081,268386305,603906049,1073643521};

代码实现

1
2
3
4
5
6
7
8
9
10
11
void Sort(int a[], int n) {
    for (int i = n >> 1; i;  i >>= 1) {//使用Shell序列
        for (int j = i; j < n; j ++) {
            int x = a[j];
            for (int k = j - i; k >= 0 && a[k] > x; k -= i) {
                a[k + i] = a[k];
            }
            a[k + i] = x;
        }
    } 
}

归并排序

归并排序是非常经典的分治算法， 思想是非常简单的：

  • 将数组分为左右两半
  • 对左半边数组和右半边数组进行归并排序
  • 将两段有序数组合并成一个有序数组

显然很适合用递归来实现， 而用递归最重要的就算确定递归的边界， 这里的边界就是数组的长度小于1， 此时数组已然是有序的。

在合并数组时， 若要达到线性的合并时间， 就要用到一个辅助数组， 将两边数组按大小依次填入辅助数组， 最后将辅助数组的数据写回原数组;显然辅助数组的长度最大要为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
void Sort(int a[], int l, int r, int t[]) {
    if (l >= r) {
        return;
    }
    int m = (l + r) >> 1;
    Sort(a, l, m, t), Sort(a, m + 1, r, t);
    //合并
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r ) {
        if (a[i] < a[j]) {
            t[k ++] = a[i ++];
        } else {
            t[k ++] = a[j ++];
        }
    }
    while (i <= m) {
        t[k ++] = a[i ++];
    }
    while (j <= r) {
        t[k ++] = a[j ++];
    }
    for (i = l; i <= r; i ++) {
        a[i] = t[i];
    }
}

快速排序

快速排序也是一个分治算法， 思想如下：

  • 从当前数组选出任意一个数作为枢纽p
  • 把数组中所有比p小的数放到p左边， 大的数放到右边(相等随意)， 这个过程叫做划分。
  • 对p左边的元素和右边的元素进行快速排序。

第一次看到时肯定是很迷茫的， 经过上面的递归过程数组怎么就有序了呢？

可以用类似数学归纳法的方法证明：

  • 首先来看递归边界： 当数组的长度小于等于1时， 数组本身是有序的。

  • 设数组经过划分后， 分出左右两个子数组为L/R， 假设L, R经过快速排序， 可以变成有序

  • 此时有L < p < R， 显然当前数组也为有序

以上就是快速排序的思想， 但要想让快速排序‘快速’， 我们就要考虑划分操作的实现。

最容易想到的是， 使用两个辅助数组， 来记录两边的信息；这当然是可以的， 但空间复杂度将于归并排序相同为

但先人发明了一个非常巧妙的双指针算法， 能以时间复杂度、空间复杂度完成划分操作。

基本思想是： 使用两个指针i, j， 从数组两边想中间遍历， i会停止在大于p的元素上， j会停止在小于p的元素上；当i， j都停止时， 将i、j指向元素进行一次交换。 遍历结束于i，j相遇。

关于时间复杂度， 我们同样关注递归的深度。 但快排于归并排序不同的是， 每次划分后两边的元素数量不一定相等， 因此快排的时间复杂度会取决于数据， 具有随机性。

对于快排的最好情况：每次划分都能划分为两个元素数量差不多的两边， 此时时间复杂度为； 对于快排的最坏情况， 每次划分都把全部元素划分到一边， 而另一边为空， 此时递归深度为n, 时间复杂度为

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
void Sort(int a[], int l, int r) {
    if (l >= r) {
        return;
    }
    int p = a[(l + r) >> 1], i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while(a[i] < p);
        do j--; while(a[j] > p);
        if (i < j) swap(a[i], a[j]);
    }
    Sort(a, l, j), Sort(a, j + 1, r);
}

堆排序

堆这个数据结构的原理就不多赘述了， 主要如何以数组自建堆、以的空间复杂度实现堆排序。

首先我们将待排序的数组看作一个完全二叉树， 然后自底向上的将二叉树调整为堆。

过程如下：

  • 首先将i的两个子树调整为堆
  • 此时将i下滤， i所在的二叉树即变成了堆。
  • 递归的终止条件为， 当结点i没有子树时， 即可以返回。

而由于完全二叉树数组存储的特殊性， 我们只需要从后往前的遍历数组， 即可保证每个结点被遍历前其子树已被遍历。

经过n次遍历， 数组已经变成了一个堆。 接下来是堆排序的第二个关键点：从堆中取n次堆顶元素得到排序序列。

我们可以发现每次弹出堆顶元素， 堆的大小减一， 即所需的数组大小减一。

参考堆实现中的删除顶点元素操作：将堆顶与最后一个元素交换， 此时堆顶的两个子树都是堆， 只需要将堆顶再次下滤， 即可完成对堆的调整；而原来的堆顶元素显然就可以保存在原堆的最后一个元素那里。

时间复杂度

每次下滤操作的时间复杂度为， 在调整原原数组及从堆中删除堆顶元素过程中， 总共需要差不多2n次下滤， 因此时间复杂度为

空间复杂度

由于我们始终是在对数组进行操作， 并没有使用到其它的额外空间。 因此空间复杂度为.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define Left(i) 2 * i + 1
void down(int a[], int i, int n) {
    int t = a[i];
    for (int son = Left(i); son <= n; son = Left(i)) {
        if (son != n && a[son + 1] > a[son]) son ++;
        if (t > a[son]) break;
        else a[i] = a[son], i = son;
    }
    a[i] = t;
}

void Sort(int a[], int n) {
    for (int i = n - 1; i >= 0; i --) down(a, i, n-1);
    for (int i = n-1; i > 0; i --) swap(a[0], a[i]), down(a, 0, i-1);
}
-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道