数据结构从入门到精通（第五篇）：排序的进阶

前言

在上一篇，我们已经讲了基本的排序方法，例如：插入排序，希尔排序，选择排序，冒泡排序

数据结构从入门到精通（第四篇）：排序的入门（插入排序，希尔排序，选择排序，冒泡排序）

这一篇将会讲解进阶的排序算法，例如：快速排序，归并排序，计数排序

请添加图片描述

快速排序

原理

任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序列分为两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右序列重复该过程，直到所有元素都排列在相应位置上为止。

递归的实现

挖坑法

//快速排序（挖坑法）
void QuickSort2(int* a, int begin, int end)
{
    if (begin >= end)//当只有一个数据或是序列不存在时，不需要进行操作
        return;

    int left = begin;//L
    int right = end;//R
    int key = a[left];//在最左边形成一个坑位
    while (left < right)
    {
        //right向左，找小
        while (left < right&&a[right] >= key)
        {
            right--;
        }
        //填坑
        a[left] = a[right];
        //left向右，找大
        while (left < right&&a[left] <= key)
        {
            left++;
        }
        //填坑
        a[right] = a[left];
    }
    int meeti = left;//L和R的相遇点
    a[meeti] = key;//将key抛入坑位

    QuickSort2(a, begin, meeti - 1);//key的左序列进行此操作
    QuickSort2(a, meeti + 1, end);//key的右序列进行此操作
}

Hoare版本

//快速排序
void QuickSort1(int* a, int begin, int end)
{
    if (begin >= end)//当只有一个数据或是序列不存在时，不需要进行操作
        return;

    int left = begin;//L
    int right = end;//R
    int keyi = left;//key的下标
    while (left < right)
    {
        //right先走，找小
        while (left < right&&a[right] >= a[keyi])
        {
            right--;
        }
        //left后走，找大
        while (left < right&&a[left] <= a[keyi])
        {
            left++;
        }
        if (left < right)//交换left和right的值
        {
            Swap(&a[left], &a[right]);
        }
    }
    int meeti = left;//L和R的相遇点
    Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值

    QuickSort1(a, begin, meeti - 1);//key的左序列进行此操作
    QuickSort1(a, meeti + 1, end);//key的右序列进行此操作
}

前后指针法

//快速排序（前后指针法）
void QuickSort3(int* a, int begin, int end)
{
    if (begin >= end)//当只有一个数据或是序列不存在时，不需要进行操作
        return;

    //三数取中
    int midIndex = GetMidIndex(a, begin, end);
    Swap(&a[begin], &a[midIndex]);

    int prev = begin;
    int cur = begin + 1;
    int keyi = begin;
    while (cur <= end)//当cur未越界时继续
    {
        if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
        {
            Swap(&a[prev], &a[cur]);
        }
        cur++;
    }
    int meeti = prev;//cur越界时，prev的位置
    Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容

    QuickSort3(a, begin, meeti - 1);//key的左序列进行此操作
    QuickSort3(a, meeti + 1, end);//key的右序列进行此操作
}

非递归的实现

Hoare版本

//Hoare版本（单趟排序）
int PartSort1(int* a, int left, int right)
{
    int keyi = left;//key的下标
    while (left < right)
    {
        //right走，找小
        while (left < right&&a[right] >= a[keyi])
        {
            right--;
        }
        //left先走，找大
        while (left < right&&a[left] <= a[keyi])
        {
            left++;
        }
        if (left < right)
        {
            Swap(&a[left], &a[right]);//交换left和right的值
        }
    }
    int meeti = left;//L和R的相遇点
    Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值
    return meeti;//返回相遇点，即key的当前位置
}

挖坑法

//挖坑法（单趟排序）
int PartSort2(int* a, int left, int right)
{
    int key = a[left];//在最左边形成一个坑位
    while (left < right)
    {
        //right向左，找小
        while (left < right&&a[right] >= key)
        {
            right--;
        }
        //填坑
        a[left] = a[right];
        //left向右，找大
        while (left < right&&a[left] <= key)
        {
            left++;
        }
        //填坑
        a[right] = a[left];
    }
    int meeti = left;//L和R的相遇点
    a[meeti] = key;//将key抛入坑位
    return meeti;//返回key的当前位置
}

前后指针法

//前后指针法（单趟排序）
int PartSort3(int* a, int left, int right)
{
    int prev = left;
    int cur = left + 1;
    int keyi = left;
    while (cur <= right)//当cur未越界时继续
    {
        if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
        {
            Swap(&a[prev], &a[cur]);
        }
        cur++;
    }
    int meeti = prev;//cur越界时，prev的位置
    Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容
    return meeti;//返回key的当前位置
}

利用栈来实现

//快速排序（非递归实现）
void QuickSortNonR(int* a, int begin, int end)
{
    Stack st;//创建栈
    StackInit(&st);//初始化栈
    StackPush(&st, begin);//待排序列的L
    StackPush(&st, end);//待排序列的R
    while (!StackEmpty(&st))
    {
        int right = StackTop(&st);//读取R
        StackPop(&st);//出栈
        int left = StackTop(&st);//读取L
        StackPop(&st);//出栈
        //该处调用的是Hoare版本的单趟排序
        int keyi = PartSort1(a, left, right);
        if (left < keyi - 1)//该序列的左序列还需要排序
        {
            StackPush(&st, left);//左序列的L入栈
            StackPush(&st, keyi - 1);//左序列的R入栈
        }
        if (keyi + 1 < right)// 该序列的右序列还需要排序
        {
            StackPush(&st, keyi + 1);//右序列的L入栈
            StackPush(&st, right);//右序列的R入栈
        }
    }
    StackDestroy(&st);//销毁栈
}

归并排序

原理：

归并排序是采用分治法的一个非常典型的应用。其基本思想是：将已有序的子序合并，从而得到完全有序的序列，即先使每个子序有序，再使子序列段间有序。

递归实现

//归并排序（子函数）
void _MergeSort(int* a, int left, int right, int* tmp)
{
    if (left >= right)//归并结束条件：当只有一个数据或是序列不存在时，不需要再分解
    {
        return;
    }
    int mid = left + (right - left) / 2;//中间下标
    _MergeSort(a, left, mid, tmp);//对左序列进行归并
    _MergeSort(a, mid + 1, right, tmp);//对右序列进行归并
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    //将两段子区间进行归并，归并结果放在tmp中
    int i = left;
    while (begin1 <= end1&&begin2 <= end2)
    {
        //将较小的数据优先放入tmp
        if (a[begin1] < a[begin2])
            tmp[i++] = a[begin1++];
        else
            tmp[i++] = a[begin2++];
    }
    //当遍历完其中一个区间，将另一个区间剩余的数据直接放到tmp的后面
    while (begin1 <= end1)
        tmp[i++] = a[begin1++];
    while (begin2 <= end2)
        tmp[i++] = a[begin2++];
    //归并完后，拷贝回原数组
    int j = 0;
    for (j = left; j <= right; j++)
        a[j] = tmp[j];
}
//归并排序（主体函数）
void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int)*n);//申请一个与原数组大小相同的空间
    if (tmp == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    _MergeSort(a, 0, n - 1, tmp);//归并排序
    free(tmp);//释放空间
}

非递归实现

//归并排序（子函数）
void _MergeSortNonR(int* a, int* tmp, int begin1, int end1, int begin2, int end2)
{
    int j = begin1;
    //将两段子区间进行归并，归并结果放在tmp中
    int i = begin1;
    while (begin1 <= end1&&begin2 <= end2)
    {
        //将较小的数据优先放入tmp
        if (a[begin1] < a[begin2])
            tmp[i++] = a[begin1++];
        else
            tmp[i++] = a[begin2++];
    }
    //当遍历完其中一个区间，将另一个区间剩余的数据直接放到tmp的后面
    while (begin1 <= end1)
        tmp[i++] = a[begin1++];
    while (begin2 <= end2)
        tmp[i++] = a[begin2++];
    //归并完后，拷贝回原数组
    for (; j <= end2; j++)
        a[j] = tmp[j];
}
//归并排序（主体函数）
void MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int)*n);//申请一个与待排序列大小相同的空间，用于辅助合并序列
    if (tmp == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    int gap = 1;//需合并的子序列中元素的个数
    while (gap < n)
    {
        int i = 0;
        for (i = 0; i < n; i += 2 * gap)
        {
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            if (begin2 >= n)//最后一组的第二个小区间不存在或是第一个小区间不够gap个，此时不需要对该小组进行合并
                break;
            if (end2 >= n)//最后一组的第二个小区间不够gap个，则第二个小区间的后界变为数组的后界
                end2 = n - 1;
            _MergeSortNonR(a, tmp, begin1, end1, begin2, end2);//合并两个有序序列
        }
        gap = 2 * gap;//下一趟需合并的子序列中元素的个数翻倍
    }
    free(tmp);//释放空间
}

计数排序

原理：

简单理解：既然排序名字是计数排序，那么肯定要有统计数据这个过程。

下面先看一个简单的例子，咱们先用一种统计数据的方法对 3，2，2，5，4，0，5，4，5，1 这十个数排序。

经过观察发现，上面的十个数中，0出现了一次，1出现了一次，2出现了两次，3出现了一次，4出现了两次，5出现三次。

我们就可以用一个数组来存这些次数（数组下标代表存数的值，数组的值代表存了几次），

即count[0]=1，count[1]=1，count[2]=2，count[3]=1，count[4]=2，count[5]=3

然后再按顺序把这些统计的数打印出来是不是就完成了一个简单的排序？，下面看代码（我相信你一定能看懂）

//计数排序
void CountSort(int* a, int n)
{
    int min = a[0];
    int max = a[0];
    for (int i = 0; i < n; i++)
    {
        if (a[i] < min)
            min = a[i];
        if (a[i] > max)
            max = a[i];
    }
    int range = max - min + 1;
    int* count = (int*)calloc(range, sizeof(int));
    if (count == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    for (int i = 0; i < n; i++)
    {
        count[a[i] - min]++;
    }
    int i = 0;
    for (int j = 0; j < range; j++)
    {
        while (count[j]--)
        {
            a[i++] = j + min;
        }
    }
    free(count);//释放空间
}