机械转码日记【5】排序算法及对比（第一次画动图）

前言

排序是我们程序员在编程中常常要接触到的知识，所以它非常重要，常见的排序算法有插入排序，选择排序，交换排序，归并排序......今天我们就来实现一下这几种排序的c语言代码，以及对比一下这几种排序的优劣。

冒泡排序

冒泡排序是我接触过的第一种排序方法，也是最简单的，当然也是时间复杂度非常高的（意味着它比较垃圾哈哈哈）。以升序为例，它的原理是：

1、从左至右遍历对比相邻两个元素的大小，将数组最大的元素推到最右边以实现升序。

2、接着数组排序个数减去1（减一是因为已经排序好的最大的元素），开始找出次大的元素。

3、重复上面的两个过程直到排序个数为0，就实现了升序排序。

单趟排序原理图：

代码实现如下：

void BubbleSort(int* a, int n)
{
    //遍历所有数
    for (int i = 0; i < n; i++)
    {
        //定义一个exchange判断是否发生交换
        int exchange = 0;
        //单趟排序
        for (int j = 1; j < n - i; j++)
        {
            //升序，如果前一个大于后一个，就交换
            if (a[j - 1] > a[j])
            {
                exchange = 1;
                Swap(&a[j - 1], &a[j]);
            }
        }
        //exchange为0，说明没有交换，跳出循环，防止消耗内存资源
        if (exchange == 0)
        {
            break;
        }
    }
}

直接插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩打斗地主理牌时，就用了插入排序的思想：

直接插入排序原理图：

直接插入排序代码实现：

// 直接插入排序
void InsertSort(int* a, int n)
{
    //遍历每个数,end为每个区间的右边缘
    for (int i = 0; i < n - 1; i++)
    {
        int end = i;
        int tmp = a[end + 1];//要插入的数为tmp
        while (end >= 0)
        {
            //升序，如果要插入的数小于a[end]，就把这个值往后挪，随后继续比较a[end-1]...
            if (tmp < a[end])
            {
                a[end+1] = a[end];
                end--;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

希尔排序

希尔排序法是直接插入排序的一种优化，他的思想是先对数据进行预排序，即大致分成左边较小，右边较大的一组数据，然后在进行插入排序，具体的步骤如下：
1、定义一个值gap，即步长，将数据间隔gap分为几组。

2、对分成的这几组数据分别进行插入排序，即完成预排序。

3、然后进行插入排序（间隔gap=1）。

原理图如下：

代码实现如下：

// 希尔排序
void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;//逐步减小gap,最后gap会为1
        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];//要插入的数为tmp
            while (end >= 0)
            {
                //升序，如果后一个数小于前一个，就将前一个的值赋给后一个
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end = end-gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

直接选择排序

直接选择排序比较暴力，其基本原理是：

每一次从待排序的数据元素中选出最小和最大的一个元素，存放在序列的起始位置和末尾位置，直到全部待排序的数据元素排完。

原理图如下：

代码实现如下：

// 选择排序
void SelectSort(int* a, int n)
{
    int left = 0;
    int right = n - 1;
    while (left < right)
    {
        int mini = left;
        int maxi = right;
        for (int i = left + 1; i <= right; i++)
        {
            if (a[i] < a[mini])
            {
                mini = i;
            }
            if (a[i] > a[maxi])
            {
                maxi = i;
            }
        }

        Swap(&a[left],&a[mini]);
        //如果left和maxi重叠，就会掉包掉最大的值，所以要防被掉包
        if (maxi == left)//left 和 maxi 重叠，最大值被换到了下标mini上
        {
            maxi = mini;
        }
        Swap(&a[right], &a[maxi]);
        left++;
        right--;
    }
}

堆排序

堆排序的原理就是在数组上建堆，实现升序建立大堆，实现降序建立小堆，接着使用向下调整算法及堆删除思想实现排序。具体的实现代码和原理可以看我的前两期博客

堆排序算法

为什么升序建立大堆，降序建立小堆

快速排序

终于到了本期博客的重头戏了，快速排序是一种非常NB的排序，难怪C语言的库函数qsort的原理也是快速排序，快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

//假设按照升序对array数组中[left, right]区间中的元素进行排序
void QuickSort1(int* a, int left, int right)
{
//递归结束条件，当区间不存在时就停止递归
    if (left >= right)
    {
        return;
    }

//按照基准值对array数组的 [left, right)区间中的元素进行划分
    int keyi = PartSort1(a, left, right);

//划分成功后以keyi为边界形成了左右两部分 [left, key-1] 和 [key+1, right]
//[left,keyi-1] keyi [keyi+1,right]

//递归排[left,keyi-1]      
    QuickSort1(a, left, keyi-1);
//递归排[keyi+1,right]
    QuickSort1(a, keyi+1, right);

}

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，我们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

将区间按照基准值划分为左右两半部分的常见方式

1.Hoare版本

Hoare版本（以实现升序为例）的思想如下：

1.keyi为基准值的下标，定义数组a的两个下标left和right，left位于区间的最左侧，right位于区间的最右侧

2.right先走，R往区间左侧走，直到找到比a[keyi]小的值停下来，left后走，往区间右侧走，直到找到比a[keyi]大的值停下来，然后交换a[left]和a[right]的值

3.重复进行2过程，直到left和right相遇，最后交换a[keyi]和a[left]的值

Hoare版本的单次快排原理图如下：

使用Hoare版本的快排实现代码如下：

// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
    int keyi = left;
    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 QuickSort1(int* a, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int keyi = PartSort1(a, left, right);
    //    [left,keyi-1] keyi [keyi+1,right]      
    QuickSort1(a, left, keyi-1);
    QuickSort1(a, keyi+1, right);

}

2.挖坑法

挖坑法（以实现升序为例）的思想如下：

1.定义数组a的两个下标left和right，left位于区间的最左侧，right位于区间的最右侧

2.将数组的第一个数据存入一个临时变量key中，key所在的下标成为一个坑位

3.right先走，right往区间左侧走，找到比key值小的数，找到后，将该值放入坑位，同时该值的位置成为一个新坑位

4.left后走，left往区间右侧走，找到比key值大的数，找到后，将该值放入坑位，同时该值的位置成为一个新坑位

5.重复进行3，4两步，直到left和right相遇，然后将key的值放入坑位

挖坑法的单次快排原理图如下：

使用挖坑法的快排实现代码如下：

// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
    int key = a[left];
    int pit = left;
    while (left < right)
    {
        //找小
        while (left < right && a[right] >= key)
        {
            right--;
        }
        //把找到的小的值放到坑里
        a[pit] = a[right];
        //找到的小成为新坑
        pit = right;
        //找大
        while (left < right && a[left] <= key)
        {
            left++;
        }
        //把找到的大的值放到坑里
        a[pit] = a[left];
        //找到的大成为新坑
        pit = left;
    }
    a[pit]=key;
    return left;
}
void QuickSort2(int* a, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int keyi = PartSort2(a, left, right);
    //    [left,keyi-1] keyi [keyi+1,right]      
    QuickSort1(a, left, keyi - 1);
    QuickSort1(a, keyi + 1, right);
}

3.前后指针法

前后指针法（以实现升序为例）的思想如下：

1.keyi为基准值的下标，定义数组a的两个指针prev和cur，prev指向数组的开头，cur指向数组开头的后一个位置

2.判断cur指针指向的数据是否小于key,若小于，则prev++，并且将cur指向的内容与prev指向的内容交换，然后cur指针++，若大于，则prev指针不动，cur++

3.重复进行2步骤，直到cur走到数组越界，此时交换a[keyi]和prev指向的内容

前后指针法的单次快排原理图如下：

使用前后指针法的快排实现代码如下：

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
    int keyi = left;
    int prev = left;
    int cur = left + 1;
    while (cur <= right)
    {
        //low的方法
        /*if(cur<right&&a[cur] <= a[key])
        {
            prev++;
            Swap(&a[cur], &a[prev]);
        }
        cur++;*/

        //大佬的写法
        if (a[cur] < a[keyi] && a[++prev] != a[cur])
        {
            Swap(&a[prev], &a[cur]);
        }
        ++cur;
    }
    Swap(&a[keyi], &a[prev]);
    return prev;
}

void QuickSort3(int* a, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int keyi = PartSort3(a, left, right);
    //    [left,keyi-1] keyi [keyi+1,right]      
    QuickSort1(a, left, keyi - 1);
    QuickSort1(a, keyi + 1, right);
}

快速排序的优化

针对有序数组快排效率较低进行优化

我们先来做一组实验，当数组有序时，使用我们刚刚写的快速排序和冒泡排序对数组进行排序计算：

//冒泡排序与快速排序计算有序数组时的时间竞速赛
void TestOP()
{

    const int N = 10000;//计算10000长的数组
    int* a1 = (int*)malloc(sizeof(int) * N);
    int* a2 = (int*)malloc(sizeof(int) * N);

//将有序数据写入数组
    for (int i = 0; i < N; ++i)
    {
        a1[i] = i;
        a2[i] = a1[i];
    }

//计时
    int begin1 = clock();
    BubbleSort(a1,N);
    int end1 = clock();

    int begin2 = clock();
    QuickSort3(a2, 0, N);
    int end2 = clock();

//打印出他们的运行时间
    printf("BubbleSort:%d\n", end1 - begin1);
    printf("QuickSort:%d\n", end2 - begin2);
}

实验结果为：

我们发现快排的运行时间居然比最垃圾的冒泡排序的运行时间都长！那你快排还怎么称王！如果我们再次增大N，使得计算的数据位100000，会发生什么呢？

什么！直接程序就崩了？我们来调试一下看看是哪里出了问题

原来是栈爆了！在实际情况中，我们不免会碰到一组数据是有序或者接近有序，这个时候快排的效率就会变的很差，那么我们如何针对这种情况优化快速排序呢？答案当然是可以！为什么栈爆了，因为递归的层次太深了，那如何减少递归的次数呢？我们可以改变每次递归时的key值，防止这个key每次都是在区间的最左侧或者最右侧（数组有序就会出现这种情况），我们可以采用三数取中选key的方法，这个key不是数组中最大和最小的数据，那么数组递归的层次就会变少。改进算法程序如下：

//选中值
int GetMidIndex(int* a, int left, int right)
{
    //int mid = (left + right) / 2;
    int mid = left + (right - left) / 2;
    // left mid right
    if (a[left] < a[mid])
    {
        if (a[mid] < a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else // a[left] > a[mid]
    {
        if (a[mid] > a[right])
        {
            return mid;
        }
        else if (a[left] < a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
}

int PartSort4(int* a, int left, int right)
{
    int midi = GetMidIndex(a, left, right);
    Swap(&a[midi], &a[left]);

    int keyi = left;
    int prev = left;
    int cur = left + 1;
    while (cur <= right)
    {
        //大佬的写法
        if (a[cur] < a[keyi] && a[++prev] != a[cur])
        {
            Swap(&a[prev], &a[cur]);
        }
        ++cur;
    }
    Swap(&a[keyi], &a[prev]);
    return prev;
}

void QuickSort4(int* a, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int keyi = PartSort4(a, left, right);
    //    [left,keyi-1] keyi [keyi+1,right]      
    QuickSort1(a, left, keyi - 1);
    QuickSort1(a, keyi + 1, right);
}

用10000个有序数组实验一下：

发现速度确实变快了，缩减到了原来的一半。

小区间优化

前面说到，如何提升快排的效率，就是减少递归的次数，那么是否还有别的方法能继续减少递归的次数呢？其实快排就是使用一次次递归将我们原来的大区间分为小区间，快排递归的展开图可以看作一棵二叉树。

可以看到，越往小区间分，需要的递归层次就越多，那么当区间很小时，我们可以不再使用递归划分的思路让他有序，而是直接使用插入排序对小区间排序，减少递归调用。实现代码如下：

void QuickSort4(int* a, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    // 小区间直接插入排序控制有序
    if (right - left + 1 <= 30)
    {
        InsertSort(a + left, right- left + 1);
    }
    else
    {
        int keyi = PartSort4(a, left, right);
        //    [left,keyi-1] keyi [keyi+1,right]      
        QuickSort1(a, left, keyi - 1);
        QuickSort1(a, keyi + 1, right);
    }
    
}

测试一下10万个有序数据改进后的运行速度：

可见小区间优化是能够提升快排的运行效率的！

为了避免篇幅过长，归并排序我们就放到下期吧！