《快速排序算法的两种实现思路(附源代码)》由会员分享，可在线阅读，更多相关《快速排序算法的两种实现思路(附源代码)（9页珍藏版）》请在金锄头文库上搜索。
1、快速快速排序排序快速排序的基本原理：leftright假设一个待排序的数组如上图所示，排序的目的就是将其从小到大排序。快速排序的主要 步骤就是设定一个待排序的元素（称作主元，记作 temp） ，经过一轮划分排序后在这个主 元左边的元素值都小于它，在主元右边的元素值都大于它，一轮划分后的效果应该是这样 的，如下图：leftrighttemp这样以 temp 元素为分隔就将原来的数组分成了两个左右两个数组，然后再分别对左右两 个子数组进行同样的分隔，然后再对子子数组进行分割，递归调用这种分隔，直到最后不 能再分了，此时数组也就是有序的了。基本原理是相同的，但是具体是怎么分隔的有两种不同的思路。一种
2、称作：“左右倒腾法” 此种方法将数组分成了三个部分，小于主元的部分，大于主元的部分，未划分的部分。leftright未比较的元素小于temp的元素大于temp的元素首先，要选定一个元素作为主元 temp，这里将第一个元素 left 视为主元 temp，然后将主 元分别从左右两头开始比较，在右边大元素区遇到小于 temp 的元素就将其放到左边的小 元素区，同时更新右边比较的下标，转到左边小元素区比较，若在小元素区遇到大于 temp 的元素就将其放到右边的大元素区；下面具体示例下过程。 1、 首先将主元 temp 与右边 right 区的元素比较，假设最右边的两个都是大于 temp 的，那 么它们
3、的位置不变，就呆在蓝区，注意这里只比较与 temp 的大小，具体蓝区这两个元 素谁大谁小没有关系，只要大于 temp，他们的顺序无关紧要。右边第三个元素小于 temp，如下图所示：leftrighttemp此时将右边第三个小于 temp 的元素放到左边 left 它应该呆在的地方，这时放到左边第 一个元素，不用担心会把左边第一个元素覆盖掉，因为此时 temp 的值就是第一个元素 的值。这时右边第三个位置就空出来了，要存放下次在左边区域找到的大于 temp 的元 素值。 用代码来表示就是：while(temp aleft) void swap(int tmp = a;a = b;b = tmp;
4、 int partion1(int a,int left,int right) int tmp = aleft;while(left aleft) aright = aleft;aleft= tmp;return left; int partion2(int a,int left,int right) int tmp = aleft;int i =left;for(int j=left+1;j=right;j+)if(ajtmp)i+;swap(ai,aj);swap(aleft,ai);return i; void quicksort1(int a,int left,int right) i
5、nt p;if(left right)p = partion1(a,left,right);quicksort1(a,left,p-1);quicksort1(a,p+1,right); void quicksort2(int a,int left,int right) int p;if(left right)p = partion2(a,left,right);quicksort2(a,left,p-1);quicksort2(a,p+1,right); int main(int arg,char *agv) int a = 3,6,9,1,0,16;cout“befor sort is :“endl;for(int i =0;i6;i+)coutai“ “;coutendl;quicksort1(a,0,5);cout“output of quick sort 1 :“endl;for(int i=0;i6;i+)coutai“ “;coutendl;cout“output of quick sort 2 :“endl;quicksort2(a,0,5);for(int i=0;i6;i+)coutai“ “;coutendl;return 0; 运行结果：
