快速排序

思路：

1. 選定一個(gè)合適的值（理想情況中值最好，但實(shí)現(xiàn)中一般使用數(shù)組第一個(gè)值）,稱為“樞軸”(pivot)。

2. 基于這個(gè)值，將數(shù)組分為兩部分拯腮，較小的分在左邊，較大的分在右邊蚁飒。

3. 可以肯定动壤，如此一輪下來，這個(gè)樞軸的位置一定在最終位置上淮逻。

4. 對兩個(gè)子數(shù)組分別重復(fù)上述過程琼懊，直到每個(gè)數(shù)組只有一個(gè)元素。

5. 排序完成

代碼：

快速排序代碼：QuickSort.java

public class QuickSort {
    public static void quickSort(int[] arr){
        qsort(arr, 0, arr.length-1);
    }
    private static void qsort(int[] arr, int low, int high){
        if (low < high){
            int pivot=partition(arr, low, high);        //將數(shù)組分為兩部分
            qsort(arr, low, pivot-1);                   //遞歸排序左子數(shù)組
            qsort(arr, pivot+1, high);                  //遞歸排序右子數(shù)組
        }
    }
    private static int partition(int[] arr, int low, int high){
        int pivot = arr[low];     //樞軸記錄
        while (low<high){
            while (low<high && arr[high]>=pivot) --high;
            arr[low]=arr[high];             //交換比樞軸小的記錄到左端
            while (low<high && arr[low]<=pivot) ++low;
            arr[high] = arr[low];           //交換比樞軸大的記錄到右端
        }
        //掃描完成弦蹂，樞軸到位
        arr[low] = pivot;
        //返回的是樞軸的位置
        return low;
    }
    public static void main(String[] args) {
        int[] arr = {3,6,2,1,5,2};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

測試用例代碼：Main.java

package com.company;

import java.util.Arrays;

import static com.company.Quicksort.quickSort;

public class Main {
    public static void main(String[] args) {
        int[] arr = {3, 6, 8, 1, 5, 2};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));

        int[] arr2 = {32, 6, 26, 12, 5, 2};
        quickSort(arr2);
        System.out.println(Arrays.toString(arr2));

        int[] arr3 = {3, 5, 45, 1, 20, 2};
        quickSort(arr3);
        System.out.println(Arrays.toString(arr3));

        int[] arr4 = {12, 15, 26, 1, 5, 2};
        quickSort(arr4);
        System.out.println(Arrays.toString(arr4));
    }
}

輸出結(jié)果

2019-2-21-16-10-37.png