排序算法---快速排序（4）

快速排序的基本思想是，通过一轮的排序将序列分割成独立的两部分，其中一部分序列的关键字（这里主要用值来表示）均比另一部分关键字小。继续对长度较短的序列进行同样的分割，最后到达整体有序。在排序过程中，由于已经分开的两部分的元素不需要进行比较，故减少了比较次数，降低了排序时间。

package com.zust.edu.sort;

import java.util.Arrays;

public class QuickSort {

        public static void main(String[] args) {
            int[] a = {7, 4, 5 , 3, 9, 0, 1 ,8 ,2 ,6};
            System.out.println(Arrays.toString(a));
            quickSort(a);
            System.out.println(Arrays.toString(a));
        }

        public static void quickSort(int[] a) {
            if(a.length>0) {
                quickSort(a, 0 , a.length-1);
            }
        }

        private static void quickSort(int[] a, int low, int high) {
            //1,找到递归算法的出口
            if( low > high) {
                return;
            }
            //2, 存
            int i = low;
            int j = high;
            //3,key
            int key = a[ low ];
            //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;
                }
            }
            // 4.4，调整key的位置
            int p = a[i];
            a[i] = a[low];
            a[low] = p;
            //5, 对key左边的数快排
            quickSort(a, low, i-1 );
            //6, 对key右边的数快排
            quickSort(a, i+1, high);
        }
}