排序 -- 选择/插入

聊聊排序吧

• 冒泡排序

• 选择排序

• 插入排序

• 快速排序

• 归并排序

• 计数排序

• 桶排序

• 堆排序

本篇 选择排序与插入排序

这俩兄弟放一起再合适不过了，排序的思路类似
将原始数组划分为有序数组与无序数组，增加有序数组或者说减少无序数组，直到无序数组为0

---

选择排序

1. 概念
   从无序数组中选择最小的放到有序数组的最后
2. 实现

private void doSort(int[] arr, int len) {

    if (len < 2) return;
    for (int i = 0; i < len; i++) {
        int j = i;
        int minPos = j;
        int tmp = arr[j];
        // find the smallest data
        while (j < len - 1) {
            if (arr[j + 1] < tmp) {
                minPos = j + 1;
                tmp = arr[j + 1];
            }
            j++;
        }
        // swap arr[maxPos] arr[i]
        if (minPos != i) {
            int xtmp = arr[i];
            arr[i] = arr[minPos];
            arr[minPos] = xtmp;
        }
    }
    System.out.println(Arrays.toString(arr));
}

• 选择排序是原地排序算法（除个别交换所需空间外），O(1)的空间复杂度
• 选择排序不是稳定排序，涉及到了非相邻元素的直接交换（存在无序数组中的第一位跟无序数组中最小元素交换的可能）
• 不管数据情况如何，选择排序都会把所有比较都走完，所以其三者的时间复杂度是一样的，都是O(N^2)

名称	原地	稳定	最好	最坏	平均
选择排序	是	否	O(N^2)	O(N^2)	O(N^2)

插入排序

• 概念
  从无序数组中取第一个元素插入到有序数组中，且保持有序
• 实现

private void doSort(int[] arr, int len) {
    if (len < 2) return;
    int tmp, j;
    for (int i = 1; i < len; i++) {
        tmp = arr[i];
        j = i - 1;
        while (j > -1 && arr[j] > tmp) {
            // swap arr[j] arr[j + 1]
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = tmp;
    }
    System.out.println(Arrays.toString(arr));
}

• 原地
• 稳定
• 当数组有序的时候，内循环只有一次，等于遍历一次，最好为O(N)；数组逆序时，就跟最坏情况下的冒泡排序类似了 -- O(N^2)

名称	原地	稳定	最好	最坏	平均
插入排序	是	是	O(N)	O(N^2)	O(N^2)