排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    各种内部排序按所采用的基本思想(策略)可分为:插入排序、交换排序、选择排序、归并排序和基数排序,它们的基本策略是:

1、插入排序
:依次将无序序列中的一个记录,按关键字值的大小插入到已排好序一个子序列的适当位置,直到所有的记录都插入为止。具体的方法有:直接插入、表插入、2-路插入和shell排序。

2、交换排序
:对于待排序记录序列中的记录,两两比较记录的关键字,并对反序的两个记录进行交换,直到整个序列中没有反序的记录偶对为止。具体的方法有:冒泡排序、快速排序。

3、选择排序:不断地从待排序的记录序列中选取关键字最小的记录,放在已排好序的序列的最后,直到所有记录都被选取为止。具体的方法有:简单选择排序、堆排序。

4、归并排序:利用“归并”技术不断地对待排序记录序列中的有序子序列进行合并,直到合并为一个有序序列为止。

5、基数排序
:按待排序记录的关键字的组成成分(“位”)从低到高(或从高到低)进行。每次是按记录关键字某一“位”的值将所有记录分配到相应的桶中,再按桶的编号依次将记录进行收集,最后得到一个有序序列。

   常见的内部排序算法有:插入排序(insertion sorting)、希尔排序(Shell Sort)、选择排序(Selection
sort)、堆排序(Heapsort)、冒泡排序(Bubble Sort)、快速排序(quick sort)、归并排序(Merge
sort)、基数排序(Radix sort)。

 
 下图列出了各种排序算法的时间复杂度、空间复杂度和稳定性情况。其中,空间复杂度仅列举了平均情况下的复杂度,由于希尔排序的时间复杂度依赖于增量函数,所以这里无法准确地给出其时间复杂度。

技术
©2019-2020 Toolsou All rights reserved,
Vue页面跳转传递参数及接收份额已超宁德时代!LG化学确认将分拆电池业务部门Keras训练数据加载实现小结Vue + Element-ui的下拉框el-select获取额外参数Element-UI二次封装实现TreeSelect 树形下拉选择组件科幻成真!“三体”被发现了(精华)2020年7月15日 微信小程序 template的使用unity 获取小车速度及前进或者后退Java Thread之Sleep()使用方法总结雷军:两年前和卢伟冰喝酒到凌晨三点 钦佩其工作热情和能力