排序算法总结

• • 冒泡排序
  • 选择排序
  • 简单插入排序

双层循环，每次挑出最大的放在最右边。循环结束后排序结束

//冒泡
private static void bubbleSort(int[] intArr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < intArr.length; i++)
    {
        for (int j = 1; j < intArr.length - i; j++)
        {
            if (intArr[j - 1] > intArr[j]) {
                int tmp = intArr[j - 1];
                intArr[j - 1] = intArr[j];
                intArr[j] = tmp;
            }
        }
    }
    printArr(intArr);
}

时间复杂度
看 N + N-1 + N-2 + N-3 + …
比 N + N-1 + N-2 + N-3 + …
交换 N
时间复杂度O(N²)

每次循环选出最小的放在最前面

//选择
private static void selectSort(int[] intArr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < intArr.length; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < intArr.length; j++)
        {
            minIndex = intArr[minIndex] > intArr[j] ? j : minIndex;
        }
        int tmp = intArr[minIndex];
        intArr[minIndex] = intArr[i];
        intArr[i] = tmp;
    }
    printArr(intArr);
}

时间复杂度同上

类似于打斗地主，从第二个元素开始向后，都与前面的元素比较，找到第一个比自己小的元素并插入在它前面。

//简单插入
private static void insertSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 1; i < arr.length; i++)
    {
        int index = i - 1;
        while(--index >= 0) {
            if (arr[i] < arr[index]) {
                int tmp = arr[i];
                arr[i] = arr[index];
                arr[index] = tmp;
                break;
            }
        }
    }
    prarr(arr);
}

时间复杂度受数据情况而定，最好情况下是O(N)，在最差情况下是O(N²)，复杂度以最差为准，即O(N²)