[数据结构与算法]排序算法总结

本文章选取常用的几个排序算法进行了总结，其中包含：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序。

标题算法复杂度总结表如下

下面将对以上排序算法一一总结（为了方便，均按照从小到大排序）：

1、冒泡排序

算法思路： 将长度为n的数组的排序进行n-1个次的冒泡，每次冒泡则是从左到右相邻数字的比较，较大的放右边，每次冒泡则会使数组右侧为最大的值且有序。

def bubleSort(nums):
	n = len(nums)
	for i in range(n):
		for j in range(n - i - 1)：
			if nums[j] > nums[j + 1]:
				nums[j], nums[j + 1] = nums[j + 1], nums[j];

注：当数组已经按照想要的顺序排列时，只需要遍历一遍，即时间复杂度为$O(n)$

2、选择排序

算法思路： 每次遍历数组中未排序部分，选择数字最小的放在数组的最前面，此时前半部分数组是已经排好序的，然后进行下一轮遍历，逐次将每次遍历未排序部分的最小值放在前面已排序部分后面。

def selecSort(nums):
    length = len(nums)
    for i in range(length):
        minIndex = i;
        for j in range(i + 1, length):
            if (nums[j] < nums[minIndex]):
                minIndex = j
        nums[i], nums[minIndex] = nums[minIndex], nums[i]

注：选择排序是一种稳定的算，无论什么数据进去都是$O(n^2)$的复杂度，所以适合小数据量的数据。

3、插入排序

算法思路： 扑克牌原理，每次遍历未排序部分就将当前的值插入到已经排序好的数组中的合适位置。

def insertSort(nums):
    length = len(nums)
    for i in range(length):
        preIndex = i - 1;
        current = nums[i]
        while preIndex >= 0 and nums[preIndex] > current:
            nums[preIndex + 1] = nums[preIndex]
            preIndex -= 1
        nums[preIndex + 1] = current

注：选择排序是一种稳定的算，无论什么数据进去都是$O(n^2)$的复杂度，所以适合小数据量的数据。

4、希尔排序

算法思路： 在插入排序的基础上加入了分治的思想，先将数组分成n组，每组为gap个元素，对每组进行插入排序，先让部分有序再让整体有序，然后gap为1最后排序一次即可完成整个数组的排序。

def shellSort(nums):
    import math
    length = len(nums)
    gap = length / 2
    while (gap > 0):
        for i in range(length):
            preIndex = i - 1;
            current = nums[i]
            while preIndex >= 0 and nums[preIndex] > current:
                nums[preIndex + 1] = nums[preIndex]
                preIndex -= 1
            nums[preIndex + 1] = current
        gap = math.floor(gap / 2)

注：希尔排序的实际时间复杂度与增量gap的选择有关，最差可退化为$O(n^2)$。

5、归并排序

算法思路： 在插入排序的基础上加入了分治的思想，先将数组分成n组，每组为gap个元素，对每组进行插入排序，先让部分有序再让整体有序，然后gap为1最后排序一次即可完成整个数组的排序。

1.递归实现：

def mergeSort(nums):
    length = len(nums)
    if length < 2:
        return nums
    mid = length // 2
    left = nums[:mid]
    right = nums[mid:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left, right):
    res = []
    while left and right:
        if left[0] <= right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))
    while left:
        res.append(left.pop(0))
    while right:
        res.append(right.pop(0))
    return res

注：归并排序十分稳定，不管输入数据如何都保持$O(nlogn)$的时间复杂度，但需要更多的空间开支。

6、快速排序

算法思路： 在数组中找一个基线值pivot， 然后将小于pivot的数放在左边，大于pivot的值放在右边，两侧进行递归地实现这一逻辑。

def quickSort(nums, left, right):
    if left < right:
        partitionIndex = partition(nums, left, right)
        quickSort(nums, left, partitionIndex - 1)
        quickSort(nums, partitionIndex + 1, right)
    
def partition(nums, left, right):
    pivot = nums[left]
    while left < right:
        while left < right and nums[right] > pivot:
            right -= 1
        nums[left], nums[right] = nums[right], nums[left]
        while left < right and nums[left] < pivot:
            left += 1
        nums[left], nums[right] = nums[right], nums[left]
    nums[left] = pivot
    return left

注：当数组已经按照想要的顺序排列时，时间复杂度退化为为$O(n^2)$

7、堆排序

算法思路： 由于是从小到大排序，所以采用大顶堆实现，堆的特性是左右子节点小于或等于父节点，于是我们将堆顶与堆尾互换，并且堆的数量减一，此时堆尾为最大值，并将剩余的数组重新建立堆的秩序，如此反复则可以实现从小到大排列。

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1
        heapify(arr, 0)
    return arr

**注：从小打到大排序用大顶堆，反之用小顶堆，并且是一种稳定的排序，最好最坏情况下时间复杂度都为$O(nlogn)$