数据结构:排序

发表于 | 分类于
| 字数统计: 6.5k 字

本文介绍了数据结构中常用的排序算法：交换类：冒泡、选择、插排、归并、快排、堆排；非交换类：计数排序、基数排序。（python实现）

1.冒泡排序

一轮循环中：两两相比，大就交换，这样在一轮循环结束的时候，就会放好1个数。

  • 时间复杂度：O( N^2 )，额外空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def bubble_sort(li):
    if len(li) < 2:
        '''空或一个数的话直接返回'''
        return li
    for end in range(1, len(li))[::-1]:
        # print(end)
        for i in range(0, end):
            if li[i] > li[i + 1]:
                li[i], li[i + 1] = li[i + 1], li[i]
    return li


li = [1, 5, 7, 3, 6, 8, 4, 2]
print(bubble_sort(li))
1
2
3
4
	0 ~ N-1
   0 ~ N-2
  0 ~ N-3
最值向右漂移

2.选择排序

  • 时间复杂度O( N^2 )，额外空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def selection_sort(li):
    '''每一次循环确定最小的元素，然后放在前面'''
    if len(li) < 2:
        '''空或一个数的话直接返回'''
        return li
    for i in range(len(li)):
        mid_index = i
        for j in range(i + 1, len(li)):
            mid_index = j if li[j] < li[mid_index] else mid_index
        li[i], li[mid_index] = li[mid_index], li[i]
    return li


li = [1, 5, 7, 3, 6, 8, 4, 2]
print(selection_sort(li))
1
2
3
0 ~ N-1
 1 ~ N-1
  2 ~ N-1

3.插入排序

与数据的状况是有关系的，所以产生以下两种情况：

  • 最好情况 O( N ) , （数组是有序的时候）
  • 最坏情况 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 方式一：
def insert_sort(li):
    if len(li) < 2:
        '''空或一个数的话直接返回'''
        return li
    for i in range(1, len(li)):
        for j in range(i)[::-1]:
            # 把第i个数字，往前面插
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
            else:
                break
    return li


li = [1, 5, 7, 3, 6, 8, 4, 2]
print(insert_sort(li))

# 方式二：

def insert_sort2(li):
    if len(li) < 2:
        '''空或一个数的话直接返回'''
        return li
    for i in range(1, len(li)):
        while i > 0:
            # 把第i个数字，往前面插
            print(i)
            if li[i] < li[i - 1]:
                li[i], li[i - 1] = li[i - 1], li[i]
                i -= 1
            else:
                break
    return li

print(insert_sort2(li))

def insert_sort3(li):
    if len(li) < 2:
        '''空或一个数的话直接返回'''
        return li
    for i in range(1, len(li)):
        while i > 0:
            # 找到可以插入的位置
            key = i
            if li[i] < li[i - 1]:
                i -= 1
            else:
                break
        li[i], li[key] = li[key], li[i]
    return li

print(insert_sort3(li))

演示过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1.    5,| 3, 4, 0, 6
         ↑q 
        从第一个数开始，第0个是有序的 
2.    3, 5,| 4, 0, 6
            ↑q

3.    3, 4, 5,| 0, 6
            ↑q

4.1   3, 4, 0, 5, 6
               ↑q

4.2   3, 0, 4, 5, 6
               ↑q

4.3   0, 3, 4, 5,| 6
               ↑q

5.	  0, 3, 4, 5, 6|
                  ↑q

递归函数的时间复杂度分析

master公式：
$$
T(N)=aT(\frac{N}{b}) + O(N^d)
$$

  1. 当log(b, a) > d 时：复杂度为 O(N^log(b, a))

    或者：b^d > a

  2. 当log(b, a) = d 时：复杂度为 O(N^d * logN)

    或者：b^d = a

  3. 当log(b, a) < d 时：复杂度为 O(N^d)

    或者：b^d < a

master公式的适用范围：划分子问题的规模是一样的

在引例中，我们的时间复杂度为：
$$
T(N)=2T(\frac{N}{2}) + O(1)
$$
N ：（父问题的样本量）

N/b ：（子过程样本量）中间切一刀，左右的样本量为 N/2

a ：（子过程发生多少次）左边跑完跑右边，所以样本量为 N/2 的情况发生了两次

N^d ：（除去子过程调用外，剩下的过程的时间复杂度）比对较大的数是一个常数操作

结论:

b = 2 , a = 2 , d = 0

log(b, a) = log(2, 2) = 1 > d

复杂度为 O( N )

note：不需要管整个递归怎么样，只需要看自己写的这个代码中，样本量为n，它是怎么划分。（因为子问题的划分也是同当前的，不管它展开几次，只需要分析父问题化子问题这一步就可以）

扩展1:

如果我们的剩余过程中含有循环的话，公式为:
$$
T(N)=2T(\frac{N}{2}) + O(N)
$$
b = 2 , a = 2 , d = 1

log( b, a ) = 1 = d

复杂度为 O( N * logN )

扩展2:

如果我们的剩余过程的时间复杂度为 O( N ^ 2 )，公式为:
$$
T(N)=2T(\frac{N}{2}) + O(N^2)
$$
b = 2 , a = 2 , d = 2

log( b, a ) = 1 < d

复杂度为 O( N^2 )

扩展3:

如果我们的子问题的规模不同，剩余过程的时间复杂度为 O( N ^ 2 )，公式为:
$$
T(N)=T(\frac{N}{3}) + T(\frac{2N}{3}) + O(N^2)
$$
这里就不能再用master公式计算时间复杂度了。

4.归并排序

  • 时间复杂度O( N*logN )，额外空间复杂度O( N )

思路

  • 分治
  • 先左侧部分排好序，在右侧部分排好序，准备一个辅助数组，用外排序的方式，小的填，依次动，一个移动到末尾后，把另一个后面的内容拷贝到辅助数组中，最后将辅助数组的内容拷贝到原数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    	 5  3  6 | 2  0  1
1.  	 3  5  6 | 0  1  2 
2.   	 ↑a        ↑b             辅助数组  li = []

    	 3  5  6 | 0  1  2 
3.1	  	 ↑a           ↑b          辅助数组  li = [0]

    	 3  5  6 | 0  1  2 
3.2	  	 ↑a              ↑b       辅助数组  li = [0, 1]
  
    	 3  5  6 | 0  1  2 
3.2	  	 ↑a              ↑b       辅助数组  li = [0, 1, 2]

    	 3  5  6 | 0  1  2 
3.3	  	       ↑a        ↑b       辅助数组  li = [0, 1, 2, 3, 5, 6]

时间复杂度分析：
$$
T(N)=2T(\frac{N}{2}) + O(N)
$$
a = 2, b = 2, d = 1

log(b, a) = 1 = d

所以时间复杂度为：O( N*logN )

疑惑：如果左边比右边多一个，或者右边多一个，不影响。样本量不估计常数（抹掉常数），只估计规模。

代码实现

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
def merge_sort(li):
    if len(li) < 2:
        return li
    sort_process(li, 0, len(li) - 1)  # L 到 R 的位置上排好序


def sort_process(li, l, r):
    if l == r:
        return li[l]
    mid = (l + r) // 2
    sort_process(li, l, mid)        # T(N/2)
    sort_process(li, mid + 1, r)    # T(N/2)
    merge(li, l, mid, r)            # O( N )
    # T(N) = 2T(N/2) + O(N)


def merge(li, l, mid, r):
    help = []
    p1 = l
    p2 = mid + 1
    while p1 <= mid and p2 <= r:
        if li[p1] < li[p2]:
            help.append(li[p1])
            p1 += 1
        else:
            help.append(li[p2])
            p2 += 1
    # 两个必有一个越界
    if p1 <= mid:
        # p2 越界，拷贝p1
        help += li[p1:mid + 1]
    if p2 <= r:
        # p1 越界，拷贝p2
        help += li[p2:r + 1]

    for i in range(len(help)):
        # 覆盖原数组的部分内容
        li[l + i] = help[i]


li = [1, 5, 3, 2, 6, 4]
merge_sort(li)
print(li)

铺垫（荷兰国旗问题）

引例

给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)。（两层）

思想：

  1. 准备一个 小于等于num的区域
  2. 如果大于num，跳到下一个数字
  3. 如果小于num，将当前这个数 与 小于等于区域的前一个数 进行交换，区域向右扩大一下
  • 小于等于区域推着 待定区域 向右扩张。（小于等于区域、待定区域）

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def sort(arr, num):
    cur = 0
    less = -1
    while cur < len(arr):
        if arr[cur] <= num:
            less += 1
            arr[less], arr[cur] = arr[cur], arr[less]
            cur += 1
        else:
            cur += 1


li = [6, 5, 4, 3, 2, 1]
sort(li, 3)
print(li)

partition

给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)。（三层）

思想:

  1. 准备一个小于num的区域，一个大于num的区域
  2. 如果当前这个数等于num，则跳到下一个
  3. 如果当前这个数小于num，则将当前这个数与 小于区域 的前一个数交换，小于区域向右扩大一下
  4. 如果当前这个数大于num，则将当前这个数与 大于区域 的前一个数交换，大于区域向左扩大一下
  5. 当 cur（当前位置） 和 more（大于区域的边界）相遇时，停止
  • 小于区域推着 等于区域 向右扩张。（小于区域、等于区域、待定区域、大于区域 ）

ps：就像发货一样

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def nether_land_flag(arr, l, r, num):
    cur, less, more = l, l - 1, r + 1  # 当前, 小于num的区域, 大于num的区域

    while cur < more:
        if arr[cur] < num:
            less += 1
            arr[less], arr[cur] = arr[cur], arr[less]
            cur += 1 # 换回来的一定是等于区域的内容
        elif arr[cur] > num:
            more -= 1
            arr[more], arr[cur] = arr[cur], arr[more]
        else:
            cur += 1

    return less + 1, more - 1  # 返回等于num的左右边界


li = [6, 5, 4, 3, 2, 1]
print(nether_land_flag(li, 0, len(li) - 1, 1))
print(li)

5.快排

经典快排

思想：每次解决一个数num的位置（<= num放左边，>num放右边）。

经典快排的问题

  • 最好情况：每次划分，左右各一半（大于和小于区域一样大），这样利用master公式得出 O(N*logN)
  • 最坏情况：每次划分，中心位置偏了，如这个例子： 6,5,4,3,2,1 —》 1,6,5,4,3,2 （只有大于/小于区域）

总拿最后一个数进行划分，跟数据状况就有关系了，如果是最坏情况，这样会蜕变成 O(N^2)

代码实现：

note：我们这里使用了荷兰国旗去进行了一个加速，不再是每次只搞定一个数x，而是将区域划分为三部分：小于区域、等于区域和大于区域，搞定一堆x。

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
import random


def quick_sort(arr, l, r):
    if l < r:
        # tmp = random.randint(l, r)
        # arr[tmp], arr[r] = arr[r], arr[tmp]
        p = partition(arr, l, r)
        print(p)
        quick_sort(arr, l, p[0] - 1)
        quick_sort(arr, p[1] + 1, r)


def partition(arr, l, r):
    '''返回的是中间部分（不用再继续排的）的左右的下标'''
    # 荷兰国旗,只不过，依据的是末尾的这个值，while结束后，再将比较的这个值放入等于区域
    less = l - 1
    more = r
    while l < more:
        if arr[l] < arr[r]:
            # 小于区域扩张
            less += 1
            arr[less], arr[l] = arr[l], arr[less]
            l += 1
        elif arr[l] > arr[r]:
            more -= 1
            arr[more], arr[l] = arr[l], arr[more]
        else:
            # arr[l] == arr[r]
            l += 1    
    arr[more], arr[r] = arr[r], arr[more]
    return less + 1, more


li = [1, 4, 2, 6, 1, 5, 8, 3]

quick_sort(li, 0, len(li) - 1)
print(li)

优化（随机快排）

  • 时间复杂度O(N*logN)，空间复杂度O(logN) （只是随机快排）
  • 它也是最常用的排序，因为它代码简洁，常数项就很低。

以前我们是选最后一个数作为划分标准，这样是存在最好和最坏情况的。但是我们随机从列表中选择一个数放在最后的位置，这样的话就不存在最好和最坏情况了，它变成了一个概率事件，通过期望来计算时间复杂度，长期期望是 O(N*logN)。

为什么随机快排的空间复杂度是O(logN) ？

  • 假设：对于位置 从 0 - 7 这八个数来打断点进行划分（大于断点，小于断点）（不弄断点就不知道在左侧划分结束后，右侧的位置）。
  • 最好情况：[1,2,3,4,5,6,7] 最开始断点打在中间位置4处，然后每次都打在中间的位置，这样数组能被二分为多少次，就需要多少个断点。
  • 最差情况：[1,2,3,4,5,6,7] 最开始断点在 7 位置处，这样向下递归的话，每一个数字需要打一个断点，所以是O(N)。
  • 因为最好情况，最坏情况都是概率事件，所以它的空间复杂度为长期期望O(logN)

代码实现：

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
import random


def quick_sort(arr, l, r):
    if l < r:
        tmp = random.randint(l, r)
        arr[tmp], arr[r] = arr[r], arr[tmp]
        p = partition(arr, l, r)
        print(p)
        quick_sort(arr, l, p[0] - 1)
        quick_sort(arr, p[1] + 1, r)


def partition(arr, l, r):
    '''返回的是中间部分（不用再继续排的）的左右的下标'''
    # 荷兰国旗,只不过，依据的是末尾的这个值，while结束后，再将比较的这个值放入等于区域
    less = l - 1
    more = r
    while l < more:
        if arr[l] < arr[r]:
            # 小于区域扩张
            less += 1
            arr[less], arr[l] = arr[l], arr[less]
            l += 1
        elif arr[l] > arr[r]:
            more -= 1
            arr[more], arr[l] = arr[l], arr[more]
        else:
            # arr[l] == arr[r]
            l += 1    
    arr[more], arr[r] = arr[r], arr[more]
    return less + 1, more


li = [1, 4, 2, 6, 1, 5, 8, 3]

quick_sort(li, 0, len(li) - 1)
print(li)

ps：

  1. 除了使用概率的方式规避最好与最坏情况（原始的数据状况），我们还可以使用hash来进行规避。
  2. 工程中是不允许递归出现的，所以工程中的快排使用的是非递归的形式。

6.堆排序

  • 时间复杂度O(N*logN)，额外空间复杂度O(1)

堆结构非常重要：

  1. 堆结构的heapInsert与heapify
  2. 堆结构的增大与减少
  3. 如果只是建立堆的过程，时间复杂度为O(N)
  4. 优先级队列结构，就是堆结构（例如，在python中，PriorityQueue用到了heapq模块（小根堆））
  • 堆是一颗完全二叉树
  • 堆是在数组上进行伸缩的

完全二叉树：

  1. 满二叉树
  2. 上面的层构成满二叉树，最下面这一层是从左到右依次补齐的。

在这里我们将一个数组抽象成一颗完全二叉树：

  1. 位置 i 处的左孩子的下标是 2*i+1 ；
  2. 位置 i 处的右孩子的下标是 2*i+2 ；
  3. 位置 i 处的父节点是 (i-1) / 2

大根堆

  • 任何一颗子树的最大值都是这颗子树的根部

建立大根堆heapinsert

  • 时间复杂度：O(logN)

  • 思想：依次把 i 位置上的数字加进来，让它在 0-i 之间形成大根堆。

  • 特点：一个新加入的数，只需要和它的父亲，祖先比较（这个向上调整的过程称为heapinsert）。

    代码:

1
2
3
4
5
6
7
8
9
10
11
def heapinsert(arr, index):
    while arr[index] > arr[(index - 1) // 2] and (index - 1) // 2 >= 0:  # (index - 1) // 2 >= 0是为了排除-1，python中 -1 // 2 == -1
        # 当index到达0的时候，两者相等，也停止
        arr[index], arr[(index - 1) // 2] = arr[(index - 1) // 2], arr[index]
        index = (index - 1) // 2


li = [2, 1, 3, 6, 0, 4]
for i in range(len(li)):
    heapinsert(li, i)
print(li)

当一个节点的值发生改变时heapify

  • 思想：改变的这个值和它的子孙进行比较然后向下沉（这个向下调整的过程称为heapify）。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def heapify(arr, index, heapsize):
    '''
    0 到 heapsize-1 范围内的堆，index位置的值发生了变化
    '''
    left = index * 2 + 1
    while left < heapsize:
        # 右孩子不越界，且右孩子的值大于左孩子
        largest = left + 1 if left + 1 < heapsize and arr[left + 1] > arr[left] else left
        # 三者/两者之间的比较
        largest = largest if arr[largest] > arr[index] else index
        if largest == index:
            # 最大值如果是你自己就中止
            break
        arr[largest], arr[index] = arr[index], arr[largest]
        index = largest
        left = index * 2 + 1

小根堆

  • 任何一颗子树的最小值都是这颗子树的根部

堆排序

利用堆结构完成的排序

  1. 先形成大根堆；
  2. 将堆顶与heapsize的值进行交换，然后heapsize–；
  3. 进行heapify后，继续执行2；

这样每一次执行过程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
30
31
32
33
34
35
def heapsort(arr):
    if len(arr) < 2:
        return
    for i in range(len(arr)):
        heapinsert(arr, i)
    heapsize = len(arr) - 1
    arr[0], arr[heapsize] = arr[heapsize], arr[0]
    heapsize -= 1
    while heapsize > 0:
        heapify(arr, 0, heapsize)
        arr[0], arr[heapsize] = arr[heapsize], arr[0]
        heapsize -= 1


def heapinsert(arr, index):
    while arr[index] > arr[(index - 1) // 2] and (index - 1) // 2 >= 0:
        arr[index], arr[(index - 1) // 2] = arr[(index - 1) // 2], arr[index]
        index = (index - 1) // 2


def heapify(arr, index, heapsize):
    left = index * 2 + 1
    while left < heapsize:
        largest = left + 1 if left + 1 < heapsize and arr[left + 1] > arr[left] else left
        largest = largest if arr[largest] > arr[index] else index
        if largest == index:
            break
        arr[largest], arr[index] = arr[index], arr[largest]
        index = largest
        left = index * 2 + 1


li = [1, 4, 2, 5, 6, 7, 2, 6]
heapsort(li)
print(li)

应用场景

添加一个数值，计算一次中位数

  • 时间复杂度是O(logN)（将栈顶与heapsize的值互换、heapsize–以及heapify的过程）
  • 如果不用这种方式，每次使用排序然后计算中位数的话，时间复杂度是O(N*logN)

思路：

大根堆保存较小的N/2个数，小根堆保存较大的N/2个数，这样想要的中位数就是堆顶了！

做法：

这个数小于等于大根堆的堆顶，进大根堆；大于大根堆的堆顶，进小根堆。当两个堆的heapsize的差值大于1时，进行调整。

ps：几乎一切贪心都可以用堆来做！

排序的稳定性

相同的值会不会因为排序算法而改变它们相对的次序。

O(N^2):

  1. 冒泡算法：如果当前这个值与后面相等的值不发生交换，让后面这个值继续向后冒泡，那这样就是稳定的，交换了就不稳定了。
  2. 插入排序：不插到相等值的前面就是稳定的。
  3. 选择排序：不稳定。（如：5，5，5，4，0 找到最小的数与0号位置交换，这样就直接不稳定了）

O(N*logN):

  1. 归并排序：在merge过程中，两个列表中遇到相同的值，先拷贝左边列表的，这样就是稳定的。
  2. 快排：不稳定，partition是不稳定的。（如：4，4，4，3）（能做到的是论文级别的）
  3. 堆排：不稳定。（如：4，4，4，5 在建大根堆的时候就不稳定了）

ps：冒泡的常数项高，是因为太多次的交换；选择排序的一个缺点是完整遍历后才能确定一个最值得位置。

稳定性的意义

  • 保证原始信息不会被抹去（排序之前的信息）
  • 如先根据身高进行排序后，再根据age进行排序，对于age相同的，可以按照之前的根据身高进行排序的结果。

工程中的综合排序算法

  • 如果数组长度很短（60），会直接使用插排。（常数项很低，小样本中N^2劣势也表现不出来）
  • 如果是基础类型，使用快排。（不用区分相对次序，不需要保证稳定性）
  • 如果是自定义的结构体，会使用归并排序。（需要区分相对次序，需要保证稳定性）
  • 在递归的过程中，如果子样本量小于60，则会使用插排。

有关排序问题的补充

  1. 规避排序的额外空间复杂度可以变成O(1)，但是非常非常难，参考“归并排序，内部缓存法”；原地归并空间是有问题的，时间复杂度弄到了O(N^2）。
  2. 快排可以做到稳定，但非常难，参考“01 stable sort”
  3. 有一道题目，是奇数放在数组左边，偶数放在数组右边，要求原始的相对次序不变，碰到这个问题，直接怼吧，非良人。要求：时间复杂度O(N)，空间复杂度O(1)
    • 它的本质和快排一样是 0 1 标准。

以上涉及的排序都为基于比较的排序

桶排序

  1. 非基于比较的排序，与被排序的样本的实际数据状况很有关系，所以在实际中并不经常使用。（当数据量特别大的时候 -40亿到40亿，就不好用了，难道要准备这么多的桶吗？）
  2. 时间复杂度O(N)，额外空间复杂度O(N)
  3. 稳定的排序
  • 桶排序是一个大的概念，在它下面，计数排序和基数排序是具体实现。
  • 桶是一个容器，每一个桶用来装一个词的词频。

7.计数排序

计数排序是一种在特定范围中基于次数的一种排序

原理：给定的输入序列中的每一个元素x，确定该序列中值小于等于x元素的个数，然后将x直接存放到最终的排序序列的正确位置上。

空间复杂度和时间复杂度

假定原始数列的规模是N，最大值和最小值的差是M，计数排序的时间复杂度是O(N+M)，如果不考虑结果数组，只考虑中间数组大小的话，空间复杂度是O(M)

局限性

  • 当数列的最大和最小值差距过大时，并不适用计数排序
  • 当数列元素不是整数，并不适用计数排序

实现代码:

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
def CountingSort(arr):
    # 检查入参类型
    if not isinstance(arr, (list)):
        raise TypeError('error para type')
    # 获取arr中的最大值和最小值
    maxNum = max(arr)
    minNum = min(arr)
    # 以最大值和最小值的差作为中间数组的长度,并构建中间数组，初始化为0
    length = maxNum - minNum + 1
    tempArr = [0 for i in range(length)]
    # 创建结果List，存放排序完成的结果
    resArr = list(range(len(arr)))
    # 第一次循环遍历 ：统计每个元素的出现次数
    for num in arr:
        tempArr[num - minNum] += 1
    # 第二次循环遍历 ：统计出小于等于当前下标的元素个数
    for j in range(1, length):
        tempArr[j] = tempArr[j] + tempArr[j - 1]
    # 第三次循环遍历：反向遍历arr的每个元素，找到该元素值在中间数组的对应下标，
    # 以这个中间数组的值作为结果数组的下标，将该元素存入结果数组
    for i in range(len(arr) - 1, -1, -1):
        resArr[tempArr[arr[i] - minNum] - 1] = arr[i]
        tempArr[arr[i] - minNum] -= 1
    return resArr


if __name__ == '__main__':
    arr = [12, 25, 26, 13, 14, 25, 12, 17, 18, 14]
    print(CountingSort(arr))

扩展练习

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)，且要求不能用非基于比较的排序。

如：3，1，6，2，7 -> 1,2,3,6,7 然后返回相邻两数的最大差值！

思路：借用了桶的概念，但没有使用桶排序。

  1. 准备桶，N个数，准备N+1个桶。
  2. 先遍历，找最小值和最大值。如果最小值和最大值相等，那就只有一种数，直接返回0。
  3. 0号桶放最小值，N号桶里放最大值。
  4. 中间进行等分，放入该桶中。

例如：

9个数字，准备10个桶，这9个数字中，最小0，最大值为99，那么中间的数就放到各自的桶内。编号0的桶存放0-9、编号1的桶存放10-19、。。。编号9的桶内存放90-99.

  • 中间必存在一个空桶。（设置空桶是为了保证，最大差值一定不是来自相同桶的数）
  • 最大差值就是空桶左边桶的最大值与右边桶最小值的差值！
  • 每个桶统计三个信息：最小值、最大值、是否有值
  • 遇到空桶，跳过；
  • 遇到非空桶，找前一个非空桶（左边最近的非空桶），用当前非空桶的最小值减去前一个非空桶中的最大值，并将这个差值设为一个全局变量。

note：答案可不一定就在非空桶的两侧，（如：桶1存放19、桶2为空、桶3存放30、桶4存放49这样两个桶之间虽然没有空桶，但他们的差值是最大的）。

代码：

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
def max_gap(arr):
    if len(arr) < 2:
        return 0
    # 先确定最大值和最小值
    max_value, min_value = max(arr), min(arr)
    if max_value == min_value:
        # 如果最大值和最小值相同，直接返回0
        return 0
    # 定义并初始化 N+1个桶，每个桶中存放是否有值，最大值和最小值
    has_num, maxs, mins = [None] * (len(arr) + 1), [None] * (len(arr) + 1), [None] * (len(arr) + 1)

    for item in arr:
        # 更新桶中数据
        bid = bucket(item, len(arr), min_value, max_value)
        mins[bid] = mins[bid] if has_num[bid] and mins[bid] >= item else item
        maxs[bid] = maxs[bid] if has_num[bid] and maxs[bid] <= item else item
        has_num[bid] = True

    res = 0  # 定义全局最大差值
    last_max = maxs[0]  # 存放前一个桶的最大值

    for i in range(len(has_num)):
        # 计算最大差值
        if has_num[i]:
            # 遇到非空桶，就是用它的最小值减去前一个桶的最大值
            res = max(res, mins[i] - last_max)
            last_max = maxs[i]
    return res


def bucket(num, length, min, max):
    # 放回该数字所属的桶的编号
    return (num - min) * length // (max - min)


print(max_gap([1, 3, 7, 9, 20, 30, 40, 50, 10, 70]))

8.基数排序

分为两类：

  1. 最低位优先法，简称LSD：先从最低位开始排序，再对次低位排序，直到对最高位排序后得到一个有序序列；
  2. 第二类：最高位优先法，简称MSD法：先从最高位开始排序，再逐个对各分组按次高位进行子排序，循环直到最低位。

原理：将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

时间复杂度 ：O(d(n+rd))

  • 设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。

空间复杂度：O(rd)

  • 需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。

实现代码（LSD）：

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
# LSD 最低位优先法
def radix_sort(a):
    i = 0  # 初始为个位排序
    n = 1  # 最小的位数置为1（包含0）
    max_num = max(a)  # 得到带排序数组中最大数
    while max_num > 10 ** n:  # 得到最大数是几位数
        n += 1
    while i < n:
        bucket = {}  # 用字典构建桶
        for x in range(10):
            bucket.setdefault(x, [])  # 将每个桶置空
        for x in a:  # 对每一位进行排序
            radix = int((x / (10 ** i)) % 10)  # 得到每位的基数
            bucket[radix].append(x)  # 将对应的数组元素加入到相应位基数的桶中
        j = 0
        for k in range(10):
            if len(bucket[k]) != 0:  # 若桶不为空
                for y in bucket[k]:  # 将该桶中每个元素
                    a[j] = y  # 放回到数组中
                    j += 1
        i += 1


if __name__ == '__main__':
    a = [12, 3, 45, 3543, 214, 1, 4553]
    print(a)
    radix_sort(a)
    print(a)
-------------The End-------------

本文标题:数据结构:排序

文章作者:Naqin

发布时间:2018年07月17日 - 17:07

最后更新:2020年02月26日 - 10:02

原始链接:https://chennq.top/数据结构/20180717-data-struct-sort.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

Naqin wechat
欢迎看官加我微信！
坚持原创技术分享，您的支持将鼓励我继续创作！
0%