【数据结构】—交换排序之快速排序究极详解，手把手带你从简单的冒泡排序升级到排序的难点{快速排序}（含C语言实现）

                                       食用指南：本文在有C基础的情况下食用更佳 

                                       🔥这就不得不推荐此专栏了：C语言

                                       ♈️今日夜电波：靴の花火—ヨルシカ

                                                                0:28━━━━━━️💟──────── 5:03
                                                                    🔄   ◀️   ⏸   ▶️    ☰ 

                                      💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍 

---

目录

♉️一、前置知识—什么是交换排序

♊️二、冒泡排序

        冒泡排序的思想

        冒泡排序的实现

♋️三、快速排序 （排序算法中的重点，肥肠重要！！！）

        快速排序的思想

        快速排序的三种版本实现

        1、hoare版本（基础版本）

        ♒️快排的优化  

        2、 挖坑法

        3、前后指针法

---

♉️一、前置知识—什么是交换排序

        交换排序的基本思想是通过比较相邻元素的大小关系，如果两个相邻元素的大小关系不满足排序要求，就交换它们的位置，以达到排序的目的。交换排序分为两种，即冒泡排序和快速排序。

♊️二、冒泡排序

        冒泡排序的思想

        冒泡排序是一种基本的排序算法，它的思想是将待排序的元素依次比较相邻的两个元素，根据比较结果交换它们的位置，从而使较大(或较小)的元素逐渐往后移动，最终实现整个序列的排序。

        具体的实现过程如下：

        1. 从序列的第一个元素开始，依次比较相邻的两个元素的大小。

        2. 如果前一个元素比后一个元素大（或小），则交换它们的位置。

        3. 继续比较序列中下一个相邻的元素，直至最后一个元素。

        4. 重复以上操作，每一轮比较都将序列中最大（或最小）的元素排到了序列的末尾。

        5. 经过多轮比较后，序列中的元素就按照从小到大（或从大到小）的顺序排好了。

         一图理解~

         冒泡排序的实现

        太简单了，就不多解释了，看代码即可

void BubbleSort(int* a, int n)
{for (int j = 0; j < n; ++j){bool exchange = false;for (int i = 1; i < n-j; i++){if (a[i - 1] > a[i]){int tmp = a[i];a[i] = a[i - 1];a[i - 1] = tmp;exchange = true;}}if (exchange == false){break;}}
}

---

♋️三、快速排序 （排序算法中的重点，肥肠重要！！！）

        快速排序的思想

        快速排序的基本思想是选定一个轴值，将待排序序列划分为两部分，一部分是小于轴值的元素，一部分是大于轴值的元素。然后对于这两部分分别递归地进行快速排序，直到排序完成。具体实现时，可以选择待排序序列的第一个元素作为轴值（通常需要进行比较选出，后面会详讲），也可以随机选择一个元素作为轴值，然后将序列中的元素与轴值进行比较，小于轴值的元素放在轴值的左边，大于轴值的元素放在轴值的右边，相等的元素可以放在任 一 一边，最后将左右两部分序列递归地进行快速排序即可。快速排序一般有三种实现方法：hoare法、挖坑法、前后指针法。

        一图先有个大概的了解~ 

        以下的内容是循序渐进的，建议大家一步一步往下看！ 

        快速排序的三种版本实现

        1、hoare版本（基础版本）

        上来请先看一张图~

具体实现步骤如下：

1. 选择一个基准元素 key，通常可以选择第一个或者最后一个元素作为基准元素（这里的key值选第一个）。

2. 定义两个指针 left和 right 分别指向数组的开头和结尾。

3. 从右向左扫描数组，如果当前元素大于或等于基准元素，则指针 right 向左移动一位。

4. 从左向右扫描数组，如果当前元素小于或等于基准元素，则指针 left 向右移动一位。

5. 如果 left < right，则交换指针所指向的元素。

6. 当 left >= right 时，说明当前分区操作已经完成，交换基准元素和 left 指针指向的元素，并返回 left 的值。

7. 对基准元素左侧的子数组和右侧的子数组分别递归执行上述步骤，直到数组长度为 1 或 0，此时数组就已经排好序了。

一些注意事项：

1. Hoare 版本的快速排序可以避免对基准元素相同的元素的不必要交换操作，因此比 Lomuto 版本效率更高。

2. 在实：现时需要注意边界条件的处理，尤其是数组下标越界问题。

        在这里大家可能会有一个疑惑，两个指针i,j相遇的位置的值，如何保证要比key的值小呢？

                答案：右边的值先走就能做到！！！

        当右侧的值先走时，如果它遇到了一个比基准元素小的值，那么它就会停下来，等待左侧的值去找到一个比基准元素大的值。接着左侧的值找到了一个比基准元素大的值后，交换左右值的位置，此时右侧的值就会从原来的位置继续走下去。由于左侧的值都比基准元素小，所以右侧的值再次遇到比基准元素小的值时，仍然会停下来等待左侧的值交换位置。这样，右侧的值先走就可以保证最后相遇的位置的值一定比基准元素的值小。

         在这里大家可能会有一个疑惑了，那我们能左边先走吗？

                当然可以，同样的道理，只需要key值在右边就行了！

         代码实现：

        详见代码内注释

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}int Partsort(int* a, int left, int right)
{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和小于key位置的值}Swap(&a[key], &a[left]);//此时left==right，交换key和left的值return left;//用于递归下一步的key的左半边以及右半边}void Quicksort(int* a, int begin, int end)
{if (begin >= end)//当下标越界时，直接退出return;int key = Partsort(a, begin, end);// [begin, key-1] key [key+1, end] 大致形状Quicksort(a, begin, key - 1);//对左key半边进行排序Quicksort(a, key + 1, end);//对右半边进行排序
}

        ♒️快排的优化  

        先看个例子：（当我们的快排是排升序，然而我们要排的数据确是一个降序时）

         对此，快速排序有相应的优化：采用“三点取中法”，即：在待排序序列中随机选取三个元素，取中间值作为key值。这样做是为了避免选取到最大或最小值作为 key值，从而导致快排算法性能下降的问题。

        代码实现：

        详见代码内注释

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}int Getmid(int* a, int left, int right)//三点取中值
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] < a[right]){return right;}else{return left;}}else{if (a[mid] > a[right]){return mid;}else if (a[right] > a[left]){return left;}else{return right;}}
}int Partsort(int* a, int left, int right)
{int mid = Getmid(a, left, right);//三点取中值，优化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和小于key位置的值}Swap(&a[key], &a[left]);//此时left==right，交换key和left的值return left;//用于递归下一步的key的左半边以及右半边}void Quicksort(int* a, int begin, int end)
{if (begin >= end)//当下标越界时，直接退出return;int key = Partsort(a, begin, end);// [begin, key-1] key [key+1, end] 大致形状Quicksort(a, begin, key - 1);//对左key半边进行排序Quicksort(a, key + 1, end);//对右半边进行排序
}

        2、 挖坑法

        上来请先看一张图~

挖坑法的实现步骤如下：

1. 设置左指针left和右指针right，以及基准元素key。

2. 从右指针开始，向左遍历数组，直到找到第一个小于准元素key的元素，将其填入左指针所在位置的坑中，并将右指针指向左边一位。

3. 从左指针开始，向右遍历数组，直到找到第一个大于准元素key的元素，将其填入右指针所在位置的坑中，并将左指针指向右边一位。

4. 重复执行步骤2和步骤3，直到左指针等于右指针。

5. 将基准元素填入最后的坑中。

6. 对基准元素左边的子数组和右边的子数组，分别递归执行以上步骤，直到完成排序。

一些注意事项： 

• 坑位可以是基准元素的位置，也可以是左指针或右指针的位置。

• 在填坑的过程中，需要先将当前指针指向的元素保存起来，然后将其填入对应的坑中。

• 在左指针等于右指针时，需要将基准元素填入最后的坑中。

代码实现：

        详见代码内注释

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}int Getmid(int* a, int left, int right)//三点取中值
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] < a[right]){return right;}else{return left;}}else{if (a[mid] > a[right]){return mid;}else if (a[right] > a[left]){return left;}else{return right;}}
}int Partsort2(int* a, int left, int right)
{int midi = Getmid(a, left, right);Swap(&a[left], &a[midi]);int key = a[left];// 保存key值以后，左边形成第一个坑int hole = left;while (left < right){// 右边先走，找小，填到左边的坑，右边形成新的坑位while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;// 左边再走，找大，填到右边的坑，左边形成新的坑位while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}void Quicksort(int* a, int begin, int end)
{if (begin >= end)//当下标越界时，直接退出return;int key = Partsort2(a, begin, end);// [begin, key-1] key [key+1, end] 大致形状Quicksort(a, begin, key - 1);//对左key半边进行排序Quicksort(a, key + 1, end);//对右半边进行排序
}

        3、前后指针法

        上来请先看一张图~

前后指针法的实现步骤如下：

1. 选取基准数。可以选择数组的第一个元素、最后一个元素、中间元素等。

2. 设置两个指针，一个指向数组的第一个位置，另一个指向数组的最后一个位置。

3. 从后往前遍历，找到第一个比基准数小的数，停止遍历。

4. 从前往后遍历，找到第一个比基准数大的数，停止遍历。

5. 交换两个数的位置。

6. 重复步骤3到步骤5，直到前后指针相遇。

7. 将基准数放到前后指针相遇的位置。

8. 对基准数左右两边的子序列分别进行快速排序。

9. 重复以上步骤，直到数组被完全排序。

 一些注意事项： 

         在交换两个数的位置时，如果前后指针指向的数相同，那么就不能进行交换操作，因为这样会导致两个数的值发生变化。同时，在递归的过程中，需要对子序列进行边界检查，避免出现数组越界的情况。

代码实现：

        详见代码内注释

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}int Getmid(int* a, int left, int right)//三点取中值
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] < a[right]){return right;}else{return left;}}else{if (a[mid] > a[right]){return mid;}else if (a[right] > a[left]){return left;}else{return right;}}
}// 前后指针
int Partsort3(int* a, int left, int right)
{int midi = Getmid(a, left, right);Swap(&a[left], &a[midi]);int prev = left;//前指针，从最左边开始int cur = prev + 1;//后指针int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)//当后指针cur找到比key小的值时，先让前指针++prev让prev到交换位置（因为原来比cur小1个位置）再判断前指针是否更cur相等，如果相等了就没有必要再交换了{Swap(&a[prev], &a[cur]);}++cur;//继续遍历找比key值小的值}Swap(&a[prev], &a[keyi]);//最后交换prev与key的值return prev;//此时prev在key最终位置，后续用于递归
}void Quicksort(int* a, int begin, int end)
{if (begin >= end)//当下标越界时，直接退出return;int key = Partsort3(a, begin, end);// [begin, key-1] key [key+1, end] 大致形状Quicksort(a, begin, key - 1);//对左key半边进行排序Quicksort(a, key + 1, end);//对右半边进行排序
}

---

                    感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！ 

                                       

                                                                         给个三连再走嘛~