数据结构与算法之排序算法_数据结构与算法排序算法

编程内功心法（Python描述）

排序算法（6个经典排序算法）

1. 快速排序（QuickSort）

import random
1

def quick_sort(list_, start, end):
    if start >= end:
        return
    
    low = start
    height = end
    
    mid = list_[low] # 让最左边的值为中间值，并且赋值给mid变量保存其值
    while low < height:
        ##### 从右到左，找到右边第一个小于mid 的元素位置###########
        while list_[height] >= mid and low < height:
            height -= 1

        if low < height:
            list_[low] = list_[height] # 把右边小于mid 的数放到左边
        else:
            list_[low] = mid # 走到此说明已经找到中间值应该在的位置

        ##### 从左到右，找到左边一个大于mid 的元素位置#######
        while list_[low] <= mid and low < height:
            low += 1

        if low < height:
            list_[height] = list_[low] # 把大于mid的值放到最右边
        else:
            list_[low] = mid # 走到此说明已经找到中间值应该在的位置
        
    # 按照mid 的位置，将列表一分为二，递归快速排序, 此时low == height
    quick_sort(list_, start, low-1) # 左边
    quick_sort(list_, height+1, end) # 右边
      
        
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

li = [random.randint(0,100) for i in range(10)]
print("排序之前：",li)
quick_sort(li, 0, len(li)-1)
print("快速排序之后：", li)
1
2
3
4

排序之前： [82, 2, 68, 13, 78, 97, 65, 61, 61, 50]
快速排序之后： [2, 13, 50, 61, 61, 65, 68, 78, 82, 97]
1
2

2. 归并排序(MergeSort)

# 先定义一个合并两个有序列表成一个有序列表的函数
def merge(left, right):
    l = 0
    r = 0
    new_list = []
    
    while True:
        if left[l] <= right[r]:
            new_list.append(left[l])
            l += 1
        else:
            new_list.append(right[r])
            r += 1
        if l>= len(left) or r >= len(right):
            break
    
    new_list += left[l:]
    new_list += right[r:]
    return new_list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 先测试一下，merge函数
l1 = [1,3,6,50]
l2 = [2,8,20]
l3 = [23]
a = merge(l1, l2)
a = merge(a,l3)
print(a)
1
2
3
4
5
6
7

[1, 2, 3, 6, 8, 20, 23, 50]
1

# 现在写归并排序函数
def merge_sort(list_):
    n = len(list_)
    # 如果拆分的列表的长度等于1，说明已经有序，递归结束，返回拆分后的列表
    if n <=1 :
        return list_
    
    # 列表一分为二
    l = n // 2
    left = list_[:l]
    right = list_[l:]
    # 递归拆分
    left = merge_sort(left)
    right = merge_sort(right)
    
    # 合并列表。经过上面的递归，函数走到此，说明列表拆分完成，进行合并
    return merge(left, right)
    
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 测试
import random
li = [random.randint(0,100) for i in range(10)]
a = merge_sort(li)
print("排序前：", li)
print('归并排序后：', a)

1
2
3
4
5
6
7

排序前： [93, 3, 15, 99, 26, 69, 72, 94, 60, 27]
归并排序后： [3, 15, 26, 27, 60, 69, 72, 93, 94, 99]
1
2

3. 插入排序(InsertionSort)

def insertion_sort(list_):
    n = len(list_)
    for i in range(1, n): # 0下标时，只有一个元素，所以是有序的，所以从1开始遍历
        for j in range(i, 0, -1): # for循环左闭右开，不包含0
            if list_[j] < list_[j-1]: # 当j==1时,j-1恰好为0
                list_[j], list_[j-1] = list_[j-1], list_[j]
            else:
                break # 提前退出遍历，因为前面的元素已经有序

1
2
3
4
5
6
7
8
9

import random
li = [random.randint(0, 100) for i in range(10)]
print("排序前：", li)
insertion_sort(li)
print("插入排序后：", li)
1
2
3
4
5

排序前： [65, 91, 49, 54, 84, 50, 32, 39, 68, 4]
插入排序后： [4, 32, 39, 49, 50, 54, 65, 68, 84, 91]
1
2

4.希尔排序（ShellSort 插入排序的优化）

def shell_sort(list_):
    n = len(list_)
    step = n // 2 # 初始步长
    
    while step >=1:
        
        for i in range(step, n):
            # for循环是左闭右开，为了i==step时能取step值，所以右边设置为step-1，同时避免下标为负数的情况
            for j in range(i, step-1, -step): 
                if list_[j] < list_[j-step]:
                    list_[j] , list_[j-step] = list_[j-step], list_[j]
                else:
                    break
                    
        step = step // 2

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

# 测试
import random
li = [random.randint(0,100) for i in range(10)]
print("排序前：", li)
shell_sort(li)
print("希尔排序后：", li)
1
2
3
4
5
6

排序前： [86, 93, 25, 36, 34, 79, 62, 59, 43, 34]
希尔排序后： [25, 34, 34, 36, 43, 59, 62, 79, 86, 93]
1
2

5. 选择排序（SelectionSort）

def selection_sort(list_):
    n = len(list_)
    for i in range(n-1):
        min_index = i
        for j in range(i, n):
            if list_[j] < list_[min_index]:
                min_index = j
        if min_index != i:  
        	list_[i], list_[min_index] = list_[min_index], list_[i]
    
1
2
3
4
5
6
7
8
9
10

# 测试
import random
li = [random.randint(0, 100) for i in range(10)]
print("排序前：", li)
selection_sort(li)
print("选择排序后：", li)
1
2
3
4
5
6

排序前： [87, 78, 89, 1, 20, 50, 12, 100, 6, 65]
选择排序后： [1, 6, 12, 20, 50, 65, 78, 87, 89, 100]
1
2

6. 冒泡排序（BubbleSort）

def bubble_sort(list_):
    n = len(list_)
    for i in range(n-1):
        is_sorted = True
        for j in range(n-1-i):
            if list_[j] > list_[j+1]:
                list_[j], list_[j+1] = list_[j+1], list_[j]
                is_sorted = False
        if is_sorted:
            break
        
1
2
3
4
5
6
7
8
9
10
11

# 测试
import random
li = [random.randint(0,100) for i in range(10)]
print("排序前：", li)
bubble_sort(li)
print("冒泡排序后：",li)
1
2
3
4
5
6

排序前： [85, 64, 12, 7, 34, 88, 16, 24, 50, 33]
冒泡排序后： [7, 12, 16, 24, 33, 34, 50, 64, 85, 88]
1
2