建设厅网站举报,焦作网站建设哪家便宜,做导航网站,帮别人做网站的公司1.快速排序
a.原理 快速排序的基本思想是在待排序的 n 个元素中任取一个元素#xff08;通常取第一个元素#xff09;作为基准#xff0c;把该元素放人最终位置后#xff0c;整个数据序列被基准分割成两个子序列#xff0c;所有小于基准的元素放置在前子序列中#xff0…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) 有待补充。
