选择排序

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

将数组arr从小到大进行排序：

const arr = [3, 4, 2, 7, 5, 9]

如图我们先找出arr中最小的元组把它放到一个新数组的开头，然后再找出arr中剩余元素中的最小值放到新数组的末尾，以此类推。像上面这样虽然完成了排序，但是这样排序的过程中创建了一个新的数组，占用了额外的空间。

java版：

public class SelectionSort {
    private SelectionSort() {}

    public static <T extends Comparable<T>> void sort(T[] arr) {
        for (int i = 0, len = arr.length; i < len; i ++)
            for (int j = i; j < len; j ++)
                if (arr[j].compareTo(arr[i]) < 0) swap(arr, i, j);
    }

    private static <T> void swap(T[] arr, int i, int j) {
        T t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        Integer[] arr = {3, 4, 2, 7, 5, 9};
        SelectionSort.sort(arr);

        for (int i: arr) System.out.print(i + " ");
    }
}

JS版：

const arr = [3, 4, 2, 7, 5, 9]

function sort(arr) {
  for (let i = 0, len = arr.length; i < len; i++) {
    for (let j = i; j < len; j++) {
      if (arr[j] < arr[i]) {
        swap(arr, i, j)
        break
      }
    }
  }
}

function swap(arr, i, j) {
  let t = arr[i]
  arr[i] = arr[j]
  arr[j] = t
}

sort(arr)

console.log(arr) // [2, 3, 4, 5, 7, 9]

JS中还有个更简单的排序方法sort()

const arr = [3, 4, 2, 7, 5, 9]
arr.sort()
console.log(arr)

// 如果想将数组降序排序
arr.sort((a, b) => b - a)
console.log(arr)

上述排序算法中我们使用了两层for循环，最内层的for执行次数为：

当i = 0的时候，内层for循环执行了n次

当i = 1的时候，内层for循环执行了n-1次

当i = 2的时候，内层for循环执行了n-2次

依次类推，当i = n - 1的时候，内层for循环只运行了1次

可得最内层for循环总的循环次数为：

n + n - + n - 2 + ... + 3 + 2 + 1

可以看出上述式子是对一个等差数列求和，我们可以运用等差数列求和公式来计算，等差数列求和公式：((1+n) * n) / 2

展开后可得 1/2n^2+1/2n，对于复杂度分析来说常数项可以忽略，低阶项也要忽略掉，因为复杂度描述的是随着n的增大，我们整个算法的性能趋势，这个新能趋势是被高阶项决定的。

插入排序

插入排序(InsertionSort)，一般也被称为直接插入排序。

对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

这里我们以数组Int arr[] = {3, 2, 1, 7}为例

Java版本：

public class InsertionSort {
    private InsertionSort() {}
    public static <T extends Comparable<T>> void sort(T[] arr) {
        for (int i = 0, len = arr.length; i < len; i++)
            for (int j = i; j - 1 >= 0 && arr[j].compareTo(arr[j - 1]) < 0; j--)
                swap(arr, j, j - 1);
    }

    private static <T> void swap(T[] arr, int i, int j) {
        T t = arr[i];
        arr[ik'd'j'l] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
       Integer arr[] = {3, 2, 1, 7};
       InsertionSort.sort(arr);
       for (int n : arr) System.out.print(n + " ");
       System.out.println();
    }
}

选择排序和插入排序的区别

如下图，当i=3时，选择排序[0, 3)的位置是整个数组中最小的元素

插入排序处理的遍历到的前四个元素，只是暂时的排序，这个结果并不意味着最终排好序的结果。