1 冒泡排序

1. 比较一对相邻元素，如果两个元素顺序不对，交换
2. 重复上述步骤直到数组末尾，则此时最大的元素已经在数组末尾
3. 对数组前N-1个元素重复执行上述操作

显然，算法有2层循环嵌套，比较交换一共执行了(N-1)+(N-2)+...+1=N(N-1)/2次，因此时间复杂度为O(n^2)

python代码：

def bubbleSort(nums):
    # step 4
    for i in range(len(nums)-1):
        # step 3
        for j in range(len(nums)-1-i):
            # step 1,2
            if nums[j]>nums[j+1]:
                nums[j],nums[j+1]=nums[j+1],nums[j]
    return nums

2 选择排序

定义一个初始位置L=0

1. 在[L,N-1]范围找到最小的数X
2. 将第L个元素和X交换
3. 增加L，并重复上述步骤直到L=N-2

时间复杂度查找最小为O(N)，遍历为O(N)，所以嵌套之后为O(n^2)。不稳定

python代码：

def selectSort(nums):
    # step 3
    for i in range(len(nums)):
        # step 1,2
        idx = i
        for j in range(i+1,len(nums)):
            if nums[idx]>nums[j]:
                idx = j
        nums[i],nums[idx] = nums[idx],nums[i]
    return nums

3 插入排序

就像打扑克牌时一样：

1. 指定要插入序列的数
2. 将该数和已经排好的序列中对数比较，插入正确的位置
3. 重复上述步骤

python代码：

def insertionSort(nums):
    for i in range(1,len(nums)):
        # 元素比前一个小，插入到前边的序列中
        if nums[i]<nums[i-1]:
            x = nums[i]
            j = i-1
            # 将前边已经排列好的序列中比该元素大的右移，腾出插入的位置
            while j>=0 and nums[j]>x:
                nums[j+1] = nums[j]
                j -= 1
            # 插入
            nums[j+1] = x
    return nums

4 归并排序

1. 分治：将数组递归地二分得到每一个元素（复杂度O(logN)）
2. 归并：将2个元素合并排序成1个2元素的有序数组，进而将2个2元素的有序数组合并排序为1个4元素有序数组，以此类推，直到全部合并。
3. 具体的合并排序两个有序数组的方法：取两个数组的第1个元素，小的放到临时数组，然后再取第一个再比较、放入，直到1个数组空了，没空的数组剩下的元素直接拼接到临时数组后边即可。最后临时数组就是归并2个数组以后排序好的数组。（复杂度O(N)）

时间复杂度O(NlogN)，比前面几种O(N^2)的快了不少，但是因为需要临时数组存放归并结果，所以空间复杂度增加了，变成了O(N)

python代码：

# 合并排序2个有序数组
def merge(a,b):
    r = []
    while len(a)>0 and len(b)>0:
        if a[0] < b[0]:
            r.append(a.pop(0))
        else:
            r.append(b.pop(0))
    r += a
    r += b
    return r

def mergeSort(nums):
    # 分治
    if len(nums) == 1:
        return nums
    mid = len(nums)//2
    left = nums[:mid]
    right = nums[mid:]
    # 递归
    r_left = mergeSort(left)
    r_right = mergeSort(right)
    # 合并排序
    return merge(r_left,r_right)

5 快速排序

快排也是分治策略。作为面试出镜率相当高的经典算法，理解它的思想是十分必要的

指定一个数，将数组中比它小的放到它左边，比它大的放到它右边，再对左右重复执行上述步骤，完成排序。这是快排的基本思想

实现：

1. 指定数组第一个元素为“基准”
2. 将数组从两头往中间遍历。先从右向左找到第一个比基准小的数，再从左向右找到第一个比基准大的数，如果2个数顺序不对，交换。继续遍历直到两边遍历到同一个元素，交换基准和该元素。这一步将大小和基准分开了
3. 对基准两侧的部分重复执行上述步骤

考虑最好的情况，如果每次基准都能将数组二分，则logN次就可以递归完。遍历排序的时间复杂度为O(N)，于是总的时间复杂度为O(NlogN)

考虑最坏的情况，即每次分完之后只能得到基准和一个数组，另一个数组是空的。那么需要做N次递归，于是总的时间复杂度为O(N^2)

python代码：

def quickSort(nums,l,r):
    if l>=r:
        return
    start = l
    end = r
    key = nums[start]
    while l<r:
        # 从右向左找第一个比基准小的数
        while l<r and nums[r]>key:
            r -= 1
        # 从左向右找第一个比基准大的数
        while l<r and nums[l]<=key:
            l += 1
        # 交换
        nums[l],nums[r] = nums[r],nums[l]
    # 交换基准和遍历结束所在的元素
    nums[start],nums[r] = nums[r],nums[start]
    # 递归
    quickSort(nums,start,l-1)
    quickSort(nums,l+1,end)

随机快排通过随机选取基准来减少最坏情况发生的可能，平均时间复杂度达到O(NlogN)

6 计数排序

以上都是基于比较的排序方式，时间复杂度的下限是O(NlogN)。计数排序不是基于比较的。

计数排序的思想很简单。假设输入的数组元素最大值为k，那么只需要统计0～k各数字出现的次数，出现一次就放到临时数组对应的位置，全部放完后再按顺序取出排好即可。

1. 遍历数组，对每个出现的数字计数，放入计数数组c
2. 将计数数组c的元素累加，从而计数转化为序号
3. 将原数组的元素i放到结果数组的c[i]位置

3次遍历，时间复杂度分别为O(N),O(k),O(N)。所以总的时间复杂度为O(2N+k)。序列比较集中时，可以看作线性复杂度O(N)，速度还是很快的。不过可以想象，临时数组很占空间(O(k)) ，总的空间复杂度为O(N+k)。如果虽然数组不大但数值跨度特别大，空间就是个问题

pytyon实现：

def countingSort(nums,k):
    N = len(nums)
    # 计数数组
    temp = [0 for i in range(k+1)]
    # 结果数组
    r = [0 for i in range(N)]
    # 计数
    for i in nums:
        temp[i] += 1
    # 将计数转化为序号
    for i in range(1,len(temp)):
        temp[i] += temp[i-1]
    # 放入结果
    for i in nums:
        r[temp[i]-1] = i
        temp[i] -= 1
    return r

7 基数排序

基数排序的思路也很简单，将多位数的各位分开计数排序，实际上就是考察关键字

1. 建立0-9一共10个桶存放数字
2. 只考察数字的某位，将每个数字放入对应的桶
3. 从个位开始考察到最高位，每次执行1-2步骤，完成排序

桶的放入和取出时间复杂度都是O(N)，根据位数d要重复d次，所以总的时间复杂度是O(2N*d)，一般来说位数比序列数量小得多，所以时间复杂度可以认为也是线性O(N)。空间复杂度为O(N+d)

python代码：

def radixSort(nums, d):
    # d为位数
    for i in range(d):
        # 0-9的桶存放数字
        s = [[] for j in range(10)]
        # 按位放入桶
        for k in nums:
            s[k/10**i%10].append(k)
        # 从桶中取出放入结果
        r = [a for b in s for a in b]
    return r

8 堆排序

堆排序作为一种复杂的排序方法在面试出现的频率也很高，是一种利用堆这种数据结构来排序的方法，也是一种选择排序，是不稳定的，时间复杂度O(NlogN)

堆是一种完全二叉树结构，最大堆每个节点值都大于子节点的值，最小堆每个节点值都小于子节点的值。升序排列时用最大堆，降序用最小堆

堆排序的思想是将序列构造成最大堆，则根节点就是最大值。将根节点的元素与数组末尾元素交换，于是将数组中最大的元素放到了数组末尾。剩下的N-1个节点再构造最大堆，重复上述步骤……最终完成排序

最大堆的构建就是堆排序的关键。堆是二叉树，所以数组形式的最大堆表达式为a[i]>=a[2i+1] && a[i]>=a[2i+2]；最小堆表达式为a[i]<=a[2i+1] && a[i]<=a[2i+2]。所以只要让数组满足上述条件，即可完成最大/小堆的构造。一旦了解了堆排序的思想，实现就不难了，步骤如下：

1. 从最后一个非叶节点开始往前遍历所有非叶节点，进行调整操作（步骤2）
2. 考察一个节点和它的两个子节点，将大的和它交换。需要注意的是交换可能打破子树中节点-子节点的大小关系，因此发生了交换就要调整子树，以被换到子节点的节点为考察节点，递归执行此步
3. 经过上述2步后最大堆已经构建完毕，根结点就是最大值，将它和堆尾元素交换。然后以其他节点为考察对象继续构建最大堆……在这过程中最大，次大……元素不断被找出，完成排序

python代码：

# 调整使大于子节点
def maxHeapify(heap, size, curr):
    left = 2 * curr + 1
    right = left + 1
    larger = curr
    # 找节点和子节点的最大值
    if left<size and heap[left]>heap[larger]:
        larger = left
    if right<size and heap[right]>heap[larger]:
        larger = right
    # 如果子节点比节点大，交换
    if larger != curr:
        heap[larger],heap[curr] = heap[curr],heap[larger]
        # 交换之后heap[curr]成了heap[larger]子节点
        # 但这可能会影响heap[curr]和其子节点的大小关系
        # 因此需要再以heap[curr]的索引larger为传入参数再调整
        maxHeapify(heap, size, larger)

def heapSort(nums):
    N = len(nums)
    # 从最后一个非叶节点往前遍历调整，构建最大堆
    for i in range(N//2-1,-1,-1):
        maxHeapify(nums,N,i)
    # 将最大元素放到堆尾，将前边元素调整为最大堆
    for i in range(N-1, -1, -1):
        nums[0],nums[i] = nums[i],nums[0]
        maxHeapify(nums,i,0)

总结