排序算法（python实现）

排序算法

• 排序算法（英语：Sorting algorithm）是一种能将一串数据依照特定顺序进行排列的一种算法。

排序算法的稳定性：

• 稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。

1.冒泡排序

算法介绍

• 冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
• 冒泡排序运作原理：

1. 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法实现

# -*- coding:utf-8 -*-
import copy
def bubble_sort(lst):
    """冒泡排序"""
    # count = 0
    lst1 = copy.deepcopy(lst)
    n = len(lst1)
    for i in range(1, n):
        print(f"第{i}趟")
        for j in range(1, n - i + 1):
            if lst1[j - 1] > lst1[j]:
                lst1[j - 1], lst1[j] = lst1[j], lst1[j - 1]
            print(f"第{j}次：{lst1}")
    return lst1
if __name__ == '__main__':
    a = [1, 2, 5, 1, 6, 3, 10, 7, 9, 8]
    result = bubble_sort(a)
    print(a)
    print(result)

代码运行结果：

算法演示图

算法时间复杂度

• 最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束）；
• 最坏时间复杂度：O(n2)；
• 稳定性：稳定。

2.选择排序

算法介绍

• 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

• 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

算法实现

# -*- coding:utf-8 -*-
import copy
def selection_sort(lst):
    lst1 = copy.deepcopy(lst)
    n = len(lst1)
    for i in range(n - 1):
        min_idx = i
        print(f"第{i + 1}趟")
        count = 0
        for j in range(i + 1, n):
            count += 1
            if lst1[min_idx] > lst1[j]:
                min_idx = j
            print(f"第{count}次：{lst1}")
        if min_idx != i:
            lst1[i], lst1[min_idx] = lst1[min_idx], lst1[i]
    return lst1
if __name__ == '__main__':
    a = [54, 226, 77, 31, 55, 20]
    b = selection_sort(a)
    print(a)
    print(b)

代码运行结果：

算法演示图

算法时间复杂度

• 最优时间复杂度：O(n2)；
• 最坏时间复杂度：O(n2)；
• 稳定性：不稳定（考虑升序每次选择最大的情况）。

3.插入排序

算法介绍

• 插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法实现

# -*- coding:utf-8 -*-
"""排序步骤：
a = [54, 226, 93, 17, 77, 31, 44, 55, 20]
已排序：                                未排序：
54                                      226, 93, 17, 77, 31, 44, 55, 20
54, 226                                 93, 17, 77, 31, 44, 55, 20
54, 93, 226                             17, 77, 31, 44, 55, 20
17，54, 93, 226                         77, 31, 44, 55, 20
17，54, 77, 93, 226                     31, 44, 55, 20   i=5 j=0, 1, 2, 3, 4
17, 31，54, 77, 93, 226                 44, 55, 20
17, 31, 44，54, 77, 93, 226             55, 20
17, 31, 44，54, 55, 77, 93, 226         20
17, 20, 31, 44，54, 55, 77, 93, 226 
"""
import copy
def insertion_sort(lst):
    lst1 = copy.deepcopy(lst)
    n = len(lst1)
    for i in range(n):
        for j in range(i):
            if lst1[i] < lst1[j]:
                lst1[i], lst1[j] = lst1[j], lst1[i]
    return lst1
if __name__ == '__main__':
    a = [54, 226, 93, 17, 77, 31, 44, 55, 20]
    b = insertion_sort(a)
    print(b)

代码运行结果：

算法演示图

算法时间复杂度

• 最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）；
• 最坏时间复杂度：O(n2)；
• 稳定性：稳定。

4.快速排序

算法介绍

• 快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

步骤为：

1. 从数列中挑出一个元素，称为"基准"（pivot）；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

• 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

算法实现

# -*- coding:utf-8 -*-
""" 排序步骤：
a = [54, 226, 93, 17, 77, 31, 44, 55, 20]
第一趟：选取54 为基数
17， 31， 44， 20  54  226, 93, 77, 55
第二趟：选取17 226 为基数
17， 31， 44， 20  54 93, 77, 55，226
第三趟：选取31 93为基数
17， 20 ， 31, 44, 54, 55, 77, 93, 226
第四趟：选取20，44， 55为基数
17， 20 ， 31, 44, 54, 55, 77, 93, 226
第四趟：选取77为基数
17， 20 ， 31, 44, 54, 55, 77, 93, 226
"""
def quicksort(lst, base_num, end):
	# 知道基数的索引>最后的索引，递归退出
    if base_num > end:
        return
    for i in range(base_num, end):
    	# 通过基数的索引将lst 分成两部分，大的放在基数右边，小的放在基数左边
        if lst[base_num] > lst[i]:
            a = lst[i]
            lst.pop(i)
            lst.insert(base_num, a)
            base_num += 1
    # 基数左边的子序列进行快速排序
    quicksort(lst, 0, base_num - 1)
    # 基数右边的子序列进行快速排序
    quicksort(lst, base_num + 1, end)
if __name__ == '__main__':
    a = [54, 226, 93, 17, 77, 31, 44, 55, 20]
    quicksort(a, 0, len(a))
    print(a)

代码运行结果：

算法时间复杂度

• 最优时间复杂度：O(nlogn)；
• 最坏时间复杂度：O(n2)；
• 稳定性：不稳定。

5.希尔排序

算法介绍

• 希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序过程

希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样(竖着的元素是步长组成)：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了，然后再以3为步长进行排序：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步长进行排序（此时就是简单的插入排序了）

算法实现

# -*- coding:utf-8 -*-
import copy
"""
a = [54, 26, 93, 17, 77, 31, 44, 55, 20]
第一轮：步长4
54, 26, 93, 17     
77, 31, 44, 55    
20
插入排序：
20， 26， 44， 17    
54， 31， 93， 55    
77
第二轮：步长2
20， 26， 
44， 17    
54， 31， 
93， 55    
77
插入排序：
20, 17
44, 26
54, 31
77, 55
93
第三轮： 步长1
20, 17, 44, 26, 54, 31, 77, 55, 93
插入排序：
17，20, 26, 31, 44, 54, 55, 77, 93
"""
def shell_sort(lst, gap):
    if gap == 0:
        return
    n = len(lst)

    for i in range(gap, n):
        j = i
        # 插入排序
        while j >= gap and lst[j - gap] > lst[j]:
            lst[j - gap], lst[j] = lst[j], lst[j - gap]
            j -= gap
    gap = gap // 2
    shell_sort(lst, gap)
if __name__ == '__main__':
    a = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    gap = len(a) // 2
    shell_sort(a, gap)
    print(a)

算法演示图

算法时间复杂度

• 最优时间复杂度：根据步长序列的不同而不同；
• 最坏时间复杂度：O(n2)；
• 稳定想：不稳定。

6.归并排序

算法介绍

• 归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
• 将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

算法实现

def merge_sort(alist):
    if len(alist) <= 1:
        return alist
    # 二分分解
    num = len(alist)/2
    left = merge_sort(alist[:num])
    right = merge_sort(alist[num:])
    # 合并
    return merge(left,right)

def merge(left, right):
    '''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组'''
    #left与right的下标指针
    l, r = 0, 0
    result = []
    while l<len(left) and r<len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result
alist = [54,26,93,17,77,31,44,55,20]
sorted_alist = mergeSort(alist)
print(sorted_alist)

算法演示图

算法时间复杂度

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

总结

转载：https://blog.csdn.net/weixin_45459224/article/details/102573167