排序之快速排序法
快速排序法是对冒泡排序法的一种改进，其基本思想是：通过一遍排序将需要排序的数据划分为两部分，使其一部分数据比另一部分数据小，然后再分别这两部分数据进行这种排序，按此规则继续，直到每个部分为空或只含一个数时，整个快速排序结束。这事一种分治策略，将大批的数据逐步分解，可使用递归的方法编写程序，使程序更简洁。按照以上思路，我们尝试对以下几个数进行排序
3 2 4 1 5
首先要把数据划分为两部分，使其一部分数据比另一部分数据小。要满足这样的条件，我们必须要选择一个数，使其可以将以上5个数分为两部分。我们不妨将最左边的数3作为一个基准。这样第一个任务就完成了。
其次我们要将这两个部分分开（即数据较大的部分与数据较小的部分），这个过程比较复杂。
这里，为了将两部分分开，我们采用的方法是将基准数不断移动，使其成为两部分的分界线。移动的方法比较复杂。用上面的例子来说，在一个数组中，我们使用一个左变量a[left]和一个右变量a[right]，用来分别表示左右两边将比较的数。首先a[left]为3，a[right]为5。先从右边开始寻找比基准小的数并移动到左边去。而5>基准3，故此时a[right]不符合，right自减一，得到a[right]为1,1<基准3，故将a[left]的值保存为1,然后再从左边找比基准大的数并移动到右边去，我们看到4即为所找的数，将它保存到a[right]（注意此时a[right]的值已经不是初始的值5了）中，再从右边找小数移动到左边去，这样循环进行，知道left=right。
我们用上述思路排序的结果依次应为以下所示：
1 3 2 4 5
1 2 3 4 5
注意不是所有数经过上述过程仅仅一次就可以完成排序的（上述数据比较特殊，大家可以试试其他数），所以我们不得不使用递归来重复完成这一过程。
以下是用C语言实现的快速排序算法的代码：
#include <stdio.h>
int Division(int a[],int left,int right)
{
int base=a[left];
while(left<right)
{
while(left<right&&a[right]>base)
right--;
a[left]=a[right];
while(left<right&&a[left]<base)
left++;
a[right]=a[left];
}
a[left]=base;
return left;
}
void Quicksort(int a[],int left,int right)
{
int i;
if(left<right)
{
i=Division(a,left,right);
Quicksort(a,left,i-1);
Quicksort(a,i+1,right);
}
return ;
}
int main(void)
{
int i,a[]={2,4,5,6,8,7,9,3,1,0};
Quicksort(a,0,9);
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
评论