快速排序算法的两种实现思路(附源代码)..docx

快速排序快速排序的基本原理：假设一个待排序的数组如上图所示，排序的目的就是将其从小到大排序。快速排序的主要步骤就是设定一个待排序的元素（称作主元，记作temp），经过一轮划分排序后在这个主元左边的元素值都小于它，在主元右边的元素值都大于它，一轮划分后的效果应该是这样的，如下图：这样以temp元素为分隔就将原来的数组分成了两个左右两个数组，然后再分别对左右两个子数组进行同样的分隔，然后再对子子数组进行分割，递归调用这种分隔，直到最后不能再分了，此时数组也就是有序的了。基本原理是相同的，但是具体是怎么分隔的有两种不同的思路。一种称作：“左右倒腾法”此种方法将数组分成了三个部分，小于主元的部分，大于主元的部分，未划分的部分。首先，要选定一个元素作为主元temp，这里将第一个元素left视为主元temp，然后将主元分别从左右两头开始比较，在右边大元素区遇到小于temp的元素就将其放到左边的小元素区，同时更新右边比较的下标，转到左边小元素区比较，若在小元素区遇到大于temp的元素就将其放到右边的大元素区；下面具体示例下过程。首先将主元temp与右边right区的元素比较，假设最右边的两个都是大于temp的，那么它们的位置不变，就呆在蓝区，注意这里只比较与temp的大小，具体蓝区这两个元素谁大谁小没有关系，只要大于temp，他们的顺序无关紧要。右边第三个元素小于temp，如下图所示：此时将右边第三个小于temp的元素放到左边left它应该呆在的地方，这时放到左边第一个元素，不用担心会把左边第一个元素覆盖掉，因为此时temp的值就是第一个元素的值。这时右边第三个位置就空出来了，要存放下次在左边区域找到的大于temp的元素值。用代码来表示就是：while((temp = a[right]) (left right)) right --; a[left]= a[right];每当发生一次交换的时候，就要反转方向比较，此时要从左边第一个开始比较，直到找到一个大于temp的元素，然后将这个元素放到右边刚刚空出来的第三个位置。显然此时左边第一个值就是刚刚右边第三个值，是满足小于temp的，然后继续比较左边第二个元素，假设左边第二个元素大于temp，显然这个大于temp的元素是应该呆在右边区域的，将此元素值放到第一步中空出来的右边第三个元素中，此时：用代码来描述就是：while((temp a[left]) (left right)) left ++; a[right] = a[left];经过左右两次比较后，数组的状态是：然后继续重复1、2两个步骤，直到将未比较区域的元素比较完，最后temp将处于一个唯一确定的位置，此位置也是整个数组排序后的最后位置，此时temp元素的左边都是小于（小于等于）temp的，右边都是大于（大于等于）temp的元素，但是蓝色和绿色区域内的大小顺序是不定的，此时要对其重复执行上述1、2，递归调用，直至所有的元素都处于唯一确定的位置，此时整个数组也就是排序完成了。 完整的一次划分代码是：int partion2(int a[],int left,int right){ int tmp = a[left]; while(left right) { while((tmp = a[right]) (left right)) right --; a[left]= a[right]; coutIn the first while a[left] = a[left] tmp = tmp a[right] = a[right]endl; while((tmp a[left]) (left right)) left ++; a[right] = a[left]; coutendlIn the second while a[left] = a[left] tmp = tmp a[right] = a[right]endl; } a[left]= tmp; return left;}这个partion函数是整个快速排序中最重要的一步。下面的则是完成了对左右子数组的递归划分：void quicksort(int a[],int left,int right){ int p; if(left right) { p = partion3(a,left,right); quicksort(a,left,p-1); quicksort(a,p+1,right); }}显然，这种划分的思路是从数组的左右两端依次分别比较，直至最终将主元放到应该放到的位置。第二种方法是这样的。将整个数组划分为三个部分，自左向右分别是小于temp元素区，大于temp元素区，未比较区，如下：、首先，选取左边第一个元素为主元temp