通用算法-排序

发表于 | 更新于 | 分类于 ， | 阅读次数：

一、环境

之前写过，但是因为作业再写一遍。

  • 系统：win10
  • 语言：python3.7

二、各种排序算法

2.1 冒泡排序

原理如下图：

GIF

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maopao(arr):
    n = len(arr)
    if n == 0:
        raise Exception

    for i in range(n):
        for k in range(n - i - 1):
            if arr[k] > arr[k + 1]:
                temp = arr[k]
                arr[k] = arr[k + 1]
                arr[k + 1] = temp
    return arr

if __name__ == "__main__":
    arr = [6,3,8,5,2,9,4,0]
    print(maopao(arr))

输出：

1
[0, 2, 3, 4, 5, 6, 8, 9]

2.2 选择排序

原理如下图：

GIF

效果比冒泡优秀一点点，冒泡每次都需要交换，而选择排序只需要交换一次。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def SelectSort(arr):
    n = len(arr)

    for i in range(n):
        minIndex = i
        for j in range(i+1, n):
            if arr[minIndex] > arr[j]:
                minIndex = j

        temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp


if __name__ == "__main__":
    arr = [6,3,8,5,2,9,4,0]
    print(SelectSort(arr))

输出：

1
[0, 2, 3, 4, 5, 6, 8, 9]

2.3 直接插入排序

原理如下图：

GIF

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def InsertSort(arr):
    n = len(arr)

    for i in range(1,n):
        if arr[i]<arr[i-1]:
            temp=arr[i]
            j=i-1
            while arr[j]>temp and j>=0:
                arr[j+1]=arr[j]
                j = j-1
            arr[j+1]=temp

    return arr


if __name__ == "__main__":
    arr = [6,3,8,5,2,9,4,0]
    print(InsertSort(arr))

结果：

1
[0, 2, 3, 4, 5, 6, 8, 9]

2.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
32
33
34
35
36
37
38
39
def HalfSort(arrData, target, mi, ma):
    i = (mi + ma) // 2  # 中间索引
    c = arrData[target] - arrData[i]
    if mi == ma or i == ma or i == mi:
        d = arrData[target] - arrData[ma]
        if c >= 0 and d < 0:
            Insert(arrData, target, i + 1)
        elif c < 0:
            Insert(arrData, target, i)
        elif d >= 0:
            Insert(arrData, target, ma + 1)
        return
    if c > 0:
        HalfSort(arrData, target, i + 1, ma)
    elif c == 0:
        Insert(arrData, target, i + 1)
        return
    else:
        HalfSort(arrData, target, mi, i - 1)
    return

def Insert(arrData, target, dest):
    tmp = arrData[target]
    i = target - 1

    while i >= dest:
        arrData[i + 1] = arrData[i]
        i = i - 1
    arrData[dest] = tmp
    return

def HalfInsertSort(arrData):
    for i in range(1, len(arrData)):
        HalfSort(arrData, i, 0, i - 1)
    return arrData

if __name__ == "__main__":
    arr = [6, 3, 3, 3, 8, 5, 2, 9, 4, 0]
    print(HalfInsertSort(arr))

输出：

1
[0, 2, 3, 3, 3, 4, 5, 6, 8, 9]

2.5 希尔排序

原理说明：

考虑到归并排序在数据原本就比较有序的情况下效率比较高，借用这种想法，每隔数个间隔进行一次比较，逐步缩短比较的间隔，直到排序完毕

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def ShellSort(arr):
    n = len(arr)
    gap = int(n/2)
    while gap > 0:
        for i in range(gap,n):
            temp = arr[i]
            j = i
            while  j >= gap and arr[j-gap] >temp:
                arr[j] = arr[j-gap]
                j -= gap
            arr[j] = temp
        gap = int(gap/2)

    return arr

if __name__ == "__main__":
    arr = [6, 3, 3, 3, 8, 5, 2, 9, 4, 0]
    print(ShellSort(arr))

输出：

1
[0, 2, 3, 3, 3, 4, 5, 6, 8, 9]

2.6 链表排序

原理说明：

在直接插入的基础上，通过链表插入，只需要更换两个节点的指针，不需要进行数据移位。

代码如下：

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
# 节点定义
class Node:
    def __init__(self, data, child=None):
        self.data = data
        self.child = child

# 生成测试链表
def GenerateTestData(arr, left, rights):
    if left == rights:
        return None

    HeadList = Node(arr[left], GenerateTestData(arr, left + 1, rights))

    return HeadList

# 链表打印
def DataTestPrint(headList):
    while headList != None:
        print(headList.data, " ", end='')
        headList = headList.child
    print(" ")

# 链表排序
def ListSort(headList):
    root = Node(None, headList)   # 生成一个空的头节点
    sortList = root               # 已经排好序的头结点

    unSortList = root.child       # 未排序的节点
    sortList.child = None         # 排好序的链表和未排好序的链表断开

    p = unSortList                # 需要插入的链表

    while p != None:
        unSortList = unSortList.child  # 与 p 的连接断开

        while sortList.child != None:  # 找到需要插入的位置
            if p.data <= sortList.child.data:
                break
            sortList = sortList.child

        p.child = sortList.child       # 插入
        sortList.child = p

        p = unSortList                 # 下一个需要插入的位置
        sortList = root                # 将指针移动到排好序链表的头位置

    return root.child


if __name__ == "__main__":
    arr = [6, 3, 3, 3, 8, 5, 2, 9, 4, 0]
    headList = GenerateTestData(arr, 0, len(arr))
    DataTestPrint(ListSort(headList))

输出：

1
0  2  3  3  3  4  5  6  8  9

2.7 快速排序

原理如下图：

GIF

代码如下：

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 getIndex(arr, left, right, tmp):
    if left >= right:
        arr[left] = tmp
        return left

    while (left  < right) and (arr[right] >= tmp):
        right = right - 1

    arr[left] = arr[right]

    while (left < right) and (arr[left] <= tmp):
        left = left + 1

    arr[right] = arr[left]

    return getIndex(arr, left, right,tmp)

def SortByQuickly(arr, left, right):
    if left >= right:
        return arr

    middle = getIndex(arr, left, right, arr[left])

    SortByQuickly(arr, left, middle - 1)
    SortByQuickly(arr, middle + 1, right)

    return arr

if __name__ == "__main__":
    arr = [6,3,3,3,8,5,2,9,4,0]
    print(SortByQuickly(arr,0,len(arr)-1))

输出：

1
[0, 2, 3, 3, 3, 4, 5, 6, 8, 9]

2.8 计数排序

原理说明：

统计每一个数大于其他数的次数，然后进行排序。优点：不需要进行交换和移位，在数据值范围较小的情况，性能比较优秀。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def CountSort(arr):
    n = len(arr)
    res = [None] * n
    for i in range(n):
        p = 0; q = 0
        for j in range(n):
            if arr[i] > arr[j]:
                p += 1
            elif arr[i] == arr[j]:
                q += 1
        for k in range(p, p+q):
            res[k] = arr[i]
    return res

if __name__ == "__main__":
    arr = [6,3,3,3,8,5,2,9,4,0]
    print(CountSort(arr))

输出：

1
[0, 2, 3, 3, 3, 4, 5, 6, 8, 9]

2.9 树选择排序

原理说明：

通过类似于树的结果，通过两两比较，类似打擂台的形式，比较出最大值（下面程序中是最小），保存输出。

代码如下：

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
import numpy as np
def TreeSelectMax(arr, left, right): # 返回最大值的index
    if left == right:
        return left

    middle = int((left + right) / 2)

    A = TreeSelectMax(arr,left,middle)
    B = TreeSelectMax(arr,middle+1,right)

    if arr[A] < arr[B]:
        return A
    else:
        return B

def TreeSelectSort(arr):
    n = len(arr)
    outArr = []

    for i in range(n):
        index = TreeSelectMax(arr,0,n-1)
        outArr.append(arr[index])         # 找到最小值，存入输出内存
        arr[index] = np.inf               # 赋值无穷大

    return outArr

if __name__ == "__main__":
    arr = [6, 3, 3, 3, 8, 5, 2, 9, 4, 0]
    print(TreeSelectSort(arr))

2.10 二路归并排序

原理如下图：

GIF

代码如下：

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
def merge(arr, left, middle, right, tmpArray):
    left_i = left
    right_k = right
    temp = middle
    middle = middle + 1
    i = 0

    while (left <= temp) and (middle <= right):   # 扫描两段，比较存入到tmpArray，直到其中一个扫描完毕
        if arr[left] < arr[middle]:
            tmpArray[i] = arr[left]
            left = left + 1
        else:
            tmpArray[i] = arr[middle]
            middle = middle + 1

        i = i + 1

    while left <= temp:     # 把第一段未扫描的结束的直接添加到tmpArray后面
        tmpArray[i] = arr[left]
        left = left + 1
        i = i + 1

    while middle <= right:   # 把第二段未扫描的结束的直接添加到tmpArray后面
        tmpArray[i] = arr[middle]
        middle = middle + 1
        i = i + 1

    i = 0

    while left_i <= right_k: # 复制到原数组中arr
        arr[left_i] = tmpArray[i]
        left_i = left_i + 1
        i = i + 1

def mergeSort(arr, left, right, tmpArray):
    if left >= right:
        return

    middle = int((left + right) / 2)

    mergeSort(arr, left, middle, tmpArray)
    mergeSort(arr, middle + 1, right, tmpArray)

    merge(arr, left, middle, right, tmpArray)


def MergeSort(arr):
    tmpArray = arr[:]  # 复制数组
    mergeSort(arr, 0, len(arr) - 1, tmpArray)
    
    
if __name__ == '__main__':
    arr = [6,3,8,5,2,9,4,0]
    MergeSort(arr)
    print(arr)

结果：

1
[0, 2, 3, 4, 5, 6, 8, 9]

2.11 堆排序

原理说明：

heapSort

程序如下：

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
import numpy as np

def heapIfy(arr, start, end):
    if start > end:
        return - np.inf

    A = heapIfy(arr, 2 * start + 1, end)    # 得到左节点数据
    B = heapIfy(arr, 2 * start + 2, end)    # 得到右节点数据

    if arr[start] < A:     # 比左儿子小，交换
        temp = arr[start]
        arr[start] = arr[2 * start + 1]
        arr[2 * start + 1] = temp

    if arr[start] < B:     # 比右儿子小，交换
        temp = arr[start]
        arr[start] = arr[2 * start + 2]
        arr[2 * start + 2] = temp

    return arr[start]


def heapSort(arr):
    n = len(arr)
    for i in range(n):
        heapIfy(arr, 0, n - i - 1)

        temp = arr[0]
        arr[0] = arr[n - i - 1]
        arr[n - i - 1] = temp

    print(arr)


if __name__ == "__main__":
    arr = [4, 1, 5, 2, 7, 5, 3, 9, 4, 9, 3, 6, 3]
    heapSort(arr)

输出结果：

1
[1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 9, 9]
-------------本文结束感谢您的阅读-------------
0%