快速排序作为应用比较广泛,而且时间复杂度比较优越的排序算法备受大家的喜爱。最近有点悠闲,就又把这个快速算法研究了一遍,目前掌握了两种排序算法的思路,为了以免忘记,故详细的记录下来,也供大家学习借鉴,不足之处望请指教。
快速排序的基本原理:
假设一个待排序的数组如上图所示,排序的目的就是将其从小到大排序。快速排序的主要步骤就是设定一个待排序的元素(称作主元,记作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;
}
运行结果:
全文完,欢迎指教。
原文:http://www.cnblogs.com/orchard/p/3800129.html