选择排序

Author Avatar
Brian Lee 8月 01, 2018
  • 在其它设备中阅读本文章

《Algorithm》(Sedgewick)笔记:选择排序


原理

  1. 找到数组中最小的那个元素
  2. 将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)
  3. 在剩下的元素中找到最小的元素,将它与第二个元素交换位置
  4. 直到将整个数组排序

复杂度

时间复杂度

$O(n^2)$

空间复杂度

$O(1)$


图示

插入排序


代码

public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (less(a[j], a[min]))
                    min = j;
            }
            exch(a, i, min);
        }
    }

特点

运行时间和输入无关

有序数组或值全部相等的数组和一个元素随机排列的数组所用的排序时间一样长。

数据移动最少

每次交换都会改变两个数组元素的值,因此选择排序用了N次交换,交换次数和数组的大小是线性关系。其他任何排序算法都不具备这个特性。


源码

https://github.com/XutongLi/Algorithm-Learn/blob/master/src/S2_Sorting/S2_1_2_Selection_Sort/Selection.java


本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/08/01/selectionSort/