快速排序法

作者 汪小祯 日期 2016-05-30
快速排序法

本文主要写排序算法中快速排序法的实现

它的基本思想是:
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
假设我们有6个数 我们先以第一个数6为基准 比6小的在左边 比6大的在右边

我们采用双边扫描
2比6小 不动
10比6大 我们卡在这个位置
然后从另一边开始 2比6小 卡在这
两个卡住的位置互换

互换后我们继续前进

到了这个位置 两个碰面了 于是我们将基准数6与3交换(为什么不是9 自己想下 考虑下极端情况)

那么此时以6为基准 左边按照刚才格式再一次排序 然后再分 然后排序右边 这样每个小部分排序完后 整个数据就排序完了

#include<stdio.h>
int a[101],n; //定义全局变量
void quicksort(int left,int right)
{
int i,j,t,temp;
if(left>right)
return;
temp=a[left]; //先储存第一个数
i=left;
j=right;
while(i!=j)
{
while(a[j]>=temp&&i<j)
j--; //从右往左找
while(a[i]<=temp&&i<j)
i++; //从左开始找
if(i<j) // 交换数据
{
t=a[j];
a[j]=a[i];
a[i]=t;
}
}
a[left]=a[i];
a[i]=temp;
quicksort(left,i-1); //处理左边 递归的过程
quicksort(i+1,right); //处理右边 递归的过程
}
int main()
{
int i,j,t;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
quicksort(1,n);
for(i=1;i<=n;i++)
printf("%d ",a[i]);
}

源代码 www.github.com/isnine/Algorithm
时间复杂度O(nLog n),最差时间复杂度O(n^2),平均时间O(nLog n)
空间复杂度为O(lg n),最差为O(n)