经典排序算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

'''前后两个对比，一次排出一个最值放在最后'''
def bubble_sort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
            else:
                continue
    return arr

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

'''每次循环选择剩余数组中的最小值，在左侧排列好'''
def select_sort(arr):
    for i in range(len(arr)):
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        if i != min_index:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

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

'''借用堆结构，利用大顶堆筛选出最值，弹出最值，递归剩余数组，不断弹出最值'''

def heapify(arr, n, i):
    large = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[large] < arr[left]:
        large = left
    if right < n and arr[large] < arr[right]:
        large = right
    if large != i:
        arr[i], arr[large] = arr[large], arr[i]
        heapify(arr, n, large)

def heap_sort(arr):
    n = len(arr)
    for i in range(n//2, -1, -1):        #从最后一个非根节点开始，由下到上，逐渐堆化
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)               #每次交换最大值和末尾值后，需要对0节点进行shiftdown操作，重新堆化
    return arr

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

'''右侧未排序的不断与已排序的左侧逐一比较，小于则已排序的往后移一位'''
def insert_sort(arr):
    for i in range(1,len(arr)):
        pre_index = i-1
        current = arr[i]  #记录当前值
        while pre_index >= 0 and arr[pre_index] > current:
            arr[pre_index+1] = arr[pre_index]  #这里直接用大数往后挪位，而不是采用交换（交换一次实际需要执行三次赋值操作），可以减少代码执行，提高效率
            pre_index -= 1
        arr[pre_index+1] = current
    return arr

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

'''分组采用插入排序，步长逐渐减小，为1时已经大部分有序，再经过最后一次插入排序；不稳定'''
def shell_sort(arr):
    gap = len(arr) // 2
    while gap > 0:
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i - gap
            while j >= 0 and arr[j] > temp:
                arr[j+gap] = arr[j]
                j -= gap
            arr[j+gap] = temp
        gap //= 2
    return arr

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

'''分而治之，迭代分组后，不同分组排序后归并，需要申请额外的存储空间'''
def merge_sort(arr):
    if len(arr)<2:
        return arr
    mid = len(arr) // 2 
    left, right = arr[:mid], arr[mid:]
    return merge(merge_sort(left), merge_sort(right))

def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

'''一、随机挑选一个基准，然后根据分大小区，迭代上述，把分区和基准连接在一起返回
      本质就是把每一个元素转换成轴点元素，数组就排好序了'''

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = [x for x in arr[1:] if x < pivot]
        right = [x for x in arr[1:] if x >= pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)

 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

'''二、在原数组上进行交换的写法'''
def quick_sort(arr):
    sort(0, len(arr)) #对[0,len(arr))范围内的数组进行排序

def sort(begin, end):
    if end-begin < 2:
        return
    mid = pivotIndex(begin, end)
    sort(begin, mid)
    sort(mid+1, end)

def pivotIndex(begin, end):
    pivot = arr[begin]  #以第一个元素为轴点
    end -= 1
    while begin < end:
        '''需要来回左右比较判断，可以用while嵌套'''
        while begin < end:
            if arr[end] > pivot:
                end -= 1
            else:
                arr[begin] = arr[end]
                begin += 1
                break
        while begin < end:
            if arr[begin] < pivot:
                begin += 1
            else:
                arr[end] = arr[begin]
                end -= 1
                break
    arr[begin] = pivot
    return begin 

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

'''针对有确定范围的整数数组，统计不同整数的个数存放在额外的存储空间，按整数大小排序'''
def count_sort(arr):
    bucket_len = max(arr) + 1
    bucket = [0] * bucket_len
    sort_index = 0
    for i in range(len(arr)):
        bucket[arr[i]] += 1
    for j in range(bucket_len):
        while bucket[j] > 0:
            arr[sort_index] = j
            sort_index += 1
            bucket[j] -= 1
    return arr

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

'''将数组分到顺序的桶内（划分范围）,对桶内数据排序后，合并在一起'''

def heap_sort(arr):
    min_num = min(arr)
    max_num = max(arr)
    bucket_range = (max_num - min_num) / len(arr)
    bucket_list = [[] for i in range(len(arr)+1)]
    for i in arr:
        bucket_list[int((i-min_num) // bucket_range)].append(i)
    arr.clear()
    for i in bucket_list:
        arr += sorted(i)
    return arr

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

'''针对比较集中的整数数组，分别根据不同位上的数分箱（0~9）,然后排序，递归上述步骤'''

def radix_sort(arr):
    i = 0
    n = 1
    max_num = max(arr)
    while max_num > 10 ** n:
        n += 1
    while i < n:
        bucket = {}
        for x in range(10):
            bucket.setdefault(x, [])
        for y in arr:
            radix = int(y / (10**i) % 10)
            bucket[radix].append(y)
        arr.clear()
        for j in range(10):
            if len(bucket[j]) != 0:
                arr += bucket[j]
        i += 1
    return arr