Java各种排序算法总结

排序是程序开发中一种非常常见的操作，对一组任意的数据元素（或记录）经过排序操作后，就可以把他们变成一组按关键字排序的有序队列。 对一个排序算法来说，一般从下面 3 个方面来衡量算法的优劣： 1. 时间复杂度：它主要是分析关键字的比较次数和记录的移动次数。 2. 空间复杂度：分析排序算法中需要多少辅助内存。 3. 稳定性：若两个记录 A 和 B 的关键字值相等，但是排序后 A,B 的先后次序保持不变，则称这种排序算法是稳定的；反之，就是不稳定的。 就现有的排序算法来看，排序大致可分为内部排序和外部排序。如果整个排序过程不需要借助外部存储器（如磁盘等），所有排序操作都是在内存中完成，这种排序就被称为内部排序。 如果参与排序的数据元素非常多，数据量非常大，计算无法把整个排序过程放在内存中完成，必须借助于外部存储器（如磁盘），这种排序就被称为外部排序。 外部排序最常用算噶是多路归并排序，即将原文件分解称多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序，接下来再对多个有序的子文件进行归并排序。 就常用的内部排序算法来说，可以分为以下几类：  选择排序（直接选择排序，堆排序）  交换排序（冒泡排序，快速排序）  插入排序（直接插入排序，折半插入排序，Shell 排序）  归并排序  桶式排序  基数排序 Java 排序算法（二）：直接选择排序 直接选择排序的基本操作就是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完，它需要经过 n-1趟比较。算法不稳定，O(1)的额外的空间，比较的时间复杂度为 O(n^2)，交换的时间复杂度为 O(n)，并不是自适应的。在大多数情况下都不推荐使用。只有在希望减少交换次数的情况下可以用。 基本思想 n 个记录的文件的直接选择排序可经过 n-1 趟直接选择排序得到有序结果： ①初始状态：无序区为 R[1..n]，有序区为空。 ②第 1 趟排序 在无序区 R[1..n]中选出关键字最小的记录 R[k]，将它与无序区的第 1 个记录 R[1]交换，使R[1..1]和 R[2..n]分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。 …… ③第 i 趟排序 第 i 趟排序开始时，当前有序区和无序区分别为 R[1..i-1]和 R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第 1 个记录 R 交换，使 ...