题目描述
给定你一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在1~109
范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围:1≤n≤100000
样例
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
算法1
快速排序思想
找一个基准,每一趟排序使得数组划分成两个区间,左区间中的值都<=基准,右区间的值都>=基准
但基准的值不一定就在左右区间的分界处,只能保证两个区间划分成两个对立的性质
时间复杂度
O(nlgn)
参考文献
java 代码
public static void quick_sort(int a[],int low,int high){
int privot=a[low];
int i=low-1;
int j=high+1;
while (low>=high){
return;
}
while (i[HTML_REMOVED]privot);
if(i<j){
swap(a,i,j);
}
}
quick_sort(a,low,j);
quick_sort(a,j+1,high);
}
算法2
(第二种快排)
每次能至少唯一确定一个元素的位置