数据结构

排序算法

"排序"

Posted by zwt on November 6, 2020

相关概念

  • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
  • 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
  • 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
  • 是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

1. 冒泡排序

1.1 算法描述

  • 比较相邻的元素，如果第一个大于第二个就交换顺序
  • 每一对相邻元素都要进行操作。
  • 针对除过最后一个元素重复以上步骤
  • 重复1-3，知道完全排序

1.2 动图演示

image

1.3 代码

  1. 每一轮都遍历所有元素，时间复杂度为$O(N^2)$ 
    1
2
3
4
5
6
7
8
9
10
11
12
13

    class Bubble:

 def __init__(self):
     super().__init__()

 def run(self, data):
     for i in range(len(data) - 1):
         for j in range(0, len(data) - 1 - i):
             if data[j] > data[j + 1]:
                 temp = data[j + 1]
                 data[j + 1] = data[j]
                 data[j] = temp
     return data
  2. 通过标识符flag，在经过循环后序列已经有序，就跳出循环提早结束。 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

    class Bubble_1:

 def __init__(self):
     super().__init__()

 def run(self, data):
     for i in range(len(data) - 1):
         flag = True
         for j in range(0, len(data) - 1 - i):
             if data[j] > data[j + 1]:
                 temp = data[j + 1]
                 data[j + 1] = data[j]
                 data[j] = temp
                 flag = False
         if flag:
             break
     return data
  3. 只循环无序数据，记录无序数据边界 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

    class Bubble_2:
 """
 只循环无序数据，记录无序数据边界
 """

 def __init__(self):
     super().__init__()

 def run(self, data):
     boundary = len(data) - 1
     lastExchangeIndex = 0
     for i in range(len(data) - 1):
         flag = True
         for j in range(0, boundary):
             if data[j] > data[j + 1]:
                 temp = data[j + 1]
                 data[j + 1] = data[j]
                 data[j] = temp
                 flag = False
                 lastExchangeIndex = j
         boundary = lastExchangeIndex
         if flag:
             break
     return data
  4. 鸡尾酒排序:当一次从左到右之后，立马从右向左来一次排序比较 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

    class Bubble_3:
 """
 鸡尾酒排序:当一次从左到右之后，立马从右向左来一次排序比较
 """

 def __init__(self):
     super().__init__()

 def run(self, data):
     length = len(data)
     for i in range(length - 1):
         flag = False
         for j in range(length - i - 1):
             if data[j] > data[j + 1]:
                 data[j], data[j + 1] = data[j + 1], data[j]
                 flag = True
         if flag:
             flag = False
             for j in range(length - 2 - i, 0, -1):
                 data[j], data[j - 1] = data[j - 1], data[j]
                 flag = True
         if not flag:
             break
     return data

    1.4 算法分析

    1
2
3

       - 时间复杂度：冒泡排序在平均和最坏情况下的时间复杂度都是O(n^2)，最好情况下都是O(n)
   - 空间复杂度：O(1)
   - 稳定性：将小元素往前调，将大元素往后调，不会影响相同元素的前后顺序，所以是稳定的。

2.选择排序

2.1 描述

遍历序列，找到最大或者最小的元素，存放到排序序列的相应位置，然后在剩余的数据里面再次循环。

  • 初始状态：无序[1,…,n],有序为空
  • 第i躺排序，开始，有序[1,…,i-1]无序[i,…,n].该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
  • n-1躺结束，数组有序了

2.2动态演示

image

2.3 代码实现

  1. 复杂度为$O(N^2)$ 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

    class Select:

 def __init__(self):
     super().__init__()

 def run(self, data):
     length = len(data)
     for i in range(length - 1):
         minIndex = i
         for j in range(i + 1, length):
             if data[j] < data[minIndex]:
                 minIndex = j
         temp = data[i]
         data[i] = data[minIndex]
         data[minIndex] = temp
     return data
  2. 如果走完一趟，最小值没变 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

    class Select_1:

 def __init__(self):
     super().__init__()

 def run(self, data):
     length = len(data)
     flag = True
     for i in range(length - 1):
         minIndex = i
         for j in range(i + 1, length):
             if data[j] < data[minIndex]:
                 minIndex = j
                 flag = False
         if flag:
             continue
         temp = data[i]
         data[i] = data[minIndex]
         data[minIndex] = temp
     return data
  3. 同时记录最大最小值 
    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 Select_2:

 def __init__(self):
     super().__init__()

 def run(self, data_list):
     length = len(data_list)
     for i in range(length - 1):
         # 存储最小值的下标
         min_index = i
         # 最大值的下标，以便最后交换
         max_index = length - i - 1

         for j in range(i + 1, length - i - 1):
             if data_list[min_index] > data_list[j]:
                 min_index = j
             if data_list[max_index] < data_list[j]:
                 max_index = j
             # 退出条件
         if min_index + 1 == max_index:
             break
         # 前面的数据与最小值交换
         # 说明需要交换，否则不需要自己自己交换
         if min_index != i:
             tmp = data_list[i]
             data_list[i] = data_list[min_index]
             data_list[min_index] = tmp
         # 后面的数据与最大值交换
         # 说明需要交换，否则不需要自己与自己交换
         if max_index != length - i - 1:
             tmp = data_list[length - i - 1]
             data_list[length - i - 1] = data_list[max_index]
             data_list[max_index] = tmp
     return data_list

    2.4 算法分析

    表现最稳定的排序算法之一，无论什么数据进去都是$O(N^2)$的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

3.插入排序

3.1 算法描述

  • 从第一个元素开始，该元素乐意被认为已经排序
  • 拿下一个元素，在已经排序的元组序列中，从后向前扫描
  • 如果该元素大于新元素，将该元素移动到下一个位置
  • 重复步骤3，知道找到已排序的元素小于或者等于新元素的位置。
  • 将新元素插入到该位置
  • 重复上述步骤

3.2 动图演示

image

3.3 代码实现

  1. 时间复杂度：$O(N^2)$；空间复杂度为$O(1)$ 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

    class Insert:

 def __init__(self):
     super(Insert, self).__init__()

 def run(self, data):
     length = len(data)
     for i in range(1, length):
         x = data[i]
         for j in range(i, -1, -1):
             # j为当前位置，试探j-1的位置
             if x < data[j -1]:
                 data[j] = data[j -1]
             else:
                 # 位置确定为j
                 break
         data[j] = x
     return data
  2. 采用二分查找法来减少比较操作的次数 
    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 Insert_2:

 def __init__(self):
     super(Insert_2, self).__init__()

 def run(self, data):
     length = len(data)
     for i in range(1, length):
         x = data[i]
         left = 0
         right = i - 1
         # 待插入的值与已排序区域的中间值比较，不断缩小区域范围，直到left和right相遇。
         while left <= right:
             mid = (left + right) // 2
             if data[mid] > x:
                 right = mid - 1
             else:
                 left = mid + 1
         # 查找出temp应插入的位置后，将left后面的数字均向后移动一位
         j = i - 1
         while j >= left:
             data[j+1] = data[j]
             j -= 1
         # 此时left位置上放置待插入的数字
         data[left] = x
     return data

    3.4 算法分析

    插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 - 时间复杂度：平均和最坏$O(N^2$，平均$O(N$ - 空间复杂度$O(1)$ - 稳定排序

4 希尔排序

4.1 算法描述

将待排序的记录序列分割为若干子序列分别进行直接插入排序

  • 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  • 按增量序列个数k，对序列进行k躺排序
  • 每趟排序，根据对应的增量ti，将待排序序列分割为若干长度为m的子序列，分别对各字表进行直接插入排序，仅增量因子为1时，整个序列作为一个表处理，表长度为整个序列的长度

4.2 动图演示

image

4.3 代码实现

  1. 普通，时间复杂度O(N^2) 
    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

    class Shell:

 def __init__(self):
     super(Shell, self).__init__()

 def run(self, data):
     length = len(data)
     if length <= 1:
         return
     # 初始步长
     gap = length // 2
     # 最后一次步长为1，然后整个希尔排序结束
     while gap > 0:
         """
         想象，以步长gap将原始序列划分为gap个待排序序列，对每个序列使用普通的插入排序进行排序
         序列1：[lenght[0], lenght[gap], length[gap*2]...]
         序列2：[length[1], length[gap + 1], length[1 + 2 *gap,....]]
         """
         # "未排序序列" 的第1个元素分别是L[gap], L[1+gap], L[2+gap] ... ，所以变量 i 表示的下标是 gap, 1+gap, 2+gap ...
         for i in range(gap, length):
             temp = data[i]
             j = i
             while j >= gap and temp < data[j - gap]:
                 data[j] = data[j - gap]
                 j -= gap
             data[j] = temp
         # 新的步长
         gap = gap // 2
     return data
  2. 优化，步长序列使用 Sedgewick 提出的[1, 5, 19, 41, 109, 209, 505, 929 …]，此时时间复杂度为 O(n (logn)^2) 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

    class Shell_1:

 def __init__(self):
     super(Shell_1, self).__init__()

 def run(self, data):
     """
     步长序列使用 Sedgewick 提出的[1, 5, 19, 41, 109, 209, 505, 929 ...]，此时时间复杂度为 O(n (logn)^2)
     :return:
     """
     length = len(data)
     gaps = sedgewick_gaps(length)
     # 将gaps生成器对象转换成列表，再倒序: [41, 19, 5, 1]
     for gap in reversed(list(gaps)):
         for i in range(gap, length):
             temp = data[i]
             j = i
             while j >= gap and temp < data[j - gap]:
                 data[j] = data[j - gap]
                 j -= gap
             data[j] = temp
     return data

    4.4 分析

    1
2
3

       - 时间复杂度：最优`$O(n)$`， 最坏`$O(N^2)$`，平均`$O(N^{1.3})$`
   - 空间复杂度：`$O(1)$`
   - 稳定性：不稳定

5 归并排序

5.1 算法描述

归并排序建立在归并操作之上，采用分而治之的思想，将已有序的子序列合并，即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路合并

  • 把长度为n的输入序列分为两个长度为n/2的子序列
  • 对这两个子序列分别采用归并排序
  • 将两个排序好的子序列合并成一个最终的排序序列

5.2 动图演示

image

5.3 代码

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

class Merge:

    def __init__(self):
        super(Merge, self).__init__()

    def temp(self, a, b):
        c = []
        h = j = 0
        while j < len(a) and h < len(b):
            if a[j] < b[h]:
                c.append(a[j])
                j += 1
            else:
                c.append(b[h])
                h += 1
        if j == len(a):
            for i in b[h:]:
                c.append(i)
        else:
            for i in a[j:]:
                c.append(i)
        return c

    def run(self, data):
        if len(data) <= 1:
            return data
        mid = len(data) // 2
        left = self.run(data[:mid])
        right = self.run(data[mid:])
        return self.temp(left, right)

5.4 算法分析

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

6. 快速排序

6.1 算法描述

快速排序的基本思想：通过一样排序将待排序记录分割为独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序。

  • 从数列中挑出一个元素，称为基准
  • 从最后面往前查找，找到比基准小的数，交换顺序，然后从前往后找，找到比基准大的元素交换顺序
  • 递归的吧小于基准值元素的子数列和大于基准元素的子序列排序

6.2 动图演示

image

6.3 代码

递归：

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

class Quick:

    def __init__(self):
        super(Quick, self).__init__()

    def run(self, data):
        length = len(data)
        if length < 2:
            return data
        # 选取基准，随便选那个都可以,选中间便于理解
        mid = data[length // 2]
        # 定义基准值在左右两个数列
        left, right = [], []
        # 从原始数组中移除基准值
        data.remove(mid)
        for item in data:
            # 大于基准放右边
            if item >= mid:
                right.append(item)
            else:
                left.append(item)
        # 使用迭代进行比较
        return self.run(left) + [mid] + self.run(right)

非递归：

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

def quick_sort_1(array, l, r):
    if l >= r:
        return
    stack = []
    stack.append(l)
    stack.append(r)
    while stack:
        low = stack.pop(0)
        high = stack.pop(0)
        if high - low <= 0:
            continue
        x = array[high]
        i = low - 1
        for j in range(low, high):
            if array[j] <= x:
                i += 1
                array[i], array[j] = array[j], array[i]
        array[i + 1], array[high] = array[high], array[i + 1]
        stack.extend([low, i, i + 2, high])
    return array
  1. 三数取中，优化有序的数据
  2. 最优：三数取中+插排+聚集相等元素

6.4 算法分析

  • 时间复杂度：平均$O(NlogN)$、最坏$O(N^2)$、最好$O(NlogN)$
  • 空间复杂度：$O(NlogN)$
  • 稳定性:不稳定

7 堆排序（Heap Sort）

7.1 算法描述

堆排序：利用堆数据结构所设计的排序算法，堆是一种近似完全二叉树的结构，并同时满足堆积的特点，即子节点的键值或者索引总是小于或者大于他的父节点

  • 将初始待排序关键字序列构建为大顶堆，此堆为初始的无序区
  • 将堆顶元素与最后一个元素交换，此时得到新的无序区和新的有序区
  • 由于交换后新的堆顶可能违反对的性质，因此，需要对当前无序区调整为新堆，然后再次进行交换，得到新的无序区，不断重复，则整个排序过程完成。

7.2 动图演示

image

7.3 代码实现

  1. 非递归 ``` class Heap:

    def init(self): super(Heap, self).init()

    def adjust_heap(self, data, parent, length): temp = data[parent] child = 2 * parent + 1 while child < length: if child + 1 < length and data[child + 1] < data[child]: child += 1 if temp < data[child]: break data[parent] = data[child] parent = child child = 2 * parent + 1 data[parent] = temp return data

    def run(self, data): length = len(data) # 初始化堆 for i in range(0, length // 2 + 1)[::-1]: data = self.adjust_heap(data, i, length) for j in range(1, length)[::-1]: data[j], data[0] = data[0], data[j] data = self.adjust_heap(data, 0, j) print(‘第%d趟排序:’ % (length - j), end=’’) print(data) return data

1



class Heap_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

def __init__(self):
    super(Heap_1, self).__init__()

def heapify(self, arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        self.heapify(arr, n, largest)

def run(self, arr):
    n = len(arr)

    for i in range(n, -1, -1):
        self.heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        # 交换
        arr[i], arr[0] = arr[0], arr[i]
        self.heapify(arr, i, 0)
    return arr ``` 2. 递归 ```




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

## 7.4 算法分析
- 时间复杂度：平均`$Nlog(N)$`、最坏`$Nlog(N)$`、最好`$Nlog(N)$`
- 空间复杂度：`$O(1)$`
- 稳定性：不稳定

# 8、计数排序（Counting Sort）
## 8.1 算法描述
计数排序的核心在于将输入的数值转化为键存储在额外开辟的数组空间中，作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数
- 找出待排序的数组中最大和最小的元素
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组，将每个元素放在新数组的第C(i)项，每放一个元素将C(i)减1

## 8.2 动图演示
![image](https://images2017.cnblogs.com/blog/849589/201710/849589-20171015231740840-6968181.gif)

## 8.3 代码




class Count:



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

def __init__(self):
    super(Count, self).__init__()

def run(self, data):
    length = len(data)
    res = [0] * length
    for i in range(length):
        p = 0
        for j in range(length):
            if data[i] > data[j]:
                p += 1
        res[p] = data[i]
    return res ``` ## 8.3 算法分析 计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。




9. 桶排序（Bucket Sort）


9.1 算法描述


桶排序作为计数排序的升级版本：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶分别排序（有可能在使用别的排序算法或者以递归方式继续使用桶排序进行排序）


    
  
  • 设置一个定量的数据当做空桶
    • 
  
  • 遍历输入数据，并且把数据一个个放到对应的桶里
    • 
  
  • 对每个不是空的桶进行排序
    • 
  
  • 从不是空的桶里把排好序的数据拼接起来
    • 




9.2 演示


image



9.3 代码


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

class Bucket:

    def __init__(self):
        super(Bucket, self).__init__()

    def run(self, data):
        # 选择一个最大的数
        max_num = max(data)
        # 创建一个元素全是0的列表，当做桶
        bucket = [0] * (max_num + 1)
        # 把所有元素放入桶中，即把对应的元素个数加1
        for i in data:
            bucket[i] += 1
        # 存储排序好的元素
        sort_num = []
        # 取出桶中的元素
        for j in range(len(bucket)):
            if bucket[j] != 0:
                for y in range(bucket[j]):
                    sort_num.append(j)
        return sort_num



9.4 算法分析


桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。



10 基数排序


10.1 算法描述


基数排序是按照低位先排序，然后收集，再按照高位进行排序，再收集，以此类推。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。


    
  
  • 取得数组中最大数，并取得位数
    • 
  
  • data为原始数组，从最低位开始取每个位组成的radix数组
    • 
  
  • 对radix数组进行计数排序
    • 




10.2 动图演示



image



10.3 代码



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

class Radix:

    def __init__(self):
        super(Radix, self).__init__()

    def run(self, data):
        # 记录当前正在排哪一位，最低位为1
        i = 0
        # 最大值
        max_num = max(data)
        # 记录最大值的位数
        j = len(str(max_num))
        while i < j:
            # 初始桶的数量
            bucket_list = [[] for _ in range(10)]
            for x in data:
                # 找到位置放入桶数组
                bucket_list[int(x / (10 ** i)) % 10].append(x)
            data.clear()
            for x in bucket_list:
                for y in x:
                    data.append(y)
            i += 1
        return data




10.4 算法分析


基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。



基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n»k，因此额外空间需要大概n个左右。



总结






                

                
                


            
  

    
        

    
            


                
                




    
        
    
    
FEATURED TAGS

    

        
        
        
        
        
        
                数学
        
                工具
        
                推荐系统
        
                llms
        
                机器学习
        
                开发
        
                深度学习
        
                语音识别
        
                nlp
        
                搜索
        
                spark
        
                数据分析
        
                开发语言
        
                bert
        
                信息抽取
        
                数据结构
        
                project