讨论/《排序算法全解析》 - 解析/
《排序算法全解析》 - 解析
共 4 个回复

贴一个python解法:

        n = len(nums)
        def quickSort(left, right):
            pviot = left
            i, j = left, right
            if left >= right:
                return nums
            while i < j:
                while i < j and nums[j] > nums[pviot]:
                    j -= 1
                while i < j and nums[i] <= nums[pviot]:
                    i += 1
                nums[i], nums[j] = nums[j], nums[i]
            nums[pviot], nums[i] = nums[i], nums[pviot]
            quickSort(left, i - 1)
            quickSort(i + 1, right)
            return nums
        return quickSort(0, n -1)
class Solution {
          /**
     * 列表大小等于或小于该大小,将优先于 quickSort 使用插入排序
     */
     private static final Random RANDOM=new Random();
    private static final int INSERTION_SORT_THRESHOLD = 7;
    public int[] sortArray(int[] nums) {
        int len = nums.length;
        quickSort(nums, 0, len - 1);
        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        // 小区间使用插入排序
        if (right - left <= INSERTION_SORT_THRESHOLD) {
            insertionSort(nums, left, right);
            return;
        }
        int pIndex = partition(nums, left, right);
        quickSort(nums, left, pIndex - 1);
        quickSort(nums, pIndex + 1, right);
    }
/**
 * 对数组 nums 的子区间 [left, right] 使用插入排序
 *
 * @param nums  给定数组
 * @param left  左边界,能取到
 * @param right 右边界,能取到
 */
    private void insertionSort(int[] nums, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int temp = nums[i];
            int j=i;
            while (j > 0 && nums[j - 1] > temp) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = temp;
        }
    }

    private int partition(int[] nums, int left, int right) {
        // 取第1个位置(也可以选择随机位置)的元素作为基准元素
       
        int pivot = nums[left];
        int l = left;
        int r = right;
        while (l != r) {
            while (l < r && nums[r] > pivot) {
                r--;
            }
            while (l < r && nums[l] <= pivot) {
                l++;
            }
            if (l < r) {
                int p = nums[l];
                nums[l] = nums[r];
                nums[r] = p;
            }
        }
        nums[left] = nums[l];
        nums[l] = pivot;
        return l;
    }    
}
/**
 * 分治:分区 
 * @param {*} arr 
 * @param {*} left 
 * @param {*} right 
 */
const partition = (arr, left, right) => {
    // 取第一个值 或者随机一个值 作为基准元素
    let pivot = arr[left]
    let mark = left
    for (let i = left + 1; i <= right; i++) {
        if (arr[i] < pivot) {
            // 如果当前值 小于 基准值、
            // 交换到左边
            mark++
            let temp = arr[mark]
            arr[mark] = arr[i]
            arr[i] = temp
        }
    }
    // 将mark位置元素与pivot所在位置进行交换
    // mark位置表示基于当前基准值应该在的位置、mark+1就是 >= pivot的元素了
    arr[left] = arr[mark]
    arr[mark] = pivot
    return mark

}

const quickSort = (arr, left = 0, right = arr.length - 1) => {
    // 单边循环法
    if (left > right) return arr
    let pivotIndex = partition(arr, left, right)
    // 根据基准值、分两部分、递归排序
    quickSort(arr, left, pivotIndex - 1)
    quickSort(arr, pivotIndex + 1, right)
    return arr
}
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
      QSort(nums,0,nums.size()-1);
      return nums;
    }
    void QSort(vector<int> &nums,int start,int end){
      if(start>=end) return;
      int mid=part(nums,start,end);
      QSort(nums,start,mid-1);
      QSort(nums,mid+1,end);
    }
    int part(vector<int> &nums,int start, int end){
      swap(nums[start],nums[start+(rand()%(end-start))]); //增加随机性
      int pivot=nums[start];
      int l=start+1,r=end;
      while(l<r){
        while(l<r and nums[l]<pivot) l++;
        while(l<r and nums[r]>pivot) r--;
        if(l<r) swap(nums[l++],nums[r--]);
      }
      if(l==r and nums[r]>pivot) r--;
      swap(nums[start],nums[r]);
      return r;
    }
};