一、排序算法的时间复杂度和空间复杂度
排序算法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性 冒泡排序 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 复杂度辅助记忆
冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)）（一遍找元素O(n)，一遍找位置O(n)）快速、归并、希尔、堆基于二分思想，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 { 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 { i = 1; while(i { 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.4.3 相关面试题 1、奇偶分割 给你一个数组，奇数放左边，偶数放右边，不要求排序 public static void main(String[] args) { // 题目，把奇数放左边，偶尔放右边 // 思路：快速排序，交换元素 int[] array = {13, 100, 17, 12, 25, 0,1,6}; quickSort(array, 0, array.length - 1); System.out.println(JSON.toJSONString(array)); } private static void quickSort(int[] array, int beginIndex, int endIndex) { if (beginIndex >= endIndex) { return; } int mid = getMid(array, beginIndex, endIndex); } private static int getMid(int[] array, int beginIndex, int endIndex) { int left = beginIndex; int right = endIndex; int temp = array[beginIndex]; boolean right2Left = true; while (left < right) { if (right2Left) { // 如果是偶数 if (array[right] % 2 == 0) { right--; } else { array[left++] = array[right]; right2Left = false; } } else { // 如果是奇数 if (array[left] % 2 != 0) { left++; } else { array[right--] = array[left]; right2Left = true; } } } array[left] = temp; return left; } 这个方法的时间复杂度是O(N），空间复杂度是 O(1），不稳定 下面这个方法的时间复杂度是O(N），空间复杂度是 O(N），稳定 public static void main(String[] args) { // 题目，把奇数放左边，偶尔放右边 // 思路：快速排序，交换元素 int[] array = {13, 100, 17, 12, 25, 0, 1, 6, 5, 5}; int[] arrayNew = new int[array.length]; int oddCount = 0; for (int i = 0; i < array.length; i++) { if (array[i] % 2 != 0) { oddCount++; } } System.out.println(oddCount); // 奇数的下标 int oddIndex = 0; // 偶数的下标 int evenIndex = oddCount; for (int i = 0; i < array.length; i++) { if (array[i] % 2 != 0) { arrayNew[oddIndex++] = array[i]; }else { arrayNew[evenIndex++] = array[i]; } } System.out.println(JSON.toJSONString(arrayNew)); } 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 稳定性：不稳定的 4.8 计数排序 前提： 1、数组规模不大，比如统计中国各个年龄的人数（因为年龄顶多就是0-150岁） 4.8.2 代码 public static void main(String[] args) { int[] nums = {10, 18, 18, 18, 18, 18, 18, 20, 20, 20, 20, 2, 8, 3, 4, 1, 2, 3, 4}; int[] ageCount = new int[200]; for (int i = 0; i < nums.length; i++) { ageCount[nums[i]]++; } for (int i = 1; i < ageCount.length; i++) { int count = ageCount[i]; for (int j = 0; j < count; j++) { System.out.print(i + ","); } } } 4.8.2 复杂度 时间复杂度： N （N是数组长度） 空间复杂度：K 稳定性：稳定的 4.9 基数排序 4.9.1 代码 如何取到指定位置的数字？ public static void main(String[] args) { int number = 1234; // 1234 如何取到个位数 4，1234 % 10 = 4 ，4/1 = 4 // 1234 如何取到十位数 3，1234 % 100 = 34 ，34/10 = 3 // 1234 如何取到百位数 2，1234 % 1000 = 234 ，234/100 = 2 // 1234 如何取到千位数 1，1234 % 10000 = 1234 ，234/1000 = 1 for (int i = 0; i < getDigitLength(number); i++) { int num = (int) (number % Math.pow(10, i + 1) / Math.pow(10, i)); System.out.println(num); } } // 1 就是1位数 // 10 就是2位数 // 100 就是3位数 // 1000 就是4位数 public static int getDigitLength(int number) { int length = 1; while (number / 10 > 0) { // 100 length++; number = number / 10; } return length; } 基数排序算法： public static void main(String[] args) { int[] array = {13, 100, 17, 12, 25}; Map for (int i = 0; i < 10; i++) { bucketMap.put(i, new ArrayList<>()); } int maxDigitLength = 0; for (int i = 0; i < array.length; i++) { maxDigitLength = getDigitLength(array[i]) > maxDigitLength ? getDigitLength(array[i]) : maxDigitLength; } for (int i = 0; i < maxDigitLength; i++) { // 从后往前取数值 for (int j = 0; j < array.length; j++) { int iValue = (int) (array[j] % Math.pow(10, i + 1) / Math.pow(10, i)); bucketMap.get(iValue).add(array[j]); // 入桶 } int arrayIndex = 0; for (int j = 0; j < 10; j++) { List for (Integer num: bucketList) { array[arrayIndex++] = num; //倒出来 } bucketMap.put(j,new ArrayList<>()); // 清空桶 } System.out.println(JSON.toJSONString(array)); } } // 1 就是1位数 // 10 就是2位数 // 100 就是3位数 // 1000 就是4位数 public static int getDigitLength(int number) { int length = 1; while (number / 10 > 0) { // 100 length++; number = number / 10; } return length; } 4.9.2 复杂度 时间复杂度： N * d （N是数组长度，d是最大位数，对于整数排序的话，d = log N 级别，因此整体是 N Log N） 空间复杂度：N 稳定性：稳定的 精彩文章
发表评论