广东网站设计品牌设计,app开发策划书范文,win8 风格网站模板,如何网站公司小程序快速排序 前言一、快速排序的基本思想常见方式通用模块 二、快速排序的特性总结三、三种快速排序的动画展示四、hoare版本快速排序的代码展示普通版本优化版本为什么要优化快速排序代码三数取中法优化代码 五、挖坑法快速排序的代码展示六、前后指针快速排序的代码展示七、非递… 快速排序 前言一、快速排序的基本思想常见方式通用模块 二、快速排序的特性总结三、三种快速排序的动画展示四、hoare版本快速排序的代码展示普通版本优化版本为什么要优化快速排序代码三数取中法优化代码 五、挖坑法快速排序的代码展示六、前后指针快速排序的代码展示七、非递归实现快速排序的代码展示Stack.hStack.c非递归实现快速排序 八、快速排序的完整代码 前言
快速排序是一种高效的排序算法通过选取一个“基准”元素将数组分为两部分比基准小的元素和比基准大的元素然后递归地对这两部分进行排序从而实现对整个数组的排序。该算法平均时间复杂度为O(nlogn)最坏情况下为O(n²)但由于实际应用中很少出现最坏情况因此快速排序仍然是一种广泛使用的排序算法。 一、快速排序的基本思想 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
快速排序的基本思想是采用分治策略通过选取一个“基准”元素将待排序的数组分为两个子数组一个子数组的元素都比基准元素小另一个子数组的元素都比基准元素大然后对这两个子数组递归地进行快速排序从而达到对整个数组排序的目的。
在快速排序的具体实现中通常选择数组中的一个元素作为基准元素然后将数组中的其他元素与基准元素进行比较根据比较结果将元素放到两个子数组中。这个过程可以通过使用双指针技术来实现一个指针从数组的开头开始向右移动另一个指针从数组的末尾开始向左移动当左指针指向的元素小于等于基准元素且右指针指向的元素大于等于基准元素时交换这两个元素的位置。当左指针移动到右指针的位置时整个数组就被划分为了两个子数组。
接下来对这两个子数组分别进行快速排序。递归地调用快速排序函数传入子数组的首尾指针作为参数直到整个数组都被排序完毕。
快速排序的时间复杂度在最坏情况下为O(n²)即当每次选取的基准元素都是当前数组中的最小或最大元素时会导致每次划分得到的子数组大小相差很大从而使得递归树的深度很大排序效率降低。然而在实际应用中由于快速排序的随机性其平均时间复杂度为O(nlogn)因此在实际应用中具有很高的效率。
此外快速排序是一种原地排序算法只需要常数级别的额外空间因此在处理大规模数据时具有很大的优势。同时快速排序也是一种不稳定的排序算法即相等的元素在排序后可能会改变它们的相对位置。
综上所述快速排序是一种基于分治策略的排序算法通过递归地将数组划分为子数组并对其进行排序实现了对整个数组的排序。虽然在最坏情况下其时间复杂度可能达到O(n²)但在实际应用中其平均时间复杂度为O(nlogn)具有很高的效率。同时快速排序也是一种原地、不稳定的排序算法适用于处理大规模数据。
常见方式
将区间按照基准值划分为左右两半部分的常见方式有 hoare版本 挖坑法 前后指针版本
通用模块
/ 假设按照升序对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, div1, right);
}二、快速排序的特性总结
快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序时间复杂度O(N*logN) 空间复杂度O(logN)稳定性不稳定
快速排序是一种高效的排序算法其最显著的特点是其“分而治之”的策略。它的基本思想是通过一个分割操作将待排序的序列划分为两个子序列其中一个子序列的所有元素都比另一个子序列的所有元素要小然后再对这两个子序列分别进行快速排序从而达到整个序列有序的目的。
快速排序的高效性主要得益于其内部循环可以在大部分的实际情况下将元素放到最终的位置上这被称为“原地排序”因为它只需要常量级的额外空间来存放辅助信息。然而这也带来了一个潜在的问题即在最坏情况下当输入序列已经有序或者逆序时快速排序的时间复杂度会退化到O(n^2)这是因为分割操作会导致不平衡的子序列划分。 为了解决这个问题通常会采用随机化或者“三数取中”等策略来选择分割点以减少最坏情况发生的概率。此外还可以采用“堆排序”或者“归并排序”等其他排序算法作为备选方案在检测到快速排序性能下降时自动切换。 快速排序的另一个重要特性是其不稳定性。这意味着在排序过程中相等的元素可能会改变它们的相对顺序。这通常不会影响到排序结果的正确性但在某些特定的应用场景下如需要保持元素原始顺序的排序就需要选择其他稳定的排序算法。
综上所述快速排序是一种强大而灵活的排序工具其“分而治之”的策略和原地排序的特性使其在许多情况下都成为首选的排序算法。然而为了充分发挥其性能优势也需要对其潜在的缺点有所了解并采取相应的策略进行规避。
三、三种快速排序的动画展示 hoare版本快速排序的动画展示 Hoare版本快速排序的动画展示揭示了该排序算法的工作原理。在动画中初始未排序的数组被选取一个基准值pivot然后将数组分为两部分小于基准值的元素和大于基准值的元素。这个过程通过不断调整基准值的位置使得数组逐渐变得有序。动画清晰展示了分区过程以及递归地对子数组进行相同操作的步骤直到整个数组完全排序。整个过程直观展示了快速排序算法的高效性和稳定性。 hoare——快速排序 挖坑法快速排序的动画展示 挖坑法快速排序是一种排序算法的可视化展现。它展示了如何通过不断挖坑、填坑的过程将数组分为两部分使得左边的元素都比右边的元素小从而实现快速排序。动画中可以看到随着排序的进行数组被逐渐整理成有序状态。 挖坑法——快速排序 前后指针快速排序的动画展示 该段话介绍了前后指针快速排序的动画展示。其核心在于通过动画形式直观地展示了前后指针快速排序的过程。该算法利用两个指针以找到需要交换的元素对并进行交换。通过重复此过程最终实现数组的排序。动画演示使得这一过程更加直观易懂。 前后指针——快速排序 四、hoare版本快速排序的代码展示
普通版本
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void QuickSort(int* a, int left, int right)//hoare
{// 区间只有一个值或者不存在就是最小子问题if (left right)return;int begin left, end right;int keyi left;while (left right){// right先走找小while (left right a[right] a[keyi]){--right;}// left再走找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);keyi left;// [begin, keyi-1]keyi[keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}这段代码是实现了经典的快速排序QuickSort算法使用了Hoare版本的分区partitioning策略。快速排序是一种非常高效的排序算法平均时间复杂度为O(nlogn)。下面我将对代码进行逐行分析 void QuickSort(int* a, int left, int right)定义了一个名为QuickSort的函数它接受三个参数一个整数数组的指针a以及要排序的区间的左右端点left和right。 if (left right) return;如果区间内只有一个元素或者没有元素即left大于或等于right那么就没有排序的必要函数直接返回。 int begin left, end right;定义了两个变量begin和end分别初始化为区间的左右端点。这两个变量将用于后续的递归调用。 int keyi left;定义了一个变量keyi并初始化为区间的左端点。keyi将作为基准pivot值用于划分数组。 while (left right)主循环当left小于right时继续执行循环体。 接下来的两个while循环用于调整数组元素的位置使得比a[keyi]小的元素都在它的左边比它大的元素都在它的右边。 第一个while循环从右向左遍历数组找到第一个小于a[keyi]的元素right的数值就是此时的下标。第二个while循环从左向右遍历数组找到第一个大于a[keyi]的元素left的数值就是此时的下标。 Swap(a[left], a[right]);交换a[left]和a[right]两个元素的位置。 Swap(a[left], a[keyi]);将基准值a[keyi]放到正确的位置上即它左边的所有元素都小于它右边的所有元素都大于它。此时left所指向的位置就是keyi的正确位置。 QuickSort(a, begin, keyi - 1);对基准值左边的子区间进行递归排序。 QuickSort(a, keyi 1, end);对基准值右边的子区间进行递归排序。
这段代码实现了快速排序的基本思想选择一个基准值通过一趟排序将数组分成两部分其中一部分的所有数据都比另一部分的所有数据要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。
优化版本
为什么要优化快速排序代码
优化快速排序代码的目的是提高排序算法的性能使其更快地完成排序任务。快速排序是一种高效的排序算法但在某些情况下原始的快速排序算法可能会比较慢或占用更多的内存。通过对代码进行优化可以减少不必要的比较和交换操作以提高算法的效率。 例如当要排序的数组是有序的时候你的数组是一个降序数组但是你要将他变成升序此时使用快速排序会使代码的时间复杂度变得非常的大即O(N2) 以下是一些常见的优化快速排序代码的方法 选取合适的枢轴元素枢轴元素的选择对快速排序的性能影响很大。选择一个合适的枢轴元素可以减少比较和交换的次数。常用的选择方法有随机选择、中位数选择和三数取中等。 使用插入排序对于小规模的子数组使用插入排序可能比快速排序更高效。当子数组的规模小于某个阈值时可以切换到插入排序来提高性能。 优化递归调用快速排序是一个递归算法递归调用会带来一定的性能开销。可以考虑使用尾递归或迭代来替代递归调用以减少函数调用的开销。 避免重复比较在递归过程中可能会重复比较相同的元素这是不必要的。可以通过增加判断条件来避免重复比较以提高性能。
总之通过优化快速排序代码可以加快排序算法的执行速度减少不必要的开销提高算法的效率。
三数取中法
三数取中法是一种排序算法中的选择方法用于快速排序等算法中选取基准元素。它选取待排序数组中第一个、中间和最后一个元素中的中值作为基准以保证基准元素的选择相对均匀从而提高排序效率。这种方法在处理大量数据时表现优秀能有效减少比较和交换次数提高排序速度。
int GetMidi(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[left] a[right]){return left;}else return right;}else{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
}这段代码是一个函数函数名为GetMidi接受一个int类型的数组a和两个整型参数left和right。
函数的作用是找到数组a中的一个索引值使得该索引值对应的元素值是数组中的中间值。中间值的定义是当数组a按照升序排列时它的前半部分元素值都小于它后半部分元素值都大于它。
函数首先计算mid值即left和right的中间值。然后通过对比a[left]、a[mid]和a[right]的值来确定mid值是否满足中间值的条件。
具体判断逻辑如下
首先判断a[left]和a[mid]的大小关系。 若a[left] a[mid]则继续判断a[mid]和a[right]的大小关系。 若a[mid] a[right]则返回mid。若a[left] a[right]则返回left。若以上条件均不满足则返回right。 若a[left] ≥ a[mid]则继续判断a[mid]和a[right]的大小关系。 若a[mid] a[right]则返回mid。若a[left] a[right]则返回left。若以上条件均不满足则返回right。
这段代码的时间复杂度是O(1)因为只是进行有限次的比较和赋值操作不涉及循环。
优化代码
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void QuickSort(int* a, int left, int right)//hoare
{// 区间只有一个值或者不存在就是最小子问题if (left right)return;//优化,也可以不加if (right - left 1 10){InsertSort(a left, right - left 1);//直接插入排序也可以换成其他排序return;}else{int begin left, end right;//优化三数取中法int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int keyi left;while (left right){// right先走找小while (left right a[right] a[keyi]){--right;}// left再走找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);keyi left;// [begin, keyi-1]keyi[keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}}该代码实现了快速排序算法。
函数Swap用于交换两个指针所指向的值。
函数QuickSort是快速排序的主函数它接受一个整型数组a、左右边界left和right作为参数。在函数中首先判断区间的大小如果区间只有一个值或者不存在则直接返回。如果区间大小小于10则使用插入排序进行排序否则进行快速排序。
在快速排序的过程中选择一个基准值这里使用三数取中法选择基准值的索引并将该基准值与左边界的值进行交换。然后使用左右两个指针分别从左右两边开始向中间遍历找到左边大于基准值的元素和右边小于基准值的元素然后交换这两个元素的位置。最后将基准值与左指针的值进行交换完成一次划分。
然后将左边和右边的子数组进行递归调用快速排序直到区间大小为1或不存在完成整个排序过程。
总结起来这段代码实现了一个使用了优化的快速排序算法其中使用了三数取中法选择基准值和插入排序来优化小区间的排序。
五、挖坑法快速排序的代码展示
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void Quick1Sort(int* a, int left, int right)
{// 区间只有一个值或者不存在就是最小子问题if (left right)return;//优化,也可以不加if (right - left 1 10){InsertSort(a left, right - left 1);return;}int keyi left, begin left, end right;int tmp a[keyi];while (left right){// right先走找小while (left right a[right] a[keyi]){--right;}Swap(a[keyi], a[right]);keyi right;// left再走找大while (left right a[left] a[keyi]){left;}Swap(a[keyi], a[left]);keyi left;}Swap(a[keyi], tmp);// [begin, keyi-1]keyi[keyi1, end]Quick1Sort(a, begin, keyi - 1);Quick1Sort(a, keyi 1, end);
}这段代码实现了快速排序的挖坑算法。函数Quick1Sort接收一个整型数组a以及数组的左右边界left和right。函数的作用是对数组a的[left, right]区间进行快速排序。
快速排序的基本思想是选取一个基准元素将数组分为两个部分一部分是小于等于基准元素的元素另一部分是大于基准元素的元素。然后分别对这两部分递归进行快速排序直到区间只有一个元素或者为空。
代码的具体实现如下
如果left大于等于right则不需要进行排序直接返回。如果区间的长度小于10使用插入排序进行排序。这是一个优化当区间长度较小时插入排序的效率可能更高。初始化两个指针keyi、begin和end。keyi指向基准元素begin和end分别指向区间的左右边界。使用tmp保存基准元素的值。通过双指针的方式找到比基准元素小的元素并交换到右侧再找到比基准元素大的元素并交换到左侧。直到左指针和右指针相遇。此时左指针的位置就是基准元素的最终位置将基准元素与tmp交换。接下来递归调用Quick1Sort函数对左右两个区间进行排序左区间是[begin, keyi-1]右区间是[keyi1, end]。
六、前后指针快速排序的代码展示
void Quick2Sort(int* a, int left, int right)
{if (left right)return;int prev left;int cur left 1;int key left;while (cur right){if (a[cur] a[key] prev ! cur)Swap(a[cur], a[prev]);cur;}Swap(a[key], a[prev]);key prev;Quick2Sort(a, left, key - 1);Quick2Sort(a, key 1, right);
}这是快速排序的一种常见的排序算法其基本思想是通过选择一个基准元素将序列分为两个子序列其中一个子序列中的元素都小于基准元素另一个子序列中的元素都大于基准元素然后对两个子序列递归地进行快速排序。
具体分析代码如下 函数定义void Quick2Sort(int* a, int left, int right) 参数a表示待排序的数组left和right表示数组的左右边界返回类型为void表示不需要返回排序后的数组。 判断递归结束条件if (left right) return; 如果左边界大于等于右边界说明已经排好序或只有一个元素无需再排序直接返回。 初始化变量 int prev left;prev表示小于基准元素的最后一个元素的位置初始化为左边界int cur left 1;cur表示当前遍历的元素的位置初始化为左边界加1int key left;key表示基准元素的位置初始化为左边界。 遍历数组 while (cur right)循环遍历数组直到当前元素的位置大于右边界。if (a[cur] a[key] prev ! cur) Swap(a[cur], a[prev])如果当前元素小于基准元素且prev不等于cur即有大于基准元素的元素存在则将当前元素与prev位置上的元素进行交换并且prev向后移动一位。cur将当前元素的位置向后移动一位继续遍历数组。 将基准元素放置到正确的位置 Swap(a[key], a[prev])将基准元素与prev位置上的元素进行交换使得基准元素放置到正确的位置。 递归调用快速排序 Quick2Sort(a, left, key - 1)对左边子数组进行快速排序左边界为left右边界为key-1Quick2Sort(a, key 1, right)对右边子数组进行快速排序左边界为key1右边界为right。 整个函数结束。
七、非递归实现快速排序的代码展示
实现栈的非递归需要使用到栈的知识——栈
对栈不理解的可以看我之前写的文章
Stack.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h
typedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;int capacity;
}ST;void STInit(ST* ps);//栈的初始化
void STDestroy(ST* ps);//栈的销毁//入栈
void STPush(ST* ps,STDatatype x);
//出栈
void STPop(ST* ps);
STDatatype STTop(ST* ps);//返回栈顶元素
int STSize(ST* ps);//返回栈中的元素个数
bool STEmpty(ST* ps);//检测是否为空Stack.c
#include Stack.hvoid STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity 0;ps-top 0;
}
void STPush(ST* ps,STDatatype x)
{assert(ps);if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDatatype* p (STDatatype*)realloc(ps-a, sizeof(STDatatype)*newcapacity);if (p NULL){perror(p malloc : );return ;}ps-a p;ps-capacity newcapacity;}ps-a[ps-top] x;ps-top;
}
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps-top--;
}bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}
STDatatype STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps-a[ps-top - 1];
}
int STSize(ST* ps)
{assert(ps);return ps-top;
}非递归实现快速排序
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(st);STPush(st, right);STPush(st, left);while (!STEmpty(st)){int begin STTop(st);STPop(st);int end STTop(st);STPop(st);// 单趟int keyi begin;int prev begin;int cur begin 1;while (cur end){if (a[cur] a[keyi] prev ! cur)Swap(a[prev], a[cur]);cur;}Swap(a[keyi], a[prev]);keyi prev;// [begin, keyi-1] keyi [keyi1, end] if (keyi 1 end){STPush(st, end);STPush(st, keyi 1);}if (begin keyi - 1){STPush(st, keyi - 1);STPush(st, begin);}}STDestroy(st);
}这段代码实现的是非递归版本的快速排序算法。
首先这段代码使用了一个栈结构ST来保存待排序子数组的起始和结束索引。
在主循环中每次从栈中弹出两个索引分别表示待排序子数组的起始和结束位置。接下来执行单趟排序即将子数组中的元素按照基准元素的大小进行分区使得基准元素左边的元素都小于或等于它右边的元素都大于它。具体的分区过程使用了prev和cur两个指针prev指向当前已处理的小于基准元素的最右边的位置cur从prev1开始遍历。如果a[cur]小于基准元素则将它与prev1位置的元素进行交换并将prev向右移动一位。最后将基准元素放到prev位置并用keyi保存基准元素的索引。
接下来根据keyi的位置将子数组分成左右两个部分。如果keyi1小于end说明右边的子数组还有未排序的元素将右子数组范围的起始和结束索引入栈。如果begin小于keyi-1说明左边的子数组还有未排序的元素将左子数组范围的起始和结束索引入栈。
最后在主循环结束后销毁栈结构。
总的来说这段代码通过栈结构实现了快速排序的非递归版本避免了递归调用带来的额外开销。
八、快速排序的完整代码
#includestdio.h
#includestdlib.h
#includetime.h
#include Stack.h
void PrintArray(int* a, int n);
void QuickSort(int* a, int left, int right);//hoare
void Quick1Sort(int* a, int left, int right);//挖坑法
void Quick2Sort(int* a, int left, int right);//前后指针法
void QuickSortNonR(int* a, int left, int right);// 非递归实现
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}elsebreak;}a[end 1] tmp;}
}void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}
void TestQuickSort()
{//int a[] { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };int a[] { 6,1,2,7,9,3,4,5,10,8 };//int a[] { 1,2,3,4,5,6,7,8,9,10,11,12,13,15,17,19};PrintArray(a, sizeof(a) / sizeof(int));QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}
void TestQuick1Sort()
{int a[] { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };//int a[] { 6,1,2,7,9,3,4,5,10,8 };//int a[] { 1,2,3,4,5,6,7,8,9,10,11,12,13,15,17,19};PrintArray(a, sizeof(a) / sizeof(int));Quick1Sort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}
void TestQuick2Sort()
{int a[] { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };//int a[] { 6,1,2,7,9,3,4,5,10,8 };//int a[] { 1,2,3,4,5,6,7,8,9,10,11,12,13,15,17,19};PrintArray(a, sizeof(a) / sizeof(int));Quick2Sort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}
void TestQuick3Sort()
{int a[] { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };//int a[] { 6,1,2,7,9,3,4,5,10,8 };//int a[] { 1,2,3,4,5,6,7,8,9,10,11,12,13,15,17,19};PrintArray(a, sizeof(a) / sizeof(int));QuickSortNonR(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}
int GetMidi(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[left] a[right]){return left;}else return right;}else{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
}
void QuickSort(int* a, int left, int right)//hoare
{// 区间只有一个值或者不存在就是最小子问题if (left right)return;//优化,也可以不加if (right - left 1 10){InsertSort(a left, right - left 1);return;}else{int begin left, end right;//优化三数取中法int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int keyi left;while (left right){// right先走找小while (left right a[right] a[keyi]){--right;}// left再走找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);keyi left;// [begin, keyi-1]keyi[keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}}
void Quick1Sort(int* a, int left, int right)
{// 区间只有一个值或者不存在就是最小子问题if (left right)return;//优化,也可以不加if (right - left 1 10){InsertSort(a left, right - left 1);return;}int keyi left, begin left, end right;int tmp a[keyi];while (left right){// right先走找小while (left right a[right] a[keyi]){--right;}Swap(a[keyi], a[right]);keyi right;// left再走找大while (left right a[left] a[keyi]){left;}Swap(a[keyi], a[left]);keyi left;}Swap(a[keyi], tmp);// [begin, keyi-1]keyi[keyi1, end]Quick1Sort(a, begin, keyi - 1);Quick1Sort(a, keyi 1, end);
}
void Quick2Sort(int* a, int left, int right)
{if (left right)return;int prev left;int cur left 1;int key left;while (cur right){if (a[cur] a[key] prev ! cur)Swap(a[cur], a[prev]);cur;}Swap(a[key], a[prev]);key prev;Quick2Sort(a, left, key - 1);Quick2Sort(a, key 1, right);
}
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(st);STPush(st, right);STPush(st, left);while (!STEmpty(st)){int begin STTop(st);STPop(st);int end STTop(st);STPop(st);// 单趟int keyi begin;int prev begin;int cur begin 1;while (cur end){if (a[cur] a[keyi] prev ! cur)Swap(a[prev], a[cur]);cur;}Swap(a[keyi], a[prev]);keyi prev;// [begin, keyi-1] keyi [keyi1, end] if (keyi 1 end){STPush(st, end);STPush(st, keyi 1);}if (begin keyi - 1){STPush(st, keyi - 1);STPush(st, begin);}}STDestroy(st);
}
void TestOP()
{srand(time(0));const int N 1000000;int* a1 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand();}int begin1 clock();QuickSort(a1,0,N- 1);int end1 clock();printf(QuickSort:%d\n, end1 - begin1);free(a1);
}
void Test1OP()
{srand(time(0));const int N 1000000;int* a1 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand();}int begin1 clock();Quick1Sort(a1, 0, N - 1);int end1 clock();printf(Quick1Sort:%d\n, end1 - begin1);free(a1);
}
void Test3OP()
{srand(time(0));const int N 1000000;int* a1 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand();}int begin1 clock();Quick2Sort(a1, 0, N - 1);int end1 clock();printf(Quick2Sort:%d\n, end1 - begin1);free(a1);
}
void Test4OP()
{srand(time(0));const int N 1000000;int* a1 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand();}int begin1 clock();QuickSortNonR(a1, 0, N - 1);int end1 clock();printf(QuickSortNonR:%d\n, end1 - begin1);free(a1);
}
int main()
{TestQuickSort();TestQuick1Sort();TestQuick2Sort();TestQuick3Sort();TestOP();Test1OP();Test3OP();Test4OP();return 0;
}
