快速排序原理及实现

1.基本原理：1.1 思考：为什么要从右边开始找呢？ 2.代码实现

1.基本原理：

确立一个基准数，一般都是选第一个。 2.从右边开始找，找出比基准数小的 3.从左边开始找，找出比基准数大的 4.交换顺序，调整新的基准数 5.对基准数左边进行排序，右边进行排序

1.1 思考：为什么要从右边开始找呢？

i在大于基准数的地方停下，j在小于基准数的地方停下，如果i先走，最后停下跟基准数交换时，总是大于基准数的

如下所示：6 1 2 3 7 9

while(i<j&&a[i]<=key){ i++; } while(i<j&&a[j]>key){ j--; }

i先走，最后停下在7这个位置，j也会停在7这个位置，i==j,交换基准数后 7 1 2 3 6 9 便出现问题啦。

2.代码实现

import java.util.Scanner; public class QuickSort{ public static void quickSort(int [] a){ if(a.length>0){ quickSort(a,0,a.length-1); } } public static void quickSort(int[] a ,int left,int right){ //1递归算法的出口 if(left>right){ return; } //2存 int i = left; int j = right; //3基准数 int key = a[left]; //4完成一次快排 while(i<j){ //4.1从右往左找比key小的 while(i<j&&a[j]>key){ j--; } //4.2从左往右找比key大的 while(i<j&&a[i]<=key){ i++; } //4.3交换 if(i<j){ int p = a[i]; a[i] = a[j]; a[j] = p; } } //5调整基准数的位置 a[left]为新的基准数 int p = a[i]; a[i] = key; a[left] = p; //6对基准数的左边进行排序 quickSort(a,left,i-1); //7对基准数的左边进行排序 quickSort(a,i+1,right); } public static void main(String[] args) { Scanner in = new Scanner(System.in); //一个或多个空格 String [] a = in.nextLine().split("\\s+"); int [] s = new int[a.length]; int k = 0; for(String i:a){ s[k++] = Integer.parseInt(i); } quickSort(s); for(Integer i:s){ System.out.print(i+" "); } } }