0
0

【C语言 - 数据结构】万字详解快速排序、归并排序

    排序是我们生活中经常会面对的问题。上一节我为大家介绍了几种相对简单的排序算法，如冒泡、插入、选择等排序，这几种排序算法的时间复杂度是o（N^2），这些排序算法在数据量比较少时，其计算的时间也不会显得很大，但数据量比较大，比如100万、1000万时，我们就要使用时间复杂度更优的算法，比如快排和归并排序，下面我就为大家详细介绍这两种先进的排序算法。


                                                你是我黄昏时买到一束花的快乐！

文章目录

  • 一、快速排序的概念
  • 二、快速排序的递归实现
  • 三、快速排序的非递归实现以及快排模板
  • 四、快排的优化
  • 五、归并排序的概念
  • 六、归并排序的递归实现
  • 七、归并排序的非递归实现以及归并排序的模板
  • 八、两种排序的复杂度对比
  • 总结
提示：以下是本篇文章正文内容，下面案例可供参考

一、快速排序的概念

1.1快排的定义

    快速排序简称快排，快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

1.2快排的动态图

1.3快速排序的几种版本介绍

    快排的基本思路

1、先找整个数组的key

2、找【begin， key-1】和【key + 1, end 】区间的key

3、再去重复递归左右区间，当区间只剩一个值或者不存在时就是最小规模的子问题。

1、hoare版本

2、挖坑法

挖坑法思路简介

第二个版本：挖坑法（PartSort）

右边找小，左边找大，右边先走

右边找到小与keyi的，然后停下来，右边的把值赋给

keyi这个位置，右边腾出一个空位

左边找大的然后赋值给这个空位

最后左右两个指针的相遇在一个空位，然后把keyi填进去

谁做keyi和谁先走不是固定的，

左边做keyi，右边先走

右边做keyi, 左边先走

3、前后指针法

前后指针法的思路简介：

    cur指针在前面找小，找到比key小的值就++prev指针，交换prev和cur位置的值

prev和cur的关系

1、cur还没遇到比key大的值时，prev紧跟着cur一前一后

2、cur遇到比key大的值后，prev和cur之间间隔着一段比key大的值的区间

二、快速排序的递归实现

2.1 hoare版本的递归实现

    有了前面的讲解，我们对于hoare版本的快速排序已经有了一定的了解了，我们现在实现其代码部分：（大家可以先理解我对hoare版本的定义再来看其实现代码，或者是结合起来理解）

int PartSort(int* a, int left, int right)
{
    int keyi = left;//key设置成最左边的数
    while (left < right)
    {
        //右边找小
        while (left < right && a[right] >= a[keyi])
            --right;
        //左边找大
        while (left < right && a[left] > a[keyi])//找大
            ++left;
        Swap(&a[left], &a[right]);
    }
    Swap(&a[keyi], &a[left]);
    return left;
}
void QuickSort(int* a, int begin, int end)
{
    //子区间相等只有一个值或者不存在那么就是递归结束的子问题
    if (begin >= end)
        return;
    int keyi = PartSort(a, begin, end);
    // [begin, keyi - 1]keyi[keyi + 1, end]
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}

贴一张图方便大家理解

2.2挖坑法的递归代码示例：

//挖坑法
int PartSort2(int* a, int left, int right)
{
    int key = a[left];
    //坑位
    int pit = left;
    while (left < right)
    {
        //右边先走,找小于key
        while (left < right && a[right] >= key )
        {
            --right;
        }
        a[pit] = a[right];
        pit = right;
        //左边走，找大于key
        while (left < right && a[left] <= key)
        {
            ++left;
        }
        a[pit] = a[left];
        pit = left;
    }
    a[pit] = key;
    return pit;
}
void QuickSort2(int* a, int begin, int end)
{
    //子区间相等只有一个值或者不存在那么就是递归结束的子问题
    if (begin >= end)
        return;
    int keyi = PartSort2(a, begin, end);
    // [begin, keyi - 1]keyi[keyi + 1, end]
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}

2.3前后指针法的递归代码示例

//前后指针法
int PartSort3(int* a, int left, int right)
{
    int keyi = left;//如果是a[left],则是局部变量，SWap后还是原来的值
    //left则是下标
    int prev = left, cur = left + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi] && a[++prev] != a[cur])
            Swap(&a[prev], &a[cur]);
        ++cur;
    }
    Swap(&a[prev], &a[keyi]);
    return prev;
}
void QuickSort3(int* a, int begin, int end)
{
    //子区间相等只有一个值或者不存在那么就是递归结束的子问题
    if (begin >= end)
        return;
    int keyi = PartSort3(a, begin, end);
    // [begin, keyi - 1]keyi[keyi + 1, end]
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}

三、快速排序的非递归实现以及快排模板

3.1快排的非递归实现

    快排的非递归应用场景是比较少的，因为快排也不是那么容易就爆栈，但是学习快排的非递归也能帮助我们更好地理解快排。

    快排的非递归写法用C语言实现会相对复杂，因为快排的非递归需要利用栈来实现，但是C语言没有自己的STL库，所以要自己手写一个栈，相对比较麻烦些。

我们还是使用前后指针法来找key，然后用栈来实现递归的作用

栈的代码：

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack//动态栈
{
    int* a;
    int top;//栈顶的位置
    int capacity;//容量
}ST;
STDataType StackTop(ST* ps);//返回栈顶的值
void StackInit(ST* ps);//初始化栈
void StackDestory(ST* ps);//销毁栈
void StackPop(ST* ps);//弹出
void StackPush(ST* ps, STDataType x);//插入
bool StackEmpty(ST* ps);//判断栈是否为空。

#include"Stack.h"

void StackInit(ST* ps)//栈的初始化
{
    assert(ps);
    ps->a = NULL;//a点的值指向空
    ps->top = 0;//栈底为0
    ps->capacity = 0;//空间为0
}
void StackDestory(ST* ps)
{
    assert(ps);
    free(ps->a);//把a释放掉
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)//入数据
{
    assert(ps);
    //满了就扩容
    if (ps->top == ps->capacity)//如果栈的栈顶恰好和容量相等就扩容
    {
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
        if (ps->a == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }

        ps->capacity = newCapacity;//新的空间赋给旧的
    }
    ps->a[ps->top] = x;//栈顶插入x;
    ps->top++;//top++
}
void StackPop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    --ps->top;//top--就相当于删除操作
}
bool StackEmpty(ST* ps)
{
    assert(ps);
    //两种写法
    //if (ps->top > 0)
    //{
    //    return false;
    //}
    //else
    //{
    //    return true;
    //}
    return ps->top == 0;
}
STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    return ps->a[ps->top - 1];//访问栈顶元素（这里因为top我们设为0，所以访问栈顶元素相当于top-1
}
int StackSize(ST* ps)
{
    assert(ps);

    return ps->top;
}

用前后指针加之栈来实现快排的代码：

快排的非递归写法
void QuickSort5(int* a, int begin, int end)
{
    ST st;
    StackInit(&st);
    //入栈
    StackPush(&st, begin);
    StackPush(&st, end);
    //栈是后进先出
    while (!StackEmpty(&st))
    {
        int right = StackTop(&st);
        StackPop(&st);
        int left = StackTop(&st);
        StackPop(&st);
        int keyi = PartSort3(a, left, right);
        //[left, keyi - 1][keyi + 1, right]
        if (left < keyi - 1)//还要继续入栈的条件
        {
            StackPush(&st, left);
            StackPush(&st, keyi - 1);
        }
        if (keyi + 1 < right)
        {
            StackPush(&st, keyi + 1);
            StackPush(&st, right);
        }
    }
    StackDestory(&st);
}

PartSort3
//前后指针法
int PartSort3(int* a, int left, int right)
{
    int mini = Getmini(a, left, right);
    Swap(&a[mini], &a[left]);
    int keyi = left;//如果是a[left],则是局部变量，SWap后还是原来的值
    //left则是下标
    int prev = left, cur = left + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi] && a[++prev] != a[cur])
            Swap(&a[prev], &a[cur]);
        ++cur;
    }
    Swap(&a[prev], &a[keyi]);
    return prev;
}

** 3.2快排的模板（适用于算法竞赛）**

它把key设为了中间值，这样好像是代码既短又是最优的情况。

#include <iostream>

using namespace std;

const int N = 100010;

int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/39784/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

四、快排的优化

4.1三数取中法优化快排

    我们为什么要对快排进行优化？

原因：

有序的时候快排的时间复杂度是O（N^2）

数据量大时会爆栈

三数取中代码示例：比快排模板选key的可靠性要更高些

int Getmini(int* a, int left, int right)//三数取中
{
    int mid = left + right;
    //防止溢出可以写成int mid = left + (right - left) / 2;
    if (a[left] < a[mid])
    {
        if (a[mid] < a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else
    {
        if (a[mid] > a[right])
        {
            return mid;
        }
        else if (a[left] < a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
}

4.2快排的优化二：小区间优化

     为什么要用小区间优化，最重要的原因就是递归的程度越深，其被分成的数目越多，子问题越多，在此时我们可以利用插入排序进行优化。

代码示例：

void QuickSort4(int* a, int begin, int end)
{
    //子区间相等只有一个值或者不存在那么就是递归结束的子问题
    if (begin >= end)
        return;
    //小区间直接插入排序控制有序
    if (end - begin + 1 <= 10)
    {
        InsertSort(a + begin, end - begin + 1);//插入好多个区间
    }
    else
    {
        int keyi = PartSort3(a, begin, end);
        // [begin, keyi - 1]keyi[keyi + 1, end]
        QuickSort(a, begin, keyi - 1);
        QuickSort(a, keyi + 1, end);
    }
}

五、归并排序的概念

5.1归并排序的基本思想：

    基本思想： 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

5.2归并排序的动态图：

5.3归并排序的图解：

简而言之就是

小的放在新数组里

先分再归

六、归并排序的递归实现

6.1按照如下归并排序的基本思路实现代码

这是按照[begin, mid] 和[mid + 1, end]区间来划分的

如果是按照[begin, mid - 1]和[mid , end]这样分会分的不均匀，出现[1, 2]的中位数也是1，造成死循环，只要是数是奇数都会出现这种情况。

6.2写一段代码看归并排序的思路：

void _MergeSort(int* a, int begin, int end, int* tmp)
{
    if (begin >= end)
    {
        return;
    }
    int mid = (begin + end) / 2;
    //[begin, mid - 1], [mid, end]
    _MergeSort(a, begin, mid, tmp);
    _MergeSort(a, mid + 1, end, tmp);

    printf("归并[%d, %d][%d, %d]\n", begin, mid, mid + 1, end);

}

归并排序的具体过程

归并排序的递归搜索树图

归并排序的递归函数代码如下：

//借助子函数
void _MergeSort(int* a, int begin, int end, int* tmp)
{
    if (begin >= end)
    {
        return;
    }
    int mid = (begin + end) / 2;
    //[begin, mid - 1], [mid, end]
    _MergeSort(a, begin, mid, tmp);
    _MergeSort(a, mid + 1, end, tmp);

    //printf("归并[%d, %d][%d, %d]\n", begin, mid, mid + 1, end);
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int index = begin;//相当于是每一个区间的开始都是begin
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
            tmp[index++] = a[begin1++];
        else
            tmp[index++] = a[begin2++];
    }
    //如果还有谁没结束，就把谁放tmp的后面
    while (begin1 <= end1)
        tmp[index++] = a[begin1++];
    while (begin2 <= end2)
        tmp[index++] = a[begin2++];
    //把tmp里的数拷贝回a数组
    //y总是用for循环实现的
    memcpy(a+begin, tmp+begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    assert(tmp);

    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);
};

七、归并排序的非递归实现以及归并排序的模板

7.1归并排序递归改非递归的思路：

思路：用循环，人为设置一个gap间隙

刚开始gap = 1,后面gap呈2倍增长

直到gap = 数组长度时结束

gap的作用就相当于划分区间了，每次划分完就排序每个区间，排完就拷贝回原数组

递归改非递归思路虽然简单但是区间的边界控制还是很伤脑筋的，和gap有关的区间边界都要控制，原因：gap突变太快了，跟gap有关的全部都存在越界访问的风险，这一点算是递归改非递归的难点，这点需要我们取突破。个人觉得这个有点像希尔排序对插入排序的优化，使用了gap间隙，使效率得到大大的提升，但是两者还是有细微区别的。

7.2归并排序递归改非递归的代码实现：

void MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    int gap = 1;
    while(gap < n)
    { 
        //间距为gap是一组，两两归并
        for (int i = 0; i < n; i+= gap*2)
        {
            int begin1 = i, end1 = i + gap -1 ;
            int begin2 = i + gap, end2 = i + 2*gap - 1;
            //end1越界，修正
            if (end1 >= n)
                end1 = n - 1;
            //begin2越界，第二个区间不存在，修正成不存在的区间
            if (begin2 >= n)
            {
                begin2 = n;
                end2 = n - 1;
            }
            //begin2 ok, end2越界，修正2即可
            if (begin2 < n && end2 >= n)
                end2 = n - 1;

            //  条件断点
            if (begin1 == 8 && end1 == 9
                && begin2 == 9 && end2 == 9)
            {
                int x = 0;
            }
            int index = i;
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] < a[begin2])
                    tmp[index++] = a[begin1++];
                else
                    tmp[index++] = a[begin2++];
            }
            //如果还有谁没结束，就把谁放tmp的后面
            while (begin1 <= end1)
                tmp[index++] = a[begin1++];
            while (begin2 <= end2)
                tmp[index++] = a[begin2++];
            
        }
        memcpy(a, tmp, n * sizeof(int));

        gap *= 2;
    }
    free(tmp);
}

7.3介绍一种比较好找bug 的调试方法：条件断点法

作用：调试时可以直接使程序停在想要的位置，从而提升调试效率

比如说我们想让程序停在出问题的归并[8, 9][9, 9]这个区域，我们只需写一段代码，然后将断点打在这个位置：

if (begin1 == 8 && end1 == 9
                && begin2 == 9 && end2 == 9)
            {
                int x = 0;
            }

7.4归并排序的模板（竞赛用）

#include<iostream>
using namespace std;
const int N = 100010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r)
{
    if(l >= r) return;// 特判区间内如果只有一个数或者为空时，直接return;
    int mid = l + r >> 1;//确定分界点mid
    merge_sort(q, l, mid), merge_sort(q, mid+1, r);//递归排序两边
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)//归并，合并两边
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
        while(i <= mid) tmp[k++] = q[i++];//再次查看左边区间是否还有剩余
        while(j <= r) tmp[k++] = q[j++];//再次查看右边区间是否还有剩余

        for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];//把tmp[i] 存到q[j]里
}
int main ()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    merge_sort(q, 0, n - 1);
    for(int i = 0; i < n; i++) printf("%d ", q[i]);

    return 0;
}

八、两种排序的对比总结

8.1快速排序的特性总结

快速排序的特性总结： 1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

  1. 时间复杂度：O(N*logN)

  2. 空间复杂度：O(logN)

  3. 稳定性：不稳定

8.2归并排序的特性总结

归并排序的特性总结： 1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

  1. 时间复杂度：O(N*logN)

  2. 空间复杂度：O(N)

  3. 稳定性：稳定

8.3快速排序的时间、空间复杂度分析（来自书籍）

    快速排序的一次划分Parttion算法两头交替搜索，直到两段区间重合，时间复杂度是O（N），整个快速排序的时间复杂度与划分的趟数有关，也就是说，快速排序的时间性能取决于快速排序递归的深度，如果是划分过程比较均匀， 递归树是平衡的，此时性能较好。在最优的情况下，划分Parttion每次都比较均匀，如果排序n个关键字，递归的搜索深度为log（n），这样整个算法的时间复杂度是O(nlogn)的。

    如果是在有序的情况下，长度为n的数据表要经过N次划分，此时的时间复杂度为o(N^2)，如果是用三数取中，可以降低其时间复杂度。

    快排的空间复杂度分析：从空间性能上看，尽管快速排序需要一个元素的辅助空间，由于快速排序是递归的，每层递归调用时的指针和参数均要栈来存放，存储开销在理想的情况下为O（logN）；在最坏的情况下为O(N)。

    另外，快速排序过程中的关键词相同的元素在排序前后相对位置发生了改变，因此，快速排序是不稳定的排序算法。

8.4归并排序的时间、空间复杂度分析

    归并排序是分治思想的最典型的例子，上面的算法中，对一组数a[n]进行排序，先将它分为[begin, mid] 和[mid + 1, end]区间来划分的，分别通过递归调用将他们单独排序，最终将有序的子数组归并为最终的排序结果。具有N个记录的序列进行归并排序的递归的深度就是具有n个结点的完全二叉树的深度，可以看出来整个排序归并排序需要进行log(N)次，因此，总的归并排序算法的时间复杂度为O(logN)，而且这是归并排序算法最好、最坏、平均的时间复杂度。

    由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为logn的栈空间，因此，空间复杂度为O(n + logn)。

    非递归的合并排序避免了递归时深度为logn 的栈空间，空间只是用到了申请归并临时用的tmp数组，因此，时间复杂度为O(n),在时间上也有一定的提升，省去了递归拆分，但总体时间复杂度还是O(logn)。应该说，使用归并排序时，尽量考虑非递归的方法。

8.5快速排序和归并排序测试用时

数据量为10万时，不分伯仲（release版本）

数据量为100万时（release版本）

数据量为1000万时（release版本）

总结

     ![](https://img-blog.csdnimg.cn/fd8dd32fa4b548d4bb80f40219992af3.jpeg)

    本文写了万字，详细地总结了快速排序和归并排序的几个关键要点，比如是快排和归并排序的递归和非递归写法，以及分析了这两种算法的特性，时间复杂度和空间复杂度等，希望对大家的学习有所帮助，有所启发。如果有写得不好的地方欢迎大家来指正。
标签： c语言 数据结构 排序算法
本文转载自: https://blog.csdn.net/qq_62662919/article/details/125373376
版权归原作者 披星戴月的贾维斯 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【C语言 - 数据结构】万字详解快速排序、归并排序”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

基于CVE安全公告号，全面修复麒麟ARM系统OpenSSH漏洞

（一篇即成功）Ubuntu下搭建qt环境和安装Qt Creator

git 提交代码忽略eslint代码检测，git更换地址后强制覆盖

Apache Flink的本地调试模式

JavaEE要想学得好，【Java spring】少不了，稳扎稳打学JavaEE

【K8S系列】Kubernetes集群资源管理与调度 深度分析

【玩转 Postman 接口测试与开发2_004】第二章：API 核心基础知识之：接口文档与设计

文章导航