首页 > 代码库 > 快速排序算法的两个写法
快速排序算法的两个写法
快速排序作为应用比较广泛，而且时间复杂度比较优越的排序算法备受大家的喜爱。最近有点悠闲，就又把这个快速算法研究了一遍，目前掌握了两种排序算法的思路，为了以免忘记，故详细的记录下来，也供大家学习借鉴，不足之处望请指教。
快速排序的基本原理：
假设一个待排序的数组如上图所示，排序的目的就是将其从小到大排序。快速排序的主要步骤就是设定一个待排序的元素（称作主元，记作temp），经过一轮划分排序后在这个主元左边的元素值都小于它，在主元右边的元素值都大于它，一轮划分后的效果应该是这样的，如下图：
这样以temp元素为分隔就将原来的数组分成了两个左右两个数组，然后再分别对左右两个子数组进行同样的分隔，然后再对子子数组进行分割，递归调用这种分隔，直到最后不能再分了，此时数组也就是有序的了。
基本原理是相同的，但是具体是怎么分隔的有两种不同的思路。一种我戏称为：“左右倒腾法”。此种方法将数组分成了三个部分，小于主元的部分，大于主元的部分，未划分的部分。如下图所示：
首先，要选定一个元素作为主元temp，这里将第一个元素left视为主元temp，然后将主元分别从左右两头开始比较，在右边大元素区遇到小于temp的元素就将其放到左边的小元素区，同时更新右边比较的下标，转到左边小元素区比较，若在小元素区遇到大于temp的元素就将其放到右边的大元素区；下面具体示例下过程。
1、首先将主元temp与右边right区的元素比较，假设最右边的两个都是大于temp的，那么它们的位置不变，就呆在蓝区，注意这里只比较与temp的大小，具体蓝区这两个元素谁大谁小没有关系，只要大于temp，他们的顺序无关紧要。右边第三个元素小于temp，如下图所示：
此时将右边第三个小于temp的元素放到左边left它应该呆在的地方，这时放到左边第一个元素，不用担心会把左边第一个元素覆盖掉，因为此时temp的值就是第一个元素的值。这时右边第三个位置就空出来了，要存放下次在左边区域找到的大于temp的元素值。
用代码来表示就是：
while((temp <= a[right]) &&(left < right))
right --;
a[left]= a[right];
2、每当发生一次交换的时候，就要反转方向比较，此时要从左边第一个开始比较，直到找到一个大于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];
cout<<"In 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];
cout<<endl<<"In 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，设置两个下标指针I,j分别指向第一个、第二个元素，绿色和蓝色的区域分别向未比较的元素区域增长，i指向绿色区域的最右边，表示是小于temp元素区的最右边的一个值，j指向蓝色区域的最右边，表示大于temp元素区域的最右边值，当j和未比较的元素区域的元素比较发现一个小于temp的值，就将此值与蓝色区域的最左边的一个值交换，此时绿色区域加1，蓝色区域长度不变，如果没有发现小于temp的元素，则j++，一直往下比较。当j一直到数组的最后一个元素后，交换a[left]和a[i]的值，此时a[i]就是a[left]所应处的位置，i的左边都是小于temp的值，i的右边都是大于temp的值。
流程如下：
1、i指向第一个元素，j指向第二个元素j，判断a[j]与temp的大小，如果a[i]大于temp表示此时a[j]就是应该处于蓝色区域，j++进行下一个比较。
2、如果a[j]<=temp，表示此时a[j]不应该处于这个大于temp的蓝色区域，应该是处于小于temp的绿色区域。i++，然后交换a[j]和a[i]的值，由于此时i=0,j=1，此时a[i]和a[j]的交换其实就是第二个数组元素自己的交换
假设，j在第5个元素发现a[j]<temp,此时：
也就是，此时j指向的元素大于temp了，应该放到i所指向的小于temp区域的下一个位置，显然要交换a[j]和蓝色区域的最左边的值，也就是a[i]的下一个值。完成后绿色区域有两个值，蓝色区域还是三个值，j指向下一个未比较的元素值。
然后依次重复进行这样的比较，直到j达到最后一个，假设是这样的：
但此时主元还是a[left],要交换a[lef]和a[i]的值，此时a[i]的左边都是小于temp的元素，右边都是大于temp的元素，如下：
这样就完成了一次划分，然后再对temp左右的子数组递归调用这种划分，直至最后完成所有元素最终位置的确定。
代码描述：
int partion3(inta[],int left,int right)
{
int tmp = a[left];
int i =left;
for(int j=left+1;j<=right;j++)
{
if(a[j]<tmp)
{
i++;
swap(a[i],a[j]);
}
}
swap(a[left],a[i]);
return i;
}
递归调用的函数和第一种方法是一样的都是：
void quicksort(inta[],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的区域（蓝色），在未比较区域（白色）寻找满足条件的值，将其放到蓝色和绿色区域。
下面是两种方法完整的代码，并附有测试用例，其排序结果显然是一样的。
/*************************************************************************
> File Name: quicksort.cpp
> Author: songyuanguo
> Description: quick sort
> Created Time: Fri 20 Jun 2014 05:17:48AM CST
************************************************************************/
#include<iostream>
using namespacestd;
void swap(int&a,int &b)
{
int tmp;
tmp = a;
a =b;
b =tmp;
}
int partion1(inta[],int left,int right)
{
int tmp = a[left];
while(left < right)
{
while((tmp <= a[right]) &&(left < right))
right --;
a[left]= a[right];
while((tmp > a[left]) &&(left < right))
left ++;
a[right] = a[left];
}
a[left]= tmp;
return left;
}
int partion2(inta[],int left,int right)
{
int tmp = a[left];
int i =left;
for(int j=left+1;j<=right;j++)
{
if(a[j]<tmp)
{
i++;
swap(a[i],a[j]);
}
}
swap(a[left],a[i]);
return i;
}
voidquicksort1(int a[],int left,int right)
{
int p;
if(left< right)
{
p = partion1(a,left,right);
quicksort1(a,left,p-1);
quicksort1(a,p+1,right);
}
}
voidquicksort2(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(intarg,char *agv[])
{
int a[] ={ 3,6,9,1,0,16};
cout<<"befor sort is:"<<endl;
for(int i =0;i<6;i++)
cout<<a[i]<<" ";
cout<<endl;
quicksort1(a,0,5);
cout<<"output of quick sort 1:"<<endl;
for(int i=0;i<6;i++)
cout<<a[i]<<" ";
cout<<endl;
cout<<"output of quick sort 2:"<<endl;
quicksort2(a,0,5);
for(int i=0;i<6;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
运行结果：
全文完，欢迎指教。