南昌网站建设公司渠道,白鹭引擎做网站,室内设计去哪里学,分类网站怎么做项目文章目录 一、创始人托尼霍尔的快速排序二、挖坑法三、前后指针法 所属专栏:C初阶 引言#xff1a;这里所说的快速排序有三种#xff0c;第一种是霍尔大佬自创的#xff0c;还有一种叫做挖坑法#xff0c;另外一种叫前后指针法 一、创始人托尼霍尔的快速排序 1.这里我们先… 文章目录 一、创始人托尼·霍尔的快速排序二、挖坑法三、前后指针法 所属专栏:C初阶 引言这里所说的快速排序有三种第一种是霍尔大佬自创的还有一种叫做挖坑法另外一种叫前后指针法 一、创始人托尼·霍尔的快速排序 1.这里我们先把中间值定位数组中的首元素的值设为key变量大于key的放右边小于key的放左边 2.定义left为从数组0下标开始找大于key的数如果小于keyleft就向前走一步定义right从数组下标为n-1的位置从右向左找小于key的数从最右边的数开始如果大于keyright就向后走一步 3.这里我们还要判断谁先和谁相遇也就是谁走到相等的位置而那个人是停止的) 如果left先走那么left与right相遇的地方就是left走遇到right(相遇的地方的值是大于key的) 如果right先走那么left与right相遇的地方就是right走遇到left(相遇的地方的值是小于key的)
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
void Swap(int* p1,int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
int QuickSort(int left,int right,int* a)
{int keyi left;int end right;//判断谁先走的问题我们把大于a[keyi]的放左边//小于a[keyi]的放右边等于的话就不管//这里要判断谁先走的问题//如果left先走那么left与right相遇的地方就是left走遇到right//如果right先走那么left与right相遇的地方就是right走遇到leftwhile (left right){//右边找小while(left right a[right] a[keyi])right--;//左边找大while(left right a[left] a[keyi])left;Swap(a[left], a[right]);}Swap(a[left], a[keyi]);return left;
}void TestSort(int* a, int begin,int end)
{if (begin end)//当只有一个数时不用排序直接返回return;//霍尔大佬的排序int keyi QuickSort(begin, end ,a);TestSort(a, begin,keyi-1);TestSort(a, keyi1,end);
}
int main()
{int a[] {6,1,2,7,9,3,4,5,10,8};TestSort(a, 0, sizeof(a) / sizeof(int) - 1);for (int i 0; i sizeof(a) / sizeof(int); i)printf(%d , a[i]);return 0;
}这里的排序就像是二叉树的遍历大家可以参考前面的代码 排序区间【beginkeyi-1】keyi 【keyi1,end】keyi为中间值已经排好序了 二、挖坑法
步骤如下 1.这里的挖坑从a[left]开始是第一个坑然后right寻找小于keya[left]的值找到了这个坑就跑到a[right]去了同时要交换一下下标holeright 2.然后就从left开始找大于key的值找到了那么就是第二个坑hole就跳到了left的位置holeleft 3.以此类推直到leftright的时候此时的坑就在leftright的地方然后a[hole]key此时的key就是中间值不需要排了
int QuickSort(int left,int right,int* a)
{int key a[left];int end right;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 left;
}三、前后指针法
步骤如下 1.首先定义一个前指针prev和一个后指针cur 2.然后cur先向前走如果大于key那么继续向前走prev不向前走如果小于key那么prev和cur同时向前走总的来说cur一直是向前走的prev只在cur位置小于key才向前走的 3.以此类推直到curend就不走了
int QuickSort3(int left, int right, int* a)
{int key a[left];int prev left;int cur left 1;while (cur right){if (a[cur] key prev ! cur)Swap(a[prev],a[cur]);cur;}//最后这里的a[prev]一定是一个小于key的值//所以需要和key这个中间值换一下以达到key已经排好序Swap(a[prev], a[left]);return prev;
}
