汇芳书院

专注计算机视觉、机器学习、分布式计算等领域, 兼聊投资、写作、生活

0%

排序算法梳理

发表于 更新于 分类于 Valine：
本文字数： 7.7k 阅读时长 ≈ 7 分钟

python3

冒泡排序

核心动作：比较和交换

  1. n-1次循环(因为最后一个数不用冒泡了)，每次循环将一个值”冒泡”至最终位置，i为循环轮次
  2. 每次循环两两比较相邻数，若不符合要求就交换，j表示比较的数
  3. 若上一次循环没有交换数据，则表示已完成排序，可以终止循环了，flag标记

复杂度：时间复杂度O(n^2), 空间复杂度O(1)

稳定性：比较的时候可以设定相等的元素不交换，所以是稳定的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# NC140 排序
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        length = len(nums)
        flag = False
        for i in range(length-1):
            for j in range(length-1-i):
                # 升序或降序只需要修改下面的比较符号即可
                if nums[j] > nums[j+1]:
                    tmp = nums[j]
                    nums[j] = nums[j+1]
                    nums[j+1] = tmp
                    flag = True
            if not flag:
                break
        return nums

选择排序

每次选择最小的一个数据放置在指定位置
核心动作：比较和交换

  1. 循环n-1次，每次循环选择一个最小的数，与未处理部分的第一个元素交换

复杂度：时间复杂度O(n^2), 空间复杂度O(1)

稳定性：交换动作可能会导致未处理部分的第一个元素与其重复值相对顺序改变，所以是不稳定的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        length = len(nums)
        for i in range(length-1):
            min_index = i
            for j in range(i+1, length):
                # 升序或降序只需要修改下面的比较符号即可
                if nums[j] < nums[min_index]:
                    min_index = j
            # 未排序部分中的最小值 与 未排序部分的第一个元素 交换
            # 此部分导致选择排序的不稳定性，因为如果「未排序部分的第一个元素」存在重复元素，交换时会导致这个值相对顺序的改变
            # 如果需要改变稳定性，可以改为：将未排序部分中的最小值 插入 到未排序部分第一个元素 之前
            # 如果是链表实现的，则比较容易实现上述插入动作
            tmp = nums[i]
            nums[i] = nums[min_index]
            nums[min_index] = tmp
        return nums

插入排序

直接插入排序

将数组分为已排序和未排序两部分，然后将未排序部分的数依次插入到已排序数组中的合适位置
核心动作：比较和移动
1.将第1个数视为已排序部分，剩下部分视为未排序部分
2.未排序部分：i表示需要依次遍历的数，从第二个数到最后一个数
3.已排序部分：i左边的所有数
4.将本次需要插入的数和已排序部分依次比较，如果需要插入的数比已排序部分这个数大，就将这个数后移一位，直到第0个数
5.将待插入数据插入到查到到的位置

复杂度：时间复杂度O(n^2), 空间复杂度O(1)

稳定性：插入的过程不改变相对位置，是稳定排序

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        length = len(nums)
        for i in range(1, length):
            j = i - 1
            tmp = nums[i]
            # 同样的，升序或降序只需要修改下面的比较符号即可
            while j >=0 and nums[j] > tmp:
                nums[j+1] = nums[j]
                j = j - 1
            nums[j+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
23
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        length = len(nums)
        for i in range(1, length):
            j = i - 1
            low = 0
            high = j
            tmp = nums[i]
            # 注意这里是<=, 可以保证最终值在low和high之间。
            while low <= high:
                mid = low + (high - low)//2
                # 如果数值相同，右边的数认为更大，可以保持排序稳定
                # 同样的，升序或降序只需要修改下面的比较符号即可
                if nums[mid] <= tmp:
                    low = mid + 1
                else:
                    high = mid - 1
            while j >=0 and j > high:
                nums[j+1] = nums[j]
                j = j - 1
                
            nums[high+1] = tmp
        return nums

快速排序

核心在于partition动作, 实现方式有多种，这里的这种比较巧妙

复杂度：时间复杂度O(nlogn), 空间复杂度O(1)

稳定性：大间隔交换动作可能导致相对顺序改变，不稳定排序

递归版本

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
class Solution:
    def partition(self, nums, left, right):
        # 选择pivot是一个比较关键的点，影响最好最快的复杂度
        if nums[left] < nums[right]:
            self.swap(nums, left, left+(right-left)//2)
        pivot = left
        index = left+1
        for i in range(index, right+1):
            # 同样的，升序或降序只需要修改下面的比较符号即可
            if nums[i] < nums[pivot]:
                self.swap(nums, i, index)
                index += 1
        self.swap(nums, index-1, pivot)
        return index-1

    def swap(self, nums, left, right):
        nums[left], nums[right] = nums[right], nums[left]
    
    def quickSort(self, nums, left, right):
        if left < right:
            pivot_index = self.partition(nums, left, right)
            self.quickSort(nums, left, pivot_index-1)
            self.quickSort(nums, pivot_index+1, right)
        return nums

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.quickSort(nums, 0, len(nums)-1)

Partition函数还有一种写法，pivot，内存2个while顺序和最后1次交换者，很值得琢磨

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def partition(self, nums, left, right):
        if nums[left] < nums[right]:
            self.swap(nums, right, left+(right-left)//2)
        begin=left
        end=right
        pivot=right
        # 最终begin和end都指向一处。
        # 若pivot指向右边，则需要先走左边的while，否则先走右边
        while begin < end:
            while begin < end and nums[begin] <= nums[pivot]:
                begin += 1
            while begin < end and nums[end] >= nums[pivot]:
                end = end - 1
            self.swap(nums, begin, end)
        self.swap(nums, begin, pivot)
        return begin

非递归版本

只修改了quickSort部分的代码

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
33
34
class Solution:
    def partition(self, nums, left, right):
        if nums[left] < nums[right]:
            self.swap(nums, left, left+(right-left)//2)
        pivot = left
        index = left+1
        for i in range(index, right+1):
            if nums[i] < nums[pivot]:
                self.swap(nums, i, index)
                index += 1
        self.swap(nums, index-1, pivot)
        return index-1

    def swap(self, nums, left, right):
        nums[left], nums[right] = nums[right], nums[left]
    
    def quickSort(self, nums, left, right):
        if left < right:
            stack = [right, left]
            while stack:
                i = stack.pop()
                j = stack.pop()
                pivot_index = self.partition(nums, i, j)
                if i < pivot_index:
                    stack.append(pivot_index-1)
                    stack.append(i)
                if pivot_index < j:
                    stack.append(j)
                    stack.append(pivot_index+1)
        return nums

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.quickSort(nums, 0, len(nums)-1)

C++版本

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quickSort2(nums, 0, nums.size()-1);
        // quickSort(nums, 0, nums.size()-1);
        return nums;

    }

    // 递归版本
    void quickSort(vector<int>& nums, int left, int right){
        if (left < right){
            int pivot = partition(nums, left, right);
            quickSort(nums, left, pivot-1);
            quickSort(nums, pivot+1, right);
        }
    }

    // 非递归版本
    void quickSort2(vector<int>& nums, int left, int right){
        if (left < right){
            stack<int> s;
            s.push(right);
            s.push(left);
            while (!s.empty()){
                int l = s.top(); s.pop();
                int r = s.top(); s.pop();
                int pivot = partition(nums, l, r);
                // l, pivot-1
                // pivot+1, r
                if (l < pivot-1){
                    s.push(pivot-1);
                    s.push(l);
                }
                if (pivot+1 < r){
                    s.push(r);
                    s.push(pivot+1);
                }
            }
        }
    }

    //快排的核心函数
    int partition(vector<int>& nums, int left, int right){
        int mid = left + (right - left)/2;
        if (nums[left] < nums[right]){
            swap(nums[left], nums[mid]);
        }
        int pivot = left;
        int index = left+1;
        for (int i = left+1; i <= right; i++){
            if (nums[i] < nums[pivot]){
                swap(nums[i], nums[index++]);
            }
        }
        swap(nums[index-1], nums[pivot]);
        return index-1;
    }
};

归并排序

核心是merge函数，主体函数里面先将数组划分为两部分，分别mergesort后，执行两部分结果的merge

时间复杂度：O(nlogn), 但是空间复杂度为O(n)
稳定性：属于稳定排序

递归版本

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
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.mergeSort(nums)

    def mergeSort(self, nums):
        if len(nums) < 2:
            return nums
        mid = len(nums)//2
        left = self.mergeSort(nums[0:mid])
        right = self.mergeSort(nums[mid:])
        return self.merge(left, right)
        

    def merge(self, left, right):
        result = []
        while left and right:
            if left[0] <= right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        while left:
            result.append(left.pop(0))
        while right:
            result.append(right.pop(0))
        return result

非递归版本

假设 nums = [5,4,0,3,1,6,2,7]
第一次：我们将数组分为 8个子数组 每个数组 1 个元素，对相邻的两个数组进行排序合并。
第二次：我们将数组分为 4个子数组 每个数组 2 个元素，对相邻的两个数组进行排序合并。
第三次：我们将数组分为 2个子数组 每个数组 4 个元素，对相邻的两个数组进行排序合并。
第一步：划分每个子数组元素的个数（也就是子数组的长度)

  1. 第一次 每个子数组元素 个数 为 1.
  2. 第二次 每个子数组元素 个数 为 2.
  3. 第三次 每个子数组元素 个数 为 4.
    可以看出来 每个子数组元素个数 以2的倍数递增. 设置step步长，初始1，2倍递增
    首先：求得要合并的两个相邻数组的区间 [low:mid) [mid:high)
  4. 当子数组长度为 1 的时候 要合并的相邻两个数组的区间为：
    [0,1) [1,2) [2,3) [3,4) [4,5) [5,6) [6,7) [7,8) 子数组长度为 1
  5. 子数组长度为 2 要合并的相邻两个数组的区间为：
    [0,2) [2,4) [4,6) [6,8) 子数组长度为 2
  6. 子数组长度为 4 要合并的相邻两个数组的区间为：
    [0,4) [4,8) 子数组长度为 4
    下面来求 区间中的 low mid height:
    low = low + 2 x step
    mid = low + step
    high = low + 2 x step

但是要注意nums长度不为2的整数倍时，high可能越界，需要优化。

中间过程可能存在轮空的情况，mid和high的关系也需要确保mid<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
25
26
27
28
29
30
31
32
33
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.mergeSort(nums)

    def mergeSort(self, nums):
        step = 1
        while step < len(nums):
            low = 0
            while low < len(nums):
                mid = low + step
                high = min(len(nums), low+2*step)
                if mid < high:
                    self.merge(nums, low, mid, high)
                low += 2*step
            step = step * 2
        return nums
                
        

    def merge(self, nums, begin, mid, end):
        result = []
        i, j = begin, mid
        while i < mid and j < end:
            if nums[i] <= nums[j]:
                result.append(nums[i])
                i += 1
            else:
                result.append(nums[j])
                j += 1
        result += nums[i:mid]
        result += nums[j:end]
        nums[begin:end] = result

堆排序

核心是一个调整动作adjust函数，

建堆过程，从倒数第一个非叶子节点开始调整，直到第一个节点。
排序过程，每次选择堆顶元素与最后一个交换后调整第一个节点。

时间复杂度：O(nlogn), 有空可以详细推导一下
稳定性：中间交换过程不可控，不稳定

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
33
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.heapSort(nums)

    def heapSort(self, nums):
        self.buildHeap(nums)
        for i in range(len(nums)-1, -1, -1):
            self.swap(nums, i, 0)
            self.adjust(nums, 0, i)
        return nums
                
    def swap(self, nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]

    def buildHeap(self, nums):
        for i in range(len(nums)//2, -1, -1):
            self.adjust(nums, i, len(nums))

    def adjust(self, nums, i, length):
        temp = nums[i]
        k = 2*i + 1
        while k < length:
            # 升序和降序修改此处第二个比较符号
            if k+1 < length and nums[k+1] > nums[k]:
                k += 1
            # 升序和降序修改此处比较符号
            if nums[k] > temp:
                nums[i] = nums[k]
                i = k
            k = 2*k + 1
        nums[i] = temp


桶排序

基数排序

计数排序

坚持原创分享，您的支持将鼓励我继续创作

欢迎关注我的其它发布渠道

------------- 本文结束,感谢阅读 如有问题可留言交流 -------------