一.算法介绍
快速排序算法是对起泡算法的一种改进。算法的思想是将一组数据以轴为中心分为两个部分,将小于轴的元素放在轴的左边(下标较低的地方),将大于轴的元素放在轴的右边(下标较高的地方)。接下来,依次对左右两部分使用上述的方法来进行排序,如此反复直到将元素排序完毕。
在一次快速排序中,我们需要两个指针,分别指向我们要排序的部分元素的最低下标low,和最高的下标high。然后取轴元素,一般我们取需要排序部分的第一个元素为轴元素,下面程序中就是这么做的。选取了轴元素之后,我们就开始从high下标处开始向下标小于high的地方依次寻找,直到找到第一个元素小于轴,然后交换轴和找到的元素的位置,接下来从low开始向下标高于它的方向开始寻找第一个比轴大的元素,然后交换两个元素的位置。如此反复下去。注意,在从high向低处遍历,和low向高处遍历的时候,没遍历一个元素都需要将high--,或者low++。
上面是算法的核心思想。经常编写算法的人会知道,算法的思想很容易理解,但是真真在计算机上实现的时候,有太多的细节要考虑了。下面我就我的程序来进行一些分析。
二.源码
#include<iostream>
using namespace std ;
#define MAX_SIZE 100
//将顺序表分为两个部分,以指定的元素为轴,大于它的元素放在下标高于轴的地方,小于轴的元素放在小于轴下标的地方
//并返回轴所在的下标
int GetPartIndex(int array[MAX_SIZE],int low,int high)
{
int keyindex = low ;
int key = array[low];
while (low < high)
{
while (true)//从较高的部分向前搜索,直到找到第一个比轴小的元素,然后交换元素
{
if (array[high]<key)//当找到一个比key轴元素小的时候
{
array[keyindex]=array[high];//就将这两个值进行交换,将轴赋值为array[high]没有什么意义
keyindex = high ;//我们只需要轴现在的下标
break;//不需要对high--,因为high此时的位置和轴的位置一样
}
else
{
high--;
if (high == low)//当这两个下标相同的时候,表示排序结束
{
array[low]=key;
return low;
}
}
}
while (true)//从较低的部分向前搜索,直到找到第一个比轴大的元素,然后交换
{
if (array[low]>key)//同上
{
array[keyindex]=array[low];
keyindex=low;
break;
}
else
{
low++;
if (low == high)
{
array[low]=key;
return low;
}
}
}
}
array[low]=key;
return low ;
}
//使用递归的思想对左右两边依次进行一次快排,直到将所有元素排序完毕
void QuickSort(int array[MAX_SIZE],int low,int high)
{
if (low<high)
{
int partindex=GetPartIndex(array,low,high);
QuickSort(array,low,partindex-1);
QuickSort(array,partindex+1,high);
}
}
//测试程序
int main()
{
int array[8];
array[0]=12;
array[1]=32;
array[2]=1;
array[3]=31;
array[4]=89;
array[5]=19;
array[6]=19;
array[7]=70;
QuickSort(array,0,7);
for (int i = 0 ; i<8;i++)
{
cout<<array[i]<<endl;
}
cin>>array[2];
return 0 ;
}
下面是程序的运行结果:
三.总结
进行快速排序,效率比较高,逻辑理解也不是太复杂。只要理解了,在加上有一定的编程经验,应该很快就能编写出来。