讨论/《排序算法全解析》 - 912. 排序数组/
《排序算法全解析》 - 912. 排序数组
共 5 个回复

1、快排算法

class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """

        def quick_sort(nums, start, end):
            if start >= end:
                return
            mid = partion(nums, start, end)
            quick_sort(nums, start, mid-1)
            quick_sort(nums, mid+1, end)
        
        def partion(nums, left, right):
            # 随机选择mid节点,不随机选择会超时
            mid = random.randint(left, right)
            pivot = nums[mid]
            # 把mid位置的数交换到left位置
            nums[left], nums[mid] = nums[mid], nums[left]
            while left < right:
                while left < right and pivot <= nums[right]:
                    right -= 1
                nums[left] = nums[right]
                while left < right and pivot > nums[left]:
                    left += 1
                nums[right] = nums[left]
            nums[left] = pivot
            return left
            
        quick_sort(nums, 0, len(nums)-1)
        return nums

2、归并排序

class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """

        def merge_sort(nums, tmp, start, end):
            if start >= end:
                return
            mid = (start + end) // 2
            merge_sort(nums, tmp, start, mid)
            merge_sort(nums, tmp, mid+1, end)
            merge(nums, tmp, start, end)
        
        def merge(nums, tmp, left, right):
            mid = (left + right) // 2
            
            i, j, k = left, mid + 1, left
            while i <= mid and j <= right:
                if nums[i] <= nums[j]:
                    tmp[k] = nums[i]
                    i += 1
                else:
                    tmp[k] = nums[j]
                    j += 1
                k += 1
            while i <= mid:
                tmp[k] = nums[i]
                i += 1
                k += 1

            while j <= right:
                tmp[k] = nums[j]
                j += 1
                k += 1
            nums[left: right+1] = tmp[left:right+1]
        
        tmp = [0] * len(nums)
        merge_sort(nums, tmp, 0, len(nums)-1)
        return nums


3、归并排序精简版

class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """

        def merge_sort(nums, tmp, start, end):
            if start >= end:
                return
            mid = (start + end) // 2
            merge_sort(nums, tmp, start, mid)
            merge_sort(nums, tmp, mid+1, end)
            merge(nums, tmp, start, end)
        
        def merge(nums, tmp, left, right):
            mid = (left + right) // 2
            
            i, j = left, mid + 1
            for k in range(left, right+1):
                if i == mid+1:
                    tmp[k] = nums[j]
                    j += 1
                elif j == right + 1 or nums[i] <= nums[j]:
                    tmp[k] = nums[i]
                    i += 1
                else:
                    tmp[k] = nums[j]
                    j += 1
            nums[left: right+1] = tmp[left:right+1]
        
        tmp = [0] * len(nums)
        merge_sort(nums, tmp, 0, len(nums)-1)
        return nums
class Solution {
public:
    void quickSort(vector<int>& nums, int start, int end){
        if(end - start < 1){
            return;
        }
        swap(nums[start],nums[start + (end-start)/2]);
        int middle=nums[start];
        int i=start+1,j=end;
        while(i<j){
            if(nums[i]>=middle){
                while(j>i && nums[j]>middle){
                    j--;
                }
                swap(nums[i],nums[j]);
                j--;
            }
            else{
                i++;
            }
        }
        if(nums[i]>middle){
            i--;
        }
        swap(nums[start],nums[i]);
        quickSort(nums,start,i-1);
        quickSort(nums,i+1,end);
    }
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums,0,nums.size()-1);
        return nums;
    }
};
class Solution {
public:
    int partition(vector<int> &nums, int left, int right)
    {
        int mid = (left + right)>>1;
        swap(nums[left], nums[mid]);
        int pivot = left;
        left += 1;

        while(left < right)
        {
            while(left < right && nums[left] <= nums[pivot])
                ++left;
            while(left < right && nums[right] > nums[pivot])
                --right;
            
            if(left < right)
            {
                swap(nums[left], nums[right]);
                ++left;
                --right;
            }
        }

        if(left == right && nums[right] > nums[pivot])
            --right;
        swap(nums[pivot], nums[right]);

        return right;
    }

    void quickSort(vector<int> &nums, int left, int right)
    {
        if(left >= right)
            return;

        int middle = partition(nums, left, right);
        quickSort(nums, left, middle-1);
        quickSort(nums, middle+1, right);
    }

    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size()-1);
        return nums;
    }
};

C++ 快排

class Solution {
public:
    void quickSort(int start,int end,vector<int>&nums)
    {
        if(start>=end)
            return;
        int mid=findMid(start,end,nums);
        quickSort(start, mid-1, nums);
        quickSort(mid+1,end,nums);
    }
    int findMid(int start,int end,vector<int>&nums)
    {
        int pivot = nums[start];
        int left=start+1,right=end;
        while(left<right)
        {
            while(left<right&&nums[left]<pivot)
                ++left;
            while(left<right&&nums[right]>pivot)
                --right;
            if(left<right)
            {
                swap(nums[left],nums[right]);
                ++left;
                --right;
            }
            
        }
        if(left==right && nums[right]>pivot)
            --right;
        swap(nums[start],nums[right]);
        return right;
        
    }
    vector<int> sortArray(vector<int>& nums) {
        quickSort(0,nums.size()-1,nums);
        return nums;
    }
};
var sortArray = function(nums, left = 0, right = nums.length - 1) {
  if (nums.length < 2) return nums;
  let index = partition(nums, left, right);
  if (left < index - 1) sortArray(nums, left, index - 1);
  if (index < right) sortArray(nums, index, right);
  return nums;
};

function partition(arr, i, j) {
  let pivotIndex = Math.floor(i + (j - i) / 2);
  let pivotValue = arr[pivotIndex];
  while (i <= j) {
    while (arr[i] < pivotValue) i++;
    while (arr[j] > pivotValue) j--;
    if (i <= j) {
      [arr[i++], arr[j--]] = [arr[j], arr[i]];
    }
  }
  return i;
}