优质的广州微网站建设,小辣椒网站开发,最新新闻事件100字,哪些网站可以做旅游文章目录 一、hoare版本二、挖坑法三、前后指针法四、非递归快排五、快速排序优化1、三数取中选key值2、小区间优化 六、代码测试 一、hoare版本 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法#xff0c;其基本思想为#xff1a;任取待排序元素序列中的某元素… 文章目录 一、hoare版本二、挖坑法三、前后指针法四、非递归快排五、快速排序优化1、三数取中选key值2、小区间优化 六、代码测试 一、hoare版本 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后左右子序列重复该过程直到所有元素都排列在相应位置上为止。 算法思想
定义一个keyi存入随机一个数key的下标换到数组首元素这里先直接默认key为数组首元素定义一个left和一个right分别存入数组首元素和尾元素的下标用来移动交换排升序我们让右边right先向左移动找到比key的值小的元素则停下来换到left移动left向右移动找到比key的值大的元素则停下交换下标为left和right的元素重复以上操作直到left与right相遇相等交换key和下标为left的元素此时key的左边都是比它小的数右边都是比它大的数再分别对左右序列进行以上的单趟排序反复操作直到左右序列只有一个或者没有元素时停止操作数列即可有序
hoare版本单趟排序图示 hoare版本代码
//交换
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
//hoare版本
void QuickSort1(int* a, int begin, int end)
{//递归结束条件if (begin end){return;}int keyi begin;int left begin;int right end;//每趟排序直到左右相遇while (left right){//右边先走找到比key值小的while (left right a[right] a[keyi]){right--;}//right找到比key值小的之后换到left走找到比key值大的while (left right a[left] a[keyi]){left;}//交换Swap(a[left], a[right]);}//将key值换到中间Swap(a[keyi], a[left]);//更新keykeyi left;//对左右序列继续排序QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi 1, end);
}整体流程图 二、挖坑法
挖坑法思想
先将第一个数据存在变量key中将此处作为最开始的坑位用下标hole记录然后right开始向前走找到比key值小的元素后停下将此元素放进坑里下标为hole处然后此处变为坑hole变为此时的right然后left开始向后移动找到比key值大的元素后停下将此元素放进坑里下标为hole处然后此处变为坑hole变为此时的left然后又换回right移动如此反复直到left与right相遇left与right相遇的地方一定是坑然后将key放入left与right相遇的位置也就是坑的位置此时hole左边都是小于等于它的右边都是大于等于它的如此单趟排序便结束然后继续对hole左右序列继续反复执行以上操作直到左右序列只有一个或者没有元素时停止操作数列即可有序
挖坑法单趟排序图示 挖坑法代码
//挖坑法
void QuickSort2(int* a, int begin, int end)
{//递归结束条件if (begin end){return;}int left begin;int right end;int key a[left];//坑最初与left一样在开始位置int hole left;//每趟排序直到左右相遇while (left right){//右边先走找到比key值小的while (left right a[right] key){right--;}//将right找到的比key小的元素放进坑中a[hole] a[right];//更新坑的位置hole right;//然后左边走找到比key值大的元素停下来while (left right a[left] key){left;}//将left找到的比key大的元素放进坑中a[hole] a[left];//更新坑的位置hole left;}//将key放入坑中a[hole] key;//对左右序列继续排序QuickSort2(a, begin, hole - 1);QuickSort2(a, hole1, end);
}三、前后指针法
前后指针法思想
定义一个keyi存入随机一个数key的下标换到数组首元素这里先直接默认key为数组首元素定义一个prev为开头元素的下标定义一个cur为prev下一个元素的下标cur下标处的值与key比较直到cur找到比key小的值则停下来prev下标后移一位然后与cur下标处的值交换然后cur后移一位prev相当于前面比key小的那些数的最后一个的下标所以要先后移一位再交换cur继续寻找比key小的值反复执行直到cur的值大于n将key与prev下标处的值交换此时key左边都是小于等于它的右边都是大于等于它的如此单趟排序便结束然后继续对key左右序列继续反复执行以上操作直到左右序列只有一个或者没有元素时停止操作数列即可有序
前后指针法单趟排序图示 前后指针法代码
//交换
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
//前后指针
void QuickSort3(int* a, int begin, int end)
{//递归结束条件if (begin end){return;}int keyi begin;int prev begin;int cur begin 1;//每趟排序直到cur下标大于endwhile (cur end){//cur找比key小的值if (a[cur] a[keyi] prev ! cur){Swap(a[cur], a[prev]);}cur;}//将key换到中间Swap(a[keyi], a[prev]);//更新key的下标keyi prev;//对左右序列继续排序QuickSort3(a, begin, keyi - 1);QuickSort3(a, keyi 1, end);
}快速排序是一种不稳定的排序它的时间复杂度为O(N*logN)但最坏可以达到O(N2) 它的空间复杂度为O(logN)
四、非递归快排
以上三种方法都是采用了分治法递归实现的快排其实快速排序也可以非递归实现非递归实现快排需要利用栈来实现
思路
将数组首尾下标存入栈中在循环中依次取出作为left和right对数组进行排序然后对得到的key的左右两边序列也进行相同的操作其中左边为left到keyi-1右边为keyi1到right这些下标的入栈顺序需要看取出的顺序如下面代码中是先取出后面元素下标的所以入栈时要先入后面的因为栈的特点是先入后出。 非递归快排代码
该代码中用到的栈需自己实现C语言实现栈可参考栈的实现
//非递归快速排序
void QuickSortNonR(int* a, int begin, int end)
{//创建一个栈ST st;//初始化栈STInit(st);//插入尾元素下标STPush(st, end);//插入首元素下标STPush(st, begin);//栈为空停下while (!STEmpty(st)){//取出栈顶元素作为leftint left STTop(st);//取出后在栈中删除STPop(st);//取出栈顶元素作为rightint right STTop(st);//取出后在栈中删除STPop(st);int keyi begin;//每趟排序直到左右相遇while (left right){//右边先走找到比key值小的while (left right a[right] a[keyi]){right--;}//right找到比key值小的之后换到left走找到比key值大的while (left right a[left] a[keyi]){left;}//交换Swap(a[left], a[right]);}//将key值换到中间Swap(a[keyi], a[left]);//更新key的下标keyi left;// 当前数组下标样子 [left,keyi-1] keyi [keyi1, right]//右边还有元素按顺序插入right和keyi1if (keyi 1 right){STPush(st, right);STPush(st, keyi 1);}//左边还有元素按顺序插入keyi-1和leftif (left keyi - 1){STPush(st, keyi - 1);STPush(st, left);}}STDestroy(st);
}五、快速排序优化
1、三数取中选key值
前面三种快速排序的方法起初都要随机选取一个值作为key我们之前是直接默认为数组首元素的这样不够随机容易出现最坏的情况使得它的时间复杂度接近O(N2)所以我们可以写一个函数来选取这个key使得它比较随机而不是直接为首元素。
三数取中
在一个数组最前面、最后面中间这三个位置的数中选出大小处于中间的数
// 三数取中
int GetMidi(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[right]){if (a[right] a[mid]){return right;}else if(a[mid]a[right]a[mid]a[left]){return mid;}else{return left;}}else{if (a[left] a[mid]){return left;}else if (a[mid] a[left] a[mid] a[right]){return mid;}else{return right;}}
}在快排时用三数取中法选取key值再将它换到数组开头可以有效避免出现最坏的情况大大提升算法效率
2、小区间优化
当递归到数据较小时可以使用插入排序使得小区间不再递归分割降低递归次数
六、代码测试
//打印数组
void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void TestQuickSort1()
{int a[] { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };QuickSort1(a, 0, sizeof(a) / sizeof(int) - 1);printf(hoare版本快速排序\n);PrintArray(a, sizeof(a) / sizeof(int));
}
void TestQuickSort2()
{int a[] { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };QuickSort2(a, 0, sizeof(a) / sizeof(int) - 1);printf(挖坑法快速排序\n);PrintArray(a, sizeof(a) / sizeof(int));
}
void TestQuickSort3()
{int a[] { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };QuickSort3(a, 0, sizeof(a) / sizeof(int) - 1);printf(前后指针法快速排序\n);PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{TestQuickSort1();TestQuickSort2();TestQuickSort3();return 0;
}
