冒泡排序

  冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
  它的时间复杂度是O(N*N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
data_set = [9, 1, 22, 31, 45, 3, 6, 2, 11]
data_len = len(data_set)
print('before sort: ', data_set)

loop_count = 0
for i in range(data_len):
    for j in range(data_len - i - 1):
        if data_set[j] > data_set[j+1]:
            data_set[j], data_set[j+1] = data_set[j+1],data_set[j]
        loop_count += 1
    print(data_set)

# 排序后
print('after sort:', data_set)
print('loop count:', loop_count)

上述代码的执行结果为：

1
2
3
4
5
6
7
8
9
10
11
12
before sort:  [9, 1, 22, 31, 45, 3, 6, 2, 11]
[1, 9, 22, 31, 3, 6, 2, 11, 45]
[1, 9, 22, 3, 6, 2, 11, 31, 45]
[1, 9, 3, 6, 2, 11, 22, 31, 45]
[1, 3, 6, 2, 9, 11, 22, 31, 45]
[1, 3, 2, 6, 9, 11, 22, 31, 45]
[1, 2, 3, 6, 9, 11, 22, 31, 45]
[1, 2, 3, 6, 9, 11, 22, 31, 45]
[1, 2, 3, 6, 9, 11, 22, 31, 45]
[1, 2, 3, 6, 9, 11, 22, 31, 45]
after sort: [1, 2, 3, 6, 9, 11, 22, 31, 45]
loop count: 36

选择排序

  首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此递归。
  它的时间复杂度是O(N*N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
data_set = [2, 23, 12, 4, 3, 7, 12, 34, 4, 1, 3, 12, 2, 456, 67, 43, 2, 1]
data_len = len(data_set)
print('before sort: ', data_set)

smallest_num_index = 0  # 初始化最小元素位置为0
loop_count = 0  # 计算循环次数
for i in range(data_len):
    smallest_num_index = i
    for j in range(i, data_len):
        if data_set[j] < data_set[smallest_num_index]:
            smallest_num_index = j
            loop_count += 1
    else:
        if smallest_num_index != i:
            data_set[i], data_set[smallest_num_index] = data_set[smallest_num_index], data_set[i]
        print(data_set)
 
# 排序后
print('after sort:', data_set)
print('loop count:', loop_count)

上述代码的执行结果为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
before sort:  [2, 23, 12, 4, 3, 7, 12, 34, 4, 1, 3, 12, 2, 456, 67, 43, 2, 1]
[1, 23, 12, 4, 3, 7, 12, 34, 4, 2, 3, 12, 2, 456, 67, 43, 2, 1]
[1, 1, 12, 4, 3, 7, 12, 34, 4, 2, 3, 12, 2, 456, 67, 43, 2, 23]
[1, 1, 2, 4, 3, 7, 12, 34, 4, 12, 3, 12, 2, 456, 67, 43, 2, 23]
[1, 1, 2, 2, 3, 7, 12, 34, 4, 12, 3, 12, 4, 456, 67, 43, 2, 23]
[1, 1, 2, 2, 2, 7, 12, 34, 4, 12, 3, 12, 4, 456, 67, 43, 3, 23]
[1, 1, 2, 2, 2, 3, 12, 34, 4, 12, 7, 12, 4, 456, 67, 43, 3, 23]
[1, 1, 2, 2, 2, 3, 3, 34, 4, 12, 7, 12, 4, 456, 67, 43, 12, 23]
[1, 1, 2, 2, 2, 3, 3, 4, 34, 12, 7, 12, 4, 456, 67, 43, 12, 23]
[1, 1, 2, 2, 2, 3, 3, 4, 4, 12, 7, 12, 34, 456, 67, 43, 12, 23]
[1, 1, 2, 2, 2, 3, 3, 4, 4, 7, 12, 12, 34, 456, 67, 43, 12, 23]
[1, 1, 2, 2, 2, 3, 3, 4, 4, 7, 12, 12, 34, 456, 67, 43, 12, 23]
[1, 1, 2, 2, 2, 3, 3, 4, 4, 7, 12, 12, 34, 456, 67, 43, 12, 23]
[1, 1, 2, 2, 2, 3, 3, 4, 4, 7, 12, 12, 12, 456, 67, 43, 34, 23]
[1, 1, 2, 2, 2, 3, 3, 4, 4, 7, 12, 12, 12, 23, 67, 43, 34, 456]
[1, 1, 2, 2, 2, 3, 3, 4, 4, 7, 12, 12, 12, 23, 34, 43, 67, 456]
[1, 1, 2, 2, 2, 3, 3, 4, 4, 7, 12, 12, 12, 23, 34, 43, 67, 456]
[1, 1, 2, 2, 2, 3, 3, 4, 4, 7, 12, 12, 12, 23, 34, 43, 67, 456]
[1, 1, 2, 2, 2, 3, 3, 4, 4, 7, 12, 12, 12, 23, 34, 43, 67, 456]
after sort: [1, 1, 2, 2, 2, 3, 3, 4, 4, 7, 12, 12, 12, 23, 34, 43, 67, 456]
loop count: 28

插入排序

  基本思想： 将列表分为2部分，左边为排序好的部分，右边为未排序的部分，循环整个列表，每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
  操作： 起初，默认第一个元素已经排序完成，然后从第二个元素开始，逐一取出元素，在已经排序的元素序列中从后向前扫描，放到适当的位置
  它的时间复杂度是O(N*N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
data_set = [9, 1, 22, 31, 45, 3, 6, 2, 11]
data_len = len(data_set)
print('before sort: ', data_set)

loop_count = 0
for index in range(1, data_len):
    current_val = data_set[index] #先记下来每次大循环走到的第几个元素的值
    position = index
    while data_set[position - 1] > current_val:
        data_set[position] = data_set[position - 1]
        position -= 1
        loop_count += 1
    data_set[position] = current_val
    print(data_set)
  
# 排序后
print('after sort:', data_set)
print('loop count:', loop_count)

1
2
3
4
5
6
7
8
9
10
11
before sort:  [9, 1, 22, 31, 45, 3, 6, 2, 11]
[1, 9, 22, 31, 45, 3, 6, 2, 11]
[1, 9, 22, 31, 45, 3, 6, 2, 11]
[1, 9, 22, 31, 45, 3, 6, 2, 11]
[1, 9, 22, 31, 45, 3, 6, 2, 11]
[1, 3, 9, 22, 31, 45, 6, 2, 11]
[1, 3, 6, 9, 22, 31, 45, 2, 11]
[1, 2, 3, 6, 9, 22, 31, 45, 11]
[1, 2, 3, 6, 9, 11, 22, 31, 45]
after sort: [1, 2, 3, 6, 9, 11, 22, 31, 45]
loop count: 18

快速排序

  设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动
  它的时间复杂度是O(N*log2(N))

  注：在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生改变，则称这种排序方法是不稳定的。
要注意的是，排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。

演示快速排序

假设用户输入了如下数组：
下标 | 0 | 1 | 2 | 3 | 4 | 5
数据 | 6 | 2 | 7 | 3 | 8 | 9

创建变量i=0（指向第一个数据）, j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。
我们要把所有比k小的数移动到k的左面，所以我们可以开始寻找比6小的数，从j开始，从右往左找，不断递减变量j的值，我们找到第一个下标3的数据比6小，于是把数据3移到下标0的位置，把下标0的数据6移到下标3，完成第一次比较：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 数据 | 3 | 2 | 7 | 6 | 8 | 9 |
这时候i=0 j=3 k=6
接着，开始第二次比较，这次要变成找比k大的了，而且要从前往后找了。递加变量i，发现下标2的数据是第一个比k大的，于是用下标2的数据7和j指向的下标3的数据的6做交换，数据状态变成下表：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 数据 | 3 | 2 | 6 | 7 | 8 | 9 |

这时候i=2 j=3 k=6
称上面两次比较为一个循环。
接着，再递减变量j，不断重复进行上面的循环比较，直到i和j碰头。
在本例中，我们进行一次循环，就发现i和j“碰头”了：他们都指向了下标2。于是，第一遍比较结束。得到结果如下，凡是k(=6)左边的数都比它小，凡是k右边的数都比它大：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 数据 | 3 | 2 | 6 | 7 | 8 | 9 |

如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。
然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止。

注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。

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
def quick_sort(array, left_index, right_index):
    """
    array: 待排序列表
    left_index: 列表的第一个索引
    right_index: 列表的最后一个索引
    return: 
    """
    
    if left_index >= right_index:
        return
    
    low = left_index
    high = right_index
    key_value = array[low]  # 将关键字设为列表的第一个值
    
    while low < high:  #只要左右未遇见
        while low < high and array[high] > key_value:  # 找到列表右边比key小的值 为止
            high -= 1
        # 此时直接把 key_value(array[low]) 跟比它小的array[high]进行交换
        array[low] = array[high]
        array[high] = key_value
        
        # 找到key左边比key大的值，这里为何是<=而不是<。
        # 因为<的话，如果array[low] == key就会陷入死循环，
        # 解决办法是这里写<,那上面的while循环应该写array[high] >= key_value
        while low < high and array[low] <= key_value:
            low += 1
        # 找到了左边比 key_value 大的值,
        # 把array[high](此时应该刚存成了 key_value) 跟这个比 key_value 大的array[low]进行调换
        array[high] = array[low]
        array[low] = key_value        

    quick_sort(array, left_index, low-1)  #最后用同样的方式对分出来的左边的小组进行同上的做法
    quick_sort(array, low+1, right_index)  #用同样的方式对分出来的右边的小组进行同上的做法


if __name__ == '__main__':
    array = [96,14,10,9,6,99,16,5,1,3,2,4,1,13,26,18,2,45,34,23,1,7,3,22,19,2]
    #array = [8,4,1, 14, 6, 2, 3, 9,5, 13, 7,1, 8,10, 12]
    print("before sort:", array)
    quick_sort(array, 0, len(array)-1)
    print("after sort:", array)