python怎么读（python range函数）

十大排序包括：冒泡、选择、插入、希尔、归并、快速、堆、计数、桶、基数。

冒泡排序

原理：它重复地访问要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。“冒泡”顾名思义，大元素会经由交换像一个泡泡一样慢慢"浮"到数列的顶端（升序排列）。

优化：冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

图：

代码：

# （升序）冒泡排序 def bubble_sort(arr): for i in range(len(arr)-1, 0, -1): for j in range(i): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr def bubble_sort_flag(arr): # 这是改进后的冒泡排序，如果一次排序中都没有交换，则代表已经排好序，以后则不需要再排序了 for i in range(len(arr)-1, 0, -1): exchange_flag = 0 for j in range(i): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] exchange_flag = 1 if exchange_flag == 0: break return arr if __name__ == __main__: arr = [2, 1, 9, 11, 10, 8, 7] arr_BS = bubble_sort(arr) arr_BSF = bubble_sort_flag(arr) print(arr_BS) print(arr_BSF)

选择排序

原理：

首先在未排序序列中找到最大元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最大元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

图：

代码：

# （升序）选择排序 def selection_sort(arr): for i in range(len(arr)-1, 0, -1): max_idx = i for j in range(i+1): if arr[j] > arr[max_idx]: max_idx = j arr[i], arr[max_idx] = arr[max_idx], arr[i] return arr if __name__ == __main__: arr = [2, 1, 9, 11, 10, 8, 7] arr_SS = selection_sort(arr) print(arr_SS)

插入排序

原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

图：

代码：

# （升序）插入排序 def insertion_sort(arr): for i in range(1, len(arr)): temp = arr[i] for j in range(i-1, -1, -1): if arr[j] > temp: arr[j+1] = arr[j] arr[j] = temp else: break return arr if __name__ == __main__: arr = [2, 1, 9, 11, 10, 8, 7] arr_IS = insertion_sort(arr) print(arr_IS)

希尔排序

归并排序

原理：分而治之。

分（divide）：将一个序列从中间分成两部分，这两部分再二分下去，直到所有子序列长度为1不能再分。

治（conquer）：用一个新的序列将两部分排好序的子序列合并在一起，使得这个新序列也有序。

图：

代码：

# （升序）归并排序 def merge(arr1, arr2): res = [] i, j = 0, 0 while i < len(arr1) and j < len(arr2): if arr1[i] <= arr2[j]: res.append(arr1[i]) i += 1 else: res.append(arr2[j]) j += 1 if i == len(arr1): while j < len(arr2): res.append(arr2[j]) j += 1 else: while i < len(arr1): res.append(arr1[i]) i += 1 return res def merge_sort(arr): if len(arr) <= 1: return arr mid = (len(arr)) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) if __name__ == __main__: arr = [14, 2, 34, 43, 21, 19] print(merge_sort(arr))

快速排序

原理：分而治之。快速排序应该算是在冒泡排序基础上的递归分治法。

在待排序的元素随机取一个元素，称为 "基准"（pivot）;重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

图：

代码：

# （升序）快速排序 import random def quick_sort(arr, i, j): if i >= j: return arr partition_idx = partition(arr, i, j) quick_sort(arr, i, partition_idx-1) quick_sort(arr, partition_idx+1, j) return arr # def partition(arr, i, j): # leetcode上面提交这个partition函数会超时,但实际上这种写法也是正确的 # pivot = arr[i] # while i < j: # while i < j and arr[j] >= pivot: # j -= 1 # arr[i] = arr[j] # while i < j and arr[i] <= pivot: # i += 1 # arr[j] = arr[i] # arr[j] = pivot # # return j def partition(nums, l, r): # leetcode提交这个partition函数不会超时 pivot = random.randint(l, r) nums[pivot], nums[r] = nums[r], nums[pivot] i = l - 1 for j in range(l, r): if nums[j] < nums[r]: i += 1 nums[j], nums[i] = nums[i], nums[j] i += 1 nums[i], nums[r] = nums[r], nums[i] return i if __name__ == __main__: arr = [11, 1, 9, 20, 16, 12, 7] arr_QS = quick_sort(arr, 0, len(arr)-1) print(arr_QS)

堆排序

计数排序

桶排序

基数排序

先写常用的，后面慢慢补充