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.稳定性
稳定
