快速排序算法
快排是基于分治的思想来的，快速排序就是在元素序列中选择一个元素作为基准值，每趟总数据元素的两端开始交替排序，将小于基准值的交换的序列前端，大于基准值的交换到序列后端，介于两者之间的位置称为基准值最终的位置。同时序列被划分成两个子序列，再对两个子序列进行排序，这个过程就是递归的过程，直到子序列的长度为1，则完成排序。
模板 洛谷：P1177排序
代码
import java.util.Scanner;
class quickSort {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int arr[]=new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i]=scanner.nextInt();
}
quick(arr,0,arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
public static void quick(int [] keys, int begin,int end){
if (begin>=0&&begin<end&&end<keys.length){
int i=begin,j=end;
int x=keys[i];//找到基准元素
while (i!=j){
//
while (i<j&&keys[j]>=x){
//从后往前找
j--;
} //直到找到小的数字了
if (i<j){
keys[i++]=keys[j]; //i往后移动一位，讲原来i的位置赋值给j
}
while (i<j&keys[i]<=x){
//从前向后寻找较大值移动
i++;
}//找到较大值了
if (i<j){
keys[j--]=keys[i];//讲较大值赋值给j，并且j往前移动一位;
}
}
//当i等于j的时候结束上面的循环 需要重新设置基准值，基准值就是当前的位置
keys[i]=x;
quick(keys,begin,j-1);
quick(keys,i+1,end);
}
}
}
时间复杂度 最好 nlogn 最坏on方
快速排序算法并且是不稳地的。
