交换排序--快速排序

2018-09-19

交换排序--快速排序

思路：
选择一个基准元素,通常选择第一个元素或者最后一个元素,
通过一趟排序将待排序的记录分割成独立的两部分，
其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
此时基准元素在其排好序后的正确位置，然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

import java.util.Arrays;

public class Untitled {
    public static void main(String[] args) {
        int arr[] = {3, 5, 7, 2, 4, 9, 1, 6, 10, 8};
        System.out.println("排序前:");
        System.out.println(Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println("排序后:");
        System.out.println(Arrays.toString(arr));
    }


    private static void quickSort(int[] arr, int start, int end){

        if (start < end){//如果不加这个判断递归会无法退出导致堆栈溢出异常
            int mid = getMiddle(arr, start, end);
            quickSort(arr, 0, mid-1);
            quickSort(arr, mid+1, end);
        }
    }


    public static int getMiddle(int[] arr, int start, int end){
        int index = arr[start];//基准元素，排序中会空出来一个位置

        while(start < end){
            while(start < end && arr[end] >= index){//从high开始找比基准小的，与low换位置
                end--;
            }
            arr[start] = arr[end];

            while (start < end && arr[start] <= index){//从low开始找比基准大,放到之前high空出来的位置上
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = index;//此时low=high 是基准元素的位置，也是空出来的那个位置

        return start;
    }

}