Python实现9大排序算法冒泡、选择、快排、堆、归并、插入、二分插入、希尔、二分查找

开篇废话

在面试过程中，白板、手撕排序算法几乎是不可避免的，所以充分的准备，能够做到手撕各种排序算法是必不可少的能力。博主也是因为之前一直不以为然，所以面试过程中碰到了很多让人尴尬的事，回来之后赶紧搜罗，把各个算法用Python实现了一遍，代码写的很简洁，而且都经过了严格的测试代码是没问题的，别的语言也不妨看一看，思路都是一样的，具体算法原理我就不再博客里多阐述了，因为这方面的博文实在是太多太丰富了。。

1.冒泡排序——时间复杂度O(N²) 空间复杂度 O(1) 稳定排序

 # 冒泡排序 时间复杂度O(N^2) 空间复杂度 O(1) 稳定排序
def bubble_sort(self, nums):
    n = len(nums)

    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] > nums[j]: nums[i], nums[j] = nums[j], nums[i]
    return nums
1
2
3
4
5
6
7
8

2.选择排序——时间复杂度O(N²) 空间复杂度O(1) 不稳定排序

 # 选择排序 时间复杂度O(N^2) 空间复杂度O(1) 不稳定排序
def selection_sort(self, nums):
    n = len(nums)

    for i in range(n):
        min_index = i
        min_val = nums[i]
        for j in range(i + 1, n):
            if min_val > nums[j]: min_index, min_val = j, nums[j]
        #if min_index != i:
        nums[i], nums[min_index] = nums[min_index], nums[i]

    return nums
1
2
3
4
5
6
7
8
9
10
11
12
13

3.快速排序——时间复杂度O(NlogN) 空间复杂度O(logN) 不稳定排序

# 快速排序 时间复杂度O(NlogN) 空间复杂度O(logN) 不稳定排序
def quick_sort(self, nums, low, high):
    if low >= high: return nums

    index = self.partition(nums, low, high)
    self.quick_sort(nums, low, index - 1)
    self.quick_sort(nums, index + 1, high)

    return nums

def partition(self, nums, low, high):
    x = nums[low]  # 哨兵

    while low < high:
        while low < high and nums[high] >= x:
            high -= 1
        nums[low] = nums[high]
        while low < high and nums[low] <= x:
            low += 1
        nums[high] = nums[low]

    nums[high] = x

    return high
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

4.堆排序——时间复杂度O(NlogN) 空间辅助度O(1) 不稳定排序

    # 堆排序 时间复杂度O(NlogN) 空间辅助度O(1) 不稳定排序
def heap_sort(self, nums):
    n = len(nums)
    # 建最大堆n//2到N均为叶子结点，0到n//2均为父节点
    for i in range(n // 2, -1, -1):
        self.heapify(nums, n, i)
    # 排序，从堆顶取最大值放到末尾，并堆的长度-1
    for i in range(n - 1, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        self.heapify(nums, i, 0)

    return nums

def heapify(self, nums, n, index):
    while True:
        # i * 2 + 1为左孩子位置，i * 2 + 2为右孩子位置
        max_index = index
        if index * 2 + 1 < n and nums[index] < nums[index * 2 + 1]:
            max_index = index * 2 + 1
        if index * 2 + 2 < n and nums[max_index] < nums[index * 2 + 2]:
            max_index = index * 2 + 2
        if index == max_index:
            break
        nums[index], nums[max_index] = nums[max_index], nums[index]
        index = max_index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

5.归并排序——时间辅助度O(NlogN) 空间复杂度O(N) 稳定排序

# 归并排序 时间辅助度O(NlogN) 空间复杂度O(N) 稳定排序
def merge_sort(self, nums, low, high):
    if low >= high: return nums

    mid = low + (high - low) // 2
    self.merge_sort(nums, low, mid)
    self.merge_sort(nums, mid + 1, high)
    self.merge(nums, low, mid, high)

    return nums

def merge(self, nums, low, mid, high):
    tmp = []
    i = low
    j = mid + 1
    while i <= mid and j <= high:
        if nums[i] > nums[j]:
            tmp.append(nums[j])
            j += 1
        else:
            tmp.append(nums[i])
            i += 1

    while i <= mid:
        tmp.append(nums[i])
        i += 1
    while j <= high:
        tmp.append(nums[j])
        j += 1

    for i in range(len(tmp)):
        nums[low + i] = tmp[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

6.插入排序——时间复杂度O(N²) 空间复杂度O(1) 稳定排序

# 直接插入排序 时间复杂度O(N^2) 空间复杂度O(1) 稳定排序
def insertion_sort(self, nums):
    n = len(nums)

    for i in range(n):
        tmp = nums[i]
        j = i - 1
        while j >= 0 and tmp < nums[j]:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = tmp

    return nums
1
2
3
4
5
6
7
8
9
10
11
12
13

7.二分插入排序——时间复杂度O(NlogN) 空间复杂度O(1)

# 二分(二分查找)插入排序 时间复杂度O(NlogN) 空间复杂度O(1) 稳定排序
def binary_insertion_sort(self, nums):
    n = len(nums)

    for i in range(n):
        tmp = nums[i]
        low = 0
        high = i - 1
        # 二分查找
        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] == tmp:
                high = mid
                break
            elif nums[mid] < tmp:
                low = mid + 1
            else:
                high = mid - 1
        nums[high + 2: i + 1] = nums[high + 1: i]
        nums[high + 1] = tmp

    return nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

8.希尔排序——时间复杂度O(N^1.3不确定) 空间复杂度O(1) 不稳定排序

# 希尔排序 时间复杂度O(N^1.3不确定) 空间复杂度O(1) 不稳定排序
def shell_sort(self, nums):
    n = len(nums)
    d = n // 2
    while d >= 1:
        for i in range(d, n):
            if nums[i] < nums[i - d]:
                tmp = nums[i]
                j = i - d
                while j >= 0 and tmp < nums[j]:
                    nums[j + d] = nums[j]
                    j -= d
                nums[j + d] = tmp

        d //= 2

    return nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

9.二分查找——时间复杂度O(logN) 空间复杂度O(1)

# 二分查找 时间复杂度O(logN) 空间复杂度O(1)
def binary_search(self, nums, low, high, target):
    end = high
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            high = mid - 1
        else:
            low = mid + 1
    # 没找到就返回最后的位置
    return end
1
2
3
4
5
6
7
8
9
10
11
12
13