讨论/《排序算法全解析》 - 912. 排序数组/
《排序算法全解析》 - 912. 排序数组

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
展开全部 5 讨论