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

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

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	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 改成gapprivate 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

稳定性：稳定的