排序算法总结-白红宇

各种排序算法的时间空间复杂度

排序算法由python实现

算法名称	最坏时间复杂度	最优时间复杂度	平均时间复杂度	额外空间复杂度	描述
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	(无序区，有序区) 从无序区通过交换找到最大元素放到有序区前端
插入排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	(有序区，无序区) 把无序区的第一个元素插入到有序区的合适位置
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	(有序区，无序区) 在无序区找一个最小的元素跟在有序区的后面
归并排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(n)$	把数据分成两段，从两段中逐个选最小的移入新数据段的末尾
快速排序	$O(n^2)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	(小数，基准数，大数) 在区间中随机挑选一个元素作为基准数，将小于基准数的元素放在基准之前，大于基准数的元素放在基准之后，再分别对小数区和大数区进行排序
堆排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	(最大堆，有序区) 从堆顶把跟卸出来放到有序区之前，再恢复堆

排序算法列表

冒泡排序

冒泡排序算法的运作如下：

比较相邻的元素，如果第一个元素比第二个大，交换他们。

对每对相邻元素作同样的工作，从开始第一对到最后一对。这步做完后，最后的元素会是最大的元素。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复以上的步骤，直到没有任何一对元素进行比较。

实现如下：

def bubble_sort(iterable):    new_list = list(iterable)    list_len = len(new_list)    for i in range(list_len-1):        for j in range(list_len-1-i):            if new_list[j] > new_list[j+1]:                new_list[j], new_list[j+1] = new_list[j+1], new_list[j]    return new_list复制代码

插入排序

插入排序算法的运作如下：

从第一个元素开始，该元素已经认为被排序。

取出下一个元素，在已经排序的元素序列中从后向前扫描。

如果该元素（已排序）大于新元素，将该元素移到下一个位置。

重复步骤3，直到找到已排序的元素小于或等于新元素的位置。

将该元素插入到该位置后。

重复步骤2-5。

实现如下：

def insertion_sort(iterable):    new_list = list(iterable)    list_len = len(new_list)    for i in range(1, list_len):        t = new_list[i]        k = -1        for j in range(i-1, -1, -1):            if new_list[j] > t:                new_list[j+1] = new_list[j]            else:                k = j                break        new_list[k+1] = t    return new_list;复制代码

def insertion_sort(iterable):    new_list = list(iterable)    list_len = len(new_list)    for i in range(1, list_len):        for j in range(i, 0, -1):            if new_list[j-1] > new_list[j]:                new_list[j-1], new_list[j] = new_list[j], new_list[j-1]    return new_list复制代码

选择排序

选择排序算法的运作如下：

从第一个元素开始寻找找到最小的元素。

将该元素存在到起始位置。

从剩余的未排序元素中，重新执行步骤1-2。

实现如下：

def selection_sort(iterable):    new_list = list(iterable)    list_len = len(new_list)    for i in range(0, list_len):        temp = i        for k in range(i+1, list_len):            if new_list[k] < new_list[temp]:                temp = k        new_list[i], new_list[temp] = new_list[temp], new_list[i]    return new_list;复制代码

归并排序

归并排序算法有2种方式，其中递归方式如下：

申请空间，使其大小为2个已排序序列之和，该空间用于存放合并后的序列

设定两个指针，初始化为两个已排好的序列的起始位置

比较两个指针所指向的元素，选择相对较小的元素放入到合并空间，并移动指针到下一个位置

重复步骤3直到某一指针到达序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

实现如下：

def merge_sort_recursive(iterable):    def merge_sort(left, right):        new_list = []        while left and right:            if left[0] < right[0]:                new_list.append(left.pop(0))            else:                new_list.append(right.pop(0))        if left:            new_list += left        if right:            new_list += right        return new_list;    if len(iterable) <= 1:        return iterable    mid = len(iterable) // 2    left = iterable[:mid]    right = iterable[mid:]    left = merge_sort_recursive(left)    right = merge_sort_recursive(right)    return merge_sort(left, right)复制代码

迭代方式如下：

将序列中每相邻两个元素进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素

若此时序列数不为1则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素

重复步骤2，直到所有元排列完毕，即序列数为1

实现如下：

def merge_sort_iteration(iterable):    step = 1    result = iterable    n = len(iterable)    while step < n:        offset = step << 1        temp = []        for index in range(0, n, offset):            left = result[index:min(index + step, n)]            right = result[min(index + step, n):min(index + offset, n)]            while left and right:                if left[0] < right[0]:                    temp.append(left.pop(0))                else:                    temp.append(right.pop(0))            if left:                temp += left            if right:                temp += right        result = temp        step = offset    return result复制代码

快速排序

快速排序的算法运作方式如下：

从数列中挑出一个元素，称为“基准”(pivot)

重新排序数列，所有比基准值小的元素放到基准前面，所有比基准值大的元素放到基准后面（相同的数可以放到任意一边）。在这个分割之后，该基准就处于数列的中间位置。这个成为 分割(partion) 操作。

递归地把小于基准元素的子数列和大于基准值元素的子数列排序。

实现如下：

def quick_sort(iterable):    def partition(iterable, left, right, pivotIndex):        pivotValue = iterable[pivotIndex]        iterable[pivotIndex], iterable[right] = iterable[right], iterable[pivotIndex]        storeIndex = left        for i in range(left, right):            if iterable[i] < pivotValue:                iterable[i], iterable[storeIndex] = iterable[storeIndex], iterable[i]                storeIndex += 1        iterable[right], iterable[storeIndex] = iterable[storeIndex], iterable[right]        return storeIndex    def quick_sort_recursive(iterable, left, right):        if right > left:            pivotIndex = (left + right) // 2            pivotNewIndex = partition(iterable, left, right, pivotIndex)            quick_sort_recursive(iterable, left, pivotNewIndex - 1)            quick_sort_recursive(iterable, pivotNewIndex + 1, right)        return iterable    return quick_sort_recursive(iterable, 0, len(iterable) - 1)复制代码

堆排序

通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：

父节点的左子节点在位置(2i+1)

父节点的右子节点在位置(2i+2)

子节点的父节点在位置floor((i-1)/2)

在堆的数据结构中，堆的最大值总是位于根节点。堆中定义以下几种操作：

最大堆调整：将堆的末端子节点做调整，使得子节点永远小于父节点

创建最大堆：将堆中的所有数据重新排序

堆排序：移除位在第一个数据的根节点，并做最大堆调整的递归运算

实现如下：

def heap_sort(iterable):    def max_heapify(start, end):        '''最大堆调整'''        root = start        while True:            child = 2 * root + 1            if child > end:                break            if child + 1 <= end and iterable[child] < iterable[child+1]:                child += 1            if iterable[root] < iterable[child]:                iterable[root], iterable[child] = iterable[child], iterable[root]                root = child            else:                break    # 创建最大堆    for start in range((len(iterable) -2) // 2, -1, -1):        max_heapify(start, len(iterable) - 1)    # 堆排序    for end in range(len(iterable) - 1, 0, -1):        iterable[0], iterable[end] = iterable[end], iterable[0]        max_heapify(0, end - 1)    return iterable复制代码