冒泡排序

思想：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。

在相邻元素相等时，它们并不会交换位置，冒泡排序是稳定排序。
代码

# O(n^2)复杂度
def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr) - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


if __name__ == '__main__':
    print(bubbleSort([134, 234, 34, 44, 5567, 564, 6, 78, 3, 32, 2, 3456, 5]))

插入排序

思想
直接插入排序O(n^2^) 稳定排序算法，适合于基本有序的情况，无序且n较大时，复杂度高。

1. 将第1个数作为已排好的序列，从第i=2个数开始，每次判断要将r[i]插入到已排好序列的第几个位置（使用顺序查找法）。
2. 每查找一个，不满足插入位置，就逐个后移， 为避免数组越界，可以在 r[0] 处暂存待插入的数据。

代码

# O(n^2)复杂度
def InsertSort(arr):
    for i in range(1, len(arr) - 1):
        for j in range(i):
            if arr[i + 1] < arr[j]:
                arr.insert(j, arr.pop(i + 1))
    return arr


a = [134, 234, 34, 44, 5567, 564, 6, 78, 3, 32, 2, 3456, 5]
print(InsertSort(a))

选择排序

思想

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

代码

# O(n^2)复杂度
def SelectSort(arr):
    for i in range(len(arr)):
        min_pos = i
        for j in range(i, len(arr)):
            if arr[j] < arr[min_pos]:
                min_pos = j
        arr.insert(i, arr.pop(min_pos))
        # print(arr)
    return arr


a = [134, 234, 34, 44, 5567, 564, 6, 78, 3, 32, 2, 3456, 5]
print(SelectSort(a))

归并排序

思想

1. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
2. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
3. 重复步骤3
4. 直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素直接复制到合并序列尾。

代码

def MergeSort(arr):
    if len(arr) == 1:
        return arr
    else:
        arr1, arr2 = MergeSort(arr[:len(arr) // 2]), MergeSort(arr[len(arr) // 2:])
        arr1_pos = 0
        arr2_pos = 0
        new_arr = []
        while True:
            if arr1_pos >= len(arr1):
                for i in range(arr2_pos, len(arr2)):
                    new_arr.append(arr2[i])
                break
            elif arr2_pos >= len(arr2):
                for i in range(arr1_pos, len(arr1)):
                    new_arr.append(arr1[i])
                break
            elif arr1[arr1_pos] < arr2[arr2_pos]:
                new_arr.append(arr1[arr1_pos])
                arr1_pos += 1
            else:
                new_arr.append(arr2[arr2_pos])
                arr2_pos += 1
        return new_arr

print(MergeSort([134, 234, 34, 44, 5567, 564, 6, 78, 3, 32, 2, 3456, 5]))

快速排序

思路
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

代码

# O(nlog(n))复杂度
def QuickSort(arr, low, high):
    if high - low == 1:
        if arr[high] < arr[low]:
            arr[high], arr[low] = arr[low], arr[high]
            return
        return
    if low < high:
        standard = arr[low]
        start_pos = low
        end_pos = high
        low += 1
        while True:
            while arr[high] > standard and low != high:
                high -= 1
            while arr[low] < standard and low != high:
                low += 1
            if low == high:
                break
            arr[high], arr[low] = arr[low], arr[high]
        arr[start_pos], arr[low] = arr[low], arr[start_pos]
        QuickSort(arr, start_pos, low - 1)
        QuickSort(arr, low + 1, end_pos)

a = [134, 234, 34,34, 44, 5567, 454, 564, 6, 78, 3, 32, 2, 3456, 5]
QuickSort(a, 0, len(a) - 1)
print(a)

希尔排序

思路

1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
2. 按增量序列个数 k，对序列进行 k 趟排序；
3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

代码

# 时间复杂度O(n^(3/2))
def ShellSort(arr: list):
    gap = len(arr) // 2
    while True:
        for j in range(gap):  # 对于gap所分的每一个组
            for i in range(j + gap, len(arr), gap):  # 进行插入排序
                tmp = arr[i]
                pos = i
                for k in range(i - gap, -1, -gap):
                    if arr[k] > tmp:
                        arr[k + gap] = arr[k]
                        pos = k
                arr[pos] = tmp

        if gap == 1:
            break
        gap = int(gap / 2)


a = [134, 234, 34, 44, 5567, 564, 6, 78, 3, 32, 2, 3456, 5]
ShellSort(a)
print(a)

堆排序

思想

1. 创建一个堆；
2. 把堆首（最大值）和堆尾互换；
3. 把堆的尺寸缩小 1，把新的数组顶端数据调整到相应位置；
4. 重复步骤 2，直到堆的尺寸为 1。

代码

# 时间复杂度O(n^(3/2))
def HeapSort(arr):
    length = len(arr)
    while True:
        for i in range(length // 2 - 1, -1, -1):
            switch(arr, i, length)
        arr[0], arr[length - 1] = arr[length - 1], arr[0]
        length -= 1
        if length == 0:
            break


def switch(arr, pos, length):
    left = pos * 2 + 1
    right = pos * 2 + 2
    if left < length and arr[left] > arr[pos]:
        arr[pos], arr[left] = arr[left], arr[pos]
    if right < length and arr[right] > arr[pos]:
        arr[pos], arr[right] = arr[right], arr[pos]


a = [134, 234, 34, 44, 5567, 564, 6, 78, 3, 32, 2, 3456, 5]
HeapSort(a)
print(a)