学院网站建设成效,石家庄免费网站制作,北京网页设计制作网站,大连哪里做网站好上篇文章中#xff0c;解释了插入排序、希尔排序、冒泡排序、堆排序及选择排序的原理及具体代码实现本片文章将针对快速排序#xff0c;快速排序的几种优化方法、快速排序的非递归进行解释。
目录
1. 快速排序原理解析以及代码实现#xff1a;
2. 如何保证相遇位置的值一… 上篇文章中解释了插入排序、希尔排序、冒泡排序、堆排序及选择排序的原理及具体代码实现本片文章将针对快速排序快速排序的几种优化方法、快速排序的非递归进行解释。
目录
1. 快速排序原理解析以及代码实现
2. 如何保证相遇位置的值一定小于所对应的值
3 优化最坏情况下快速排序的时间复杂度
4. 对于快速排序代码书写格式的优化挖坑法
5. 对于快速排序代码的另一种书写格式优化前后指针法 1. 快速排序原理解析以及代码实现
给定下面一个数组 对于快速排序其中心思想就是首先选取一个值一般选择数组中最左边的数据例如本数组中的。创建一个变量来保存这个值所对应的下标为了方便表达将这个变量命名为。 在确定了之后分别从两头遍历数组定义两个变量用于遍历数组其中。 对于遍历数组的过程需要分成两种情况来查看。其中用于从左向右遍历数组用于从右向左遍历数组。当数组从左向右进行遍历时一旦遇到比所对应的值大的数据则停在这个数据的所对应的下标处。即 当数组从右向左进行遍历时一旦遇到比所对应的值小的数据则停在这个数据的所对应的下标处。即 在找到了符合上面规定的值后交换两个值在数组中的位置 接着继续向下遍历并且重复之前的动作。当相遇时停止循环此时的数组可以表示为 最后将所对应的值与此时或者所对应的值进行一次交换便完成了整个流程用图形表示为 在进行了上面一整套流程后此时的数组虽然还是无序但是可以观察到所对应的值的右半部分的数组的值都大于所对应的值。左半部分数组的值都小于所对应的值。
对于上述流程可以用下面的代码进行表示 //部分快排int PortSort(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]);}Swap(a[key], a[left]);return left;}
对于上述给出的代码中需要注意两个点
1.在进行遍历数组寻找值的时候必须先从右边开始遍历找小于所对应的值的数据再从左边找大于所对应的值的数据对于原因将会在文章的后面进行探讨
2.在遍历寻找值的循环中需要注意循环的两个条件即并且前面的条件是为了防止下面的两种情况若从左向右遍历时不存在比对应的值大的数据从右向左遍历时不存在比对应的值小的数据。以上两种情况均会导致的范围超出数组下标的范围对于第二个条件如果不加上一旦在遍历的过程中遇到了与对应的值相等的值会造成死循环。 完成了上述步骤后数组依然是无序的为了处理数组中其他的数据需要利用到类似二叉树中递归的思想来实现 对于上述数组他的数组左半部分的数据都是小于所对应的值的对于数组的右半部分的数据都是大于所对应的值的因此在下面的递归中需要以为分界线的左半部分为一组右半部分为一组对这两组值再次进行一次上面给出代码所对应的操作。 例如对于左半部分 此时所对应的值为按照上述代码进行操作后数组可以表示为 随后再以为分界线分出左右部分对于左右部分进行上述代码的操作对于左半部分进行一次操作后可以表示为 此时再向下进行递归的左半区间不存在的右半区间只有一个值。因此对于上面两种情况视作递归结束的条件。 上面只是展示了每一次的递归中数组的左半部分的情况对于右半部分原理相同这里不再进行赘述。当作伴部分右半部分的递归都结束后整个区间会变成有序的区间即 对于上述递归可以用下列代码进行实现 void QuickSort(int* a, int begin, int end){if (begin end)return;int keyi PortSort(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);} 测试函数如下
void TestQuickSort()
{int e[] { 6,1,2,7,9,3,4,5,10,8 };int size sizeof(e) / sizeof(int);QuickSort(e, 0,size-1);printf(快速排序);ArrayPrint(e, size);
}
结果如下 2. 如何保证相遇位置的值一定小于所对应的值 上面说到在进行遍历寻找值这一步骤时一定要先从右边开始向左遍历来找到比对应的值小的值再从左边向右开始遍历来寻找比对应值大的值原因如下
例如对于上面给出的数组对于相遇的前一步情况 假设左边先进行遍历去寻找值再从右边向左遍历来寻找值则二者相遇的位置为 此时如果按照上面代码的内容对对应的值和位置对应的值进行交换则 此时比对应的值大的值不只是只存在右边。
这里需要注意先从右边往左边遍历的对应的是的位置在数组的左端。当在数组的右端时需要先从左边向右遍历。 3 优化最坏情况下快速排序的时间复杂度
快速排序的时间复杂度一般都认为是但是对于下面的一种情况 前面说到在快速排序中当取左端的值时应该优先从右边开始遍历对于例子中这种完全升序或者说大部分区间都是升序的情况每次从右端进行遍历时都必须遍历到数组的最左边。因此对于一个有个数据的这样的数组来说从右向左遍历的次数为次这种情况下的快速排序的时间复杂度为。为了优化这种情况这里引入三数取中的方法。代码如下因为原理就是简单的两数相比所以不做过多解释 //三数取中int GetMidi(int* a, int left, int right){int mid (left right) / 2;if (a[left] a[mid]){if (a[right] a[mid]){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;}}} 在构建了三数取中函数之后需要对之前的快速排序代码进行修改。修改的部分为首先在函数的开头创建一个变量用于接受三数取中函数的返回值。接着让对应的数值与后续下标对应的数据即最左端或者最右端用交换函数交换即可。 4. 对于快速排序代码书写格式的优化挖坑法
对于挖坑法具体的实现原理如下
首先还是确认以及所对应的值例如在下面的例子中
注为了方便演示原理下面的情况不包括三数取中但是在书写代码时使用三数取中的方法与上方的使用发放相同 首先确定一个这里按照左端处理创建一个变量令接着确定所在的下标就是第一个坑位。在确认了第一个坑位后与上面的快速排序相同都需要先从右端开始遍历来找到比小的值即 随后直接让所指向的值覆盖到的位置再让指向的位置变成新的坑即 再从左边向右进行遍历找到比小的值并且让这个值覆盖到坑位中再令下图中的成为新的坑位 继续从右向左进行遍历再从左向右遍历直到相遇为止即 最后再令二者相遇的位置赋值即可。然后再按照上面的思想递归即可。代码实现为
//快排优化(挖坑法int QuickDigSort(int* a, int begin, int end){int mid GetMidi(a, begin, end);Swap(a[begin], a[mid]);int key a[begin];int hole begin;while (begin end){//先从右边开始找小的while (begin end a[end] key){end--;}a[hole] a[end];hole end;//再从左边开始找大的while (begin end a[begin] key){begin;}a[hole] a[begin];hole begin; }a[hole] key;return hole; }void QuickSort2(int* a, int begin, int end){if (begin end)return;int keyi QuickDigSort(a, begin, end);QuickSort2(a, begin, keyi - 1);QuickSort2(a, keyi 1, end);}
测试函数如下
void TestQuickDigSort()
{int f[] { 6,1,5,3,9,10,7,4,2,8 };int size sizeof(f) / sizeof(int);QuickSort2(f, 0, size - 1);printf(快速排序(挖坑法));ArrayPrint(f, size);
}
运行结果如下 5. 对于快速排序代码的另一种书写格式优化前后指针法 对于前后指针法就是通过控制两个指针这里分别命名为,。通过控制这两个指针的动作时序来完成对于数组的排序中心思想如下 对于指针的作用就是用来寻找比小的值 的意义与上面相同对于指针的动作时序分为下面两种情况 当没有遇到比大的值时一直紧跟着当遇到比大的值后令的位置处于这个值的前面。 继续令向后遍历如果又找到了比小的值则交换这个值与后面的值。
例如对于下面的数组 按照上面所说的思想在没有遇到比大的值时一直紧跟着运动即 此时再向下运动遇到了比大的值令继续向后遍历直至找到比小的值令停在比大的值的前面即 再向下运动后遇到了比小的值令后面的值与比小的值交换即 接着继续向下遍历此时指向的位置为 此时再对两个指针指向的值进行交换即 在遍历结束时数组如下 在结束遍历后交换位置的值与的值即 交换完后比小的值都位于左边比 大的值都位于右边。
总览上面的整个过程当遇到了比大的值后两个指针便开始拉开差距。此时每次向后遍历都会找到一个比大的值并且形成一个比大的值的区间在其期间一直保持不动直到遇到一个小的值在向后指向第一个比大的值并且交换此后每找到一个小的值都会把之前大的值置换到后面把小的值置换到前面。
代码如下 //快速排序(前后指针法)int QuickTailSort(int* a, int begin, int end){int key begin;int prev begin, cur begin1;while (cur end){if (a[cur] a[key]){Swap(a[prev], a[cur]);}cur;;}Swap(a[key], a[prev]);return prev;}
测试函数如下
void TestQuickTailSort()
{int g[] { 5,1,6,9,3,10,4,7,2,8 };int size sizeof(g) / sizeof(int);QuickSort3(g, 0, size - 1);printf(快速排序(挖坑法));ArrayPrint(g, size);
}
运行结果如下
