数据结构 排序算法

数据结构-几种桶排序和堆排序

基数排序，计数排序，桶排序，堆排序

Posted by Hzy on November 25, 2019

今天学习了3种桶排序，基数排序，计数排序，桶排序。

1.1 基数排序

  • 基数排序是一种非比较型排序，步骤
  • 1.创建一个下标0~9的数组，也就是桶。
  • 2.依次比较待排序数组中的个位数，然后放入桶中去。
  • 放入完后，我们会得到一个按照个位数排序的有顺序的10个桶。
  • 3.然我们在把桶中的数字取出来，形成一个新的待排序数组。
  • 4.接着在按照上面的同样的方式循环，依次比较十位，百位…
  • 5.最终可以得到一个排好序的数组。

1.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

# 基数排序
def radixSort(l):
    # 创建桶，0~9 共10个桶,分别记录0，1,2,3,4,5,6,7,8,9
    bucket =[[],[],[],[],[],[],[],[],[],[]]
    dev = 1
    maxNumberLen = 1 # 代表要比较的多少位数，1:代表只比较个位，2:代表十位 ...
    currentNumberLen  = 1
    while currentNumberLen <=maxNumberLen:
        # 比较列表中数字的所有个,十位...数，然后放入桶中
        for number  in l:
            bucket[(number//dev)%10].append(number)
            if len(str(number)) > maxNumberLen:
                maxNumberLen = len(str(number))
        index = 0
        # 从桶中取出来，排列成一个新的序列
        for k,alist in enumerate(bucket):
            for n in alist:
                l[index] = n
                index +=1
            bucket[k] = [] # 清空桶里的元素
        dev *=10
        currentNumberLen +=1
    return l

print(radixSort([123, 91, 1, 97, 17, 23, 84, 28, 72, 5, 67, 25]))

2.1 计数排序

计数排序,计数排序如同字面意思，记录每一个数字出现的次数，变相 的也就知道这个数组的顺序了。

缺点：如果待排序的数组很大，需要创建一个很大的数组来存储出现的数字的次数

  • 步骤：
    1. 找到待排列数组中最大的数和最小的数，（最大的数字）-(最小的数字)+1,代表生成桶的数量。
  • 循环待排列数组，将数字放入对应的桶中，并且计数+1
  • 最后在从桶中按顺序取出元素，计数-1，直到循环结束。
  • 可以得到一个有序的数组。

2.2 计数排序 代码

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

# 计数排序
# 计数排序速度快于 比较排序算法,但需要大量的内存，当数字很大的时候
def countSort(l):
    # 找到最大值
    maxValue= max(l)
    bucket = [0]*(maxValue+1) #创建桶的数量，我们用下标来判断数字
    for n in l:
        bucket[n] +=1 # 下标为n的桶，计数加1
    # 计数完成后，我们在遍历出来
    index= 0
    for i,n in enumerate(bucket):
        while n >0:
            l[index] = i # 桶的下标就是元素的值，进行赋值操作
            index +=1 # 数组索引+1
            n-=1 #桶中的元素数量减1
    return l

print(countSort([123, 91, 1, 97, 17, 23, 84, 28, 72, 5, 67, 25]))

3.1 桶排序

桶排序有些类似计数排序，也是把数放入到桶中，但是通过映射关系放入到桶中!!! 一个桶中会有多个数字。

  • 步骤
  • 同样的创建桶
  • 通过某种映射关系，把数字映射到桶中去，映射关系最好可以让每个桶中的元素均匀分配。
  • 最后排序使用排序算法，排序每一个桶中的元素。
  • 最后在把桶中的元素都取出来，形成一个排好序的数组。

3.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

# 桶排序
def bucketSort(l):
    # 首先将数组中的元素映射到桶中去
    # 桶的数量为(最大值-最小值)+1
    # 映射函数，通过((元素值)-数组最小值)//桶数的映射关系来映射,映射关系可以换成其他的，这里只是示范
    maxN = max(l)
    minN = min(l)
    bucket = [[] for i in range((maxN-minN)+1)]
    # 映射到桶中
    for n in l:
        bucket[(n-minN)//5].append(n)
    index= 0
    # 对每个桶中的元素进行排序,这里我们使用冒泡排序
    for alist in bucket:
        # 冒泡排序
        for i in range(len(alist)):
            for j in range(i+1,len(alist)):
                if alist[i] > alist[j]:
                    alist[i], alist[j] = alist[j], alist[i]
        # 排序完以后，在添加回l中
        for n in alist:
            l[index] = n
            index +=1
    return l

print(bucketSort([12, 91, 1, 97, 17, 23, 84, 28, 72, 5, 67, 25]))

4.1 堆排序

堆排序可以看看这篇文章： 图解堆排序

  • 步骤
  • 1.创建一个大顶堆，也就是数组满足arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 关系
  • 2.交换跟节点和最后一个节点，交换后,剪掉最后一个节点==此时也就是数组中最大的数字。
  • 3.堆的长度减少了1，继续构建大顶堆，然后交换跟节点和最后一个节点，在剪掉最后一个节点。
  • 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
25
26
27
28
29
30
31

# 堆排序
def heapSort(l):
    buildMaxHeap(l)
    length = len(l)-1
    while length >0:
        l[length] ,l[0] = l[0],l[length] # 交换跟节点和，最后一个节点
        l[:length] = buildMaxHeap(l[:length])
        length -= 1
    return l

# 构建最大堆
def buildMaxHeap(l):
    for i in range(len(l)//2,-1,-1):
        heapify(l,i)
    return l
def heapify(l,i):
    left = 2 * i + 1  # 左孩子
    right = 2 * i + 2  # 右孩子
    lastgest = i  # 最大的数字

    if left<len(l) and  l[left] > l[lastgest]:
        lastgest = left
    if right<len(l) and l[right] >l[lastgest]:
        lastgest = right
    if lastgest !=i:
        l[i],l[lastgest] = l[lastgest],l[i]
        heapify(l,lastgest)
    return l
t = heapSort([12, 91, 1, 97, 17, 23, 84, 28, 72, 5, 67, 25])

print(t)
FEATURED TAGS
Python 数据结构