数据结构与算法--聊聊那些常见的排序算法

589 阅读26分钟

前言

  在开发中会经常用到排序,经常用到排序比如:冒泡排序,选择排序,直接插入排序等。

那什么是排序呢?这个其实都很熟悉了,其实排序还分为内排序外排序

内排序:在排序整个过程中,待排序的所有记录全部被放置在内存中

外排序:由于排序的记录个数太多,不能同时放置在内存,整个排序过程需要在内外存 之间多次交换数据才能进⾏。

常用的是内排序。接下来聊聊常见的排序算法。 在排序的过程过程中进行比较,然后交换是不可避免的。

所以可以先设计一个公共的交换函数,利用哨兵思想来设计一次数据结构,第0个位置不做数据存储,作为哨兵或者临时遍历使用,具体代码如下:

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

// 排序算法数据结构设计
#define MAXSIZE 10000
typedef struct
{
    // 用于存储要排序数组,r[0]用作哨兵或临时变量
    int r[MAXSIZE+1];
    // 用于记录顺序表的长度
    int length;
}SqList;


// 常用交换函数
// 交换L中数组r的下标为i和j的值
void swap(SqList *L,int i,int j)
{
    int temp = L->r[i];
    L->r[i]  = L->r[j];
    L->r[j]  = temp;
}

// 打印
void print(SqList L)
{
    int i;
    for(i=1;i<L.length;i++)
        printf("%d,",L.r[i]);
    printf("%d",L.r[i]);
    printf("\n");
}

1. 冒泡排序

冒泡排序:是一种交换排序,两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

在冒泡排序的实现时,可能会写成下面的形式:

// 冒泡排序-(冒泡排序初级版本)
void BubbleSort0(SqList *L){
   
    int i,j;
    for (i = 1; i < L->length; i++) {
        for (j = i+1; j <= L->length; j++) {
            if(L->r[i] > L->r[j])
                swap(L, i, j);
        }
    }
    
}

其实上面的代码严格的来说并不是冒泡排序,是对顺序表L进行交换排序,因为并不满足两两比较,所以对其进行改进,如下:

// 冒泡排序-对顺序表L作冒泡排序(正宗冒泡排序算法)
void BubbleSort(SqList *L){
    int i,j;
    for (i = 1; i < L->length; i++) {
        // ✅ j是从后面往前循环
        for (j = L->length-1; j >= i; j--) {
            
            // 若前者大于后者(注意与上一个算法区别所在)
            if(L->r[j]>L->r[j+1])
                //交换L->r[j]与L->r[j+1]的值;
                swap(L, j, j+1);
        }
    }
}

其实,还可以对冒泡排序进行优化,如果这个数据交换一次时,是有序的,那么后面的比较是重复无意义的。我们可以用一个值来标记是否有序。

// 冒泡排序-对顺序表L冒泡排序进行优化
void BubbleSort2(SqList *L){
    int i,j;
    // flag用作标记
    Status flag = TRUE;
    
    // i从[1,L->length) 遍历;
    // 如果flag为False退出循环. 表示已经出现过一次j从L->Length-1 到 i的过程,都没有交换的状态;
    for (i = 1; i < L->length && flag; i++) {
        
        // flag 每次都初始化为FALSE
        flag = FALSE;
        for (j = L->length-1; j>=i; j--) {
            
            if(L->r[j] > L->r[j+1]){
            //交换L->r[j]和L->r[j+1]值;
            swap(L, j, j+1);
            //如果有任何数据的交换动作,则将flag改为true;
            flag=TRUE;
            }
        }
    }
}

2. 简单选择排序

简单排序算法:就是通过n-i次关键词比较,从n - i +个记录中找到关键字最小的记录,并和第i(1<i<n)个记录进行交换。

如上图,先从下标(1-9)中找到最小记录,i=1, min=2,然后和第一个记录交换,得到如下:

然后,i=2, min = 9,和第二个记录交换:

依次类推,进行比较,最终完成排序。

代码实现:

// 选择排序--对顺序表L进行简单选择排序
void SelectSort(SqList *L){
    
    int i,j,min;

    for (i = 1; i < L->length; i++) {
        //✅ 1.将当前下标假设为最小值的下标
        min = i;
        //✅ 2.循环比较i之后的所有数据
        for (j = i+1; j <= L->length; j++) {
            //✅ 3.如果有小于当前最小值的关键字,将此关键字的下标赋值给min
            if (L->r[min] > L->r[j]) {
                min = j;
            }
        }
        
        //✅ 4.如果min不等于i,说明找到了最小值,则交换2个位置下的关键字
        if(i!=min)
            swap(L, i, min);
    }
}

3. 直接插入排序

直接插入排序:是将一个记录插入到已经排好序的有序表中,从而得到一个新的记录数增加1的有序表

如上图:

  1. 循环将i从第二个元素到最后一个元素作为待排序元素
  2. 判断当前待排序元素是否小于其前一个元素(i-1),小于,则参与插入排序
  3. 使用临时遍历变量temp,存储待排序元素,(在本次循环中temp = 3
  4. 循环遍历,找到第二个元素之前,能插入的位置,判断依据是从i-1到0这个空间,满足L->r[j] > temp, 则将L->r[j+1] = L->r[j]
  5. 找到元素5 > temp, 需要把5往前⾯面移动,覆盖元素3

6. 此时r[0] 不大于temp 则j层循环结束. 目前 j = 0 7. 此时需要把 3覆盖到j=1的位置,但是由于j 退出循环时等于0, 所以是r[j+1] = temp

最终完成本次循环,如下:

然后依次i++,参照上面的步骤,最终完成排序。具体实现如下:

// 直接插入排序算法
void InsertSort(SqList *L){
    int i,j;
    //L->r[0] 哨兵 可以把temp改为L->r[0]
    int temp=0;
    
    //假设排序的序列集是{0,5,4,3,6,2};
    //i从2开始的意思是我们假设5已经放好了. 后面的牌(4,3,6,2)是插入到它的左侧或者右侧
    for(i=2;i<=L->length;i++)
    {
        //需将L->r[i]插入有序子表
        if (L->r[i]<L->r[i-1])
        {
            //设置哨兵 可以把temp改为L->r[0]
            temp = L->r[i];
            for(j=i-1;L->r[j]>temp;j--)
                    //记录后移
                    L->r[j+1]=L->r[j];
            
            //插入到正确位置 可以把temp改为L->r[0]
            L->r[j+1]=temp;
        }
    }
}

空间复杂度: O(1)

时间复杂度: O(n2)

4. 希尔排序

希尔排序思想:在插入排序之前,将整个序列调整为基本有序,然后再对全体序列进行一次直接插入排序。

那么怎么将序列调整为基本有序呢? 希尔排序是把记录按照下标的一定增量分组,对每组直接使用插入排序, ;随着增量逐渐减少,每组包含的关键字越来越多,当增量减为1时,整个序列被分为1组,算法终止。

假设,有下面的一组序列,按照希尔排序的原理,对其进行分组:

初始化增量为increment = Length / 2 = 5,每组对应不同的颜色,即分为{8,3},{9,5},{1,4},{7,6},{2,0}五组,然后对每组进行插入排序,那么此时3、5、6、0,这些小元素会被调整到前面。

然后缩小增量(第一次循环增量为5),increment = increment / 2= 5/2 = 2,增量为2,即数组被分为两组:{3,1,0,9,7} {5,6,8,4,2}

然后对这2个序列进行直接插⼊排序,结果为:{0,1,3,7,9} {2,4,5,6,8},最终结果如下:

然后缩小增量(第二次循环增量为2),increment = increment / 2= 2/2 = 1,增量为1,即数组被分为一组,对这个序列直接进行插入排序如下,最终完成排序。

思路(伪代码):

1. 初始化增量为整个序列的长度
2. 开始循环,对序列根据增量进行分组,每组进行插入排序,当增量大于1时结束循环
3. 增量序列 = 增量序列/3 + 1
4. 循环每个分组,判断分组中,是否需要交换,需要则按照插入排序交换对应位置的元素。
// 希尔排序
void shellSort(SqList *L){
    int i,j;
    // ✅ 初始化增量为整个序列的长度
    int increment = L->length;
    
    //0,9,1,5,8,3,7,4,6,2
    // ✅ 开始循环,当increment 为1时,表示希尔排序结束
    do{
        // ✅ 增量序列
        increment = increment/3+1;
        // ✅ i的待插入序列数据 [increment+1 , length]
        for (i = increment+1; i <= L->length; i++) {
            // 如果r[i] 小于它的序列组元素则进行插入排序,例如3和9. 3比9小,所以需要将3与9的位置交换
            // ✅ 判断,然后进行插入排序
            if (L->r[i] < L->r[i-increment]) {
                // 将需要插入的L->r[i]暂时存储在L->r[0].和插入排序的temp 是一个概念;
                L->r[0] = L->r[i];
                // 记录后移
                for (j = i-increment; j > 0 && L->r[0]<L->r[j]; j-=increment) {
                    L->r[j+increment] = L->r[j];
                }
                
                // 将L->r[0]插入到L->r[j+increment]的位置上;
                L->r[j+increment] = L->r[0];
            }
        }
    }while (increment > 1);
}

5. 堆排序

是具有一下性质的完全二叉树

  • 每个结点的值都大于或者等于其左右孩子结点的值,称为大顶堆
  • 每个结点的值都小于或者等于其左右孩子结点的值,称为小顶堆

如果按照层寻遍历的方式给结点从1开始编号,则结点之间满足以下关系:

堆排序就是利用堆(假设选择大顶堆)进行排序的算法,其基本思想如下:

  • 将待排序的序列构成一个大顶堆,此时,整个序列最大值就的堆顶的根节点,将其有堆数组的末尾元素交换,此时末尾元素为最大
  • 然后将剩余的n-1个序列重新构成一个堆,这样就会得到n个元素的次大值, 如此重复执行,就能得到⼀个有序列

接下来以序列{4,6,8,5,9}为例,详细的分析一下:

  1. 构造初始堆,将给定⽆序列构造成一个⼤顶堆(一般升序采⽤大顶堆,降序采用小顶堆) A. 给的无序序列结构如下:

  B. 从最后一个非叶子结点开始(叶子结点不用调整),第一个非叶子结点2

   结点2上数据 6 大于左子树结点数据5,小于其右子树结点数据9,所以要将9 和 6 互换。

  C. 找到第二个非叶子结点4,从[4,9,8]中找到最大的进行交换。

  D. 因为49的交换,导致【4,5,6】结构混乱,不符合大顶堆条件,需要继续调整,交换46。至此,经过上面的调整,我们将无序列 调整成⼀个⼤顶堆结构。

  1. 将堆顶元素和末尾元素进行交换,使末尾元素最大,然后继续调整堆,再将堆顶元素与末尾元素交换,得到第⼆大元素。如此反复进行交换、重建、交换,

    A. 将堆顶元素9和末尾元素4交换,此时末尾元素9,将不参与后续排序

    B. 重新调整结构,使其继续满⾜堆定义[ 4, 6 , 8]中找到最大的, 48进行交换. 经过调整得到大顶堆

    C. 再将堆顶元素8与末尾元素5进行交换,得到第⼆大元素8,然后继续上面的步骤进行调整交换,最终得到如下的有序序列

堆排序思路

  • 将无需序列构建成一个堆,根据升降序,选择构建大顶堆或者小顶堆(升序,大顶堆,降序,小顶堆)
  • 将堆顶元素与末尾元素交换,将最⼤元素或者最小元素“沉”到数组末端
  • 重新调整使之满足堆定义,继续交换堆顶和当前末尾元素;反复,直到序列有序

在构建大顶堆时,从最后一个非叶子开始,由于堆是一个完全二叉树,其结点按层序编号,对任⼀结点i (1 ≤ i ≤ n)有:

  • 如果 i=1,则结点 i 是⼆叉树的根. 无双亲结点。 如果i > 1,则其双亲是结点 [ i / 2 ]
  • 如果 2i > n ,则结点 i ⽆左孩子 (结点i 为叶⼦结点), 否则左孩⼦子是结点 2i
  • 如果 2i + 1 > n ,则结点 i ⽆右孩子; 否则其右孩⼦子是结点 2i+1

接下来实现一下大顶堆调整函数:

// 大顶堆调整函数
void HeapAjust(SqList *L,int s,int m){
    
    int temp,j;
    //1. 将L->r[s] 存储到temp ,方便后面的交换过程;
    temp = L->r[s];
    
    //2. 
    //因为这是颗完全二叉树,而s也是非叶子根结点. 所以它的左孩子一定是2*s,而右孩子则是2s+1
    for (j = 2 * s; j <=m; j*=2) {
        
        //3. ✅判断j是否是最后一个结点, 并且找到左右孩子中最大的结点;
        //如果左孩子小于右孩子,那么j++; 否则不自增1. 因为它本身就比右孩子大;
        if(j < m && L->r[j] < L->r[j+1])
            ++j;
        
        //4. ✅比较当前的temp 是不是比较左右孩子大;如果大则表示我们已经构建成大顶堆了,跳出循环
        if(temp >= L->r[j]) {
            break;
        }
        //5. ✅小于,则将L->[j] 的值赋值给非叶子根结点
        L->r[s] = L->r[j];
        //6. ✅将s指向j; 因为此时L.r[4] = 60, L.r[8]=60. 那我们需要记录这8的索引信息.等退出循环时,能够把temp值30 覆盖到L.r[8] = 30. 这样才实现了30与60的交换;
        s = j;
    }
    
    //7. ✅将L->r[s] = temp. 其实就是把L.r[8] = L.r[4] 进行交换;
    L->r[s] = temp;
}

堆排序实现:

// 堆排序--对顺序表进行堆排序
void HeapSort(SqList *L){
    int i;
   
    //✅ 1.将现在待排序的序列构建成一个大顶堆;
    //将L构建成一个大顶堆;
    //i从length/2.因为在对大顶堆的调整其实是对非叶子的根结点调整.
    for(i=L->length/2; i>0;i--){
        HeapAjust(L, i, L->length);
    }
    
    
    //✅ 2.逐步将每个最大的值根结点与末尾元素进行交换,并且再调整成大顶堆
    for(i = L->length; i > 1; i--){
        
        //✅ 将堆顶记录与当前未经排序子序列的最后一个记录进行交换;
        swap(L, 1, i);
        //✅ 将L->r[1...i-1]重新调整成大顶堆;
        HeapAjust(L, 1, i-1);
    }
}

堆排序的时间复杂度为:O(nlogn)

堆排序是就地排序,空间复杂度为常数:O(1)

6. 归并排序

归并排序是利用归并的思想实现排序,它的原理是假设初始序列含有n个记录,则可以看成n个有序的子序列,每个子序列的长度为1,然后两两合并,得 到[n/2]个长度为21的有序子序列。再两两归并,如此重复,直到得到一个长度为n 的有序列为此,这种排序方法称为2路路归并排序

如下图,将序列依次拆分为长度为1子序列,然后在两两归并,得到四个长度为2的有序序列,然后再两两归并,得到2个长度为4的有序序列,再归并为一个有序序列

接下来分析一下归并排序的执行流程:

假设对下面的一个无序序列进行归并排序

首先low = 1,hight = 9,求得mid = (low + hight)/2 = 5,然后将原序列拆分为下面两个序列,

然后对[low-mid][mid+1-hight]的两个序列递归拆分,最终拆分为长度为1的子序列。 然后开始两两合并。

我们来着重分析一下最后两个子序列的合并:

  • 第一次循环,SR[i] = SR[1] = 10SR[j] = SR[6] = 20 进⾏比较。

    SR[i] < SR[j],那么将 TR[k] = SR[i];此时 i++, k++,

    那么如果是 SR[i] > SR[j]的话,将 SR[j] 存储到TR[k] 这个数组。就是j++, k++ 第一次循环结束:i = 2,m = 5,j = 6,n = 9

  • 第二次循环,SR[i] = SR[2] = 30SR[j] = SR[6] = 20 进⾏比较。

    SR[i] > SR[j],那么将 TR[k] = SR[j];此时 j++, k++,

    第二次循环结束:i = 2,m = 5,j = 7,n = 9

  • 第三次循环,SR[i] = SR[2] = 30SR[j] = SR[7] = 40 进⾏比较。

    SR[i] < SR[j],那么将 TR[k] = SR[i];此时 i++, k++,

    第三次循环结束:i = 3,m = 5,j = 7,n = 9

  • 第四次循环,SR[i] = SR[3] = 50SR[j] = SR[7] = 40 进⾏比较。

    SR[i] > SR[j],那么将 TR[k] = SR[j];此时 j++, k++,

    第四次循环结束:i = 3,m = 5,j = 8,n = 9

  • 第五次循环,SR[i] = SR[3] = 50SR[j] = SR[8] = 60 进⾏比较。

    SR[i] < SR[j],那么将 TR[k] = SR[i];此时 i++, k++,

    第五次循环结束:i = 4,m = 5,j = 8,n = 9

  • 第六次循环,SR[i] = SR[4] = 70SR[j] = SR[8] = 60 进⾏比较。

    SR[i] > SR[j],那么将 TR[k] = SR[j];此时 j++, k++,

    第六次循环结束:i = 4,m = 5,j = 9,n = 9

  • 第七次循环,SR[i] = SR[4] = 70SR[j] = SR[9] = 80 进⾏比较。

    SR[i] < SR[j],那么将 TR[k] = SR[i];此时 i++, k++,

    第七次循环结束:i = 5,m = 5,j = 9,n = 9

  • 第八次循环,SR[i] = SR[5] = 90SR[j] = SR[9] = 80 进⾏比较。

    SR[i] > SR[j],那么将 TR[k] = SR[j];此时 j++, k++,

    第八次循环结束:i = 5,m = 5,j = 10,n = 9

第八次循环结束后,j>n, 不满足循环条件,结束循环。

然后判断,将两个子序列中剩余的元素拼到TR后面,最终合并为有序序列。

代码实现如下:

//3 ✅将有序的SR[i..mid]和SR[mid+1..n]归并为有序的TR[i..n]
void Merge(int SR[],int TR[],int i,int m,int n)
{
    int j,k,l;
    //1.✅将SR中记录由小到大地并入TR
    for(j=m+1,k=i;i<=m && j<=n;k++)
    {
        if (SR[i]<SR[j])
            TR[k]=SR[i++];
        else
            TR[k]=SR[j++];
    }
    
    //2.✅将剩余的SR[i..mid]复制到TR
    if(i<=m)
    {
        for(l=0;l<=m-i;l++)
            TR[k+l]=SR[i+l];
    }
    
    //3.✅将剩余的SR[j..mid]复制到TR
    if(j<=n)
    {
        for(l=0;l<=n-j;l++)
            TR[k+l]=SR[j+l];
    }
}


//2. ✅将SR[s...t] 归并排序为 TR1[s...t];
void MSort(int SR[],int TR1[],int low, int hight){
    int mid;
    int TR2[MAXSIZE+1];
    
    if(low == hight)
        TR1[low] = SR[low];
    else{
        //1.将SR[low...hight] 平分成 SR[low...mid] 和 SR[mid+1,hight];
        mid = (low + hight)/2;
        //2. 递归将SR[low,mid]归并为有序的TR2[low,mid];
        MSort(SR, TR2, low, mid);
        //3. 递归将SR[mid+1,hight]归并为有序的TR2[mid+1,hight];
        MSort(SR, TR2, mid+1, hight);
        //4. 将TR2[low,mid] 与 TR2[mid+1,hight], 归并到TR1[low,hight]中
        Merge(TR2, TR1, low, mid, hight);
    }
}

//1. ✅对顺序表L进行归并排序
void MergeSort(SqList *L){
   
    MSort(L->r,L->r,1,L->length);
}

归并排序的非递归实现:

//归并排序(非递归)-->对顺序表L进行非递归排序
//对SR数组中相邻长度为s的子序列进行两两归并到TR[]数组中;
void MergePass(int SR[],int TR[],int s,int length){
  
    int i = 1;
    int j;
    
    //1. ✅合并数组
    //s=1 循环结束位置:8 (9-2*1+1=8)
    //s=2 循环结束位置:6 (9-2*2+1=6)
    //s=4 循环结束位置:2 (9-2*4+1=2)
    //s=8 循环结束位置:-6(9-2*8+1=-6) s = 8时,不会进入到循环;
    while (i<= length-2*s+1) {
        //两两归并(合并相邻的2段数据)
        Merge(SR, TR, i, i+s-1, i+2*s-1);
        i = i+2*s;
        
        /*
         s = 1,i = 1,Merge(SR,TR,1,1,2);
         s = 1,i = 3,Merge(SR,TR,3,3,4);
         s = 1,i = 5,Merge(SR,TR,5,5,6);
         s = 1,i = 7,Merge(SR,TR,7,7,8);
         s = 1,i = 9,退出循环;
         */
        
        /*
         s = 2,i = 1,Merge(SR,TR,1,2,4);
         s = 2,i = 5,Merge(SR,TR,5,6,8);
         s = 2,i = 9,退出循环;
         */
        
        /*
         s = 4,i = 1,Merge(SR,TR,1,4,8);
         s = 4,i = 9,退出循环;
         */
    }
    
    //2. ✅如果i<length-s+1,表示有2个长度不等的子序列. 其中一个长度为length,另一个小于length
    // 1 < (9-8+1)(2)
    //s = 8时, 1 < (9-8+1)
    if(i < length-s+1){
        //Merge(SR,TR,1,8,9)
        Merge(SR, TR, i, i+s-1, length);
    }else{
        //③只剩下一个子序列;
        for (j = i; j <=length; j++) {
            TR[j] = SR[j];
        }
    }
}

void MergeSort2(SqList *L){
    int *TR = (int *)malloc(sizeof(int) * L->length);
    int k = 1;
    //k的拆分变换是 1,2,4,8;
    while (k < L->length) {
        //将SR数组按照s=2的长度进行拆分合并,结果存储到TR数组中;
        //注意:此时经过第一轮的归并排序的结果是存储到TR数组了;
        MergePass(L->r, TR, k, L->length);
        k = 2*k;
        //将刚刚归并排序后的TR数组,按照s = 2k的长度进行拆分合并. 结果存储到L->r数组中;
        //注意:因为上一轮的排序的结果是存储到TR数组,所以这次排序的数据应该是再次对TR数组排序;
        MergePass(TR, L->r, k, L->length);
        k = 2*k;
        
    }
}

7. 快速排序

快速排序的基本思想:通过一趟排序将待排序记录分割为独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可以分别对两部分记录继续进行排序,以达到整个排序有序的目的。

快速排序思路

  • 判断low是否小于hight
  • 求得枢轴,并将数组枢轴左边的关键字都比枢轴对应的关键字小,右边的关键字都比枢轴对应的关键字大
  • 将数组一份为二,分别对低子表和高子表排序

那么如何找一个枢轴,怎么将枢轴变量放在合适的位置,并且使得它的左侧关键字均⽐它⼩, 右侧关键字均⽐比它大。

接下来,我们一下面的数组为例,分析一下快速排序的执行流程。

首先,选择子表中第1个记录作为枢轴变量,pivotkey = 50

然后,从表的两端往中间扫描,开始循环,循环判断,

  • 从高位开始,找到比pivokey更小的值的下标位置,即:循环判断是否满足low<high并且r[high] >= pivotkey,满足,则递减high,不满足条件,则跳出循环
  • 然后交换比枢轴值小的记录到低端
  • 从低位开始,找到比pivokey更大的值的下标位置。即:循环判断是否满足low<high并且r[low] <= pivotkey,满足,则递增low,不满足条件,则跳出循环
  • 然后交换比枢轴值大的记录到高端

对上图的序列第一轮循环,判断条件low < high

  1. 首先比较 L->r[high] >= pivotkey && low < high,此时 low=1,high=9,L->r[9] < 50 , 则循环退出。然后交换,将比枢轴记录小的记录交换到低端位置上,得到下图:

  1. 循环判断low < high && L->r[low] <= pivotkey,此时low=1,high=9,L->r[1] < 50,则low++,low=2

    然后继续判断是否满足low < high && L->r[low] <= pivotkey,此时low=2,high=9,L->r[2] < 50,则low++,low=3

    然后继续判断是否满足low < high && L->r[low] <= pivotkey,此时low=3,high=9,L->r[3] > 50,不满足条件,跳出循环,然后将比枢轴记录大的记录交换到高端位置上,得到下图:

至此第一轮循环结束,low = 3, high = 9,满足循环条件,进入第二轮循环。

对上图的序列第二轮循环,判断条件low < high(此时low = 3, high = 9):

  1. 首先比较 L->r[high] >= pivotkey && low < high,此时 low=3,high=9,L->r[9] > 50 ,满足条件,high--,得到high=8

    继续比较 L->r[high] >= pivotkey && low < high,此时 low=3,high=8,L->r[8]=60 > 50 ,满足条件,high--,得到high=7

    继续比较 L->r[high] >= pivotkey && low < high,此时 low=3,high=7,L->r[7]=80 > 50 ,满足条件,high--,得到high=6

    继续比较 L->r[high] >= pivotkey && low < high,此时 low=3,high=6,L->r[6]=40 < 50 ,不满足条件,跳出循环。然后交换lowhigh的值,将比枢轴记录小的记录交换到低端位置上,得到下图:

  1. 循环判断low < high && L->r[low] <= pivotkey,此时low=3,high=6,L->r[3] < 50,则low++,low=4

    循环判断low < high && L->r[low] <= pivotkey,此时low=4,high=6,L->r[4] < 50,则low++,low=5

    循环判断low < high && L->r[low] <= pivotkey,此时low=5,high=6,L->r[5] > 50,不满足条件,跳出循环,然后交换lowhigh的值,将比枢轴记录大的记录交换到高端位置上,得到下图:

至此第二轮循环结束,low = 5, high = 6,满足循环条件,进入第三轮循环。

对上图的序列第三轮循环,判断条件low < high(此时low = 5, high = 6):

首先比较 L->r[high] >= pivotkey && low < high,此时 low=5,high=6,L->r[5] < 50 ,满足条件,high--,得到high=5

此时low == high 退出循环! 表示这一次从两端交替向中间的扫描已经全部完成了。此时返回low=5

接下来按照上面的逻辑,对序列的【1,5-1】和【5+1,9】子序列进行操作。最终得到一个有序的序列。

//✅3. 交换顺序表L中子表的记录,使枢轴记录到位,并返回其所在位置
//此时在它之前(后)的记录均不大(小)于它
int Partition(SqList *L,int low,int high){
    int pivotkey;
    //pivokey 保存子表中第1个记录作为枢轴记录;
    pivotkey = L->r[low];
    //1. 从表的两端交替地向中间扫描;
    while (low < high) {
        
        //2. 比较,从高位开始,找到比pivokey更小的值的下标位置;
        while (low < high &&  L->r[high] >= pivotkey) {
            high--;
        }
        //3. 将比枢轴值小的记录交换到低端;
        swap(L, low, high);
        //4. 比较,从低位开始,找到比pivokey更大的值的下标位置;
        while (low < high && L->r[low] <= pivotkey) {
            low++;
        }
        //5. 将比枢轴值大的记录交换到高端;
        swap(L, low, high);
        
    }
    
    //返回枢轴pivokey 所在位置;
    return low;
}

//✅2. 对顺序表L的子序列L->r[low,high]做快速排序;
void QSort(SqList *L,int low,int high){
    int pivot;
    
    if(low < high){
        //将L->r[low,high]一分为二,算出中枢轴值 pivot;
        pivot = Partition(L, low, high);
        printf("pivot = %d L->r[%d] = %d\n",pivot,pivot,L->r[pivot]);
        //对低子表递归排序;
        QSort(L, low, pivot-1);
        //对高子表递归排序
        QSort(L, pivot+1, high);
    }
    
}

//✅ 1. 调用快速排序(为了保证一致的调用风格)
void QucikSort(SqList *L){
    QSort(L, 1, L->length);
}

时间复杂度:最好情况为O(nlogn),最坏情况为O(n2)

空间复杂度取决于递归造成的栈空间,最好情况为O(logn),最坏情况为O(n),平均情况下时间复杂度为O(logn)

上面的算法,在求解枢轴的时候,我们比较暴力,直接取第一个元素为枢轴,这样可能存在一些问题,比如第一个元素在当前序列中是最大或者最小时,交换后就会出现一些问题。

那么,我们可以对枢轴的求解进行优化,取当前序列的中间数为枢轴,尽量避免取到最大或者最小的情况。

在比较时,要频繁的交换高位和低位的值,我们可以对高低位进行覆盖,在最后一次(low = high)时,用枢轴进行赋值。

比如:

  1. ⽤高位highpivotkey 进⾏比较找到⽐枢轴小的记录. 交换到低端位置上

替换后为:

  1. ⽤低位lowpivotkey 进⾏比较找到⽐枢轴大的记录. 交换到高端位置上

替换后为:

3. 这样依次比较替换,最终得到:

然后替换L->r[low] = L->r[0],即:将低位的值替换为枢轴的值。

优化实现:

int Partition2(SqList *L,int low,int high){
   
    int pivotkey;
    
    // ✅ 1.优化选择枢轴
    //✅ 计算数组中间的元素的下标值;
    int m = low + (high - low)/2;
    //✅ 将数组中的L->r[low] 是整个序列中左中右3个关键字的中间值;
    //交换左端与右端的数据,保证左端较小;[9,1,5,8,3,7,4,6,2]
    if(L->r[low]>L->r[high])
        swap(L, low, high);
    //交换中间与右端的数据,保证中间较小; [2,1,5,8,3,7,4,6,9];
    if(L->r[m]>L->r[high])
        swap(L, high, m);
    //交换中间与左端,保证左端较小;[2,1,5,8,3,7,4,6,9]
    if(L->r[m]>L->r[low])
        swap(L, m, low);
    //交换后的序列:3,1,5,8,2,7,4,6,9
    //此时low = 3; 那么此时一定比选择 9,2更合适;
    
    
    // ✅ 2. 优化不必要的交换
    //pivokey 保存子表中第1个记录作为枢轴记录;
    pivotkey = L->r[low];
    //将枢轴关键字备份到L->r[0];
    L->r[0] = pivotkey;
    
    // ✅ 3. 从表的两端交替地向中间扫描;
    while (low < high) {
        //✅ 比较,从高位开始,找到比pivokey更小的值的下标位置;
        while (low < high &&  L->r[high] >= pivotkey)
            high--;
        
        //✅ 将比枢轴值小的记录交换到低端;
        //swap(L, low, high);
        //✅ 用替换的方式将比枢轴值小的记录替换到低端
        L->r[low] = L->r[high];
        
        //✅ 比较,从低位开始,找到比pivokey更大的值的下标位置;
        while (low < high && L->r[low] <= pivotkey)
            low++;
        
        //✅ 将比枢轴值大的记录交换到高端;
        //swap(L, low, high);
        //✅ 替换的方式将比枢轴值大的记录替换到高端
        L->r[high] = L->r[low];
    }
    //将枢轴数值替换会L->r[low]
    L->r[low] = L->r[0];
    
    //返回枢轴pivokey 所在位置;
    return low;
}

//✅2. 对顺序表L的子序列L->r[low,high]做快速排序;
#define MAX_LENGTH_INSERT_SORT 7 //数组长度的阀值
void QSort2(SqList *L,int low,int high){
    int pivot;

    //✅ 当high-low 大于常数阀值是用快速排序;
    if((high-low)>MAX_LENGTH_INSERT_SORT){
        //将L->r[low,high]一分为二,算出中枢轴值 pivot;
        pivot = Partition(L, low, high);
        printf("pivot = %d L->r[%d] = %d\n",pivot,pivot,L->r[pivot]);
        //对低子表递归排序;
        QSort(L, low, pivot-1);
        //对高子表递归排序
        QSort(L, pivot+1, high);
    }else{
        // ✅当high-low小于常数阀值是用直接插入排序
    }
}

//✅1. 快速排序优化
void QuickSort2(SqList *L)
{
    QSort2(L,1,L->length);
}

排序总结: