上一篇详述了冒泡排序及其优化, 有兴趣的可以看看:
如何优化冒泡排序?
一, 选择排序(SelectionSort)
算法思想: 首先在未排序序列中找到最小 (大) 元素, 存放到排序序列的起始位置, 然后, 再从剩余未排序元素中继续寻找最小 (大) 元素, 然后放到已排序序列的末尾. 以此类推, 直到所有元素均排序完毕.
排序过程:(默认升序)
从原序列中找到最小值, 与数组第一个元素交换;
除第一个元素外, 从剩下未排序的序列中找到最小值, 与数组第二个元素交换;
共 N-1 趟, 每趟都找到未排序的最小值, 放到已排序的序列后面.
如图所示, 每一趟找到未排序的最小值, 并放到有序序列的后面(即当前趟对应于数组中的第几个元素).
java 实现选择排序:
- private static <T extends Comparable<? super T>> void selectionSort(T[] nums) {
- if (null == nums || nums.length == 0) {
- throw new RuntimeException("数组为 null 或长度为 0");
- }
- int length = nums.length;
- int minValueIndex = 0;
- T temp = null;
- for (int i = 0; i < length - 1; i++) {
- minValueIndex = i;
- for (int j = i + 1; j < length; j++) {
- if (nums[j].compareTo(nums[minValueIndex]) < 0) {
- minValueIndex = j;
- }
- }
- if (minValueIndex != i) {
- temp = nums[i];
- nums[i] = nums[minValueIndex];
- nums[minValueIndex] = temp;
- }
- }
- }
时间, 空间复杂度及稳定性分析:
最好时间复杂度: 最好情况是输入序列已经升序排列, 需要比较 n*(n-1)/2 次, 但不需要交换元素, 即交换次数为: 0; 所以最好时间复杂度为 O(n^2).
最坏时间复杂度: 最坏情况是输入序列是逆序的, 则每一趟都需要交换. 即需要比较 n*(n-1)/2 次, 元素交换次数为: n-1 次. 所以最坏时间复杂度还是 O(n^2).
平均时间复杂度: O(n^2).
空间复杂度: 只用到一个临时变量, 所以空间复杂度为 O(1);
稳定性: 不稳定排序. 如序列 3,5,3,1. 第一次交换结果为 1,5,3,3, 我们发现原序列的第一个 3 排在了第二个 3 的后面.
二, 插入排序(InsertSort)
算法思想: 通过构建有序序列, 对于未排序数据, 在已排序序列中从后向前扫描, 找到相应位置并插入. 插入排序因而在从后向前扫描过程中, 需要反复把已排序元素逐步向后挪位, 为最新元素提供插入空间.
排序过程:(默认升序)
InsertionSort 和打扑克牌时, 从牌桌上逐一拿起扑克牌, 在手上排序的进程相同.
举例:
Input: {4, 3, 8, 5, 2, 6, 1, 7}.
首先拿起第一张牌, 手上有 {4}.
拿起第二张牌 3, 把 3insert 到手上的牌 {4}, 得到 {3 ,4}.
拿起第三张牌 8, 把 8 insert 到手上的牌 {3,4 }, 得到 {3 ,4,8}.
以此类推.
插入排序由 N-1 趟排序组成. 对于 p=1 到 N-1 趟排序后, 插入排序保证从位置 0 到位置 p 上的元素为已排序状态. 即插入排序利用了从位置 0 到 p-1 位置上已经有序的条件, 将位置 p 上的元素向前查找适当的位置插入此元素.
如图所示: 在第 p 趟, 我们将位置 p 上的元素向左移动, 直到它在前 p+1 个元素 (包括当前位置的元素) 中的正确位置被找到.
java 实现插入排序
- private static <T extends Comparable<? super T>> void insertSort(T[] nums) {
- if (null == nums || nums.length == 0) {
- throw new RuntimeException("数组为 null 或长度为 0");
- }
- int length = nums.length;
- T temp = null;
- int i = 0;
- for (int p = 1; p < length; p++) {
- temp = nums[p];
- for (i = p; i > 0 && (temp.compareTo(nums[i - 1]) < 0); i--) {
- nums[i] = nums[i - 1];
- }
- nums[i] = temp;
- }
- }
时间, 空间复杂度及稳定性分析:
最好时间复杂度: 最好情况就是, 序列已经是升序排列了, 在这种情况下, 需要进行的比较操作需 n-1 次即可. 即最好时间复杂度为 O(n).
最坏时间复杂度: 最坏情况就是, 序列是降序排列, 那么总共需要 n(n-1)/2 次比较; 移动次数 (赋值操作) 是比较次数减去 n-1 次(因为每一次循环的比较都比赋值多一次, 共 n-1 次循环), 即 n(n-1)/2 - (n-1); 所以最坏时间复杂度为 O(n^2).
平均时间复杂度: O(n^2).
空间复杂度: 只用到一个临时变量, 所以空间复杂度为 O(1);
稳定性: 稳定.
三, 总结
选择排序的主要优点与数据移动有关. 如果某个元素位于正确的最终位置上, 则它不会被移动. 选择排序每次交换一对元素, 它们当中至少有一个将被移到其最终位置上, 因此对 n 个元素的表进行排序总共进行 n-1 次交换. 在所有的完全依靠交换去移动元素的排序方法中, 选择排序属于非常好的一种. 选择排序最好, 最坏时间复杂度都为 O(n^2), 空间复杂度为 O(1), 属于不稳定排序.
插入排序不适合对于数据量比较大的排序应用. 但是, 如果需要排序的数据量很小, 例如, 量级小于千; 或者若已知输入元素大致上按照顺序排列, 那么插入排序还是一个不错的选择. 插入排序最好时间复杂度为 O(n), 最坏时间复杂度为 O(n^2), 空间复杂度为 O(1), 属于稳定排序.
来源: https://www.cnblogs.com/9dragon/p/10710735.html