常见排序方法

1、选择排序

• 时间复杂度：O(N^2)

• 空间复杂度：O(1)

• 不稳定

• 思路：一开始，在[0, n-1]范围内选取一个最小的数放在0位置；第二次在[1, n-1]范围内选取一个最小的数放在1位置上；依次类推，直到访问到最后一个数，数组有序。

• Python写法：

  def SelectionSort(arr):
    length = len(arr)
    for i in range(length):
        minIndex = i
        for j in range(i+1, length):
            if arr[j] < arr[minIndex]:
                minIndex = j
            else:
                minIndex = minIndex
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

2、冒泡排序

• 时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 稳定

def BubbleSort(arr):
    length = len(arr)
    if length < 2:
        return arr
    for i in range(length-1):
        for j in range(length-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

3、插入排序

• 时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 稳定

def InsertSort(arr):
    length = len(arr)
    if length < 2:
        return arr
    for i in range(1, length):
        for j in range(i-1, -1, -1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

4、归并排序

• 时间复杂度：O(NlogN)
• 空间复杂度：O(N)
• 稳定

def MergeSort(arr):
    length = len(arr)
    if length < 2:
        return arr
    process(arr, 0, length-1)
    return arr

def process(arr, left, right):
    if left == right:
        return
    mid = left + ((right - left + 1) >> 1)
    process(arr, left, mid)
    process(arr, mid+1, right)
    Merge(arr, left, mid, right)

def Merge(arr, left, mid, right):
    help = []
    p1 = left
    p2 = mid + 1
    while (p1 <= mid) and (p2 <= right):
        if arr[p1] <= arr[p2]:
            help.append(arr[p1])
            p1 += 1
        else:
            help.append(arr[p2])
            p2 += 1
    while p1 <= mid:
        help.append(arr[p1])
        p1 += 1
    while p2 <= right:
        help.append(arr[p2])
        p2 += 1
    for i in range(len(help)):
        arr[left+i] = help[i]
    return arr