一、排序算法的时间复杂度和空间复杂度

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	稳定
直接选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
直接插入排序	O(n²)	O(n²)	O(n)	O(1)	稳定
快速排序	O(nlogn)	O(n²)	O(nlogn)	O(nlogn)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
希尔排序	O(nlogn)	O(n²)	O(nlogn)	O(1)	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定
基数排序	O(N*M)	O(N*M)	O(N*M)	O(M)	稳定

注：

1 归并排序可以通过手摇算法将空间复杂度降到O(1)，但是时间复杂度会提高。

2 基数排序时间复杂度为O(N*M)，其中N为数据个数，M为数据位数。

1.1 复杂度辅助记忆

1. 冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)）（一遍找元素O(n)，一遍找位置O(n)）
2. 快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）

1.2 稳定性辅助记忆

• 稳定性记忆-“快希选堆”（快牺牲稳定性） 
• 排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。

二、理解时间复杂度

2.1 常数阶O(1)

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

 2.2 对数阶O(logN)

int i = 1;
while(i<n)
{
    i = i * 2;
}

2.3 线性阶O(n)

for(i=0; i<=n; i++)
{
   System.out.println("hello");
}

2.4 线性对数阶O(n)

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

2.5 平方阶O(n)

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       System.out.println("hello");
    }
}

2.6 K次方阶O(n)

    for(i=0; i<=n; i++)
        {
            for(j=0; i<=n; i++)
            {
                for(k=0; i<=n; i++)
                {
                    System.out.println("hello");
                }
            }
        }


// k = 3 , n ^ 3

上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。

三、空间复杂度

3.1 常数阶O(1) —— 原地排序

只用到 temp 这么一个辅助空间

原地排序算法，就是空间复杂度为O(1)的算法，不牵涉额外得到其他空间~

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

2.2 对数阶O(logN)

2.3 线性阶O(n)

        int[] newArray = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            newArray[i] = nums[i];
        }

四、排序算法

4.1 冒泡排序

（思路：大的往后放）

4.1.1 代码

    private static void bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

4.1.2 复杂度

时间复杂度： N^2

空间复杂度：1

最佳时间复杂度：N^2  (因为就算你内部循环只对比，不交换元素，也是一样是N）

稳定性：稳定的 （大于的才换，小于等于的不交换）

    // { 0,1,2,3,4}
    private static void bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            boolean isChange = false;
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    isChange = true;
                }
            }
            if(!isChange){
                return;
            }
        }
    }

改进后的代码，最佳时间复杂度： N  （因为假如第一轮对比就没有任何元素交换，那么可以直接退出，也就是只有一次外循环）

4.2 选择排序

（思路：最小的放最前）

4.2.1 代码

private static void selectSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            swap(nums,minIndex,i);
        }
    }

4.2.2 复杂度

时间复杂度： N^2

空间复杂度：1

最佳时间复杂度：N^2  

稳定性：不稳定的 

4.3 直接插入排序

（思路：往排序好的数组中，找到合适的位置插进去）

4.3.1 代码

private static void insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int temp = nums[i];
            int j = i - 1;
            for (; j >= 0 && temp < nums[j]; j--) {
                nums[j + 1] = nums[j];
            }
            nums[j + 1] = temp;
        }
    }

4.3.2 复杂度

时间复杂度： N^2

空间复杂度：1

最佳时间复杂度：N  (因为你不进入内部循环。 [1,2,3,4,5]）

稳定性：稳定的 

4.4 快速排序

（思路：利用数字target，把数组切成两边，左边比 target大，后边比 target小）

4.4.1 代码

/**
 * 快速排序算法
 * @param nums 待排序的数组
 * @param beginIndex 排序起始索引
 * @param endIndex 排序结束索引
 */
private static void quickSort(int[] nums, int beginIndex, int endIndex) {
    if (beginIndex >= endIndex) {
        return; // 递归终止条件：当开始索引大于等于结束索引时，表示已经完成排序
    }
    int mid = getMid(nums, beginIndex, endIndex); // 获取中间索引，用于分割数组
    quickSort(nums, beginIndex, mid - 1); // 对中间索引左侧的数组进行快速排序
    quickSort(nums, mid + 1, endIndex); // 对中间索引右侧的数组进行快速排序
}

/**
 * 获取分区中的中间元素的索引
 * @param nums 待排序的数组
 * @param beginIndex 分区的起始索引
 * @param endIndex 分区的结束索引
 * @return 中间元素的索引
 */
private static int getMid(int[] nums, int beginIndex, int endIndex) {
    int target = nums[beginIndex]; // 以数组的起始元素作为基准值
    int left = beginIndex;
    int right = endIndex;
    boolean right2left = true; // 标识位，表示当前从右往左搜索
    while (right > left) {
        if (right2left) {
            while (right > left && nums[right] > target) {
                right--;
            }
            if (right > left) {
                nums[left] = nums[right]; // 当右侧元素较大时，将右侧元素移到插入位置
                right2left = false; // 切换为从左往右搜索
            }
        } else {
            while (right > left && nums[left] < target) {
                left++;
            }
            if (right > left) {
                nums[right] = nums[left]; // 当左侧元素较小时，将左侧元素移到插入位置
                right2left = true; // 切换为从右往左搜索
            }
        }
    }
    nums[left] = target; // 将基准值放入插入位置，完成一轮交换
    return left;
}

4.4.2 复杂度

时间复杂度： N Log N （每个元素找到中间位置的，需要 LogN 时间，N个元素就是NLogN）

空间复杂度：N Log N （递归调用，需要栈空间）

最差时间复杂度：N ^ 2  （ 比如正序数组 [1,2,3,4,5] ）

稳定性：不稳定的 

4.5 堆排序

（思路：最大放上面，然后与最后元素交换，继续建堆）

4.5.1 代码

/**
 * 堆排序算法
 * @param nums 待排序的数组
 * @param beginIndex 排序的起始索引
 * @param endIndex 排序的结束索引
 */
private static void heapSort(int[] nums, int beginIndex, int endIndex) {
    if (beginIndex >= endIndex) {
        return; // 当开始索引大于等于结束索引时，排序完成
    }
    for (int i = endIndex; i >= beginIndex; i--) {
        createHeap(nums, i); // 构建最大堆
        swap(nums, 0, i); // 将最大元素移到数组末尾
    }
}

/**
 * 构建最大堆
 * @param nums 待构建的数组
 * @param endIndex 当前堆的结束索引
 */
private static void createHeap(int[] nums, int endIndex) {
    int lastFatherIndex = (endIndex - 1) / 2;
    for (int i = lastFatherIndex; i >= 0; i--) {
        int biggestIndex = i;
        int leftChildIndex = i * 2 + 1;
        int rightChildIndex = i * 2 + 2;
        if (leftChildIndex <= endIndex) {
            biggestIndex = nums[biggestIndex] > nums[leftChildIndex] ? biggestIndex : leftChildIndex;
        }
        if (rightChildIndex <= endIndex) {
            biggestIndex = nums[biggestIndex] > nums[rightChildIndex] ? biggestIndex : rightChildIndex;
        }
        swap(nums, biggestIndex, i); // 调整堆，确保最大元素位于堆顶
    }
}

/**
 * 交换数组中两个元素的位置
 * @param nums 数组
 * @param i 索引1
 * @param j 索引2
 */
private static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

4.5.2 复杂度

时间复杂度： N Log N （每个元素都要构建1次堆，需要 LogN 时间，N个元素就是NLogN，任何情况下都一样）

空间复杂度：1 （原地排序）

最差时间复杂度：N ^ 2  （ 比如正序数组 [1,2,3,4,5] ）

稳定性：不稳定的 

4.6 归并排序

递归思路，左右两边排序好了，就已经排序好了

4.6.1 代码

// 归并排序的主方法
private static void mergeSort(int[] nums, int beginIndex, int endIndex) {
    // 如果起始索引大于等于结束索引，表示只有一个元素或没有元素，不需要排序
    if (beginIndex >= endIndex) {
        return;
    }
    
    // 计算数组的中间索引
    int mid = beginIndex + (endIndex - beginIndex) / 2;
    
    // 递归排序左半部分
    mergeSort(nums, beginIndex, mid);
    
    // 递归排序右半部分
    mergeSort(nums, mid + 1, endIndex);
    
    // 合并左右两部分
    merge(nums, beginIndex, mid, endIndex);
}

// 合并函数，用于将左右两部分合并成一个有序的数组
private static void merge(int[] nums, int beginIndex, int mid, int endIndex) {
    int left = beginIndex;
    int right = mid + 1;
    int[] newArrays = new int[endIndex - beginIndex + 1];
    int newArraysIndex = 0;

    // 比较左右两部分的元素，将较小的元素放入新数组
    while (left <= mid && right <= endIndex) {
        newArrays[newArraysIndex++] = nums[left] <= nums[right] ? nums[left++] : nums[right++];
    }

    // 将剩余的左半部分元素复制到新数组
    while (left <= mid) {
        newArrays[newArraysIndex++] = nums[left++];
    }

    // 将剩余的右半部分元素复制到新数组
    while (right <= endIndex) {
        newArrays[newArraysIndex++] = nums[right++];
    }

    // 将合并后的新数组复制回原数组
    for (int i = 0; i < newArrays.length; i++) {
        nums[beginIndex + i] = newArrays[i];
    }
}

4.6.2 复杂度

时间复杂度： N Log N （每个元素都要递归，需要 LogN 时间，N个元素就是NLogN，任何情况下都一样）

空间复杂度：N

稳定性：稳定的 

 4.7 希尔排序

思路：直接插入排序的升级版（分段式插入排序）

4.7.1 代码

private static void quickSort(int[] nums) {
//        int gap = nums.length / 2;
//        while (gap > 0) {
        for (int i = 1; i < nums.length; i++) {
            int temp = nums[i];
            int j;
            for (j = i - 1; j >= 0 && temp < nums[j]; j--) {
                nums[j + 1] = nums[j];
            }
            nums[j + 1] = temp;
        }
//        gap = gap / 2;
//        }
    }

    // 把上面的快速排序改成shell排序，只需要把间隔1 改成gap
    private static void shellSort(int[] nums) {
        int gap = nums.length / 2;
        while (gap > 0) {
            for (int i = gap; i < nums.length; i++) {
                int temp = nums[i];
                int j;
                for (j = i - gap; j >= 0 && temp < nums[j]; j = j - gap) {
                    nums[j + gap] = nums[j];// 如果当前元素比待插入元素大，将当前元素向后移动
                }
                nums[j + gap] = temp; // 因为上边 j=j-gap退出的时候，j已经被剪掉1次了，可能小于0了
            }
            gap = gap / 2;
        }
    }

4.7.2 复杂度

时间复杂度： N Log N 

空间复杂度：1

稳定性：稳定的