快速排序 | 半卷书

快速排序

松懈了,仅有的一个周日打了一下午游戏…

上图,大致描述递归实现快速排序思路

代码截图

public class QuickSort {

    public static void main(String[] args) {
        int[] arr=new int[] {4,6,8,1,3,2,4,7,9,3};
        quickSort(arr, 0, arr.length-1);
        System.err.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr,int start,int end) {
        //起始位要小于终止位,也就是说最少两个数才能一轮进行比较
        if(start<end) {
            //记录基准数(每轮数据的第一个数)
            int mark=arr[start];
            //最低位
            int low=start;
            //最高位
            int high=end;
            while(low<high) {
                //高位的值大于基准数时,高位减一,否则高位的值赋给低位
                while(low<high&&mark<=arr[high]) {
                    high--;
                }
                arr[low]=arr[high];
                //低位的值小于基准数时,低位加一,否则低位的值赋给高位
                while(low<high&&mark>=arr[low]) {
                    low++;
                }
                arr[high]=arr[low];
            }
            //一轮比较完成后,把基准数赋给高位、低位重合的位置
            arr[low]=mark;
            //继续比较start到低位low
            quickSort(arr, start, low);
            //继续比较low+1到高位
            quickSort(arr, low+1, end);
        }
    }
}