python--排序总结

1.快速排序

a.原理

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

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

b.代码 

def quick_sort(arr):if len(arr) <= 1:return arrpivot = 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))

 

2.插入排序

a.原理 

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

b.代码

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

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 arrarr = [3, 5, 2, 4, 1]
print(bubble_sort(arr))

4.希尔排序

a.原理

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

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

b.代码 

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

5.选择排序

a.原理 

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

b.代码 

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

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 arrdef heapify(arr, n, i):largest = il = 2 * i + 1r = 2 * i + 2if l < n and arr[largest] < arr[l]:largest = lif r < n and arr[largest] < arr[r]:largest = rif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)arr = [3, 5, 2, 4, 1]
print(heap_sort(arr))

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

有待补充。