数据结构与算法学习笔记（9）——排序

发表于   |   分类于   |  

许久未更新，继续将数据结构的知识整理一遍。

本文仅供个人记录和复习，不用于其他用途

O(N²)复杂度

有冒泡排序、选择排序、插入排序三种。

冒泡排序

  • 设i=0，那么比较i和i+1的大小，大的放后面
  • ++i，重复上述过程
  • 当完成一轮排序后，设i=1，进行第二轮排序
  • 若数列长度为n，当进行完n-1次排序后，所得数列便是由小到大排布

选择排序

  • 设数列长度为n，从0~n-1中选出最小的数，放到索引0处
  • 从1~n-1中选出最小的数，放到索引1处
  • 重复上述过程，直到数列结束

插入排序

  • 设i=0，比较i与i+1，若i小于i+1，那么二者交换位置
  • ++i，将i+1与0~i进行比较，当某个数小于i+1时，将i+1插在它的后面，否则将i+1放在第一位
  • 重复上述过程，直到数列结束

O(N*logN)复杂度

有归并排序、快速排序、堆排序、希尔排序四种

归并排序

  • 将数列划分为长度为1的多个小块
  • 相邻的两个块进行合并，合并时按照由小到大的顺序
  • 当前块的长度都为2，合并相邻两个块，按照由小到大排序
  • 重复上述过程，直到剩下一个块

快速排序

  • 将数列最左边的数作为基准数flag，i和j的初始值为数列左右两边的位置索引
  • —j，从右往左进行查找，直到找到一个小于基准数的数
  • ++i，从左往右进行查找，直到找到一个大于基准数的数
  • 交换a[i]和a[j]的位置
  • 交换a[i]和a[left]，并将a[i]作为新的基准数
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
void quicksort(int left, int right)
{
    int i, j, t, flag;
    if(left > right)  //如果左边值大于右边值，证明排序结束
        return;
    i = left;
    j = right;
    flag = a[left];  //flag即为基准数
    while(i != j)  //该循环一直到i和j重合为止，使得结束循环时，基准数大于等于左边小于等于右边
    {
        while(a[j] >= flag && i < j)  //先从右往左找，找到一个比基准数小的数停下，同时也要保证i<j
            j--;
        while(a[i] <= flag && i < j)  //从左往右找到一个比基准数大的数停下
            i++;
        if(i < j)  //一定要保证i<j，也就是没有重合，重合就应该退出，否则没有意义
        {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    a[left] = a[i];  //将基准数调整位置
    a[i] = flag;
    quicksort(left, right - 1);  //将基准数左边的数列排序
    quicksort(left + 1, right);  //将基准数右边的数列排序
}

堆排序

堆排序首先要知道如何生成最小堆，具体的我会在二叉树一章讲解。

  • 将数列调整为最小堆
  • 将顶部结点删除，并记录到数组中
  • 将末尾结点移至顶部，并调整为最小堆
  • 重复上述过程，直至堆为空
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
void swap(int x, int y)  //交换x和y的数据
{
    int t;
    t = h[x];
    h[x] = h[y];
    h[y] = t;
    return;
}
void siftdown(int i)  //传入一个需要向下调整的节点编号i
{
    int t, flag = 0;  //flag标记是否要继续向下调整，t主要用来记录当前需要调整的编号
    while(i * 2 <= n && flag == 0)  //i*2是i的左子节点，当至少有左子节点并且还需要调整时，执行循环
    {
        if(h[i] < h[i * 2])  //这里是调整为最大堆
            t = i * 2;
        else
            t = i;
        if(i * 2 + 1 <= n)  //如果存在右子节点，将之与t比较，得出三个节点中的最大值
        {
            if(h[t] < h[i * 2 + 1])
                t = i * 2 + 1;
        }
        if(t != i)  //如果最大的节点不是自己，那么将i与t换位，也就是向下调整
        {
            swap(t, i);  //交换最大节点和i的数据
            i = t;  //将i改为最大节点，进入堆的下一层
        }
        else
            flag = 1;  //如果最大的节点是i，证明往下的都比i小，不需要调整
    }
    return;
}
void creat()  //初始化堆
{
    int i;
    for(i = n / 2; i >= 1; i--)  //从第n-1层的最右边开始处理堆，使其符合堆的规则
        siftdown(i);
    return;
}
void heapsort()  //堆排序
{
    while(n > 1)  //由于是从小到大排序，那么先将堆顶与n交换，将其出堆，然后调整堆顶使其符合规则，一直循环到只剩下堆顶，也就是最小的数。每次交换都能保证最后的数n能够是当前堆中最大的数
    {
        swap(1, n);
        n--;
        siftdown(1);
    }
    return;
}

希尔排序

进行插入排序时，每次都是和前面的一个数进行比较，步长为1。希尔排序的步长是不断变化的，并且步长都在逐渐减小，到1时便结束。
简单来说，希尔排序将数列分为若干个子列，然后对这些子列分别进行插入排序，随后依次缩小步长进行排序。一般来说，希尔排序的步长每次都是取数列长度的一半，当然也有其他更高效的办法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void shell(int a[], int n)  
{  
    int i, j, gap;  
  
    for (gap = n / 2; gap > 0; gap /= 2) //步长  
        for (i = 0; i < gap; i++)        //直接插入排序  
        {  
            for (j = i + gap; j < n; j += gap)   
                if (a[j] < a[j - gap])  
                {  
                    int temp = a[j];  
                    int k = j - gap;  
                    while (k >= 0 && a[k] > temp)  
                    {  
                        a[k + gap] = a[k];  
                        k -= gap;  
                    }  
                    a[k + gap] = temp;  
                }  
        }  
}

O(N)复杂度

此类算法不在于进行数之间的比较，而是运用巧妙的思想，并且算法思路都是建立在捅排序的基础上。

计数排序

  • 建立一个数组，数组长度即为数列中的最大值加一
  • 对数列进行遍历，设当前的数值为i，那么++a[i]
  • 遍历结束后，数组中就记录了数列中各个数的出现次数

基数排序

  • 若所排序的数为十进制（所有数的位数应该相同，不同的在前面补零），例如101、011、014等
  • 建立0~9等十个桶
  • 按照数值的个位数，将所有的数放进对应的桶中
  • 按顺序倒出所有的数，组成新的数列
  • 按照数值的十位数，将所有的数放进对应的桶中
  • 按顺序倒出所有的数，组成新的数列
  • 重复上述过程，直到最大数值的每一位都遍历完成

如果最大数为3位数，总共有5个数，那么就需要进行3*5次操作，效率比与之前的算法要高很多。

总结

稳定的排序算法：冒泡排序、插入排序、归并排序、计数排序、基数排序
不稳定排序算法：选择排序、快速排序、希尔排序、堆排序

排序算法无优劣之分，看似快速的算法其实运用的环境比较少。一般来说，假如对时间要求不高，我们可以使用插入排序。如果要求了时间，那么便可以使用归并排序。

例题

几乎有序数组

问：已知一个几乎有序的数组，请问用什么方法排序比较好？（注：几乎有序是指当数组排序完毕时，每个元素移动的距离不超过k，而k相对于数组长度来说很小）

首先来看看简单的算法：冒泡排序、选择排序、插入排序。首先，冒泡排序和选择排序与数列的原始排列无关，而对于插入排序而言，原始序列越有序，所花费的时间越少。

至于速度更快的算法，其中归并排序与原始序列无关，其他的也不够稳定，所以我们必须要对算法稍作改进。那么，我便介绍一下改进的堆排序：

  • 取0~k-1，建立一个小根堆
  • 弹出栈顶并记录，随后加入下一个数k，调整为小根堆
  • 重复上述过程

显然，出栈顺序就是排列完毕的数组，由于题目说明了每个元素的移动距离不超过k。那么，如果按照从小到大来排列的话，最小数必在0~k-1中。如此一来，便能够更快得到排序好的数组。

判断重复数

问：判断数组中是否有重复的数，必须保证额外空间复杂度为O(1)。

哈希表可以在遍历数组的过程中，统计所有数出现的次数。不过既然要求了空间复杂度，那么就不能用哈希表了。这里我们还是使用堆排序，不过也得做一些修改，那就是将递归实现的堆排序转变为非递归实现的堆排序。

合并有序数组

问：将两个有序数组合并为一个数组，且第一个数组空间正好可以容纳两个数组的元素。

举个例子：
数组A：1 3 5
数组B：2 4 6

我们将A最大的数和B最大的数进行比较（显然数组A的大小为6），然后将数组B的6拷贝到A[5]。随后再将A最大的数和B最大的数进行比较，然后将数组A的5拷贝到A[4]。重复上述过程，直到数组A全部更新完毕，就会得到两个数组合并之后的结果。

这个方法的主要思想就是从后往前拷贝，这样就不用担心拷贝时替换了重要的数据。

荷兰国旗问题

问：对只包含0、1、2的数组进行排序，要求只能使用交换和原地排序，不能用计数排序。

其实这个问题与快速排序很像，我们只需要在数组的两边设置一个0区域和一个2区域，随后遍历整个数组，遇到1就跳到下个数，遇到0和2就放到两边对应的位置。

二维数组查找

问：给定一个排序完毕二维数组，查找数组中是否包含k。

二维数组展开后就是一个矩阵，我们从右上角开始找，如果当前数大于要找的数，那么向左移动一格；如果当前数小于要找到的数，那么向下移动一格。

最短排序数组

问：给定一个数组，查找数组中需要排列的最短子数组长度。

  • 从左到右遍历数组，记录当前数的最大值。当某个数小于最大值时，记录这个位置。
  • 从右往左遍历数组，记录当前数的最小值。当某个数大于最小值时，记录这个位置。

例如：现在有数列1、5、4、3、2、6、7。从左往右不断的更新最大值，那么4、3、2显然小于5，而6、7大于5，所以记录2的位置。从右往左不断的更新最小值，那么3、4、5显然大于2，而1小于2，所以记录5的位置。

那么5和2中间的5、4、3、2，就是需要排序的最短子数组长度。

最大差值

问：给定一个数组，排序完毕后，返回相邻两数的最大差值。

先找出数组的最小值min和最大值max，然后根据数组的元素个数n，将区间[min, max)分成n个桶，最大值额外放在一个桶中。分完之后，第一个桶中绝对有最小值，最后一个桶中只有最大值。

由于有n+1个桶，只有n的元素，那么必然会在中间出现空桶。事实上，空桶两边的数的差值是最大的，同一个桶中的差值绝对不会大于这个数，所以不用考虑同一个桶的相邻数，只用考虑桶间的相邻数。我们取每一个桶的最小值，减去上一个非空桶的最大值，记录其中的最大差值即可。