数据结构 排序算法

时间：2017/3/14 13:31:30

参考:

• 数据结构与算法分析（Java语言描述）第三版

排序算法

1. 冒泡排序 算法描述：依次比较数组中的元素，如果左边的比右边的大，则交换位置，一轮结束后会把最大的元素移动到数组的最右边。然后继续下一轮。
   时间复杂度： n^2
   稳定性： 稳定
2. 插入排序
   算法描述： 前 n（轮数 + 1）个元素已经排序，把第 n + 1 个元素插入已经排序的数组中。
   时间复杂度： 最后情况 O(n)，最坏情况 O(n^2)。总体 O(n^2)。
   稳定性： 稳定
   特点： 当数据基本排序排序的时候，内层循环执行的次数较少基本能达到 O(n) 的时间复杂度。
3. 选择排序
   算法描述： 每次从剩余的未排序的元素中选取最小的，和第 n（轮数）个元素交换位置。
   时间复杂度： O(n^2)
   稳定性： 不稳定
4. 归并排序
   算法描述： 把一个大数组从中间分隔成两个小数组，递归分隔，直到数组的长度为一。分隔完成之后，开始递归向上依次完成两个有序数组的合并。
   代码：链表归并 Sort List
   时间复杂度：O(nLogn)
   特点：时间稳定，需要额外空间进行数组和并。
5. 快速排序
   算法描述：从数组选取一个元素 n，把比 n 小的放在数组左边，比 n 大的放在数组右边，然后递归排序比 n 小的部分和比n 大的部分。。
   代码： Quick Sort
   时间复杂度：最坏情况 O(n^2), 一般情况 O(nlogn)
   特点：算法性能受每次所选的 n 的影响，选择越接近中位数效率越高。
6. 基数排序
   算法描述： 使用数组表示数字以及数字出现的次数，如 a[100] = 10 表示 100 出现 10 次，遍历数组即可拿到已经排序的数组。
   代码: Radix sort
   时间复杂度： O(n)
   特点： 适用于排序数据在已知的小范围之内的情况。
7. 堆排序
   算法描述： 把数据构造成最大堆或最小堆，然后依次删除对顶元素直到堆空为止，此时删除元素的顺序就是排序的顺序。
   代码：
   时间复杂度： O(nlog(n))