时间:2021-05-22
排序算法,下面算法均是使用Python实现:
插入排序
原理:循环一次就移动一次元素到数组中正确的位置,通常使用在长度较小的数组的情况以及作为其它复杂排序算法的一部分,比如mergesort或quicksort。时间复杂度为 O(n2) 。
# 1nd: 两两交换def insertion_sort(arr): for i in range(1, len(arr)): j = i while j >= 0 and arr[j-1] > arr[j]: arr[j], arr[j-1] = arr[j-1], arr[j] j -= 1 return arr# 2nd: 交换,最后处理没交换的def insertion_sort2(arr): for i in range(1, len(arr)): j = i-1 key = arr[i] while j >= 0 and arr[j] > key: arr[j+1] = arr[j] j -= 1 arr[j+1] = key return arr# 3nd: 加速版本,利用已经排好了序的进行二分查找def insertion_sort3(seq): for i in range(1, len(seq)): key = seq[i] # invariant: ``seq[:i]`` is sorted # find the least `low' such that ``seq[low]`` is not less then `key'. # Binary search in sorted sequence ``seq[low:up]``: low, up = 0, i while up > low: middle = (low + up) // 2 if seq[middle] < key: low = middle + 1 else: up = middle # insert key at position ``low`` seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:] return seq# 4nd: 原理同上,使用bisectimport bisectdef insertion_sort4(seq): for i in range(1, len(seq)): bisect.insort(seq, seq.pop(i), 0, i) # 默认插在相同元素的左边 return seq选择排序
原理:每一趟都选择最小的值和当前下标的值进行交换,适用在大型的数组,时间复杂度为 O(n2)
# 1nd: fordef select_sort(seq): for i in range(0, len(seq)): mi = i for j in range(i, len(seq)): if seq[j] < seq[mi]: mi = j seq[mi], seq[i] = seq[i], seq[mi] return seq# 2nd: mindef select_sort2(seq): for i, x in enumerate(seq): mi = min(range(i, len(seq)), key=seq.__getitem__) seq[i], seq[mi] = seq[mi], x return seq冒泡排序
原理:比较数组中两两相邻的数,如果第一个大于第二个,就进行交换,重复地走访过要排序的数列,达到将最小的值移动到最上面的目的,适用于小型数组,时间复杂度为O(n2)
def bubble_sort(seq): for i in range(len(seq)): for j in range(len(seq)-1-i): if seq[j] > seq[j+1]: seq[j], seq[j+1] = seq[j+1], seq[j] return seqdef bubble_sort2(seq): for i in range(0, len(seq)): for j in range(i + 1, len(seq)): if seq[i] > seq[j]: seq[i], seq[j] = seq[j], seq[i] return seq快速排序
原理:从数组中选择pivot,分成两个数组,一个是比pivot小,一个是比pivot大,最后将这两个数组和pivot进行合并,最好情况下时间复杂度为O(n log n),最差情况下时间复杂度为O(n2)
def quick_sort(seq): if len(seq) >= 1: pivot_idx = len(seq)//2 small, large = [], [] for i, val in enumerate(seq): if i != pivot_idx: if val <= seq[pivot_idx]: small.append(val) else: large.append(val) quick_sort(small) quick_sort(large) return small + [seq[pivot_idx]] + large else: return seq归并排序
原理:归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
# 1nd: 将两个有序数组合并到一个数组def merge(left, right): i, j = 0, 0 result = [] while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result += left[i:] result += right[j:] return resultdef merge_sort(lists): if len(lists) <= 1: return lists num = len(lists) / 2 left = merge_sort(lists[:num]) right = merge_sort(lists[num:]) return merge(left, right)# 2nd: use mergefrom heapq import mergedef merge_sort2(m): if len(m) <= 1: return m middle = len(m) // 2 left = m[:middle] right = m[middle:] left = merge_sort(left) right = merge_sort(right) return list(merge(left, right))堆排序
原理:堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。平均时间复杂度为O(n logn)
# 1nd: normaldef swap(seq, i, j): seq[i], seq[j] = seq[j], seq[i]# 调整堆def heapify(seq, end, i): l = 2 * i + 1 r = 2 * (i + 1) ma = i if l < end and seq[i] < seq[l]: ma = l if r < end and seq[ma] < seq[r]: ma = r if ma != i: swap(seq, i, ma) heapify(seq, end, ma)def heap_sort(seq): end = len(seq) start = end // 2 - 1 # 创建堆 for i in range(start, -1, -1): heapify(seq, end, i) for i in range(end - 1, 0, -1): swap(seq, i, 0) heapify(seq, i, 0) return seq# 2nd: use heapqimport heapqdef heap_sort2(seq): """ Implementation of heap sort """ heapq.heapify(seq) return [heapq.heappop(seq) for _ in range(len(seq))]希尔排序
原理:希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
def shell_sort(seq): count = len(seq) step = 2 group = count // step while group > 0: for i in range(0, group): j = i + group while j < count: k = j - group key = seq[j] while k >= 0: if seq[k] > key: seq[k + group] = seq[k] seq[k] = key k -= group j += group group //= step return seq区别
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
python算法学习之计数排序实例复制代码代码如下:#-*-coding:utf-8-*-def_counting_sort(A,B,k):"""计数排序,伪码
本文实例为大家分享了python实现排序算法的具体代码,供大家参考,具体内容如下一、冒泡排序defbububle_sort(alist):"""冒泡排序(稳定|
本文实例总结了python选择排序算法。分享给大家供大家参考。具体如下:代码1:defssort(V):#Visthelisttobesortedj=0#jis
本文实例讲述了Python实现的插入排序,冒泡排序,快速排序,选择排序算法。分享给大家供大家参考,具体如下:#!/usr/bin/python#coding:u
本文所述的Python实现冒泡,插入,选择排序简单实例比较适合Python初学者从基础开始学习数据结构和算法,示例简单易懂,具体代码如下:#-*-coding: