📚选择排序和插入排序区别-DS笔记

选择排序法

• A[i...n)未排序，A[0...i)已排序

• A[i...n]中最小值要放到A[i]的位置

  

• 复杂度 \(O(n^2)\)

  第一层循环n次

  第二层循环：i=0，n次；i=1，n-1次......i=n-1，1次。即1+2+3+...+n

  public static void sort(int[] arr) {    for (int i = 0; i < arr.length; i++) {        int minIdx = i;        // 选择A[i...n]中的最小值的索引        for (int j = i; j < arr.length; j++) {            if (arr[j] < arr[minIdx])                minIdx = j;        }        swap(arr, i, minIdx);    }}/* 使用带约束的泛型 */public static <E extends Comparable<E>> void sort(E[] arr) {        for (int i = 0; i < arr.length; i++) {            int minIdx = i;            for (int j = i; j < arr.length; j++) {                if (arr[j].compareTo(arr[minIdx]) < 0)                    minIdx = j;            }            swap(arr, i, minIdx);        }}

  比较引用类型必须要实现Comparable 接口！

插入排序

• A[i...n)未排序，A[0...i)已排序

  将arr[i]插入适当的位置

• 整体复杂度 \(O(n^2)\)

  对于有序数组，插入排序的复杂度是\(O(n)\)

public <E extends Comparable<E>> void insertSort(E[] arr) {    for (int i = 0; i < arr.length; i++) {        // 将arr[i]插入适当的位置        for (int j = i; j-1 >= 0; j--)            if (arr[j].compareTo(arr[j-1]) < 0)                swap(arr, j, j-1);         	else break;    }}/* 小优化 */public <E extends Comparable<E>> void insertSort2(E[] arr) {    for (int i = 0; i < arr.length; i++) {        int t = arr[i];  // 暂存arr[i]        int j;        for (j = i; j-1>=0 && t.comparaTo(arr[j-1]) < 0) {            arr[j] = arr[j-1];  // 向后移动元素        }        arr[j] = t;    }}

区别：

选择排序：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

插入排序：将元素逐个插入到有序排列之中，其特点是要不断的移动数据，空出一个适当的位置，把待插入的元素放到里面去