常见的排序算法---快速排序算法

快速排序算法
快排是基于分治的思想来的，快速排序就是在元素序列中选择一个元素作为基准值，每趟总数据元素的两端开始交替排序，将小于基准值的交换的序列前端，大于基准值的交换到序列后端，介于两者之间的位置称为基准值最终的位置。同时序列被划分成两个子序列，再对两个子序列进行排序，这个过程就是递归的过程，直到子序列的长度为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方

快速排序算法并且是不稳地的。