【算法速查】万字图解带你快速入门八大排序(下）

Hello,米娜桑们，这里是君兮_，首先在这里祝大家中秋国庆双节同乐！！抓住假期的小尾巴，今天来把算法速查的八大排序的后续写完，当然由于篇幅的原因不是每一种算法都详解，这篇文章更多是作为让初学者有一个初步的了解以及学过的人某个排序算法忘了的话的快速回忆，后续我也会把每种算法的重点以及难点挑出来单独为大家讲解的

• 好了废话不多说，开始我们今天的学习吧！！
  

  目录

  八大排序

  • 前言
  • 五.冒泡排序
  • 六.快速排序
  • • 1.hoare版本
    • 2.挖坑版本
    • 3.前后指针版本
  • 七.归并排序
  • • 非递归实现
  • 八.计数排序
  • 几种排序对比
  • • 不同排序的适用场景
    • 稳定性以及时/空间复杂度对比
  • 总结

前言

• 在开始前，我们还是通过一张图片带大家认识一下有哪八大排序
  
• 之前我们已经讲了什么是排序以及前面的四种排序，具体内容在以下链接
  【算法速查】一篇文章带你快速入门八大排序(上）
• 今天我们来讲讲后面四种排序

五.冒泡排序

• 在我们日常的应用中，实际上由于冒泡排序的时间复杂度实在是太高，我们几乎不会用到，但由于冒泡排序比较简单，它通常出现在课堂上帮助大家入门排序算法
• 由于比较简单，这里就不详细讲了，感兴趣可以看看我之前写过的这篇博客
  【C语言初阶】带你玩转C语言中的数组，并逐步实现冒泡排序，三子棋，扫雷
• 这里是冒泡排序的动图
  

void Qsort(int* a, int n)
{
    assert(a);//断言防止越界
    for (int i = 0; i < n-1; i++)
    {
        for (int j = 0; j < n - 1 - i; j++)
        {
            int tmp = a[j + 1];
            if (a[j] > a[j + 1])
            {
                a[j + 1] = a[j];
                a[j] = tmp;
            }
        }
    }
}

int main()
{
    int a[5] = { 5,6,2,9,0 };
    Qsort(a, 5);
    for (int i = 0; i < 5; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

六.快速排序

• 相信很多人都听过快速排序的顶顶大名，什么排序算法这么狂，敢叫快速排序，根本不把其他算法放在眼里
  
• 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中
  的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右
  子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
• 下面我们来讲讲三种实现快速排序的方法

1.hoare版本

• 这是由Hoare提出的最初的快速排序，具体的排序是这样的
  

基本思想：
1.确定一个key值，先让右走，遇到比key值大的就继续走，遇到比key值小的就停下，此时让左走，遇到比key小的就继续走，遇到比key大的就停下，此时交换两者的值，让比key大的值到右边，比key小的值到左边
2.重复上述的循环，直到左右两者相遇，此时交换key和此时左右相遇位置的值，由于我们是让右先走的，如果此时相遇的位置的值比key大，它不可能停下，也就是说，两者相遇位置的值一定是比key小的，交换后，我们就实现了一趟快排循环，此时key右边的值一定大于等于key，key左边的值一定小于等于key值
3.以key为界限，把key左边和key右边的数据继续进行单趟快排的操作，直至该数组中所有数据都有序，完成快速排序

Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
int getMid(int* a, int left, int right)
{
    assert(a);
    int mid = (left + right) / 2;
    if (a[left] > a[mid])
    {
        if (a[mid] > a[right])
            return mid;
        else if(a[right]>a[left])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else
    {
        if (a[mid] < a[right])
            return mid;
        else if (a[left] > a[right])
        {
            return left;
        }
        else
        {
            return right;
        }

    }
}
int PartSort1(int* a, int left, int right)
{
    int mid = getMid(a, left, right);//三数取中
    //把取好的key放到left中
    Swap(&a[left], &a[mid]);
    int key = left;
    while (left<right)
    {
    //右边先走
        while (left < right && a[right] >= a[key])
        {
            right--;
        }
      //左边走
        while (left<right&&a[left]<=a[key])
        {
            left++;
        }
        //交换
        Swap(&a[left], &a[right]);
    }
    //交换停下的位置的值把key换到此时左右相遇的位置
    Swap(&a[key], &a[left]);
    //此时key的左右都有序，由于right，left都指处于key的位置返回任意即可
    return right;
}
void QuickSort(int* a, int left,int right)
{
	//只剩下一个值了，说明已经有序，不需要再排，递归结束
    if (left >= right)
        return;
   
    int key = PartSort1(a,left,right);
    //key已经满足左右都有序了不需要再排
    //排key的左边
    QuickSort(a, left, key-1);
    //排key的右边
    QuickSort(a, key+1, right);

}

2.挖坑版本

• 与上面的hoare版本的快速排序非常类似，但是用“挖坑”的形式来替换上面的left和right
• 动图演示如下：
  

基本思想：
1.和hoare一样，先找到一个key值保存到所需排序数据的第一个位置中，通过临时变量保存下来，使此时的第一个位置变成一个“坑位”，让右边先移动，当遇到比key值大的就继续朝左走，遇到比key值小的位置时，就把这个位置的值赋给“坑位”，此时，当前位置变成了新的“坑位”，此时让左边移动，遇到比key值小的继续向右走，遇到比key值大的就把这个值赋给“坑位”，此时这个位置变成新的“坑位”
2.重复上述的过程，直到左右相遇，此时它们一定是在某个“坑位”相遇的，再把key值赋给这个“坑位”，就完成了一次快排
3.对此时位置的左右再分别进行上述操作，直至整个所需排序的数据都有序。

int PartSort2(int* a, int left, int right)
{
    int mid = getMid(a, left, right);
    Swap(&a[left], &a[mid]);
    int hole = left;//坑位
    int key = a[left];//保存left的值
    while (left<right)
    {
        while (left < right && a[right] >= key)
        {
            right--;
        }
        //把此时小于key的值赋给坑位，此时的位置变成新的坑
        a[hole] = a[right];
        hole = right;
        while (left < right && a[left] <= key)
        {
            left++;
        }
        //把此时大于key的值赋给坑位，此时的位置变成新的坑
        a[hole] = a[left];
        hole = left;
    }
    //key的值赋给坑
    a[hole] = key;
    return hole;
}
void QuickSort(int* a, int left,int right)
{
    if (left >= right)
        return;
   
    int key = PartSort2(a,left,right);
    QuickSort(a, left, key-1);
    QuickSort(a, key+1, right);

}

3.前后指针版本

• 本质上与前面两个版本都差不多，使用两个快慢不同的指针实习
• 动图演示如下：
  

基本思想：
1.找到一个key值保存在left中，定义一前一后两个指针prev和cur，当cur中保存的值比key小的时候，两个指针一起朝右走，当cur中保存的值比key大时，只有cur向右走走，直至再次遇到比key值小的，此时交换cur和prev中保存的值。
2.重复上述的过程直至cur走到尾，此时交换prev中的值与key的值，完成一次快速排序
3.此时prev左右均有序，对左右再进行上述的循环，直至待排数组全部有序

int PartSort3(int* a, int left, int right)
{
    int mid = getMid(a, left, right);
    Swap(&a[left], &a[mid]);
    int key = left;
    //定义两个指向前后位置的整形
    int prev = left;
    int cur = prev + 1;
    while (cur <= right)
    {
       //当cur中的值比key小且此时cur和prev中有大于key值的数时
        while (a[cur]<=a[key] && ++prev != cur)
        {
        //交换下一个位置的prev的值和此时cur保存的值
            Swap(&a[prev], &a[cur]);
        }
        //无论cur中的值比key大还是小，每次循环都要向前走
        ++cur;

    }
    //cur走到尾，交换此时prev的值和key的值
    Swap(&a[prev], &a[key]);
    //把左右有序的位置返回
    return prev;
}
void QuickSort(int* a, int left,int right)
{
    if (left >= right)
        return;
   
    int key = PartSort3(a,left,right);
    QuickSort(a, left, key-1);
    QuickSort(a, key+1, right);

}

• 这里有些小细节需要说明：
• 1.++prev！=cur ，当相等时，说明prev和cur没拉开差距，此时它们保存的值都是小于key的，不需要进行交换
• [x] 2.前置的++，无论两者是否拉开差距，只要满足cur的值小于key，cur和prev都得++，因此先++再判断是否拉开差距
• 3.prev没走到尾，但是我们知道，只要prev和cur拉开差距，说明只有cur++了，此时里面保存的值一定都是大于key的，因此只需要cur走到尾就能满足prev左边的值小于key右边的值大于key了。

• 注意：这三种快速排序的实现中间都加了三数取中的优化，主要是保证取到的值不在最左或者最右增加排序的效率，由于篇幅原因，这里不展开讲了，之后会具体出有关博客讲讲快速排序中的细节优化和非递归实现的。
• 快速排序的特性总结：
• 1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
• 2. 时间复杂度：O(N*logN)
• 3. 空间复杂度：O(logN)
• 4. 稳定性：不稳定

七.归并排序

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

• 简单的来说，就是先保证子序列有序，把子序列合并排序，最终把整个序列变为有序（你可以对应二叉树的后序遍历来理解）
• 动图演示如下：

基本思想：先拆分后合并
1.拆分
把所需排序的序列拆除左序列和右序列，循环这个过程直至左序列和右序列都只有一个数结束
2.合并
把拆分好的左右子序列合并并排序，这个过程在我们开辟的和原所需排序的数组大小相同的数组中进行，每次排序完后都把这部分排序好的值重新赋给原数组，重复这个过程，直至合并所有左右子序列，此时新的数组即为有序。

void _MergeSort(int* a, int* tmp, int left, int right)
{
    if (left >= right)
        return;
    int mid = (left + right) / 2;
    //分左子列
    _MergeSort(a, tmp, left, mid);
    //分右子列
    _MergeSort(a, tmp, mid + 1, right);
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = left;
    //排序，把左右子列的数据从小到大填入我们开辟的数组中
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
        {
            tmp[index++] = a[begin1++];
        }
        else
        {
            tmp[index++] = a[begin2++];
        }
    }
    //左子列还有数据
    while (begin1 <= end1)
    {
        tmp[index++] = a[begin1++];
    }
    //右子列还有数据
    while (begin2 <= end2)
    {
        tmp[index++] = a[begin2++];
    }
    //每排完一次，都把对应排好的合并序列拷回原数组中
    memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}
void MergeSort(int* a, int n)
{
 //开辟与原数组大小相同的数组
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        return;
    }
    _MergeSort(a, tmp, 0, n - 1);
    free(tmp);
}

非递归实现

• 上面讲的是递归实现归并排序，但是我们知道，递归是在栈空间开辟内存，而栈空间往往都是很小的，当数据很大时容易“爆栈”，由于归并排序是八大排序中唯一一种外排序算法，而磁盘中的数据往往又很多很容易就“爆栈”了，因此我们还需要学会使用循环非递归实现归并算法
  

基本思想：
1.通过一个gap来控制归并子序列的大小，gap从1开始，同递归一样，每次把子序列排序好后合并拷贝回原数组
2.gap的值从1开始，每经过上述过程，gap*=2，循环直至gap>=n，此时所有子序列均排序合并，完成归并排序

MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    int gap = 1;
    while(gap < n)
    {
    //每次需要排序并归并的子序列大小为2*gap，从0开始，到n-1结束此时gap大小的合并
        for (int i = 0; i < n; i += 2*gap)
        {
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + gap * 2 - 1;
            //gap太大超出数组大小越界，直接break返回
            if (begin2 >= n)
                break;
             //n比2*gap小，直接让end2等于最后一个元素，防止越界
            if (end2 >= n)
                end2 = n - 1;
            int index = i;
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] < a[begin2])
                {
                    tmp[index++] = a[begin1++];
                }
                else
                {
                    tmp[index++] = a[begin2++];
                }
            }
            while (begin1 <= end1)
            {
                tmp[index++] = a[begin1++];
            }
            while (begin2 <= end2)
            {
                tmp[index++] = a[begin2++];
            }
            //拷贝回
            memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));
        }
        //完成一次子序列合并，把合并后的序列当子序列，增大gap继续
        gap *= 2;
    }
    free(tmp);
}

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

八.计数排序

• 基本思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
• 1. 统计相同元素出现次数
• 2. 根据统计的结果将序列回收到原来的序列中
• 其实就是笨办法，我们通过找出最大最小值来确定排序序列的范围，统计每一个数出现的次数然后把出现的数从小到大按次数从小到大插入回原序列中
  

void CountSort(int* a, int n)
{
    int min = a[0];
    int max = a[0];
    for (int i = 0; i < n; i++)
    {
        if (a[i] > max)
            max = a[i];
        if (a[i] < min)
            min = a[i];
    }
    //统计数的范围
    int Range = max - min + 1;
    int* Count = (int*)malloc(sizeof(int) * Range);
    if (Count == NULL)
    {
        perror("malloc failed");
        exit(-1);
    }
    //初始化一下，防止出现随机数
    memset(Count, 0, sizeof(int) * Range);
    for (int i = 0; i < n; i++)
    {
        //对应位置的数的次数
        Count[a[i] - min]++;
    }
    int j = 0;
    for (int i = 0; i < Range; i++)
    {
        //把Count中存在的数出现了几次重新填回原序列
        while (Count[i]--)
        {
            //i+min是对应位置的值
            a[j++] = i + min;
        }
    }
    free(Count);
}

• 计数排序的特性总结：
• 1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
• 2. 时间复杂度：O(MAX(N,范围))
• 3. 空间复杂度：O(范围)
• 4. 稳定

几种排序对比

不同排序的适用场景

• 冒泡排序：适用于小规模数据的排序，时间复杂度为O(n^2)，不适合处理大规模数据。

• 插入排序：适用于对已经接近有序的数据进行排序，时间复杂度为O(n^2)，效率较高。

• 选择排序：适用于简单选择最小（或最大）的元素，时间复杂度为O(n^2)，适合处理小规模数据。

• 快速排序：适用于任意规模的数据排序，具有较好的平均时间复杂度O(nlogn)，但最坏情况下可能达到O(n^2)。

• 归并排序：适用于任意规模的数据排序，具有稳定的时间复杂度O(nlogn)，但需要额外的空间来存储临时数组。

• 堆排序：适用于对大规模数据进行排序，时间复杂度为O(nlogn)，不需要额外的空间。

• 希尔排序：适用于当数据规模较大，插入排序性能较差，且要求对内存消耗较小时，时间复杂度约为O(n^1.3)。

• 计数排序：适用于数据存在大量重复值且数据范围相对集中，时间复杂度为O(MAX(N,Range))

稳定性以及时/空间复杂度对比

总结

• 好啦，我们总算把八大排序算法都讲完了，算法这一块光靠看代码不是那么容易理解的，因此我花了大量的时间画图分析，希望能对你有所帮助
• 当然，这篇文章创作的初衷是希望帮助初学者对排序算法有一个大致的了解，对已经学过的人起到在需要使用的时候快速回忆的效果，因此可能还有一部分细节不全，之后我会挑出重点单独出博客讲解
• 有任何的问题和对文章内容的疑惑欢迎在评论区中提出，当然也可以私信我，我会在第一时间回复的！！

新人博主创作不易，如果感觉文章内容对你有所帮助的话不妨三连一下再走呗。你们的支持就是我更新的动力！！！