免费发布的网站,连云港seo优化公司,网页版梦幻西游杨洋兑换码是多少,网站首页修改前言 本篇博客我们继续介绍一种排序——快速排序#xff0c;让我们看看快速排序是怎么实现的 #x1f493; 个人主页#xff1a;小张同学zkf ⏩ 文章专栏#xff1a;数据结构 若有问题 评论区见#x1f4dd; #x1f389;欢迎大家点赞#x1f44d;收藏⭐文章 目录
… 前言 本篇博客我们继续介绍一种排序——快速排序让我们看看快速排序是怎么实现的 个人主页小张同学zkf ⏩ 文章专栏数据结构 若有问题 评论区见 欢迎大家点赞收藏⭐文章 目录
1.快速排序hoare方法
2.快速排序挖坑法
3.快速排序前后指针法 4.快速排序非递归法
5.快速排序特性 1.快速排序hoare方法 快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法其基本思想为 任取待排序元素序列中 的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右 子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止 。 // 假设按照升序对 array 数组中 [left, right) 区间中的元素进行排序 void QuickSort ( int array [], int left , int right ) { if ( right - left 1 ) return ; // 按照基准值对 array 数组的 [left, right) 区间中的元素进行划分 int div partion ( array , left , right ); // 划分成功后以 div 为边界形成了左右两部分 [left, div) 和 [div1, right) // 递归排 [left, div) QuickSort ( array , left , div ); // 递归排 [div1, right) QuickSort ( array , div 1 , right ); } 我们先看看快速排序的动图 整体思想以左面的数据为key然后先让right指针向右走找比key位置上的值小的值找到之后停止移动然后left指针向左移动找比key大的值找到之后交换left和right位置上的值然后右指针继续找小左指针继续找大找到之后继续交换重归此过程直到左指针与右指针相遇相遇的位置与key位置上的值交换再把key赋值成相遇的位置。这是单趟排序。再将以key为中心分成两个左右区间再次递归到这个函数中不断递归直到最后的区间为1或不存在区间。递归返回。 代码如下 但如果我们想让快排效率高我们得考虑些极端情况比如如果右边指针一直没找到比最左边的数大的左右指针直接在key位置上相遇了。 递归只有一个区间一直递归就会大大降低了快排的效率特别是在有序的情况下所以只有每次递归key都在中间位置时效率才最快所以我们可以定义一个三数取中的函数函数的返回值与left位置上的值交换就ok了。 那三数取中么写其实很简单就是比较最左边最右边以及最中间的值谁是第二大的返回第二大的就行。
三数取中代码如下
int sanshuquzhong(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[right] a[left]){return left;}else{return right;}}}else{if (a[mid] a[right]){return mid;}else{if (a[right] a[left]){return right;}else{return left;}}}
}
有了三数取中快排效率就明显提高但是还是有人觉得快排不够快确实随着递归的深入效率会越来越慢所以为了加快效率我们可以进行小区间优化 我们由图分析可知最后一次递归耗费次数最多所以我们可以对最后几次小区间下手用其他排序替换快排从而让效率提高我们可以在最后几个区间时用插入排序来进行
void charupaixu(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}
ok,到这里我们的代码就写完了我们想一个问题为什么我们要选key并且选的key在左边时一定要右边指针先走才行为什么这么规定那。如下图分析 这样快速排序hoare方法就初步得成所有代码如下
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
void swap(int* as, int* ak)
{int tmp *as;*as *ak;*ak tmp;
}
void charupaixu(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}
int sanshuquzhong(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[right] a[left]){return left;}else{return right;}}}else{if (a[mid] a[right]){return mid;}else{if (a[right] a[left]){return right;}else{return left;}}}
}
void kuaisupaixu(int* arr, int left,int right)
{if (right left){return;}if (right - left 1 10)//小区间排序{charupaixu(arr left, right -left 1);}int mid sanshuquzhong(arr,left, right);//三数取中swap(arr[mid], arr[left]);int key left;int begin left;int end right;while (beginend){while (beginendarr[end] arr[key]){end--;}while (beginendarr[begin] arr[key]){begin;}swap(arr[end], arr[begin]);}swap(arr[begin], arr[key]);key begin;kuaisupaixu(arr,left,key-1);kuaisupaixu(arr,key1,right);
} 2.快速排序挖坑法
随着快排的不断发展人们优化了hoare方法用挖坑法虽然这种方法没有效率的提升不过方便了人们对代码的理解再也不用考虑为什么要右边先走的问题
我们看一下这个方法的动图 其实就是把交换换成填补定义一个临时变量为坑最后把Key自然放进坑位就行这个方法更方便我们理解
就是在hoare方法代码中微调一下就行
代码如下
// 快速排序挖坑法
void PartSort2(int* a, int left, int right)
{if (left right){return;}if (right - left 1 10){charu(aleft, right - left 1);}else{int mid sanshuquzhong(a, left, right);swap(a[mid], a[left]);int key a[left];int begin left;int end right;int keng left;while (begin end){while (begin end a[end] key){end--;}a[keng] a[end];keng end;while (begin end a[begin] key){begin;}a[keng] a[begin];keng begin;}a[begin] key;PartSort2(a, left, begin- 1);PartSort2(a, begin 1, right);}} 3.快速排序前后指针法
快速排序还有另一种方法也是最容易记住的我们可以通过定义两个指针刚开始一个指向key一个指向key的下一个数让前面那个指针一直向前走找比key小的数第二个若找到比key小的数那么前后指针之间的数就是比key大的数后指针再交换俩指针指向的数前指针继续向前找直到超过边界停止最后key与此时后指针指向的书交换并且key赋值于后指针的位置递归key前key后空间
动图如下 我们可以画图分析一下 代码如下
// 快速排序前后指针法
void PartSort3(int* a, int left, int right)
{if (left right){return;}if (right - left 1 10){charu(a left, right - left 1);}else{int mid sanshuquzhong(a, left, right);swap(a[mid], a[left]);int key left;int man left;int kuai left 1;while (kuai right){if (a[kuai] a[key] man ! kuai){swap(a[man], a[kuai]);}kuai;}swap(a[key], a[man]);key man;PartSort3(a, left, key - 1);PartSort3(a, key 1, right);}
} 4.快速排序非递归法
前三种方法都是递归法若不用递归我们该怎么弄不用递归我们就得需要栈这个结构代码整体不变把最后递归的部分改成把key左右两个区间全入栈先右区间入栈再左区间入栈因为栈是后进先出原则出栈就是左区间先出栈直到栈空入栈的条件左指针小于Key-1,右指针大于key1。
画图看一下 区间边界值入栈来替代了递归
代码如下
#include stack.h
int yici(int* a,int left,int right)
{int mid sanshuquzhong(a, left, right);swap(a[mid], a[left]);int key left;int begin left;int end right;while (begin end){while (begin end a[end] a[key]){end--;}while (begin end a[begin] a[key]){begin;}swap(a[begin], a[end]);}swap(a[key], a[begin]);key begin;return key;
}
void QuickSortNonR(int* a, int left, int right)
{if (right - left 1 10){charu(a left, right - left 1);}else{Stack as;StackInit(as);StackPush(as, right);StackPush(as, left);while (!StackEmpty(as)){int begin1 StackTop(as);StackPop(as);int end1 StackTop(as);StackPop(as);int key yici(a, begin1, end1);if (key 1 end1){StackPush(as, end1);StackPush(as, key 1);}if (key - 1 begin1){StackPush(as, key - 1);StackPush(as, begin1);}}StackDestroy(as);}
} 5.快速排序特性 快速排序的特性总结 1. 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫 快速 排序 2. 时间复杂度 O(N*logN) 3. 空间复杂度 O(logN) 4. 稳定性不稳定 结束语 快排有关知识就总结完了我认为快速排序这个排序还是蛮重要的大家要对这个排序更加重视最后一个排序就是归并排序了留在下篇博客说 0K本篇博客结束
