数据结构排序算法有哪些常用的

Question

如题所述

Answer 1

最常用的是快速排序，基数排序，计数排序，归并排序，堆排序，（偶尔还有插入排序）
都有各自的应用，快排就是单纯的快，但是特殊数据下复杂度会退化
基数排序可以配合一些特定的算法，譬如后缀数组的构建
计数排序简单且常用，通常排序值域小但是数据量大的情况
归并直接用来排序并不多，但是可以用来求解一些其他问题，本身的思想也非常重要，有很多拓展的算法（不是排序算法）
堆排序胜在稳定，不论数据如何最坏都是O(nlogn)，一般情况比快速排序慢些，但是极端情况下表现十分优秀，常用来配合快速排序，优化其稳定性
插入排序适合极少量数据的排序（几个到十几个），速度要比这些高级算法快一些

Answer 2

简单选择排序的基本思想：比较+交换。

从待排序序列中，找到关键字最小的元素；

如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；

从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。
因此我们可以发现，简单选择排序也是通过两层循环实现。
第一层循环：依次遍历序列当中的每一个元素
第二层循环：将遍历得到的当前元素依次与余下的元素进行比较，符合最小元素的条件，则交换。