算法设计 分治法 快速排序 C语言实现

分治法 - 快速排序

题目描述

利用快速排序算法将读入的 N个数从小到大排序后输出，请勿使用std::sort。

输入格式

第一行一个整数 n (1≤n≤105)。

第二行 n 个整数 ai (1≤ai≤109)。

输出格式

输出一行，为 ai 排序后的结果。

解题思路

先从数列中取出一个基准数，将比这个数大的数全放在它右边，小于这个数的数全放在左边，再对左右区间重复，直到每个区间只有一个数。

当left<right时，才开始。以temp为基准，temp=a[left],i=left,j=right

若a[j]>=temp,j-- ,从右往左扫描

若a[i]<=temp,i++,从左往右扫描

交换a[i]、a[j].

出循环后，再改变基准，然后对左右区间分别递归调用

完整代码及测试结果

#include<stdio.h>void quicksort(int left,int right,int a[]){int i,j,temp,k;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){k = a[i];a[i] = a[j];a[j] = k;}}a[left] = a[i];a[i] = temp;quicksort(left,i-1,a);quicksort(i+1,right,a);}int main(){int a[100000];int i=0,n;scanf("%d",&n);getchar();char temp;while(i<n){scanf("%d",&a[i]);getchar();i++;}quicksort(0,i-1,a);int j;for(j=0;j<i;j++){printf("%d ",a[j]);}return 0;}

一组测试用例及结果