快速排序

代碼源自該視訊

算法思想：選擇一個中心點，将比中心點小的移動到左邊，反之移動到右邊；

這時形成兩個子序列，對子序列遞歸直至，每個序列隻有一個元素為止；

為了省空間 設第一個元素為中心節點并存儲該元素的值，從數組後面往前找一個

比中心節點小的放在第一個元素的位置上，然後再從前面往後找找一個元素，放在

後面空出來的元素的位置上。

當左右指針重合的時候，說明此時就是中心位置，故隻需将最開始存儲的第一個元素

放到該位置即可

時間複雜度 最好的情況是O(nlogn) 最差的情況是O(n²)

特點 如果基本有序 則會變成冒泡排序，時間複雜度為O(n²)

package whale.simpleAlgorithm;

/**
 * @Author: WhaleFall541
 * @Date: 2021/6/10 22:42
 * @see <a href="https://www.bilibili.com/video/BV1nJ411V7bd?p=164">https://www.bilibili.com/video/BV1nJ411V7bd?p=164</a>
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-1, 20, -3, -10, 100, -255};

        quickSort(arr, 0, arr.length - 1);
        StringBuilder sb = new StringBuilder();
        for (int i : arr)
            sb.append(i).append(" ");
        System.out.println("sb = " + sb);
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {// 長度大于1
            int position = moveBaseOnPivot(arr, low, high);
            quickSort(arr, low, position - 1);
            quickSort(arr, position + 1, high);
        }
    }

    private static int moveBaseOnPivot(int[] arr, int low, int high) {
        // {, 20, -3, -10, 100, -255};-1
        int pivot = arr[low];
        // 當low 和high相同時，說明中心點就在這裡可以回填pivot元素了
        while (low < high) {
            // NOTE: 條件别忘了 low < high
            // 當一直往前都沒找到比pivot小的元素 進而造成數組越界
            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;
    }
}

           

轉載請注明 原文位址