大型建站公司是干嘛的,北京最富裕的三个区,做数据新闻的网站有哪些,个人网站设计作品图片#x1f4d9;作者简介#xff1a; 清水加冰#xff0c;目前大二在读#xff0c;正在学习C/C、Python、操作系统、数据库等。 #x1f4d8;相关专栏#xff1a;C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 #x1f44d… 作者简介 清水加冰目前大二在读正在学习C/C、Python、操作系统、数据库等。 相关专栏C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 收藏 ⭐留言 如有错误还望各路大佬指正 ✨每一次努力都是一种收获每一次坚持都是一种成长✨ 目录 前言
1. 快速排序 1.1 hoare版本
1.2 挖坑法
1.3 双指针版本
2. 非递归实现快速排序
总结 前言 快速排序是一种常用的排序算法也是一种很高效的排序的它是由Hoare于1962年提出的一种二叉树结构的交换排序方法。本篇文章我将带你深入了解快速排序。 1. 快速排序 快速排序是一种常用的排序算法它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分其中一部分的所有数据都比另一部分的所有数据小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列的目的。快速排序常见的实现方法主要分为三种版本 hoare版本挖坑法版本前后指针版本 我们废话不多说直接步入正题。 1.1 hoare版本 hoare版本是选择一个key值一般选用最左边例如 然后开始从数组两边开始移动寻找符合条件的值R向左移动寻找小于key的值L向右移动寻找大于key的值。R和L都找到符合条件的数字后进行交换。 然后再继续走直到L和R相遇停止。 它们相遇的位置是数字33比key小最后再将相遇位置的数据和key的数据进行交换。整个逻辑过程如下图 这个图呈现的逻辑过程更加形象然后我们再从R和L相遇的位置将数组分为两部分当左半部分和右半部分有序那么这个数组就会有序所以我们重复上述过程 继续分数组最终被细分为一个数据或没有数据。 当数据为1个或没有时就开始返回执行完毕后左半部分就变得有序右半部分也是这样的逻辑返回后两边子数组就会变得有序进而使整个数组有序。以上便是hoare版本的整个过程。 接下来我们对代码进行实现
void PathSort(int* a, int left,int right)
{int key a[left];while (left right){while (a[right] a[key]){right--;}while (a[left] a[key]){left--;}Swap(a[left], a[right]);}Swap(key, a[right]);
} 快速排序的hoare版本有很多的坑上述的代码是否存在错误呢
上述的代码存3个问题 死循环问题数组越界问题key值交换问题 首先是死循环问题R要找比key小的数据L要找比key大的数据那当L和R都遇到了和key相同的数据时它们都停止移动开始进行交换交换后仍然相等以此往复一直交换进而形成了死循环。 数组越界问题R找比key的值如果R一直到数组遍历结束都没有找到那它就会发生越界。 key值交换问题我们在上述逻辑中需要将key值第一个数据位置上的数据与L和R相遇位置的数据进行交换。而上述代码中交换的是key的值与L和R相遇位置的数据实际上第一个数据key值位置并没有变这样会造成数据丢失。 这三个问题都是在编写代码时经常遇到的错误。改正后代码如下
int PathSort(int* a, int left,int right)
{int key left;while (left right){while (rightleft a[right] a[key]){right--;}while (right left a[left] a[key]){left;}Swap(a[left], a[right]);}Swap(a[key], a[left]);return left;
}上述代码我们是进行了一次调整接下来就是递归使得左右两边数组有序。递归调用这里没有什么问题重点在于递归结束条件。当递归到最后时要么是数组只有一个数据要么是没有数据。
那要如何编写设置结束条件呢 以左边递归为例第一次进入左边区间是0到4第二次是0到1然后key是下标为1的数据key-10第三次调用传入的key-1begin0返回后调用右边右边没有数据key12end1所以由此我们可以做出判断当beginend时就证明递归已经到最小然后就返回。 递归过程如下图 void QuickSort(int* a, int begin,int end)
{if (begin end){return;}int keyPathSort(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key 1, end);
} 从上述的逻辑过程可以发现L和R相遇的位置一定比key小相遇位置比key小交换才有意义那凭什么说L和R相遇位置一定比key小 它是有一个前提的就是一定要让R先走但是又会存在两种情况 最后一次R不动让L去相遇。 L不动让R去相遇。 如下图让R先走最后是R不动让L去相遇但如果是L先走当R到下标为6的位置停止交换后L开始走此时相遇位置就会变成下标为6的位置数据是9比6大。R不动让L去相遇 当然还有一种情况最后一次时是L不动让R去相遇 两次交换后如上图此时R先走11比key大R会继续走R就会去和L相遇相遇的位置还是比key小L和R交换后L位置数据一定比key小。 上述的方式和代码排序很不稳上述过程最理想的状态是key的值是中位数这样在分割数组进行递归时能尽可能将数组二分。
最坏的情况就是没有比key小的数据或者大的数据那么就会造成如下情况 这样它的时间复杂度和空间复杂度也会变差所以我们还需要对hoare版本的进行优化以避免这样情况的发生。我们可以将左右和中间的值进行比较取三数的中间值作为key值。优化后
//三数取中
int GetMid(int* a, int left, int right)
{int mid (left right) / 2;if (a[mid] a[left]){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[right] a[left]){return right;}else{return left;}}
}
int PathSort(int* a, int left,int right)
{int mid GetMid(a, left, right);Swap(a[left], a[mid]);int key left;while (left right){while (rightleft a[right] a[key]){right--;}while (right left a[left] a[key]){left;}Swap(a[left], a[right]);}Swap(a[key], a[left]);return left;
}
1.2 挖坑法 挖坑法是对hoare版本思路上的一种优化挖坑法的整体逻辑如下 挖坑法不用考虑R先走还是L先走开始时第一个数据作为坑位必须R先走R找到比key小的数数据填补到坑位R位置形成新的坑位。然后L开始走遇到比key大的将数据填补到坑位然后L位置形成新的坑位。具体代码如下
int PathSort2(int* a, int left, int right)
{int mid GetMid(a, left, right);Swap(a[left], a[mid]);int key a[left];//保存key值左边形成第一个坑位int hole left;while (left right) {//右边先走寻找比key小的数据填补到左边坑位while (right left a[right] key){right--;}a[hole] a[right];hole right;//左边走寻找比key大的数据填补到右边坑位while (right left a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;}
1.3 双指针版本 双指针法是对快排的更近一步优化相对于前两种思路和代码也更简单使用两个指针cur和prev来控制数据进行调整。
逻辑如下 cur遍历数组如果cur比key小那就prev向后移动将prev指向的数据于cur指向的数据进行交换。 然后cur继续向后走遇到比key小的数据就重复上述过程 直到cur遍历结束停止之后再将prev最终指向位置的数据与key位置的数据进行交换。最终情况如下图 根据上述的逻辑我们对代码进行实现
int PathSort3(int* a, int left, int right)
{int cur left 1;int prev left;int key left;while (cur right){if (a[cur] a[key] ){prev;Swap(a[prev], a[cur]);}cur;}Swap(a[key], a[prev]);return prev;} 在cur指向1和2时cur指向的数据依然和prev指向的数据进行了交换此时cur和prev指向同一个数据此时交换并没有什么意义所以我们也可以为了防止prev和cur指向同一位置时进行交换这里我们可以进行优化
int PathSort3(int* a, int left, int right)
{int mid GetMid(a, left, right);Swap(a[left], a[mid]);int cur left 1;int prev left;int key left;while (cur right){if (a[cur] a[key] prev!cur){Swap(a[prev], a[cur]);}cur;}Swap(a[key], a[prev]);return prev;} 双指针法不需要考虑从哪边先走也不需要考虑数组越界问题代码和逻辑都十分的清晰简单。在这三种方法的实际调用时都是使用了递归来进行分治排序。 但快速排序使用递归是需要不断进行开空间的快速排序的二分递归模式类似于满二叉树我们知道满二叉树的后两层的节点个数占了总个数的75%所以我们可以考虑在递归到小区间时使用插入排序来进行优化。
void QuickSort2(int* a, int begin, int end)
{if (begin end){return;}if ((end - begin 1) 10){int key PathSort3(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key 1, end);}else{InsertSort(a begin, end - begin 1);}}同时我们还可以使用非递归的方法来实现快排。
2. 非递归实现快速排序 上述的快速排序使用了递归但使用递归还是存在弊端的递归的深度问题递归创建的空间在栈区而栈区的空间大概只有8MB所以我们还是很有必要学习非递归的方法。 非递归实现快排需要用到栈的数据结构通过栈来模拟系统栈区。 不断地入栈每次调整的数组区间使用栈的特性来模拟递归调用的调整函数。 还是以上述的数组为例 以左边为例 先入栈0和9数据的区间下标然后出栈取栈顶元素作为调整函数的参数然后调用调整函数再将key两边的数组下标区间入栈直至栈为空结束。具体代码实现如下
逻辑比较简单不再进行细节讲解。
void QuickSort3(int* a, int begin, int end)
{Stack st;InItStack(st);StackPush(st, end);StackPush(st, begin);while (!IsEmpty(st)){int leftTopData(st);StackPop(st);int right TopData(st);StackPop(st);int key PathSort3(a, left, right);if (key right){StackPush(st, right);StackPush(st, key1);}if (left key - 1){StackPush(st, key - 1);StackPush(st, left);}}DestoryStack(st);} 总结 快速排序是一种极其高效的排序方法从上述的分析快速排序使用的二分分治排序的方法可以得出时间复杂度为O(N*logN)同时快速排序并不稳定我们使用了各种方法来进行优化使它的时间复杂度稳定在O(N*logN)。好了以上便是本期全部内容感谢阅读
