排序算法_需要对无序数组

1.插入排序

(1)插入排序算法

• 时间复杂度为O(n^2)
• 空间复杂度为O(1)
• 是稳定的排序方法

思想：

• 数组内部的操作，选择的元素不断插入前面已经排好序的有序元素中。

def insert(L):
    for i in range(len(L)):
        for j in range(i,0,-1):
            if L[j]<L[j-1]:
                L[j-1],L[j]=L[j],L[j-1]
        print(L)
    return L
1
2
3
4
5
6
7

(2).折半插入排序

思想：

1. 分别指向数列的第一位和末位，下标为low和high
2. m = (low + high)/2
3. 如果要插入的数小于m位置的数，说明要在低半区查找，high = m - 1
4. 如果要插入的数大于m位置的数，说明要在高半区查找，low = m + 1
5. 如果要插入的数等于m位置的数，直接退出，high=m
6. 当low > high时，停止查找
7. 插入的位置为high+1

在有序数组中插入一个元素

def binaryinsert_a(l,a):
    low = 0
    high = len(l) - 1
    mid = (low + high) // 2
    while low <= high:
        if l[mid] > a:
            high = mid - 1
        elif l[mid] < a:
            low = mid + 1
        else:
            high = mid
        mid = (low + high) // 2
    l.insert(high + 1, a)
    return l
1
2
3
4
5
6
7
8
9
10
11
12
13
14

无序数组的排序

def binaryinsert(l,a):
    for i in range(len(l)):
        low=0
        high=len(a)-1
        mid=(low+high)//2
        while low<=high:
            if a[mid]>l[i]:
                high=mid-1
            elif a[mid]<l[i]:
                low=mid+1
            else:
                high=mid
            mid=(low+high)//2
        a.insert(high+1,l[i])
    return a
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

l=[3,1,2,5,6,7,9,4]
a=[]
a=binaryinsert(l,a)
a_1=binaryinsert_a(sorted(l),8)
print(a)
print(a_1)
1
2
3
4
5
6
7

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

(3).希尔排序

传送门

希尔排序的思想建立在插入排序的想法上，加了一个想法就是加上按列排序。

• 时间复杂度为O(n^2)
• 空间复杂度为O(1)
• 是不稳定的排序方法

def shell_sort(L):
    shell=len(l)//2
    while shell>=1:
        for i in range(shell,len(L)):
            j=i
            while j-shell>=0:
                if L[j] < L[j - shell]:
                    L[j - shell], L[j] = L[j], L[j - shell]
                j=j-shell
        shell=shell//2
    return L
1
2
3
4
5
6
7
8
9
10
11

l=[3,1,2,5,6,7,9,4]
shell=shell_sort(l)
print(shell)
1
2
3

[1, 2, 3, 4, 5, 6, 7, 9]

2.交换类算法

(1).冒泡排序

• 每遍历一次就确定一个元素
• 每比较一次就是两两互换

def bubble_sort(s):
    for i in range(len(s)-1):
        for j in range(len(s)-i-1):
            if s[j]>s[j+1]:
                s[j+1],s[j]=s[j],s[j+1]
    return s
l=[3,1,2,5,6,7,9,4]
bubble=bubble_sort(l)
print(bubble)
1
2
3
4
5
6
7
8
9

(2).快速排序

思想：

• 定一个基准
• 比基准大的放在右边，比基准小的放在左边
• 从左边和右边中分别做前面两个操作直到长度为2返回，使用递归完成

def quick_sort(data):
    """quick_sort"""
    if len(data) >= 2:
        mid = data[0]
        left,right = [], []
        data.remove(mid)
        for num in data:
            if num >= mid:
                right.append(num)
            else:
                left.append(num)
        return quick_sort(left) + [mid] + quick_sort(right)
    else:
        return data
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.选择排序

(1).直接选择排序

• 每一次从候选元素中选择出一个最小/大的值，直接插入该元素所在位置，交换元素

def select_sort(l):
    for i in range(len(l)):
        min=l[i]
        min_index=i
        for j in range(i,len(l)):
            if l[j]<min:
                min_index=j
                min=l[j]
        l[i],l[min_index]=l[min_index], l[i]
    return l
1
2
3
4
5
6
7
8
9
10

(2).堆排序

传送门来啦
写的超级好
大根堆：每个结点的值都大于或等于左右子结点
小根堆：每个结点的值都小于或等于左右子结点

• 时间复杂度：O(nlogn)
• 空间复杂度： 因为堆排序是就地排序，空间复杂度为常数：O(1)

通常堆是通过一维数组来实现的。在阵列起始位置为0的情况中：

• 父节点i的左子节点在位置(2*i+1);
• 父节点i的右子节点在位置(2*i+2);
• 子节点i的父节点在位置(i-1)//2;
  堆的操作过程：

1. 大根堆调整(max_heapify)：
   将堆的末端子节点作调整，使得子节点永远小于父节点。这是核心步骤，在建堆和堆排序都会用到。比较i的根节点和与其所对应i的孩子节点的值，当i根节点的值比左孩子节点的值要小的时候，就把i根节点和左孩子节点所对应的值交换，同理，就把i根节点和右孩子节点所对应的值交换。然后再调用堆调整这个过程，可见这是一个递归的过程。

def max_heapify(heap,heapSize,root):  # 调整列表中的元素并保证以root为根的堆是一个大根堆
    '''
    给定某个节点的下标root，这个节点的父节点、左子节点、右子节点的下标都可以被计算出来。
    父节点：(root-1)//2
    左子节点：2*root + 1
    右子节点：2*root + 2  即：左子节点 + 1
    '''
    left = 2*root + 1
    right = left + 1
    larger = root
    if left < heapSize and heap[larger] < heap[left]:
        larger = left
    if right < heapSize and heap[larger] < heap[right]:
        larger = right
    if larger != root:  # 如果做了堆调整则larger的值等于左节点或者右节点的值，这个时候做堆调整操作
        heap[larger], heap[root] = heap[root], heap[larger]
        # 递归的对子树做调整
        max_heapify(heap, heapSize, larger)

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

2. 建立大根堆(build_max_heap)：
   将堆中所有的数据重新排序。建堆的过程其实就是不断做大根堆调整的过程，从(heapSize-2)//2处开始调整，一直调整到第一个根节点。

def build_max_heap(heap):  # 构造一个堆，将堆中所有数据重新排序
    heapSize = len(heap)
    for i in range((heapSize -2)//2,-1,-1):  # 自底向上建堆
        max_heapify(heap, heapSize, i)

1
2
3
4
5

3. 堆排序(heap_sort)：
   将根节点取出与最后一位做对调，并做最大堆调整的递归运算。堆排序是利用建堆和堆调整来进行的。
   首先建堆，然后将堆的根节点选出与最后一个节点进行交换，然后将前面len(heap)-1个节点继续做堆调整，直到将所有的节点取出，对于有n个元素的一维数组我们只需要做n-1次操作。

import random

def heap_sort(heap):  # 将根节点取出与最后一位做对调，对前面len-1个节点继续进行堆调整过程。
    build_max_heap(heap)
    # 调整后列表的第一个元素就是这个列表中最大的元素，将其与最后一个元素交换，然后将剩余的列表再递归的调整为最大堆
    for i in range(len(heap)-1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        max_heapify(heap, i, 0)

# 测试
if __name__ == '__main__':
    a = [30, 50, 57, 77, 62, 78, 94, 80, 84]
    print(a)
    heap_sort(a)
    print(a)
    b = [random.randint(1,1000) for i in range(1000)]
    print(b)
    heap_sort(b)
    print(b)

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

我是小小搬运工~~

3.归并排序

• 最优时间复杂度：O(nlongn)
• 最坏时间复杂度 ：O(nlongn)
• 稳定性：稳定

归并排序思想：（合-分-合)

1. 将一个序列从中间位置分成两个序列；
2. . 在将这两个子序列按照第一步继续二分下去；
3. 直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。

def merge_sort(lists):
    '''
    递归进行归并排序。
    '''
    # 递归结束条件
    if len(lists) <= 1:
        return lists
########合-分#########
    # 分治进行递归
    middle = len(lists) // 2
    left = merge_sort(lists[:middle])
    right = merge_sort(lists[middle:])
########分-合########
    # 将两个有序数组进行合并
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        # 将较小值放入到result中
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # 将未被扫描到的直接追加到result后面
    if i == len(left):
        result.extend(right[j:])
    else:
        result.extend(left[i:])
    return result
if __name__ == '__main__':
    a = [2, 6, 10, 3, 5, 8, 4]
    print(merge_sort(a))

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

基数排序

太简单易懂了

(1).基数排序

根据位数排序：
需要10个桶，分别是从0-9：

1. 先是按照个位数大小把元素有序的装进桶中
2. 从0-9个桶，一次收集数据
3. 先是按照十位数大小把元素有序的装进桶中
4. 重复过程

def RadixSort(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]
    RadixSort(a)
    print(a)
 

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

(2).多关键字排序

• 多关键字排序就是根据多个关键字的重要性排序。
• 在python排序时需要利用sort和sorted两个内置函数完成。

sort()方法

• 直接改变数组的值
• 返回None
• reverse：True，False（默认升序）

sorted()方法

• 返回为排序后的数组
• reverse：True，False（默认升序）
• 利用key进行多关键字排序

单关键字排序

l=[2,1,3,5,4,8,7,9]
l.sort(reverse=True)
l2=sorted(l,reverse=True)
print(l)
print(l2)
1
2
3
4
5

多关键字排序

students = [
            ('john', 'A', 18),
            ('jane', 'B', 19),
            ('dave', 'B', 17)
            ]
print(sorted(students, key=lambda s: s[0]))
 
[('dave', 'B', 17), ('jane', 'B', 19), ('john', 'A', 18)]
1
2
3
4
5
6
7
8

L = [
    ('摩洛哥', 2, 2, 0, 1),
    ('葡萄牙', 5, 4, 1, 5),
    ('西班牙', 6, 5, 1, 5),
    ('伊朗', 2, 2, 0, 4)
]
L = sorted(L, key=lambda t: t[1],reverse=True) # 积分数
print(L)
L = sorted(L, key=lambda t: t[3], reverse=True) # 净胜球数
print(L)
L = sorted(L, key=lambda t: t[4], reverse=True) # 进球数
print(L)
 
 
 
[('西班牙', 6, 5, 1, 5), ('葡萄牙', 5, 4, 1, 5), ('摩洛哥', 2, 2, 0, 1), ('伊朗', 2, 2, 0, 4)]
[('西班牙', 6, 5, 1, 5), ('葡萄牙', 5, 4, 1, 5), ('摩洛哥', 2, 2, 0, 1), ('伊朗', 2, 2, 0, 4)]
[('西班牙', 6, 5, 1, 5), ('葡萄牙', 5, 4, 1, 5), ('伊朗', 2, 2, 0, 4), ('摩洛哥', 2, 2, 0, 1)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

两个关键字排序：正序

arr=[(1,4,3),(1,3,3),(2,1,4),(3,5,1)]

arr.sort(key=lambda s:(s[0],s[1])) #两个关键字排序
print(arr) # 可以看到输出结果是根据列表中元组的第一项和第二项排序

1
2
3
4
5

第一个关键字正序，第二个关键字倒序

arr=[(1,4,3),(1,3,3),(2,1,4),(3,5,1)]

arr.sort(key=lambda s:(s[0],-s[1])) #两个关键字排序,在需要倒序排列的关键字前加`-`号
print(arr) 

1
2
3
4
5