郴州市住房建设局门户网站,深度网营销型网站建设,网络监控系统,网页设计与制作精品课程网站转载自 涨姿势#xff0c;图文带你了解 8 大排序算法
排序算法可以分为内部排序和外部排序#xff0c;内部排序是数据记录在内存中进行排序#xff0c;而外部排序是因排序的数据很大#xff0c;一次不能容纳全部的排序记录#xff0c;在排序过程中需要访问外存。
常见…转载自 涨姿势图文带你了解 8 大排序算法
排序算法可以分为内部排序和外部排序内部排序是数据记录在内存中进行排序而外部排序是因排序的数据很大一次不能容纳全部的排序记录在排序过程中需要访问外存。
常见的内部排序算法有插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
本文将依次介绍上述八大排序算法。
算法一插入排序 插入排序是一种最简单直观的排序算法它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。
算法步骤
1将第一待排序序列第一个元素看做一个有序序列把第二个元素到最后一个元素当成是未排序序列。
2从头到尾依次扫描未排序序列将扫描到的每个元素插入有序序列的适当位置。如果待插入的元素与有序序列中的某个元素相等则将待插入元素插入到相等元素的后面。点击这里了解常用的加密算法。
算法二希尔排序 希尔排序也称递减增量排序算法是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的 插入排序在对几乎已经排好序的数据操作时 效率高 即可以达到线性排序的效率 但插入排序一般来说是低效的 因为插入排序每次只能将数据移动一位
希尔排序的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录“基本有序”时再对全体记录进行依次直接插入排序。点击这里了解常用的加密算法。
算法步骤
1选择一个增量序列t1t2…tk其中titjtk1
2按增量序列个数k对序列进行k 趟排序
3每趟排序根据对应的增量ti将待排序列分割成若干长度为m 的子序列分别对各子表进行直接插入排序。仅增量因子为1 时整个序列作为一个表来处理表长度即为整个序列的长度。
算法三选择排序 选择排序(Selection sort)也是一种简单直观的排序算法。
算法步骤
1首先在未排序序列中找到最小大元素存放到排序序列的起始位置
2再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。
3重复第二步直到所有元素均排序完毕。 算法四冒泡排序 冒泡排序Bubble Sort也是一种简单直观的排序算法。它重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。点击这里了解常用的加密算法。
算法步骤
1比较相邻的元素。如果第一个比第二个大就交换他们两个。
2对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。
3针对所有的元素重复以上的步骤除了最后一个。
4持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 算法五归并排序 归并排序Merge sort是建立在归并操作上的一种有效的排序算法。该算法是采用分治法Divide and Conquer的一个非常典型的应用。
算法步骤
1. 申请空间使其大小为两个已经排序序列之和该空间用来存放合并后的序列
2. 设定两个指针最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾 算法六快速排序 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较但这种状况并不常见。事实上快速排序通常明显比其他Ο(n log n) 算法更快因为它的内部循环inner loop可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法Divide and conquer策略来把一个串行list分为两个子串行sub-lists。
算法步骤
1 从数列中挑出一个元素称为 “基准”pivot
2 重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作。
3 递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形是数列的大小是零或一也就是永远都已经被排序好了。虽然一直递归下去但是这个算法总会退出因为在每次的迭代iteration中它至少会把一个元素摆到它最后的位置去。 算法七堆排序 堆排序Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。
堆排序的平均时间复杂度为Ο(nlogn) 。
算法步骤
1创建一个堆H[0..n-1]
2把堆首最大值和堆尾互换
3把堆的尺寸缩小1并调用shift_down(0)目的是把新的数组顶端数据调整到相应位置
4 重复步骤2直到堆的尺寸为1 算法八基数排序
基数排序是一种非比较型整数排序算法其原理是将整数按位数切割成不同的数字然后按每个位数分别比较。由于整数也可以表达字符串比如名字或日期和特定格式的浮点数所以基数排序也不是只能使用于整数。点击这里了解常用的加密算法。
说基数排序之前我们简单介绍桶排序
算法思想是将阵列分到有限数量的桶子里。每个桶子再个别排序有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候桶排序使用线性时间Θn。但桶排序并不是 比较排序他不受到 O(n log n) 下限的影响。
简单来说就是把数据分组放在一个个的桶中然后对每个桶里面的在进行排序。
例如要对大小为[1..1000]范围内的n个整数A[1..n]排序
首先可以把桶设为大小为10的范围具体而言设集合B[1]存储[1..10]的整数集合B[2]存储 (10..20]的整数……集合B[i]存储( (i-1)*10 i*10]的整数i 12..100。总共有 100个桶。
然后对A[1..n]从头到尾扫描一遍把每个A[i]放入对应的桶B[j]中。 再对这100个桶中每个桶里的数字排序这时可用冒泡选择乃至快排一般来说任 何排序法都可以。
最后依次输出每个桶里面的数字且每个桶中的数字从小到大输出这 样就得到所有数字排好序的一个序列了。
假设有n个数字有m个桶如果数字是平均分布的则每个桶里面平均有n/m个数字。如果
对每个桶中的数字采用快速排序那么整个算法的复杂度是
O(n m * n/m*log(n/m)) O(n nlogn – nlogm)
从上式看出当m接近n的时候桶排序复杂度接近O(n)
当然以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中那就退化成一般的排序了。
前面说的几大排序算法 大部分时间复杂度都是On2也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现On的时间复杂度。但桶排序的缺点是
1首先是空间复杂度比较高需要的额外开销大。排序有两个数组的空间开销一个存放待排序数组一个就是所谓的桶比如待排序值是从0到m-1那就需要m个桶这个桶数组就要至少m个空间。
2其次待排序的元素都要在一定的范围内等等。 总结
各种排序的稳定性时间复杂度、空间复杂度、稳定性总结如下图 关于时间复杂度
(1)平方阶(O(n2))排序
各类简单排序直接插入、直接选择和冒泡排序
(2)线性对数阶(O(nlog2n))排序
快速排序、堆排序和归并排序
(3)O(n1§))排序§是介于0和1之间的常数。
希尔排序
(4)线性阶(O(n))排序
基数排序此外还有桶、箱排序。
关于稳定性
稳定的排序算法冒泡排序、插入排序、归并排序和基数排序
不是稳定的排序算法选择排序、快速排序、希尔排序、堆排序
