排序算法

选择排序

算法过程：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素就和自己交换）。然后在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，知道整个数组排序。

def selectionSort(nums):
    for i in range(len(nums)-1):
        minIndex = i
        for j in range(i+1, len(nums)):
            if nums[j]<nums[minIndex]:
                minIndex = j
        nums[i], nums[minIndex] = nums[minIndex], nums[i]
    return nums

性质：时间复杂度：$O(n^2)$，空间复杂度：$O(1)$，非稳定排序，原地排序

插入排序

算法过程：1）从数组第2个元素开始抽取元素。2）把它与左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较，知道遇到不必它大的元素，然后插入到这个元素的右边。3）继续选取第3,4,…,n个元素，重复步骤2，选择适当的位置插入。

def insertionSort(nums):
    for i in range(len(nums)-1):
        curNum, preIndex = nums[i+1], i
        while preIndex>=0 and curNum<nums[preIndex]:
            nums[preIndex+1] = nums[preIndex]
            preIndex -= 1
        nums[preIndex+1] = curNum
    return nums

性质：时间复杂度：$O(n^2)$，空间复杂度：$O(1)$，稳定排序，原地排序。

冒泡排序

算法过程：1）把第一个元素和第二个元素比较，如果第一个比第二个大，则交换他们的位置。接着比较第二个与第三个元素，如果第二个比第三个大，则交换它们的位置…。这样一趟比较交换之后，排在最右的就会是最大的数。2）除去最右的数，我们对剩余的元素做同样的工作，如此重复下去，直到排序完成。

def bubblesort(nums):
    for i in range(len(nums)-1, 0, -1):
        for j in range(0, i):
            if nums[j]>nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

性质：时间复杂度：$O(n^2)$，空间复杂度：$O(1)$，稳定排序，原地排序。
优化冒泡排序算法:假如开始的第一队到结尾的最后一对，相邻的元素之间都没有发生交换的操作，这意味着右边的元素总是大于等于左边的元素，此时数组已经是有序的，无须再对剩余的元素重复比较下去。

def bubblesort2(nums):
    if not nums:
        return
    for i in range(len(nums)-1, 0, -1):
        swapped = False
        for j in range(0, i):
            if nums[j]>nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                swapped = True
        if not swapped:
            break
    return nums

希尔排序

希尔排序可以说是插入排序的一种变种，无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要n-1次移动。也就是说原数组的一个元素如果距离它正确的位置很远，则需要与相邻元素交换很多次才能到达正确的位置，这是相对比较花时间了。
希尔排序就是为了加快速度简单地改进插入排序，交换不相邻的元素对数组的局部进行排序。基本思想是：先将整个待排序列分割成为若干子序列分别进行插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。希尔排序的核心在于间隔序列的设定，既可以提前设定好间隔序列，也可以动态地定义间隔序列。

def shellSort(nums):
    gap = 1
    while gap<len(nums)//3:
        gap = gap*3+1
    while gap>0:
        for i in range(gap, len(nums)):
            curNum, preIndex = nums[i], i-gap
            while preIndex>=0 and curNum<nums[preIndex]:
                nums[preIndex+gap] = nums[preIndex]
                preIndex -= gap
            nums[preIndex+gap] = curNum
        gap //= 3
    return nums

性质：时间复杂度：$O(nlogn)$，空间复杂度：$O(1)$，非稳定排序，原地排序。

归并排序

归并排序使用递归分治的思想，其基本思想是：把待排序列看成两个有序的子序列，然后合并两个子序列，接着把子序列再看成两个有序的子子序列，…，以此类推。

def mergeSort(nums):
    if len(nums)<=1:
        return nums
    # 归并过程
    def merge(left, right):
        result = []
        i = j = 0
        while i<len(left) and j<len(right):
            if left[i]<=right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result = result + left[i:] + right[j:]
        return result
    # 递归过程
    mid = len(nums)//2
    left = mergeSort(nums[:mid])
    right = mergeSort(nums[mid:])
    return merge(left, right)

非递归做法

def mergeSort2(nums):
    i = 1  # i是步长
    while i<len(nums):
        left = 0
        while left<len(nums):
            mid = left+i
            right = min(left+2*i, len(nums))
            if mid<right:
                nums[left:right]=merge(nums[left:mid], nums[mid:right])
            left += 2*i
        i *= 2
    return nums

快速排序

快速排序通常明显比同为$O(nlogn)$的其他算法更快，因此常被采用，而且快排采用了分治的思想，所以在面试中经常看到快排的影子。
步骤：
1）从数列中跳出一个元素作为基准数。
2）分区过程，将比基准数大的放在右边，小于或等于它的数都放在左边。
3）再对左右分区递归执行第二步，直至各区间只有一个数。
快排过程

# 划分策略，适用于链表
def partition(nums, left, right):
    if left == right:
        return left
    pivot = left
    slow, fast = left, left+1
    while fast<=right:
        if nums[fast]<nums[pivot]:
            slow += 1
            nums[slow], nums[fast] = nums[fast], nums[slow]
        fast += 1
    nums[pivot], nums[slow] = nums[slow], nums[pivot]
    return slow

# 递归方法
def quickSort(nums, left, right):
    if left<=right:
        midIndex = partition(nums, left, right)
        quickSort(nums, left, midIndex-1)
        quickSort(nums, midIndex+1, right)
    return nums

非递归方式，利用栈的思想将需要继续排序的首尾下标存入栈中，不断弹栈进行分区操作。

def partition2(nums, left, right):
    mid = nums[left]
    while left<right:
        while left<right and nums[right]>mid:
            right -= 1
        nums[left] = nums[right]
        while left<right and nums[left]<=mid:
            left += 1
        nums[right] = nums[left]
    nums[left] = mid
    return left
def quickSort2(nums):
    if len(nums)<=1:
        return nums
    stack = []
    left, right = 0, len(nums)-1
    stack.append(left)
    stack.append(right)
    while stack:
        r = stack.pop()
        l = stack.pop()
        midIndex = partition2(nums, l, r)
        if l<midIndex:
            stack.append(l)
            stack.append(midIndex-1)
        if r>midIndex:
            stack.append(midIndex+1)
            stack.append(r)
    return nums

堆排序

堆排序是借助堆来实现的选择排序，思想同选择排序，以下以大根堆为例。注意：如果想升序排序就使用大根堆，反之使用小根堆。原因是堆顶元素需要交换到序列尾部。
首先，实现堆排序需要解决两个问题：
1）如何由一个无序序列建成一个堆？
2）如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？
第一个问题，可以直接使用线性数组来表示一个堆，由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始按个调整成一个堆。
第二个问题，怎么调整成堆？首先是将堆顶元素和最后一个元素交换，然后比较当前堆顶元素的左右孩子节点，因为除了当前的堆顶元素，左右孩子均满足条件，这时需要选择当前堆顶元素与左右孩子节点的较大者（大根堆）交换，直到叶子节点。我们称这个自堆顶至叶子节点的调整为筛选。
从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端节点是n/2（取底）个元素，由此筛选即可。

# 大根堆
def heapSort(nums):
    def adjustHeap(nums, i, size):
        lchild = 2*i+1
        rchild = 2*i+2
        largest = i
        if lchild<size and nums[lchild]>nums[largest]:
            largest = lchild
        if rchild<size and nums[rchild]>nums[largest]:
            largest = rchild
        if largest != i:
            nums[largest], nums[i] = nums[i], nums[largest]
            adjustHeap(nums, largest, size)
    # 建立堆
    def buildHeap(nums, size):
        for i in range(len(nums)//2)[::-1]:  # 从倒数第一个非叶子节点开始建立大根堆
            adjustHeap(nums, i, size)        # 对所有非叶子节点进行堆的调整
    # 堆排序
    size = len(nums)
    buildHeap(nums, size)
    for i in range(len(nums))[::-1]:
        nums[0], nums[i] = nums[i], nums[0]
        adjustHeap(nums, 0, i)
    return nums

计数排序

（待补充）

桶排序

（待补充）

基数排序

（待补充）