分治法 - 快速排序
题目描述
利用快速排序算法将读入的 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;}
一组测试用例及结果