基础排序法有哪些

登录注册

摘要：基础排序法有：1、选择排序，分为“简单选择排序”和“堆排序”；2、插入排序，分为“简单插入排序”和“希尔排序”；3、交换排序，分为“冒泡排序”和“快速排序”；4、归并排序；5、基数

基础排序法有：1、选择排序，分为“简单选择排序”和“堆排序”；2、插入排序，分为“简单插入排序”和“希尔排序”；3、交换排序，分为“冒泡排序”和“快速排序”；4、归并排序；5、基数排序。

基础排序法

排序

没有一种排序算法在任何情况下都是最优的，必须根据实际情况选择最优的算法来解决问题

算法稳定性：在一组待排序记录中，如果存在任意两个相等的记录 R 和 S，且在待排序记录中 R 在 S 前，如果在排序后 R 依然在 S 前，即它们的前后位置在排序前后不发生改变，则称为排序算法为稳定的

选择排序

简单选择排序

简单选择排序(Simple Selection Sort)是一种直观的排序算法，在未排序的序列中，选出最小的元素和序列的首位元素交换，接下来在剩下的未排序序列中再选出最小元素与序列的第二位元素交换，依次类推，最后形成从小到大的已排序序列

时间复杂度：O(N2)

堆排序

将无序的序列生成一个最大堆，将堆顶元素与最后一个元素对换位置，将剩下元素生成最大堆，依次进行元素交换并生成最大堆

时间复杂度：O(NlogN) 空间复杂度：O(1)

插入排序

简单插入排序

将待排序的一组序列分为已排好序和未排序的两个部分，初始状态时，已排序序列仅包含第一个元素，未排序序列中的元素为除了第一个以外N-1个元素；此后将未排序序列中的元素逐一插入到已排序的序列中。如此往复，经过N-1次插入后，未排序序列中元素个数为0，则排序完成

时间复杂度：O(N2) 稳定排序

希尔排序

将待排序的一组元素按一定间隔分为若干个序列，分别进行插入排序。开始时设置的"间隔"较大，在每轮排序中将间隔逐步减小，直到"间隔"为1，也就是最后一步是进行简单插入排序

时间复杂度：和增量序列的选取有关非稳定排序

交换排序

冒泡排序

对元素个数为 N 的待排序序列进行排序时，共进行N-1次循环。在第 k 次循环中，对从第1到第N-k个元素从前往后进行比较，每次比较相邻的两个元素，若前一个元素大于后一个元素，则两者互换位置，否则保持位置不变

时间复杂度：O(N2)

快速排序

将未排序元素根据一个作为基准的"主元"分为两个子序列，其中一个子序列的记录均大于主元，而另一个子序列均小于主元，然后递归地对这两个子序列用类似的方法进行排序

时间复杂度：O(Nlog2N)

归并排序

将大小为 N 的序列看成 N 个长度为1的子序列，接下来将相邻子序列两两进行归并操作，形成N/2(+1)个长度为2(或1)的有序子序列；然后再继续进行相邻子序列两两归并操作，如果一直循环，直到剩下1个长度为 N 的序列，则该序列为原序列完成排序后的结果

时间复杂度：O(Nlog2N) 空间复杂度：O(N)

基数排序

桶排序

如果已知 N 个关键字的取值范围是在 0 到 M-1 之间，而 M 比 N 小的多，则桶排序算法将关键字的每个取值建立一个"桶"，即建立 M 个桶，在扫描 N 个关键字时，将每个关键字放入相应的桶中，然后按桶的顺序收集一遍就自然有序了

基数排序

基数排序是桶排序的一种推广，它所考虑的待排记录包含不止一个关键字