Python的常用排序算法实现

一、引言

        所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。——百度百科

        常见的排序算法(8种)有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

        由于最近经常用到排序算法，这里给出5中更常用的排序算法(选择排序、插入排序、冒泡排序、快速排序和归并排序)的实现方式，以防不便之需。这样，再次遇到排序问题的时候，我可以通过直接复习自己的代码来解决自己所遇到的问题，而不至于看网上代码、改来改去。毕竟，自己写出来的代码，自己理解起来更快。

        下列代码（没啥注释，想理解排序算法的不建议看）全部按照升序的方式进行排序。

二、选择排序

        选择排序最好、最坏、平均时间复杂度均为O(n^2)，空间复杂度为O(1)。

        代码

def insert_sort(data_list):
    for i in range(len(data_list)):
        j = i
        while j > 0:
            if data_list[j] < data_list[j-1]: // 交换，例如10 5 -> 5 10
                temp, data_list[j] = data_list[j], data_list[j-1]
                data_list[j-1] = temp
            else: 
                break
            j -= 1
data = [45, 123, 89, 1, -15]
insert_sort(data)
print(data)

        测试程序输出

[-15, 1, 45, 89, 123]

三、插入排序

        插入排序最好时间复杂度为O(n)，最坏时间复杂度为O(n^2)，平均时间复杂度为O(n^2)，空间复杂度为O(1)。

        代码

def select_sort(data_list):
    for i in range(len(data_list) - 1):
        min_index = i       # 记录最小数的索引
        for j in range(i+1, len(data_list)):
            if data_list[j] < data_list[min_index]:
                min_index = j
        if i != min_index:  # i不是最小数时，将i和最小数进行交换
            data_list[i], data_list[min_index] = data_list[min_index], data_list[i]
data = [45, 123, 89, 1, -15]
select_sort(data)
print(data)

        测试程序输出

[-15, 1, 45, 89, 123]

四、冒泡排序

        冒泡排序最好时间复杂度为O(n)，最坏时间复杂度为O(n^2)，平均时间复杂度为O(n^2)，空间复杂度为O(1)。

        代码

def bubble_sort(data_list):
    for i in range(1, len(data_list)):
        for j in range(0, len(data_list)-i):
            if data_list[j] > data_list[j+1]:
                data_list[j], data_list[j + 1] = data_list[j + 1], data_list[j]
data = [45, 123, 89, 1, -15]
bubble_sort(data)
print(data)

        测试程序输出

[-15, 1, 45, 89, 123]

五、快速排序

        快速排序最好时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)，平均时间复杂度为O(nlogn)，最好空间复杂度为O(logn)，最坏空间复杂度为O(n)，平均空间复杂度为O(logn)。

        代码

def quick_sort(data_list, left=None, right=None):
    left = 0 if not isinstance(left, (int, float)) else left
    right = len(data_list) - 1 if not isinstance(right, (int, float)) else right
    if left < right:
        partitionIndex = partition(data_list, left, right)
        quick_sort(data_list, left, partitionIndex - 1)
        quick_sort(data_list, partitionIndex + 1, right)
def partition(data_list, left, right):
    pivot = left
    index = pivot + 1
    i = index
    while i <= right:
        if data_list[i] < data_list[pivot]:
            swap(data_list, i, index)
            index += 1
        i += 1
    swap(data_list, pivot, index - 1)
    return index - 1
def swap(data_list, i, j):
    data_list[i], data_list[j] = data_list[j], data_list[i]
data = [45, 123, 89, 1, -15]
quick_sort(data)
print(data)

        测试程序输出

[-15, 1, 45, 89, 123]

六、归并排序

        归并排序的最好、最坏、平均时间复杂度均为O(nlogn)，空间复杂度为O(n)。

        代码

import math
def merge_sort(data_list):
    if len(data_list) < 2:
        return data_list
    middle = math.floor(len(data_list) / 2)
    left, right = data_list[0:middle], data_list[middle:]
    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
data = [45, 123, 89, 1, -15]
data = merge_sort(data)
print(data)

        测试程序输出

[-15, 1, 45, 89, 123]

七、Python内置排序方法

        Python内置的排序方法是Timsort，其最好时间复杂度为O(n)，最坏、平均时间复杂度为O(nlogn)，空间复杂度为O(n)。

        第一种使用方式如下

data = [45, 123, 89, 1, -15]
data = sorted(data, reverse=False)
print(data)

        上述程序输出为

[-15, 1, 45, 89, 123]

        第二种使用方式如下

data = [45, 123, 89, 1, -15]
data.sort(reverse=False)
print(data)

        上述程序输出为

[-15, 1, 45, 89, 123]

八、参考

        1. 百度百科

        2. 菜鸟教程

        3. Python内置算法