Re: [閒聊] 每日leetcode

[Rushia (早瀬ユウカの体操服 )]

※ 引述《sustainer123 (caster)》之銘言：
: 思路:
: 本來想說quick sort
: 結果翻一下書才發現quick sort最糟狀況會n**2
: 能用的就heap sort跟merge sort
: 剛好複習一下排序
: 不然平常都sort() 啟動
其實排序這題quick sort是可以過的
只要對pivot做特殊處理
1.從[i:j]隨機選一個數字交換到開頭當pivot
2.從left, mid, right 位置挑選中間大小的當pivot
這樣就不會遇到排好的陣列每次都100%切成1和n-1
書裡的東西不用全信
就像書裡說快速排序是不穩定排序
但是java的Arrays.sort()用快排但是他的實現保證了穩定性


java code
--------------------------------------------------
class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    void quickSort(int[] nums, int left, int right) {
        if (left >= right) return;
        int index = partition(nums, left, right);
        quickSort(nums, left, index - 1);
        quickSort(nums, index + 1, right);
    }

    int partition(int[] nums, int left, int right) {
        randomPivot(nums, left, right);
        int index = left;
        int pivot = nums[index];
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                swap(nums, ++index, i);
            }
        }
        swap(nums, index, left);
        return index;
    }
    void randomPivot(int[] nums, int left, int right) {
        int i = left + new Random().nextInt(right - left + 1);
        swap(nums, i, left);
    }

    void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}
--------------------------------------------------

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722094100.A.8B2.html
※ 編輯: Rushia (122.100.73.13 臺灣), 07/27/2024 23:33:54
推 oin1104: 大師
推 sustainer123: 大師