1、选择排序算法

选择排序算法的核心思想是 从剩下的数组中选择最小的元素，然后和数组头部的元素交换，然后重复操作，根据其最多的操作次数，可以计算其时间复杂度为

快速排序算法的实现 - 图1

  1. 从数组中选择最小的元素
  2. 将最小的元素和数组的第1位元素交换
  3. 从剩下的元素中找到最小的元素
  4. 将最小的元素和第2位元素交换
  5. 从生效的元素中找到最小的元素
  6. 将最小的元素和第3位元素交换
  7. 重复上述流程，直到遍历完毕

快速排序算法的实现 - 图2

  1. **
  2.  * 选择排序法
  3.  *
  4.  * @apiNote 时间复杂度: O(n + (n-1) + ... + 1) = O(n^2)
  5.  */
  6. public class ChooseSort {
  8.   public static void main(String[] args) {
  9.     Integer[] numbers = ArrayUtils.generatorRandomArray(10, 100);
  10.     sort(numbers);
  11.     // 断言数组是升序的
  12.     assert SortUtils.isSorted(0, numbers);
  13.   }
  15.   private static void sort(Integer[] numbers) {
  16.     for (int i = 0; i < numbers.length; i++) {
  17.       // 省略，从 i开始到数组结尾知道最小元素的索引
  18.       Integer minIndex = findMin(i, numbers);
  19.       // 省略,交换数组中的i和j的元素数据
  20.       swap(i, minIndex, numbers);
  21.     }
  22.   }
  23. }

2、插入排序算法

插入排序的核心思想是从数组第二位开始，依次遍历将数据插入到前面的有序数组中，其执行的次数为 快速排序算法的实现 - 图3 其动画演示如下:

快速排序算法的实现 - 图4

/**
 * 插入排序法
 *
 * @apiNote 时间复杂度: O(n + (n-1) + (n-2) + ... + 1) = O(n^2)
 */
public class InsertSort {

  public static void main(String[] args) {
    Integer[] numbers = ArrayUtils.generatorRandomArray(10, 100);
    sort(numbers);
    // 断言数组是升序的
    assert SortUtils.isSorted(0, numbers);
  }

  private static void sort(Integer[] numbers) {
    int sortedIndex = 0;
    for (int i = 1; i < numbers.length; i++) {
      if (numbers[i] < numbers[sortedIndex]) {
        for (int tmp = i, j = sortedIndex; j >= 0; j--) {
          if (numbers[tmp] < numbers[tmp - 1]) {
            // 交换第tmp和tmp--位置的数据
            swap(tmp, --tmp, numbers);
          } else {
            break;
          }
        }
      }
      sortedIndex++;
    }
  }
}