1.快速排序

a.原理

快速排序的基本思想是在待排序的 n 个元素中任取一个元素（通常取第一个元素）作为基准，把该元素放人最终位置后，整个数据序列被基准分割成两个子序列，所有小于基准的元素放置在前子序列中，所有大于基准的元素放置在后子序列中，并把基准排在这两个子序列的中间，这个过程称为划分。然后对两个子序列分别重复上述过程，直到每个子序列内只有一个元素或空为止。

这是一种二分法思想，每次将整个无序序列一分为二。归位一个元素，对两个子序列采用同样的方式进行排序，直到子序列的长度为1或0为止。（摘自算法分析与设计第二版 有删改）

b.代码 

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]#轴
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)
s = list(map(float,input("输入用空格分隔的数字：").split()))#
print(quick_sort(s))

 

c.复杂度

时间复杂度最好情况O(nlog2n),

时间复杂度最坏情况O(n^2),

时间复杂度平均情况O(nlog2n),

空间复杂度最好情况O(log2n),

d.稳定性

不稳定

2.插入排序

a.原理 

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

b.代码

def insert_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr
 
arr = [3, 5, 2, 4, 1]
print(insert_sort(arr))

c.复杂度

时间复杂度最好情况O(n),

时间复杂度最坏情况O(n^2),

时间复杂度平均情况O(n^2),

空间复杂度最好情况O(1),

d.稳定性

稳定

3.冒泡排序

a.原理 

重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成

b.代码 

def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
 
arr = [3, 5, 2, 4, 1]
print(bubble_sort(arr))

c.复杂度

时间复杂度最好情况O(n),

时间复杂度最坏情况O(n^2),

时间复杂度平均情况O(n^2),

空间复杂度最好情况O(1),

d.稳定性

稳定

4.希尔排序

a.原理

希尔排序是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

b.代码 

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr
 
arr = [3, 5, 2, 4, 1]
print(shell_sort(arr))

c.复杂度

时间复杂度最好情况,

时间复杂度最坏情况,

时间复杂度平均情况O(n^1.3),

空间复杂度最好情况O(1),

d.稳定性

稳定

5.选择排序

a.原理 

选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法

b.代码 

def selection_sort(arr):
    for i in range(len(arr)):
        min_index = i
        for j in range(i + 1, len(arr)):
            if arr[min_index] > arr[j]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr
 
arr = [3, 5, 2, 4, 1]
print(selection_sort(arr))

c.复杂度

时间复杂度最好情况O(n^2),

时间复杂度最坏情况O(n^2),

时间复杂度平均情况O(n^2),

空间复杂度最好情况O(1),

d.稳定性

稳定

6.堆排序

a.原理 

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

发明人：罗伯特·弗洛伊德

b.代码 

def heap_sort(arr):
    n = len(arr)
    # 建立大顶堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # 将堆顶元素与末尾元素交换，并重新调整大顶堆
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr
 
def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[largest] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
 
arr = [3, 5, 2, 4, 1]
print(heap_sort(arr))

c.复杂度

时间复杂度最好情况O(nlog2n),

时间复杂度最坏情况O(nlog2n),

时间复杂度平均情况O(nlog2n),

空间复杂度最好情况O(1),

d.稳定性

不稳定

7.归并排序

a.原理 

归并排序的基本思想是首先将 a [0.. n 一1］看成 n 个长度为1的有序表，将相邻的 k ( k ≥2）个有序子表成对归并，得到 n / k 个长度为 k 的有序子表：然后再将这些有序子表继续归并，得到 n /k2个长度为 k 的有序子表，如此反复进行下去，最后得到一个长度为 n 的有序表。由于整个排序结果放在一个数组中，所以不需要特别地进行合并操作。若 k =2，即归并是在相邻的两个有序子表中进行的，称为二路归并排序。若 k >2，即归并操作在相邻的多个有序子表中进行，则叫多路归并排序。（摘自算法分析与设计第二版）

b.代码 

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        merge_sort(left)
        merge_sort(right)
 
        i = j = k = 0
 
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1
 
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
 
        while j < len(right):
            arr[k] = right[j]
            j+= 1
            k += 1
 
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print(arr)
 

c.复杂度

时间复杂度最好情况O(nlog2n),

时间复杂度最坏情况O(nlog2n),

时间复杂度平均情况O(nlog2n),

空间复杂度最好情况O(n),

d.稳定性

稳定