算法-快排法

思想： 快排法主要是运用二分法的思想来对一批数字进行排序，这种排序方法好处是比冒泡排序节省时间，因为冒泡排序是两两比对，而快排法是以某个数为基准数，通过比对，将大于和小于此基准数的数分别排列在左右两边，以此类推，进行递归，直至排序完成。
例子：假设我们现在对“ 6 1 2 7 9 3 4 5 10 8”这 10 个数进行排序。首先在这个序列中随便找一个数作为基准数。为了方便，就让第一个数 6 作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在 6 的右边，比基准数小的数放在 6 的左边，类似下面这种排列。3 1 2 5 4 6 9 7 10 8。
在初始状态下，6在第一个位置，先从右边向左找小于6的数，再从左往右找到大于6的数，然后交换他们。如下图：

快排法.png

代码如下
int a[101],n;//定义全局变量
void quicksort(int left,int right);

int main(int argc, const char * argv[]) {
@autoreleasepool {
int i;
//读入数据
printf("请输入N的值:");
scanf("%d",&n);
for(i=1;i<=n;i++){
printf("请输入第%d个数:",i);
scanf("%d",&a[i]);
}
quicksort(1,n); //快速排序调用
//输出排序后的结果
for(i=1;i<=n;i++)
printf("%d ",a[i]);
return 0;
}
return 0;
}

void quicksort(int left,int right)
{
int i,j,t,temp;
if(left>right){
return;
}
temp=a[left]; //temp中存的就是基准数
i=left;
j=right;
while(i!=j)
{
//顺序很重要，要先从右往左找
while(a[j]>=temp && i<j)
{
j--;
}
//再从左往右找
while(a[i]<=temp && i<j)
{
i++;
}
//交换两个数在数组中的位置
if(i<j)//当i和j不相等的时候交换位置
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//最终将基准数归
a[left]=a[i];
a[i]=temp;
quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程
quicksort(i+1,right);//继续处理右边的，这里是一个递归的过程
}
输出结果为：
请输入N的值:10
请输入第1个数:6
请输入第2个数:1
请输入第3个数:2
请输入第4个数:9
请输入第5个数:8
请输入第6个数:3
请输入第7个数:4
请输入第8个数:6
请输入第9个数:7
请输入第10个数:10
1 2 3 4 6 6 7 8 9 10