数据结构（初阶）—— 排序算法（下）

一、冒泡排序

    **基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。**

1.动图演示

2.代码实现

// 冒泡排序
void Swap(int* px, int* py)
{
    int tmp = *px;
    *px = *py;
    *py = tmp;
}
void BubbleSort(int* a, int n)
{
    int end = n;
    while (end > 0)
    {
        int exchange = 0;
        for (int j = 0; j < end - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                exchange = 1;
                Swap(&a[j], &a[j + 1]);
            }
        }
        --end;
        if (exchange == 0)
        {
            break;
        }
    }
    /*for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                Swap(&a[j], &a[j + 1]);
            }
        }
    }*/
}

二、快速排序

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

基本思想如下：

1. 递归实现

1.Hoare版本（含动图演示）

**动图演示 **

**代码实现 **

int Partion1(int* a,int left,int right)
{
    int keyi = left;
    while (left < right)
    {
        //右边先走，找小
        while (a[right] > a[keyi])
        {
            --right;
        }
        //左边再走，找大
        while (a[left] < a[keyi])
        {
            ++left;
        }
        Swap(&a[left], &a[right]);
    }
    Swap(&a[left], &a[keyi]);

    return left;
}

上述代码存在两大缺陷:

场景1：

如果是一个有序的数组（升序），每个数都比第一个数大，小黄就没人管了，撒开腿就一直跑；

** 场景2：**

如果这个数组元素都相同，小黄先跑，发现跑不动；（死循环）

** 针对刚才的代码很明显在这两种场景下一定会出问题；**

如何解决：

1.确保** 右边找小**** 或 左边找大 的时候，判断它（小黄或小白）的下标有没有越界；**

2.要考虑元素相等的情况；

int Partion1(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[left], &a[keyi]);

    return left;
}

** 单趟排序完成之后，比key大的数都放在右边，比key小的数都放在右边，只要以key为基准值，它的左子区间再有序，右子区间再有序，那么整体就有序了；这种问题和二叉树很类似；第一趟排序找了一个key，分成了左右区间，只要为左右区间各找一个key，不断的去划分，那么久把整个数组排序完成了；**

int Partion1(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[left], &a[keyi]);

    return left;
}
void QuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;
        int keyi = Partion1(a, left, right);/*hoare版本*/
        //区间划分[begin , keyi-1] keyi [keyi+1 , end]
        QuickSort(a, left, keyi - 1);//左子区间
        QuickSort(a, keyi + 1, right);//右子区间
    }
}

如何定位基准值（key）：

** 先看下面的图例，发现快排在针对无序的数组进行排序时，它的效率是很快的，但是在有序或接近有序的情况下，就会变得很糟糕；这里最关键的就是key的选择问题； 也就是如何针对快排对于数组有序情况下选key的问题；**

为了解决选key的问题，可以采用三数取中法；

三数取中法：最左边的数、中间数、最右边的数；

对这三个数进行比较，选出一个中间值(既不是最大也不是最小)，作为key； 那么针对于有序的情况，就会瞬间变得很好，直接将数据二分；

** 快排完整动图**

**代码实现 **

/*hoare版本*/
//快排（递归）

//三数取中
int GetMidIndex(int* a, int left, int right)
{
    //int mid = (left + right) / 2;
    int mid = left + ((right - left) >> 1);
    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 Partion1(int* a,int left,int right)
{
    //三数取中
    /*int mini = GetMidIndex(a, left, right);
    Swap(&a[mini], &a[left]);*/

    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[left], &a[keyi]);

    return left;
}
//O(N*logN)
void QuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;
    //小区间优化，当分割到小区间时，不在用递归思路让这段子区间有序
    //对于递归快排，减少递归次数
    if (right - left + 1 < 10)
    {
        InsertSort(a + left, right - left + 1);
    }
    else
    {
        int keyi = Partion1(a, left, right);/*hoare版本*/
        //区间划分[begin , keyi-1] keyi [keyi+1 , end]
        QuickSort(a, left, keyi - 1);
        QuickSort(a, keyi + 1, right);
    }
}

在上面的代码中有这样一段代码：

    if (right - left + 1 < 10)
    {
        InsertSort(a + left, right - left + 1);
    }
    else
    {
        int keyi = Partion1(a, left, right);/*hoare版本*/
        //区间划分[begin , keyi-1] keyi [keyi+1 , end]
        QuickSort(a, left, keyi - 1);
        QuickSort(a, keyi + 1, right);
    }

由于采用递归的方式进行快排，如果数据量很大，就会造成栈的溢出；为了解决这个问题，采用了一个小区间优化的方法，在不断划分区间去进行递归的时候，越往下划分区间越来越小，但是区间数量越来越多，递归次数也越来越多；我们采取当区间相差小于10（最低给10）时，直接让这些区间的数据进行直接插入排序；

2.挖坑法 （含动图演示）

1.基本思路：

** 先将第一个变量存储在临时变量key中，右边先走，去找小扔到左边的坑，自己成为新的坑；然后左边再走，去找大扔到右边的坑(pivot)，自己成为新的坑(pivot)；直到两者相遇把保存的key的值放进坑(pivot)；**

**2.动图演示 **

下图为挖坑法的单趟演示，其完整排序和上面的快排完整版类似，需要划分左右子区间； 进行递归调用；

3.代码实现

//挖坑法

//三数取中
int GetMidIndex(int* a, int left, int right)
{
    //int mid = (left + right) / 2;
    int mid = left + ((right - left) >> 1);
    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 Partion2(int* a, int left, int right)
{
    //三数取中
    int mini = GetMidIndex(a, left, right);
    Swap(&a[mini], &a[left]);

    int key = a[left];
    int pivot = left;
    while (left < right)
    {
        //右边找小，扔到左边的坑
        while (left < right && a[right] >= key)
        {
            --right;
        }
        a[pivot] = a[right];
        pivot = right;//自己形成新的坑

        //左边找大，扔到右边的坑
        while (left < right && a[left] <= key)
        {
            ++left;
        }
        a[pivot] = a[left];
        pivot = left;//自己形成新的坑
    }
    a[pivot] = key;
    return pivot;
}
void QuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;
    //小区间优化，当分割到小区间时，不在用递归思路让这段子区间有序
    //对于递归快排，减少递归次数
    if (right - left + 1 < 10)
    {
        InsertSort(a + left, right - left + 1);
    }
    else
    {
        //int keyi = Partion2(a, left, right);//挖坑法
        //区间划分[begin , keyi-1] keyi [keyi+1 , end]
        QuickSort(a, left, keyi - 1);
        QuickSort(a, keyi + 1, right);
    }
}

3.前后指针法 （含动图演示）

1.基本思路：

** 前后指针法的基本思想其实和前面两种方法类似，cur去找小，prev去找大；也会得到key的左边是小值右边是大值；**

2.代码实现

//前后指针法

//三数取中
int GetMidIndex(int* a, int left, int right)
{
    //int mid = (left + right) / 2;
    int mid = left + ((right - left) >> 1);
    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 Partion3(int* a, int left, int right)
{
    //三数取中
    int mini = GetMidIndex(a, left, right);
    Swap(&a[mini], &a[left]);
    int keyi = left;
    int prev = left;
    int cur = left +1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi] && ++prev != cur)
        {
            Swap(&a[cur], &a[prev]);
        }
        cur++;
    }
    Swap(&a[prev], &a[keyi]);
    return prev;
}
void QuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;
    //小区间优化，当分割到小区间时，不在用递归思路让这段子区间有序
    //对于递归快排，减少递归次数
    if (right - left + 1 < 10)
    {
        InsertSort(a + left, right - left + 1);
    }
    else
    {
        int keyi = Partion3(a, left, right);//前后指针法
        //区间划分[begin , keyi-1] keyi [keyi+1 , end]
        QuickSort(a, left, keyi - 1);
        QuickSort(a, keyi + 1, right);
    }
}

2.非递归实现

1.基本思路

**快排的递归实现，由于存在栈溢出的可能性；往往需要用模拟栈来实现非递归； **

** 给定一个N个数据的数组，其下标范围为[ 0,N-1 ],将这段区间入栈，然后出栈去找key，划分左右区间，因为栈的特点是后进先出，将这两个区间看做两个的整体，那么这两个区间入栈的顺序就是先入右子区间，再入左子区间；（详解如下）**

其实整体的思路和递归很类似，但本质上是循环迭代的过程； 也是通过找key划分区间，每次划分出来的区间都去找key，每个区间key的左边都比key小，右边都比key大，直到不可划分为止，那么整个数组就排序完成了；

2.代码实现

//快排（非递归）
void QuickSortNonR(int* a, int left, int right)
{
    ST st;
    StackInit(&st);
    //先入0-9区间
    StackPush(&st, left);
    StackPush(&st, right);
    while (!StackEmpty(&st))
    {
        //取出0-9区间
        int end = StackTop(&st);
        StackPop(&st);
        int begin = StackTop(&st);
        StackPop(&st);
        //找中间基准值、划分左右区间
        int keyi = Partion3(a, begin, end);
        //[begin,keyi-1] keyi [keyi+1,end]
        //先入右区间
        if (keyi + 1 < end)
        {
            StackPush(&st, keyi + 1);
            StackPush(&st, end);
        }
        //再入左区间
        if (begin < keyi - 1)
        {
            StackPush(&st, begin);
            StackPush(&st, keyi - 1);
        }
    }
    StackDestroy(&st);
}

三、归并排序

1.递归实现

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

代码实现

//归并排序(递归)
//时间复杂度：O(N*logN)
//空间复杂度：O(N)
void _MergeSort(int* a, int left, int right, int* tmp)
{
    if (left >= right)
    {
        return;
    }
    int mid = (left + right) / 2;
    //如果[left,mid]  [mid+1,right]有序
    _MergeSort(a, left, mid, tmp);//归并左区间
    _MergeSort(a, mid+1, right, tmp);//归并右区间
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int i = left;
    //进行合并
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
        {
            tmp[i++] = a[begin1++];
        }
        else
        {
            tmp[i++] = a[begin2++];
        }
    }
    //在合并的时候，存在某个区间数组未合并完的情况
    while (begin1 <= end1)
    {
        tmp[i++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[i++] = a[begin2++];
    }
    //tmp数组的值拷贝回a数组中
    for (int 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);
    tmp = NULL;
}

2.非递归实现

1.方法1：分组归并、整体拷贝——边界控制的阐述

1.基本思路：

** 2.边界控制**

    **上图进行gap分组依次归并，可以看出：两个数据归并——>四个数据归并——>八个数据归并——>归并结束，排序完成；也就说明这种非递归的思想只适用于数组元素个数是2^n；**

** 针对数组元素个数非2^n时，要对其边界进行控制，这也是归并排序的一个难点；整体的框架可能大家都理解，利用临时的tmp数组，然后把待排序数组拆分成两个数组，依次取遍历两个数组，哪个小就先入tmp数组，可能存在没入完的数组，再将剩下的全部入tmp数组；**

假设现有一个9个元素的数组，如何对其进行边界控制？

以gap=gap*2（gap>=1）的增长方式进行每组的归并操作，首先将数组分成两个区间，分别表示为[ begin1，end1 ]和[ begin2，end2 ];

如图所示：

** 这两个区间，在gap的以2倍的变化中且与元素个数存在一定的关系，我们需要利用这两个区间加上tmp数组的利用，进行归并操作；那么就必须保证这两个区间是有效的（区间一定要有数据）；因为在遍历数组的过程中，两个区间时时发生变化，就存在以下三种情况：**

具体情况具体分析：

情况1：

** 此时****[ begin2, end2 ]=[ 9, 9 ]，此区间是不存在元素的；根据归并的思想：把数据入tmp数组，再拷贝回原数组；就入数据而言，是对这两个区间的元素大小进行判断，既然此时只有一个区间有元素，那么就可以把没有元素的区间进行修正，修正为不存在的区间；元素个数n=9，将end2修正为8（end=n-1），那么就不存在这样的区间，就会把[ begin1, end1 ]=[ 8, 8 ]**的数据入到tmp数组中去；能不能

情况2：

此时[ begin1, end1 ]=[ 8, 9 ]，[ begin2, end2 ]=[ 10, 11 ]；**[ begin2, end2 ]区间不存在元素，虽然在情况1的基础上将其修改为不存在的区间，但是[ begin1, end1 ]有两个元素，一个是2，一个是随机值，当数据入tmp数组时，会把这个随机值带入，并拷贝回原数组；此时数组已经越界，一定会存在错误；此时还要将end1修正为8（end=n-1），那么此区间就只有一个元素了，就不会出现数组越界的情况；**

情况3：

​​​​​

此时**[ begin2, end2 ]=[ 8, 15 ]**，此区间是不存在元素的；还需要将end2进行修正，修正为8（end=n-1）；也是由于此区间存在3个随机值，修正的目的就是让此区间只有一个明确的值存在的值，确保数组不越界；

以上就是针对数组元素个数非2^n时的边界控制，只要掌握归并排序的边界控制，其代码实现就变得容易许多；

**代码实现 **

//归并排序(非递归)----适用于2的n次方
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)
    {
        for (int i = 0; i < n; i += 2 * gap)
        {
            //区间范围[i,i+gap-1] [i+gap,i+2*gap-1]
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;

            /*******************************重要*****************************/
            //end1越界 [begin2,end2]不存在
            if (end1 >= n)
            {
                //进行修正
                end1 = n - 1;
            }

            // [begin1,end1]存在,[begin2,end2]不存在
            if (begin2 >= n)
            {
                //进行修正
                begin2 = n;
                end2 = n - 1;
            }

            //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++];
            }
        }
        //printf("\n");
        //把归并好的数据拷贝回原数组
        for (int i = 0; i < n; ++i)
        {
            a[i] = tmp[i];
        }
        gap *= 2;
    }

    free(tmp);
    tmp = NULL;
}

3.方法2：分组归并、逐次归并拷贝——边界控制的阐述

**1.基本思路： **

**2.边界控制 **

** 假设现有一个9个元素的数组，如何对其进行边界控制？**

以gap=gap*2（gap>=1）的增长方式进行每组的归并操作，首先将数组分成两个区间，分别表示为[ begin1，end1 ]和[ begin2，end2 ];

如图所示：

    **与方法一不同的是，此方法不需要整体归并完后拷贝到原数组中去，而是归并一次拷贝一次，所有并不需要考虑原数组中数字2会被覆盖为随机值的情况；但是对于边界的问题在循环迭代的过程中，依然存在如下几中情况：**

情况1：

** 因为是归并一次数据就拷贝回原数组，所以并不会影响到原数组末尾的2；此时end越界，将end修正，修正为8（end=n-1）；**

**情况2与情况3： **

** 这两种情况在end2修正后，end1和begin2存在越界，因为是归并一次数据就拷贝回原数组，所以并不会影响到原数组末尾的2；所以只要当end1和begin2越界时，让其不执行拷贝的操作就可以了（即代码实现时让其遇到此情况就跳出循环，去执行下一次gap分组）**

**代码实现 **

/*第二种*/
void MergeSortNonR2(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)
    {
        for (int i = 0; i < n; i += 2 * gap)
        {
            //[i,i+gap-1] [i+gap,i+2*gap-1]
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            int index = i;

            //核心思想：end1、begin2、end2都有可能越界
            //end1越界
            if (end1 >= n || begin2 >= n)
            {
                break; 
            }
            //end2越界,需要归并，修正end2
            if (end2>=n)
            {
                end2 = n - 1;
            }

            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++];
            }
            //把归并好的数据拷贝回原数组
            for (int j = i; j <= end2; ++j)
            {
                a[j] = tmp[j];
            }
        }
        gap *= 2;
    }
    free(tmp);
    tmp = NULL;
}

四、计数排序

1.基本思想

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

** 1. 统计相同元素出现次数；**

** 2. 根据统计的结果将序列回收到原来的序列中；**

**注意： **

如果是这样的数组进行计数排序，按照上图所说这里count数组空间就开辟1501个空间，但是这个待排序数组只有7个元素，那么前面的1000个空间就浪费了，为了解决这样的问题，在开辟空间上可以采用：最大值-最小值+1的方式进行空间开辟****（1500-1000+1=501）；

2.动图演示

3.代码实现

//计数排序
void CountSort(int* a, int n)
{
    int max = a[0], min = a[0];
    //找出最大值和最小值
    for (int i = 1; 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);
    memset(count, 0, sizeof(int) * range);//将count数组元素全部置为0
    if (count == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    //统计次数
    for (int i = 0; i < n; ++i)
    {
        count[a[i] - min]++;
    }
    //根据次数，进行排序
    int j = 0;
    for (int i = 0; i < range; ++i)
    {
        while (count[i]--)
        {
            a[j++] = i + min;
        }
    }
}

五、排序算法总结

1.时间及空间复杂度

排序方式平均情况最好情况最坏情况辅助空间稳定性*冒泡排序***O(N^2)****O(N)****O(N^2)*O(1)稳定简单选择排序*O(N^2)****O(N^2)****O(N^2)*O(1)不稳定直接插入排序*O(N^2)****O(N)***O(N^2)*O(1)稳定希尔排序*O(NlogN)O(N^2)****O(N^1.3)***O(N^2)*O(1)不稳定堆排序*O(NlogN)***O(NlogN)***O(N^2)*O(1)不稳定归并排序*O(NlogN)***O(NlogN)***O(NlogN)*O(N)稳定快速排序*O(N*logN)***O(NlogN)****O(N^2)****O(logN)O(N)**不稳定

2.排序算法的稳定性

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[ i ] = r[ j ]，且r[ i ]在r[ j ]之前，而在排序后的序列中，r[ i ]仍在r[ j ]之前，则称这种排序算法是稳定的；否则称为不稳定的。

---

1.稳定的排序

**冒泡排序、直接插入排序、归并排序； **

2.不稳的排序

**选择排序、希尔排序、堆排序、快排、计数排序； **