算法-选择排序和插入排序

选择排序的思想就是对n个数进行排序，我们只需要通过比较依次将最小的值放到数组的第0、1、2、3…个位置即可

/**
 * 选择排序 ,时间复杂第O(n^2)原地排序
    */
public static void selectSort(int[] data) {
    int tmp;
    for (int i = 0; i < data.length - 1; i++) {
        for (int j = i + 1; j < data.length; j++) {
            if (data[j] < data[i]) {
                tmp = data[j];
                data[i] = data[j];
                data[j] = tmp;
            }
        }
    }
}

插入排序算法就类似于我们打牌插排的过程，前面的已经排好序了，当后面来了一个新数据，依次从后向前与已经排好序的部分进行比较，然后选择合适的位置插入，java实现代码如下

/**
 * 插入排序 ,时间复杂第O(n^2)原地排序
 */
public static void insertSort(int[] data) {
    // 已排序完毕的最后一个数值的下标
    for (int i = 0; i < data.length -1; i++) {
        // 已排好序的列表下一个数
        int nextData = data[i + 1];
        // 与前面已排好序的列表以此进行比较,j为待比较数据的下表
        // 将nextData < data[j]，而不是放到for循环里面的好处就是当比较不成立时就不需要执行后面的w操作了
        for (int j = i; j >= 0 && nextData < data[j]; j--) {
            data[j + 1] = data[j];
            data[j] = nextData;
        }
    }
}