排序类型	时间复杂度
选择排序(Selection Sort)	$$O(n^2)$$
合并/归并排序（Merge Sort）	$$O(n\log n)$$
快速排序(Quick Sort)	平均情况$$O(n\log n)$$最糟情况$$O(n^2)$$
计数排序(Counting Sort)	$$O(n+k)$$

一、选择排序

来自《算法图解》一书

def findSmallest(arr):smallest = arr[0]  # 存储最小值smallest_index = 0  # 存储最小值索引for i in range(1,len(arr)):if arr[i] < smallest:smallest = arr[i]smallest_index = ireturn smallest_indexdef selectionSort(arr):newArr = []for i in range(len(arr)):smallest_ind = findSmallest(arr)newArr.append(arr.pop(smallest_ind))return newArrprint(selectionSort([5,3,6,2,10,58,23,31,9,14,4,46,25,35,1,56,29,20,18,43,40,36,49]))

结果：

二、合并/归并排序

参考： Python实现合并排序（归并排序）（一文看懂）

1. 将一个序列从中间位置分成两个序列；
2. 在将这两个子序列按照第一步继续二分下去；
3. 直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。

def merge(arr_a, arr_b):arr_c = []i = j = 0while i < len(arr_a) and j < len(arr_b):if arr_a[i] < arr_b[j]:arr_c.append(arr_a[i])i += 1else:arr_c.append(arr_b[j])j += 1if i == len(arr_a):return arr_c + arr_b[j:]else:return arr_c + arr_a[i:]def mergeSort(arr):if len(arr) < 2:return arrmiddle = len(arr) // 2left = mergeSort(arr[:middle])right = mergeSort(arr[middle:])return merge(left, right)print(mergeSort([23,12,3,7,5,32,37,29,15,24,19]))

结果：

三、快速排序

来自《算法图解》一书

1. 选择基准值
2. 将数组分成两个子数组：小于基准值的元素和大于基准值的元素
3. 对这两个子数组进行快速排序

def quickSort(arr):if len(arr) < 2:return arr  # 基线条件：为空或只包含一个元素的数组是“有序”的else:pivot = arr[0]  # 递归条件，基准值less = [i for i in arr[1:] if i <= pivot]  # 由所有小于基准值的元素组成的子数组greater = [i for i in arr[1:] if i > pivot]  # 由所有大于基准值的元素组成的子数组return quickSort(less) + [pivot] + quickSort(greater)print(quickSort([10,28,2,36,45,23,14,39,32,24]))

结果：

四、计数排序

参考： python实现【计数排序】(Count Sort)

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为i的元素出现的次数，存入count_nums数组的第i项；
3. 将count_nums数组中从左向右每一个计数不为0的值依次填充进最终的res排序数组中。

def countingSort(arr):max_value = max(arr)res = []count_nums = [0 for i in range(max_value + 1)]for num in arr:count_nums[num] += 1for i in range(len(count_nums)):if count_nums[i] != 0:# res.extend(count_nums[i] * [i]) # 元素i有 count_nums[i]个，添加入最终的排序数组res += count_nums[i] * [i]return resprint(countingSort([12,30,2,29,23,18,5,7,25,15,8]))

结果：