0
0

＜ 数据结构 ＞ 八大排序

常见算法排序概览

1、直接插入排序

  • 基本思想：

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

  • 动图演示：

  • 解释其过程：

插入排序，听名字就觉着是有一串数字，随后插入了1个数字，并将其排成有序，是这样吗？当然不是，但是抽象来看确实有点道理。

  • 假如我们已经有一串有序的数字【2，3，5，10，11】，现在想再插入一个数字7使其仍然有序，该如何比呢？

实现过程很简单，只需要拿数组依次从后往前跟插入的数字比较，如果插入的数字比原有序数字最后一个的值小，那把最后一个数字往后挪，此时会出现一个空位，当挪到插入的数字放到空位刚好有序时停止，如下图示：

  • 但是上述情况仅支持其是有序的情况下，如果原本给出的一串数字是无序呢？如何利用插入排序？如下列一串乱序数字：

解法很简单，既然给定的一串数字是无需的，那就把第一个数字看成有序并用变量tmp将其保存起来，把第二个数字看成是插入进去的数字进行挪动排序覆盖像上文一样，排好了前两个数字，再把第三个数字看成是插入进去的数字进行挪动排序覆盖，此时前三个数字就有序了，依次类推，最终数字均是有序的。

  • 动图演示：

现在再来看直接插入排序似乎也没这么难，也就是把原数字的从第1个数字开始就看作有序，每次把后面的数字看成要插入的，然后进行排序，随后以此类推，继续看作有序，继续插入……直至数字全部插入进去。

  • 总代码如下：
//直接插入排序
void InsertSort(int* a, int n)
{
    // i的取值范围：[0,n-2]
    for (int i = 0; i < n - 1; i++)
    {
        //每一趟排序
        int end = i;
        int tmp = a[end + 1]; //将tmp视为插入的数字
        while (end >= 0)
        {
            if (tmp < a[end]) //若插入的数字小于有序数字的最后一个数
            {
                a[end + 1] = a[end]; //将大于tmp的值往后挪
                --end;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

直接插入排序特性总结

1、元素集合越接近有序，直接插入排序算法的时间效率越高

2、时间复杂度：O(N^2)

3、空间复杂度：O(1)，它是一种稳定的排序算法

4、稳定性：稳定

2、希尔排序

  • 基本思想：

希尔排序其实是建立在直接插入排序的基础上进行的优化，希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

而上述操作可以分为两大部分：

  1. 预排序
  2. 直接插入排序

假如有这样一串乱序数组：

希尔排序的预排序就是让大的数尽快到后面去，小的数尽快到前面去，以此接近有序。而预排序利用的又是分组排。比如说它给出的间隔gap为3，那么上述中，【9，5，8，5】这4个数就分为一组，【1，7，6】这3个数分为一组，【2，4，3】分为一组。总的来说：gap为几，这里就会分割成几组数据。分组后如下图：

接下来分别对每一组进行插入排序的思想对这gap组数据进行排序。

既然是分组进行插入排序，那就好办了，像第一组：【9，5，8，5】排序后为【5，5，8，9】，第二组【1，7，6】排序后为【1，6，7】，第三组【2，4，3】排序后为【2，3，4】，如图所示：

  • 动图演示其过程：

  • 代码演示预排序：
void ShellSort(int* a, int n)
{
    int gap = 3;
    for (int j = 0; j < gap; j++)
    {
        //控制gap组都进行预排序
        for (int i = j; i < n - gap; i += gap)
        {
            //确保一组中的数据都进行插入排序
            int end = i;
            //定义一个变量tmp保存end的后一个数,其下标是end+gap
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + gap] = a[end];//如果end下标的数值大于后面的值tmp，也就意味着end下标的值要往后挪
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            //单趟循环结束或循环中直接break出来均直接赋值
            a[end + gap] = tmp;
        }
    }
}

这里可以看出第一次预排成功，达到想要的效果了，但是此段代码我们套了三层循环，可以对它进行优化

  • 多组并列预排序：

只需要把第二层的for循环中的i+=gap变化为i++即可，i+=gap再和第一层循环结合的目的是，每一组进行排序，排好了进入下一组。而现在省去第一趟循环，把第二趟的条件改为i++，恰好实现了多组并列进行预排序

  • 动图演示：

  • 代码如下：
//希尔排序
void ShellSort(int* a, int n)
{
    int gap = 3;
    //控制gap组都进行预排序
    for (int i = 0; i < n - gap; i++)
    {
        //确保一组中的数据都进行插入排序
        int end = i;
        //定义一个变量tmp保存end的后一个数,其下标是end+gap
        int tmp = a[end + gap];
        while (end >= 0)
        {
            if (a[end] > tmp)
            {
                a[end + gap] = a[end];//如果end下标的数值大于后面的值tmp，也就意味着end下标的值要往后挪
                end -= gap;
            }
            else
            {
                break;
            }
        }
        //单趟循环结束或循环中直接break出来均直接赋值
        a[end + gap] = tmp;
    }
}
  • 注意：
  1. gap为1，它就是直接插入排序
  2. 如果gap越小，越接近有序
  3. 如果gap越大，大的数据可以更快到最后，小的数可以更快到前面，但是它越不接近有序

现在我们面临一个问题：gap到底取值多少？

如果gap给小了，并且数组情况最坏是逆序且数组很长，那么大的数想要到后面就要跳很多次，如果gap越小，那么还用希尔排序干啥呢？直接用插入排序（冒泡也不是不行！doge ！）综上，我们可以再套一层循环，此循环不光接近gap的问题，还实现了多次预排直至排序结束达到最终效果

    //1、gap > 1 预排序
    //2、gap == 1 直接插入排序
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1; //+1能够保证最后一次gap一定是1
        //…… 预排序
    }

这里我们可以看到这样一个循环，实现了多组预排序直至最终效果，我们控制gap要分类，当gap > 1就继续预排序，当gap == 1就插入排序，而 gap = gap / 3 + 1足矣满足上述要求，或者说gap=n/2，gap/=2;这行代码也可以实现。仔细体会这行代码。

  • 总代码如下：
//希尔排序
void ShellSort(int* a, int n)
{
    //1、gap > 1 预排序
    //2、gap == 1 直接插入排序
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1; //+1能够保证最后一次gap一定是1
        //控制gap组都进行预排序
        for (int i = 0; i < n - gap; i++)
        {
            //确保一组中的数据都进行插入排序
            int end = i;
            //定义一个变量tmp保存end的后一个数,其下标是end+gap
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + gap] = a[end];//如果end下标的数值大于后面的值tmp，也就意味着end下标的值要往后挪
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            //单趟循环结束或循环中直接break出来均直接赋值
            a[end + gap] = tmp;
        }
    }
}

  • 针对上述代码我们重新画一张图演示：

希尔排序特性总结

1、希尔排序是对直接插入排序的优化。

2、当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3、稳定性：不稳定

4、时间复杂度分析：

希尔排序的时间复杂度不是很好算，我们先简要看下预排序的时间复杂度：

  1. gap很大时，数据跳的很快，里面套的循环可以忽略不记，差不多是O(N)。
  2. gap很小时，数据跳的很慢，很接近有序，差不多也是O(N)

再来看外面套上循环后的时间复杂度：

while循环中的gap = gap / 3 + 1相当于是循环了log{_{3}}^{N}次

既然外循环执行log_{3} ^{ N}次，内循环执行N次，那么时间复杂度为O(N*log{_{3}}^{N})。但是上述计算顶多是估算，有人在大量的实验基础上推出其时间复杂度应为：O(N^{1.3})

3、选择排序

  • 动图演示：

  • 基本思想：

遍历一遍数组选出最小的放在前面，剩下的数再遍历一遍，再选出小的放前面，以此类推直至遍历完毕排序结束。如下的一串数组：

虽说是遍历一遍，选出最小的数放在最前面，但并不是覆盖到最前面，而是进行交换。比如说我遍历了一遍，最小为1，跟第一个9交换，再从剩下的选出最小的2放到第二个位置……

  • 这里我们做出一点改动进行优化：

遍历一次，选出两个数，最小的和最大的，最小的放到第一个位置，最大的放到最后一个位置，随后缩小区间，在这个区间内重复上述操作。

  • 画图演示：

  • 代码演示：
//直接选择排序
void SelectSort(int* a, int n)
{
    int left = 0;
    int right = n - 1;
    while (left < right)
    {
        int mini = left, maxi = left;
        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重叠，修正下maxi即可
        if (left == maxi)
        {
            maxi = mini;
        }
        Swap(&a[right], &a[maxi]);
        //交换完后，缩小区间
        left++;
        right--;
    }
}

选择排序特性总结

1、直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

2、时间复杂度：O(N^2)

3、空间复杂度：O(1)

4、稳定性：不稳定

4、堆排序

堆排序我在上篇博文已经重点讲解过，这里简要提下

  1. 对数组建堆要向下建堆，因为其时间复杂度小
  2. 排升序要建大堆，排降序建小堆

如若各位小伙伴们还有些疑问，可以看这篇博文

堆排序 + topK问题

  • 这里直接给出代码：
//交换
void Swap(int* pa, int* pb)
{
    int tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}
//向下调整算法
void AdjustDown(int* a, size_t size, size_t root)
{
    int parent = (int)root;
    int child = 2 * parent + 1;
    while (child < size)
    {
        //1、确保child的下标对应的值最大，即取左右孩子较大那个
        if (child + 1 < size && a[child + 1] > a[child]) //得确保右孩子存在
        {
            child++; //此时右孩子大
        }
        //2、如果孩子大于父亲则交换，并继续往下调整
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}
//升序
void HeapSort(int* a, int n)
{
    //向下调整建堆
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }
    //大堆升序
    size_t end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
}
int main()
{
    int a[] = { 4,2,7,8,5,1,0,6 };
    HeapSort(a, sizeof(a) / sizeof(int));
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

堆排序特性总结

1、堆排序使用堆来选数，效率就高了很多。

2、时间复杂度：O(N*logN)

3、空间复杂度：O(1)

4、稳定性：不稳定

5、冒泡排序

  • 基本思想：

冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。元素项向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。

  • 排序步骤：
  1. 相邻的两个元素比较，大的上浮，小的下沉，这样一趟冒泡排序即可确保大值排列在一端
  2. 确定趟数，趟数为数组总个数-先前排过的趟数
  • 动图演示：

  • 代码如下：
//交换
void Swap(int* pa, int* pb)
{
    int tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}
//冒泡排序
void BubbleSort(int* a, int n)
{
    for (int j = 0; j < n; j++)
    {
        //单趟
        for (int i = 1; i < n - j; i++)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i], &a[i - 1]);
            }
        }
    }
}
  • 冒泡排序的优化：

根据上述代码，有个缺陷：如果我的数组本身就有序或着说是接近有序，那我还需要每一趟都进去比较相邻两个数字的大小吗？如果每次都要比，那时间复杂度就要提升，为此可以定义一个变量exchange，如果说发生了比较，那么exchange的值保存为1，如果没有比较，则exchange为0，就退出

  • 总代码如下：
//交换
void Swap(int* pa, int* pb)
{
    int tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}
//冒泡排序
void BubbleSort(int* a, int n)
{
    for (int j = 0; j < n; j++)
    {
        int exchange = 0;
        //单趟
        for (int i = 1; i < n - j; i++)
        {
            if (a[i - 1] > a[i])
            {
                exchange = 1;
                Swap(&a[i], &a[i - 1]);
            }
            if (exchange == 0)
                break;
        }
    }
}

冒泡排序特性总结

1、冒泡排序是一种非常容易理解的排序

2、稳定性：稳定

3、空间复杂度：O(1)

4、时间复杂度：O(N^2)

最好情况：数组本身是顺序的，外层循环遍历一次就完成O(N)

最坏情况：数组本身是逆序的，内外层遍历O(N^2)

6、快速排序

  • 基本思想：

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

快速排序分为三种方法

  1. hoare法
  2. 挖坑法
  3. 前后指针法

而其右可以使用递归和非递归来实现，接下来我将依次演示：

hoare法

  • 单趟动图演示：

hoare法的快排分为以下步骤：

  1. 选出一个key，一般是第一个数，或者是最后一个数
  2. 定义变量L和R，L从左走，R从右走
  3. R先向前走，找到比key小的位置停下，再让L向后走，找到比key大的值停下
  4. 交换L和R代表的数值
  5. 继续遍历，同样让R先走，L后走，同上规则
  6. 当L和R相遇的时候，把相遇位置的值与key位置的值交换，结束

排完一趟要求如下：

  1. 左边的值都比key小
  2. 右边的值都比key大

提问：如何保证相遇位置的值比key小？

  • 答案：不需要保证，此算法思想（右边先走）足矣解决。注意看本算法思想，它明确了每次让R先走，R找到比key小的值之后才会停下来，这时候才轮到L走，L要么找不到比key大的值就一直走直至相遇R，此时正好满足小于key，要么L找到比key大，交换L和R的值，但随后，R又会继续向前走，一直走，最坏刚好遇到L，因为L先前和R已经换过一次，也就是说这个L的值一定是比key小的，那么同样交换key的值，综上，此算法思想足矣解决。

提问：如若key为最右边的值呢？排完一趟如何？

思想和上面一样，唯一要改变的是此时是L先走，R后走，其余没有变

  • 动图演示：

  • 接下来，就先写下单趟排序：
//快排单趟排序
int PartSort(int* a, int left, int right)
{
    int keyi = left; //选左边作key
    while (left < right)
    {
        //右边先走，找小
        while (left < right && a[right] >= a[keyi]) //防止right找不到比keyi小的值直接飙出去，要加上left < right
        {
            right--;
        }
        //右边找到后，左边再走，找大
        while (left < right && a[left] <= a[keyi]) //同上，也要加上left < right
        {
            left++;
        }
        //右边找到小，左边找到大，就交换
        Swap(&a[left], &a[right]);
    }
    //此时left和right相遇，交换与key的值
    Swap(a[keyi], &a[left]);
    return left;
}
  • 写好了单趟排序，就要进行整体排序了

仔细观察上述单趟排序，有没有发现排完后，key已经排到了正确的位置，因为其左边的值均小于key，而右边的值均大于key，此时key的位置就是最终排序好后应该在的位置。那么如果左边有序，右边有序，那么整体就有序了，只需要用到递归+分治的思想即可。

  • 画图演示：

  • 总代码如下：
//hoare
//快排单趟排序
int PartSort(int* a, int left, int right)
{
    int keyi = left; //选左边作key
    while (left < right)
    {
        //右边先走，找小
        while (left < right && a[right] >= a[keyi]) //防止right找不到比keyi小的值直接飙出去，要加上left < right
        {
            right--;
        }
        //右边找到后，左边再走，找大
        while (left < right && a[left] <= a[keyi]) //同上，也要加上left < right
        {
            left++;
        }
        //右边找到小，左边找到大，就交换
        Swap(&a[left], &a[right]);
    }
    //此时left和right相遇，交换与key的值
    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+1, end]
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}

挖坑法

  • 动图演示单趟挖坑：

挖坑法的步骤如下：

  1. 把最左边的位置用key保存起来，此位置形成坑位
  2. 定义变量L和R分别置于最左和最右
  3. 让R先向前走，找到比key小的位置停下
  4. 找到后，将该值放入坑位，自己形成新的坑位
  5. 再让L向后走，找比key大的位置停下
  6. 找到后，将该值放入坑位，自己形成新的坑位
  7. 再让R走……
  8. 当L和R相遇时，把key的值放到坑位，结束

挖坑法相较于上面的hoare法并没有优化，本质上也没有区别，但是其思想更好理解

  1. 不需要理解为什么最终相遇位置比key小
  2. 不需要理解为什么左边做key，右边先走
  • 总代码如下：
//挖坑法
int PartSort2(int* a, int left, int right)
{
    //把最左边的值用key保存起来
    int key = a[left]; 
    //把left位置设为坑位pit
    int pit = left;
    while (left < right) //当left小于right时就继续
    {
        //右边先走，找小于key的值
        while (left < right && a[right] >= key)
        {
            right--; //如若right的值>=key的值就继续
        }
        //找到小于key的值时就把此位置赋到坑位，并把自己置为新的坑位
        a[pit] = a[right];
        pit = right;

        //左边走，找大于key的值
        while (left < right && a[left] <= key)
        {
            left++;
        }
        //找到大于key的值就把此位置赋到坑位，并把自己置为新的坑位
        a[pit] = a[left];
        pit = left;
    }
    //此时L和R相遇，将key赋到坑位
    a[pit] = key;
    return pit;
}

//快速排序
void QuickSort(int* a, int begin, int end)
{
    //子区间相等只有一个值或者不存在那么就是递归结束的子问题
    if (begin >= end)
    {
        return;
    }
    int keyi = PartSort2(a, begin, end);
    //分成左右两段区间递归
    // [begin, keyi-1] 和 [keyi+1, end]
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}

前后指针法

  • 动图演示：

前后指针法的步骤如下：

  1. 把第一个位置的值设为key保存起来
  2. 定义prev指针指向第一个位置，cur指向prev后一个位置
  3. 若cur指向的数值小于key，prev和cur均后移
  4. 当cur指向的数据大于key时，prev不动，cur继续后移
  5. 当cur的值小于key时，prev后移一位，交换与cur的值，cur再++
  6. 重复上述操作，当cur越界时，交换此时的prev和key的值。结束

总的来说，cur是在找小，找到后就++prev，prev的值无论怎么走都是小于key的值的，当cur找到大与key时，cur的后面紧挨着的prev是小于key的，接下来让cur++到小于key的值，此过程间prev始终不动，唯有cur找到了小于key的值时，让prev再++，此时的prev就是大于key的值了，仔细揣摩这句话，随后交换cur和prev的值，上述操作相当于是把小于key的值甩在左边，大于key的值甩在右边。

  • 总代码如下：
//前后指针法
int PartSort3(int* a, int left, int right)
{
    int key = left;//注意不能写成 int key = a[left]
    int prev = left;
    int cur = prev + 1;
    while (cur <= right)
    {
        if (a[cur] < a[key] && a[++prev] != a[cur]) 
        {
            Swap(&a[prev], &a[cur]);//在cur的值小于key的值的前提下，并且prev后一个值不等于cur的值时交换，避免了交换两个小的（虽然也可以，但是没有意义）
        }
        cur++; //如若cur的值大于key，则cur++
    }
    Swap(&a[prev], &a[key]); //此时cur越界，直接交换key与prev位置的值
    return prev;
}

//快速排序
void QuickSort(int* a, int begin, int end)
{
    //子区间相等只有一个值或者不存在那么就是递归结束的子问题
    if (begin >= end)
    {
        return;
    }
    int keyi = PartSort2(a, begin, end);
    //分成左右两段区间递归
    // [begin, keyi-1] 和 [keyi+1, end]
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}

提问：如若把key设定为最后一个数据呢？该如何控制？

总的来说有三处发生变动：

  1. cur和prev初始时的位置：先前定义的prev是第一个数据，cur是prev的后一个，而现在，cur是第一个位置，而prev是cur的前一个，相当于是初始时整体后移一位
  2. 停止的条件：原先的cur有效范围是整个数组，现在的cur有效范围是前n-1个数组，省去最后一个定为key的值
  3. 交换与key的值的条件：先前是cur越界时，直接交换prev与key的值，现在是先++prev，再交换与key的值，（因为此时的prev值依旧小于key，要++后才大于key）

除了这三处有所变动外，别的没有什么变动，交换的过程步骤都是一样的。

  • 动图演示：

  • 代码如下：
//前后指针法key在右边
int PartSort3(int* a, int left, int right)
{
    int key = right;
//变动1：    int prev = left - 1;  //先前 int prev =left;   int cur = left + 1;
    int cur = left;
//变动2：    while (cur < right)  //先前 while (cur <= right) 
    {
        if (a[cur] < a[key] && a[++prev] != a[cur]) 
        {
            Swap(&a[prev], &a[cur]); 
        }
        cur++;  
    }
//变动3：    Swap(&a[++prev], &a[key]); //先前Swap(&a[prev], &a[key]);
    return prev;
}

//快速排序
void QuickSort(int* a, int begin, int end)
{
    //子区间相等只有一个值或者不存在那么就是递归结束的子问题
    if (begin >= end)
    {
        return;
    }
    int keyi = PartSort3(a, begin, end);
    //分成左右两段区间递归
    // [begin, keyi-1] 和 [keyi+1, end]
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}

快排特性总结

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

2、稳定性：不稳定

3、空间复杂度：O(logN)

4、时间复杂度：O(N*logN)

快排的时间复杂度分两种情况讨论：

  1. 最好：每次选key都是中位数，通俗讲是左边一半右边一半，具体看是key的左序列长度和右序列长度相同。时间复杂度O(N*logN)
  2. 最坏：每次选出最小的或者最大的作为key。时间复杂度O(N^{2})
  • 画图分析：

可能有人会觉着正常的数组怎么会次次都会选出最小的或者最大的作为key呢？这也太巧合了，但是仔细想想，当数组是有序或者接近有序时，不就是最坏的情况吗？更何况如若数据量再大一点，程序很有可能会因为数据量过多而递归次数过多以至于栈溢出，

综上我们需要深思：能否针对快排最坏的情况进行优化？看下文：

快排优化

就以最坏的情况为例：

三数取中

对于我们自己来说，是很清楚其是有序的，可计算机并不清楚，它依旧是选取最左边或者最右边作为key，如果key不是取最小或者最大的，取出的值是介于之间的，那么情况也会好很多，至此：引出三数取中

  • 规则：

取第一个数，最后一个数，中间那个数，在这三个数中选不是最大也不是最小的那个数作为key。此法针对有序瞬间从最坏变成最好，针对随机数，那么选出来的数也同样不是最大也不是最小，同样进行了优化。

三数取中其实针对hoare法，挖坑法，前后指针法都适用，这里我们就以前后指针法示例：

  • 总代码如下：
//快排
//三数曲中优化
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]) // left < mid < right
            return mid;
        else if (a[left] < a[right]) // left < right <mid
            return right;
        else  // right < left < mid
            return left; 
    }
    else // left > mid
    {
        if (a[right] > a[left]) // right > left > mid
            return left;
        else if (a[mid] > a[right])// left > mid > right
            return mid;
        else // left > right > mid
            return right;
    }
}

//前后指针法
int PartSort3(int* a, int left, int right)
{
    //三数取中优化
    int midi = GetMidIndex(a, left, right);
    Swap(&a[midi], &a[left]);

    int key = left;//注意不能写成 int key = a[left]
    int prev = left;
    int cur = prev + 1;
    while (cur <= right)
    {
        if (a[cur] < a[key] && a[++prev] != a[cur]) 
        {
            Swap(&a[prev], &a[cur]); 
        }
        cur++;  
    }
    Swap(&a[prev], &a[key]);  
    return prev;
}

//快速排序
void QuickSort(int* a, int begin, int end)
{
    //子区间相等只有一个值或者不存在那么就是递归结束的子问题
    if (begin >= end)
    {
        return;
    }
    int keyi = PartSort3(a, begin, end);
    //分成左右两段区间递归
    // [begin, keyi-1] 和 [keyi+1, end]
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}

小区间优化

假设快排每次递归的过程中，选出key，然后递归分成左边和右边，并且都是均匀的，如果是有序，每次选中间值，这个过程就像是二分，跟二叉树的样子差不多，正如上述画过的图：

快排递归调用的简化图其实就类似于一个二叉树，假设长度N为1000，那么递归调用就要走logN层也就是10层，假设其中一个递归到只有5个数了，那么还要递归3次，当然这只是左边的，右边还要递归3次，这么小的一块区间还要递归这么多次，小区间优化就是为了解决这一问题，针对最后的小区间进行其它的算法排序，就比如插入就很可以

当递归到越小的区间时，递归次数就会越多，针对这一小区间采取插入排序更优，减少了大量的递归次数

  • 代码如下：
//三数取中优化
int GetMidIndex(int* a, int left, int right)
{
    //……
}

//前后指针法
int PartSort3(int* a, int left, int right)
{
    //三数取中优化
    int midi = GetMidIndex(a, left, right);
    Swap(&a[midi], &a[left]);
    //……
}

//小区间优化
void QuickSort2(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+1, end]
        QuickSort(a, begin, keyi - 1);
        QuickSort(a, keyi + 1, end);
    }
}

快排非递归

先前的学习中，我们的快排都是用递归来实现的，但是要知道：递归也是有缺陷的。如果深度过大，可能会导致栈溢出，即使你用了快排优化可能也无法解决此问题，所以我们引出非递归的版本来解决栈溢出问题。

  • 规则：

在快排递归的过程中是要建立栈帧的，仔细看看每次递归时传的参数，有begin和end，其递归过程存储的是排序过程中要控制的区间，那我们用非递归模拟递归的过程中也要按照它这个存储方式进行，这就需要借助栈了，跟上篇博文的层序遍历一样利用到了栈

依旧以如下乱序数组示例：

  • 代码如下：
//快排非递归
void QuickSort3(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); // keyi已经到了正确位置

        // [left, kryi-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);
}

上述代码恰好巧妙的实现了递归的过程，仔细观察上述代码，一开始我们入栈了下标为begin和end的值，如下：

随后，取出这两个值，并用right和left分别保存起来，随后对区间[left，right]这块区间进行单趟排序，取出keyi的值为5，此时a[keyi]也就排到了正确的位置了，接下来就是效仿递归的关键了，以keyi为分界线，将数组分为两块区间：【left，keyi-1】和【keyi+1，right】，此时再把这两块区间的入栈：

接下来进入第二趟while循环，同样是再次出栈里的两个数据6和9，并再次传入单趟排序，算出keyi的值为8，也就意味着a[keyi]到了正确的位置，再以keyi为分界线，将右区间的数组分为【6，7】和【9，8】以此类推……一直排下去

7、归并排序

  • 动图演示：

  • 基本思想：分治思想

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

假设我们有左右两块有序区间的数组，可以对它直接进行合并。此时我们需要借助第三方数组，一次比较两块区间的起始位置，把小的那个放到新数组，随后依次比较，小的就放新数组，一直到结束。

但是现在存在一个问题？上述条件是假设了左半区间和右半区间有序，但是原先数组是无序的啊，也就是左半区间和右半区间均无序。怎么才能达到左半区间和右半区间有序最后再归并成整体有序呢？这就体现到了分治的思想了，将数组一直分，分到1个1个的，归并成有序变成2个2个的，然后归并成有序成4个4个的，最后再4个4个的归并成有序，最终至整体有序。

  • 画图解析其完整的归并过程：

这里我们先用代码实现其分解递归的过程，并用打印法表示其结果

画图演示其部分递归分治的过程：

  • 总代码如下：
void _MergeSort(int* a, int begin, int end, int* tmp)
{
    if (begin >= end)
        return; //区间不存在就返回
    int mid = (begin + end) / 2;
    //[begin, mid] [mid+1, end]
    _MergeSort(a, begin, mid, tmp); //递归左半
    _MergeSort(a, mid + 1, end, tmp); //递归右半

    //归并[begin, mid] [mid+1, end]
    //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;
    while (begin1 <= end1 && begin2 <= end2)
    {
        //将较小的值放到tmp数组里头
        if (a[begin1] < a[begin2])
        {
            tmp[index++] = a[begin1++];
        }
        else
        {
            tmp[index++] = a[begin2++];
        }
    }
    //如若begin2先走完，把begin1后面的元素拷贝到新数组
    while (begin1 <= end1)
    {
        tmp[index++] = a[begin1++];
    }
    //如若begin1先走完，把begin2后面的元素拷贝到新数组
    while (begin2 <= end2)
    {
        tmp[index++] = a[begin2++];
    }
    //归并结束后，把tmp数组拷贝到原数组
    memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

//归并排序
void MergeSort(int* a, int n)
{
    //malloc一块新数组
    int* tmp = (int*)malloc(sizeof(int) * n);
    assert(tmp);
    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);
}

归并排序非递归

  • 思想：

归并的非递归不需要借助栈，直接使用循环即可。递归版中我们是对数组进行划分成最小单位，这里非递归我们直接把它看成最小单位进行归并。我们可以通过控制间距gap来完成，先看图：

上述情况其实是在理想状态下可行的，只要数组长度不是2的次方倍都会出现问题，先简要看下理想状态下的伪代码，并用printf打印下归并过程：

再强调一遍，只要数组长度不是2的次方倍都会出现问题，像上述长度为8没有问题，那如若长度为6呢？

当长度为6不再是2的次方数时就运行出现问题了，综上我们需要考虑下极端情况：根据上述的区间范围，我们可以总结出以下三个可能会出现越界的情况：

  1. end1越界
  2. begin2越界
  3. end2越界

1、end2越界：

2、begin2和end2均越界：

3、end1和begin2和end2均越界

综上，我们需要单独对这些极端情况处理

//end1越界，修正即可
if (end1 >= n)
{
    end1 = n - 1;
}
//begin2越界，第二个区间不存在
if (begin2 >= n)
{
    begin2 = n;
    end2 = n - 1;
}
//begin2 ok，end2越界，修正下end2即可
if (begin2 < n && end2 >= n)
{
    end2 = n - 1;
}
  • 总代码如下：
//归并非递归
void MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    assert(tmp);
    int gap = 1;
    while (gap < n)
    {
        //分组归并，间距为gap是一组，两两归并
        for (int i = 0; i < n; i += 2 * gap)
        {
            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越界，修正下end2即可
            if (begin2 < n && end2 >= n)
            {
                end2 = n - 1;
            }
            printf("归并[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
            int index = i;
            while (begin1 <= end1 && begin2 <= end2)
            {
                //将较小的值放到tmp数组里头
                if (a[begin1] < a[begin2])
                {
                    tmp[index++] = a[begin1++];
                }
                else
                {
                    tmp[index++] = a[begin2++];
                }
            }
            //如若begin2先走完，把begin1后面的元素拷贝到新数组
            while (begin1 <= end1)
            {
                tmp[index++] = a[begin1++];
            }
            //如若begin1先走完，把begin2后面的元素拷贝到新数组
            while (begin2 <= end2)
            {
                tmp[index++] = a[begin2++];
            }
        }
        memcpy(a, tmp, n * sizeof(int));
        gap *= 2;
    }
    free(tmp);
}

归并排序特性总结

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

2、时间复杂度：O(N*logN)

3、空间复杂度：O(N)

4、稳定性：稳定

内排序和外排序

在排序中，分为内排序和外排序，简单了解下其概念：

  • 内排序：数据量较少，在内存中进行排序
  • 外排序：数据量很大，在磁盘上进行排序

而我们前面学习的排序中，归并排序既可作为内排序，也可作为外排序，而其它几个排序只能是内排序，这也就说明了在处理数据量很大时，采用归并排序才能解决，其它排序不可。

如若我要排10亿个整数，就只能使用归并排序了，现在来简要算下其占比大小：

  • 1G = 1024MB
  • 1MB = 1024KB
  • 1KB = 1024Byte
  • 综上1G = 102410241024Byte，而10亿个整数40亿Byte，所以10亿个整数占4G

现在有10亿个整数（4G）的文件，只给你1G的运行内存，请对文件中的10亿个数进行排序

核心思想：数据量大，加载不到内存。想办法控制两个有序文件，两个有序文件归并成一个更大的有序文件。可以把这4G的文件分成4等份，每一份1G，分别读到内存进行归并排序，排完后再写回到磁盘小文件

8、计数排序

  • 动图演示：

  • 基本思想：

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。用到的是哈希映射的思想。

  • 操作步骤：
  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列中

假设现在要对如下数组进行排序：

计数的核心步骤就是数组中数字的值是多少，就把该值映射到新开辟数组的下标上。仔细观察这串数组，最大数字为10，所以这里我们要开辟11个空间，才能保证数字10放到新数组下标为10的位置，遍历原数组，一个val出现几次，它映射的位置++几次

上述方法即哈希的绝对映射思想，原数组的某个元素是几，对应新开辟数组下标为几的位置就相应的加加，出现几次，加加几次。此方法看似可行，但存在一个大问题，空间复杂度过大，如若一组数据为【10000，9999，5000，9999，5000，8888】，难道说为了排这几个数字，你要开辟10001个大小空间的数组吗，得不偿失，更何况你这10001个空间的前5000个空间没有值映射，纯纯浪费了空间，这就是绝对映射的弊端，因此要用相对映射

  • 绝对映射：原数组是几，映射到新数组下标位置++
  • 相对映射：此时新数组下标的范围是从0到原数组最小的值，而映射到下标的位置为原数组val的值 - 原数组最小min的值

看图说话：

综上，基数排序使用于数据有一些重复，数据范围比较集中 ，从而避免空间浪费过于严重

  • 代码如下：
//计数排序
void CountSort(int* a, int n)
{
    int min = a[0], max = a[0];
    //先求出原数组的最大和最小值
    for (int i = 1; i < n; i++)
    {
        if (a[i] < min)
            min = a[i];
        if (a[i] > max)
            max = a[i];
    }
    //求出新数组的范围
    int range = max - min + 1;
    //开辟新数组
    int* countA = (int*)malloc(sizeof(int) * range);
    assert(countA);
    //把新开辟数组初始化为0
    memset(countA, 0, sizeof(int) * range);

    //计数
    for (int i = 0; i < n; i++)
    {
        countA[a[i] - min]++; //统计相同元素出现次数（相对映射）
    }

    //排序
    int j = 0;
    for (int i = 0; i < range; i++)
    {
        while (countA[i]--)
        {
            a[j++] = i + min; //赋值时，记得加回原先的min
        }
    }
    free(countA);
}

计数排序特性总结

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

9、图表汇总

排序方法平均情况最好情况最坏情况辅助空间稳定性冒泡排序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(NlogN)O(1)不稳定归并排序O(NlogN)O(NlogN)O(NlogN)O(N)稳定快速排序O(NlogN)O(N*logN)O(N^2)O(logN) ~ O(N)不稳定

10、总结

读到这的小伙伴，非常感谢你们的支持，此博文真的是耗费了n久，写了得有1周多，本不需要这么长，奈何自己手残，在创作快结束的时候按了个ctrl+z键，1.8w的大长文只剩下2k不到了，自己还没备份，可真是命苦啊，纯纯大冤种！！最后无奈又重新复盘了一份，害，说多了都是泪。以后再无ctrl z。还得感慨下这个动图是真的不好做，还记得自己前些天挑灯夜战动图，只为呈现更好的效果~

  • 想要排序源码的可以到我的gitee仓库里查看：

八大排序汇总集合

标签： 排序算法 算法 c语言
本文转载自: https://blog.csdn.net/bit_zyx/article/details/124529185
版权归原作者 三分苦 所有， 如有侵权，请联系我们删除。
登录后发布评论

“＜ 数据结构 ＞ 八大排序”的评论:

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

泷羽sec-星光不负a-学习打卡-安全见闻(1)

Linux 经典面试八股文

docker 拉取MySQL8.0镜像以及安装

【PowerShell】如何使用Pester进行单元测试？

PyCharm中TensorFlow安装指南及.whl文件使用

移动UI：意见反馈设计的8大要点，让用户和产品畅快沟通。

git | 删除指定 commit

文章导航