python学习之几种经典排序算法

一、一些比较常用的方法

一、列表
1、li.append() #添加元素到末尾，返回none
2、li.clear() #一个比较危险的方法(QAQ)
3、li.copy() #复制 不是同一个对象（内存地址不一样）
4、li.count() #计算列表里的元素出现的次数
5、li.extend([]) #可迭代的参数
6、li.index() #默认返回元素第一次出现的位置，可以添加查找范围
7、liinsert() #指定索引插入元素
8、li.pop() #默认删除最后一个元素，可以指定索引删除
9、li.remove() #指定删除
10、li.reverse() #反向列表元素
11、li.sort() #默认ASCII码排序，按照首字母大小排序
按长度排序
li.sort(key=len) 由短到长
li.sort(key=len,reverse=True) 由长到短
归纳总结
与增加元素有关的方法
1、li.append #添加元素到末尾，返回none
2、li.extend([]) #可迭代的参数
3、liinsert() #指定索引插入元素
与减少元素有关的方法
1、li.clear() #一个比较危险的方法(QAQ)
2、li.pop() #默认删除最后一个元素，可以指定索引删除
3、li.remove() #指定删除
与查找，统计，调整列表有关的方法
1、li.count() #计算列表里的元素出现的次数
2、li.index() #默认返回元素第一次出现的位置，可以添加查找范围
3、li.reverse() #反向列表元素
4、li.sort() #默认ASCII码排序，按照首字母大小排序
5、li.copy() #复制 不是同一个对象（内存地址不一样）

二、二分查找以及几种经典的排序算法

二分查找

二分查找只适用于排好序的列表，对于无序列表不适用，可以先进行排序再进行查找，（当然如果需要的话）

def binary_search(li, val):
    left = 0
    right = len(li) - 1
    while left <= right:
        mid = (left + right) // 2
        if li[mid] == val:
            return mid
        elif li[mid] < val:
            left = mid + 1
        else:
            right = mid - 1
    else:
        return None


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

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

在这些排序中，冒泡排序、选择排序、插入排序相对来说就比较low，通常时间复杂度比较高；相比而言，堆排序、归并排序、快速排序的时间复杂都就比较小，而且这三种也比较常用；当然还有几种排序算法，比如桶排序、希尔排序、计数排序、基数排序，这四种一般都不是很常用；
对于常见的六种排序算法来说，冒泡排序、归并排序、插入排序是比较稳定的，其他三种都不太稳定（这里的稳定性判定是由是否跳跃式的排序来判断）

冒泡排序

import random


def bubble_sort(li):
    for i in range(len(li) - 1):
        exchange = False
        for j in range(len(li) - 1 - i):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
                exchange = True
        print(li)
        if not exchange:
            return


li = [random.randint(0, 100) for i in range(10)]
print(li)
bubble_sort(li)

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

选择排序

def select_sort(li):
    for i in range(len(li) - 1):
        min_loc = i
        for j in range(i + 1, len(li)):
            if li[j] < li[min_loc]:
                min_loc = j
        li[i], li[min_loc] = li[min_loc], li[i]


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

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

快速排序

def partition(li, left, right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] > tmp:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] < tmp:
            left += 1
        li[right] = li[left]
    li[left] = tmp
    return left


def quick_sort(li, left, right):
    if left < right:
        mid = partition(li, left, right)
        quick_sort(li, left, mid - 1)
        quick_sort(li, mid + 1, right)
        print(li)


li = [5, 3, 9, 8, 6, 2, 7, 4, 1]
print(li)
quick_sort(li, 0, len(li) - 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

堆排序

def sift(li, low, high):
    i = low
    j = 2 * i + 1
    tmp = li[low]
    while j <= high:
        if j + 1 <= high and li[j + 1] > li[j]:
            j = j + 1
        if tmp < li[j]:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            li[i] = tmp
            break
    else:
        li[i] = tmp


def heap_sort(li):
    n = len(li)
    for i in range((n - 2) // 2, -1, -1):
        sift(li, i, n - 1)
    for i in range(n - 1, -1, -1):
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i - 1)


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

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

有关堆排序的topk问题

import random

from 算法.sift import sift


def topk(li, k):
    heap = li[0:k]
    for i in range((k - 2) // 2, -1, -1):
        sift(heap, i, k - 1)
    for i in range(k, len(li) - 1):
        if li[i] > heap[0]:
            heap[0] = li[i]
            sift(heap, 0, k - 1)
    for i in range(k - 1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        sift(heap, 0, i - 1)
    return heap


li = list(range(100))
random.shuffle(li)
print(li)
print(topk(li, 10))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

归并排序

def merge(li, low, mid, high):
    i = low
    j = mid + 1
    ltmp = []
    while i <= mid and j <= high:
        if li[i] < li[j]:
            ltmp.append(li[i])
            i += 1
        else:
            ltmp.append(li[j])
            j += 1
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high + 1] = ltmp


def merge_sort(li, low, high):
    if low < high:
        mid = (low + high) // 2
        merge_sort(li, low, mid)
        merge_sort(li, mid + 1, high)
        merge(li, low, mid, high)


li = list(range(1000))
import random

random.shuffle(li)
print(li)
merge_sort(li, 0, len(li) - 1)
print(li)

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