十大常见排序算法

序言

冒泡排序

def bubbleSort(nums: List[int]) -> List[int]:
    n = len(nums)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return numspython

• 时间复杂度：O(n^2)。时间复杂度近似n的阶加, 即 = ，省略常数1/2,
• 空间复杂度：O(1)
• 稳定

选择排序

def selectionSort(nums):
    n = len(nums)
    for i in range(n):
        minIndex = i
        for j in range(i + 1, n):
            if nums[minIndex] > nums[j]:
                minIndex = j
        nums[i], nums[minIndex] = nums[minIndex], nums[i]
    return numspython

• 时间复杂度 O(n^2)
• 空间复杂度 O(1)
• 不稳定

插入排序

def insertionSort(nums):
    n = len(nums)
    for i in range(1, n):
        cur = nums[i]
        bef = i - 1
        while bef >= 0 and cur < nums[bef]:
            nums[bef + 1] = nums[bef]
            bef -= 1
        nums[bef + 1] = cur
    return numspython

• 时间复杂度 O(n^2)
• 空间复杂度 O(1)
• 稳定

希尔排序

def shellsort(nums: list):
    n = len(nums)
    h = 1
    while h < n // 3:
        h = h * 3 + 1
    while h > 0:
        for i in range(h, n):
            j = i - h
            cur = nums[i]
            while j >= 0 and cur < nums[j]:
                nums[j + h] = nums[j]
                j -= h
            nums[j + h] = cur
        h = (h - 1) // 3
    return numspython

• 时间复杂度 O(nlogn)
• 空间复杂度 O(1)
• 不稳定

归并排序

def mergeSort(self, nums: List[int], l: int, r: int) -> None:
    if l == r:
        return
    mid = (l + r) // 2
    self.mergeSort(nums, l, mid)
    self.mergeSort(nums, mid + 1, r)
    tmp = []
    i = l
    j = mid + 1
    while i <= mid or j <= r:
        if i > mid or (j <= r and nums[j] < nums[i]):
            tmp.append(nums[j])
            j += 1
        else:
            tmp.append(nums[i])
            i += 1
    nums[l: r + 1] = tmppython

• 时间复杂度 O(nlogn)
• 空间复杂度 O(n)
• 稳定

快速排序

def randomizedPartition(self, nums: List[int], l: int, r: int) -> int:
        pivot = random.randint(l, r)
        nums[pivot], nums[r] = nums[r], nums[pivot]
        i = l - 1
        for j in range(l, r):
            if nums[j] < nums[r]:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        i += 1
        nums[i], nums[r] = nums[r], nums[i]
        return i

def randomizedQuicksort(self, nums: List[int], l: int, r: int) -> None:
    if l >= r:
        return
    mid = self.randomizedPartition(nums, l, r)
    self.randomizedQuicksort(nums, l, mid - 1)
    self.randomizedQuicksort(nums, mid + 1, r)python

• 时间复杂度 O(nlogn)
• 空间复杂度 O(logn)
• 不稳定

堆排序

def maxHeapify(self, heap, root, heapLen):
        p = root
        # control the node have sub node and not in last layer
        while p * 2 + 1 < heapLen:
            # sub node index of p
            l, r = p * 2 + 1, p * 2 + 2
            # check which is the smaller sub node
            if heapLen <= r or heap[r] < heap[l]:
                nex = l
            else:
                nex = r
            # compare and swap if needed
            if heap[p] < heap[nex]:
                heap[p], heap[nex] = heap[nex], heap[p]
                p = nex
            else:
                break

    def buildHeap(self, heap):
        for i in range(len(heap) - 1, -1, -1):
            self.maxHeapify(heap, i, len(heap))

    def heapSort(self, nums):
        self.buildHeap(nums)
        for i in range(len(nums) - 1, -1, -1):
            nums[i], nums[0] = nums[0], nums[i]
            self.maxHeapify(nums, 0, i)python

• 时间复杂度 O(nlogn)
• 空间复杂度 O(1)
• 不稳定

计数排序

def countingSort(nums, bucketLen):
    bucket = [0] * bucketLen
    for num in nums:
        bucket[num] += 1
    index = 0
    for i in range(bucketLen):
        while bucket[i] > 0:
            nums[index] = i
            index += 1
            bucket[i] -= 1
    return numspython

• 时间复杂度 O(n+k)
• 空间复杂度 O(k)
• 稳定

桶排序

def bucketSort(nums, bucketSize):
    def insertionSort(arr):
        for i in range(1, len(arr)):
            cur = arr[i]
            bef = cur - 1
            while bef >= 0 and arr[bef] > cur:
                arr[bef + 1] = arr[bef]
                bef -= 1
            arr[bef + 1] = cur
        return arr

    buckets = [[] for _ in range(bucketSize)]
    for num in nums:
        buckets[int(bucketSize * num)].append(num)
    for i in range(bucketSize):
        buckets[i] = insertionSort(buckets[i])
    sortIndex = 0
    for i in range(bucketSize):
        for j in range(len(buckets[i])):
            nums[sortIndex] = buckets[i][j]
            sortIndex += 1
    return numspython

• 时间复杂度 O(n+k)
• 空间复杂度 O(n+k)
• 稳定

基数排序

def radixSort(nums):
    def countingSort(nums, exp, n):
        count = [0] * 10
        output = [0] * n
        for i in range(n):
            count[(nums[i] // exp) % 10] += 1
        # ASC
        for i in range(1, 10):
            count[i] += count[i - 1]
        # DESC
        # for i in range(8, -1, -1):
        #     count[i] += count[i + 1]
        for i in range(n-1, -1, -1):
            num = nums[i] // exp
            output[count[num % 10] - 1] = nums[i]
            count[num % 10] -= 1
        for i in range(n):
            nums[i] = output[i]

    n = len(nums)
    ma = max(nums)
    exp = 1
    while ma // exp >= 1:
        countingSort(nums, exp, n)
        exp *= 10
    return numspython

• 时间复杂度 O(n × k)
• 空间复杂度 O(n + k)
• 稳定

总结