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

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

    排序算法

    平均时间复杂度

    最坏时间复杂度

    最好时间复杂度

    空间复杂度

    稳定性

    冒泡排序

    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)

    1. int i = 1;
    2. int j = 2;
    3. ++i;
    4. j++;
    5. int m = i + j;

     2.2 对数阶O(logN)

    1. int i = 1;
    2. while(i
    3. {
    4.     i = i * 2;
    5. }

    2.3 线性阶O(n)

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

    2.4 线性对数阶O(n)

    1. for(m=1; m
    2. {
    3.     i = 1;
    4.     while(i
    5.     {
    6.         i = i * 2;
    7.     }
    8. }

    2.5 平方阶O(n)

    1.  
    2. for(x=1; i<=n; x++)
    3. {
    4.    for(i=1; i<=n; i++)
    5.     {
    6.        System.out.println("hello");
    7.     }
    8. }

    2.6 K次方阶O(n)

    1.     for(i=0; i<=n; i++)
    2.         {
    3.             for(j=0; i<=n; i++)
    4.             {
    5.                 for(k=0; i<=n; i++)
    6.                 {
    7.                     System.out.println("hello");
    8.                 }
    9.             }
    10.         }
    11.  
    12.  
    13. // k = 3 , n ^ 3

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

    三、空间复杂度

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

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

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

    1.     private static void swap(int[] nums, int i, int j) {
    2.         int temp = nums[i];
    3.         nums[i] = nums[j];
    4.         nums[j] = temp;
    5.     }

    2.2 对数阶O(logN)

    2.3 线性阶O(n)

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

    四、排序算法

    4.1 冒泡排序

    （思路：大的往后放）

    4.1.1 代码

    1.     private static void bubbleSort(int[] nums) {
    2.         for (int i = 0; i < nums.length; i++) {
    3.             for (int j = 0; j < nums.length - 1 - i; j++) {
    4.                 if (nums[j] > nums[j + 1]) {
    5.                     swap(nums, j, j + 1);
    6.                 }
    7.             }
    8.         }
    9.     }

    4.1.2 复杂度

    时间复杂度： N^2

    空间复杂度：1

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

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

    1.     // { 0,1,2,3,4}
    2.     private static void bubbleSort(int[] nums) {
    3.         for (int i = 0; i < nums.length; i++) {
    4.             boolean isChange = false;
    5.             for (int j = 0; j < nums.length - 1 - i; j++) {
    6.                 if (nums[j] > nums[j + 1]) {
    7.                     swap(nums, j, j + 1);
    8.                     isChange = true;
    9.                 }
    10.             }
    11.             if(!isChange){
    12.                 return;
    13.             }
    14.         }
    15.     }

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

    4.2 选择排序

    （思路：最小的放最前）

    4.2.1 代码

    1. private static void selectSort(int[] nums) {
    2.         for (int i = 0; i < nums.length; i++) {
    3.             int minIndex = i;
    4.             for (int j = i + 1; j < nums.length; j++) {
    5.                 if (nums[j] < nums[minIndex]) {
    6.                     minIndex = j;
    7.                 }
    8.             }
    9.             swap(nums,minIndex,i);
    10.         }
    11.     }

    4.2.2 复杂度

    时间复杂度： N^2

    空间复杂度：1

    最佳时间复杂度：N^2  

    稳定性：不稳定的 

    4.3 直接插入排序

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

    4.3.1 代码

    1. private static void insertSort(int[] nums) {
    2.         for (int i = 1; i < nums.length; i++) {
    3.             int temp = nums[i];
    4.             int j = i - 1;
    5.             for (; j >= 0 && temp < nums[j]; j--) {
    6.                 nums[j + 1] = nums[j];
    7.             }
    8.             nums[j + 1] = temp;
    9.         }
    10.     }

    4.3.2 复杂度

    时间复杂度： N^2

    空间复杂度：1

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

    稳定性：稳定的 

    4.4 快速排序

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

    4.4.1 代码

    1. /**
    2.  * 快速排序算法
    3.  * @param nums 待排序的数组
    4.  * @param beginIndex 排序起始索引
    5.  * @param endIndex 排序结束索引
    6.  */
    7. private static void quickSort(int[] nums, int beginIndex, int endIndex) {
    8.     if (beginIndex >= endIndex) {
    9.         return; // 递归终止条件：当开始索引大于等于结束索引时，表示已经完成排序
    10.     }
    11.     int mid = getMid(nums, beginIndex, endIndex); // 获取中间索引，用于分割数组
    12.     quickSort(nums, beginIndex, mid - 1); // 对中间索引左侧的数组进行快速排序
    13.     quickSort(nums, mid + 1, endIndex); // 对中间索引右侧的数组进行快速排序
    14. }
    15.  
    16. /**
    17.  * 获取分区中的中间元素的索引
    18.  * @param nums 待排序的数组
    19.  * @param beginIndex 分区的起始索引
    20.  * @param endIndex 分区的结束索引
    21.  * @return 中间元素的索引
    22.  */
    23. private static int getMid(int[] nums, int beginIndex, int endIndex) {
    24.     int target = nums[beginIndex]; // 以数组的起始元素作为基准值
    25.     int left = beginIndex;
    26.     int right = endIndex;
    27.     boolean right2left = true; // 标识位，表示当前从右往左搜索
    28.     while (right > left) {
    29.         if (right2left) {
    30.             while (right > left && nums[right] > target) {
    31.                 right--;
    32.             }
    33.             if (right > left) {
    34.                 nums[left] = nums[right]; // 当右侧元素较大时，将右侧元素移到插入位置
    35.                 right2left = false; // 切换为从左往右搜索
    36.             }
    37.         } else {
    38.             while (right > left && nums[left] < target) {
    39.                 left++;
    40.             }
    41.             if (right > left) {
    42.                 nums[right] = nums[left]; // 当左侧元素较小时，将左侧元素移到插入位置
    43.                 right2left = true; // 切换为从右往左搜索
    44.             }
    45.         }
    46.     }
    47.     nums[left] = target; // 将基准值放入插入位置，完成一轮交换
    48.     return left;
    49. }

    4.4.2 复杂度

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

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

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

    稳定性：不稳定的 

    4.4.3 相关面试题

    1、奇偶分割

    给你一个数组，奇数放左边，偶数放右边，不要求排序

    1. public static void main(String[] args) {
    2.         // 题目，把奇数放左边，偶尔放右边
    3.         // 思路：快速排序，交换元素
    4.         int[] array = {13, 100, 17, 12, 25, 0,1,6};
    5.         quickSort(array, 0, array.length - 1);
    6.         System.out.println(JSON.toJSONString(array));
    7.  
    8.     }
    9.  
    10.     private static void quickSort(int[] array, int beginIndex, int endIndex) {
    11.         if (beginIndex >= endIndex) {
    12.             return;
    13.         }
    14.         int mid = getMid(array, beginIndex, endIndex);
    15.     }
    16.  
    17.     private static int getMid(int[] array, int beginIndex, int endIndex) {
    18.         int left = beginIndex;
    19.         int right = endIndex;
    20.         int temp = array[beginIndex];
    21.  
    22.         boolean right2Left = true;
    23.         while (left < right) {
    24.             if (right2Left) {
    25.                 // 如果是偶数
    26.                 if (array[right] % 2 == 0) {
    27.                     right--;
    28.                 } else {
    29.                     array[left++] = array[right];
    30.                     right2Left = false;
    31.                 }
    32.             } else {
    33.                 // 如果是奇数
    34.                 if (array[left] % 2 != 0) {
    35.                     left++;
    36.                 } else {
    37.                     array[right--] = array[left];
    38.                     right2Left = true;
    39.                 }
    40.             }
    41.         }
    42.         array[left] = temp;
    43.         return left;
    44.     }

    这个方法的时间复杂度是O(N），空间复杂度是 O(1），不稳定

    下面这个方法的时间复杂度是O(N），空间复杂度是 O(N），稳定

    1. public static void main(String[] args) {
    2.         // 题目，把奇数放左边，偶尔放右边
    3.         // 思路：快速排序，交换元素
    4.         int[] array = {13, 100, 17, 12, 25, 0, 1, 6, 5, 5};
    5.  
    6.         int[] arrayNew = new int[array.length];
    7.  
    8.         int oddCount = 0;
    9.         for (int i = 0; i < array.length; i++) {
    10.             if (array[i] % 2 != 0) {
    11.                 oddCount++;
    12.             }
    13.         }
    14.         System.out.println(oddCount);
    15.         // 奇数的下标
    16.         int oddIndex = 0;
    17.         // 偶数的下标
    18.         int evenIndex = oddCount;
    19.         for (int i = 0; i < array.length; i++) {
    20.             if (array[i] % 2 != 0) {
    21.                 arrayNew[oddIndex++] = array[i];
    22.             }else {
    23.                 arrayNew[evenIndex++] = array[i];
    24.             }
    25.  
    26.         }
    27.         System.out.println(JSON.toJSONString(arrayNew));
    28.     }

    4.5 堆排序

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

    4.5.1 代码

    1. /**
    2.  * 堆排序算法
    3.  * @param nums 待排序的数组
    4.  * @param beginIndex 排序的起始索引
    5.  * @param endIndex 排序的结束索引
    6.  */
    7. private static void heapSort(int[] nums, int beginIndex, int endIndex) {
    8.     if (beginIndex >= endIndex) {
    9.         return; // 当开始索引大于等于结束索引时，排序完成
    10.     }
    11.     for (int i = endIndex; i >= beginIndex; i--) {
    12.         createHeap(nums, i); // 构建最大堆
    13.         swap(nums, 0, i); // 将最大元素移到数组末尾
    14.     }
    15. }
    16.  
    17. /**
    18.  * 构建最大堆
    19.  * @param nums 待构建的数组
    20.  * @param endIndex 当前堆的结束索引
    21.  */
    22. private static void createHeap(int[] nums, int endIndex) {
    23.     int lastFatherIndex = (endIndex - 1) / 2;
    24.     for (int i = lastFatherIndex; i >= 0; i--) {
    25.         int biggestIndex = i;
    26.         int leftChildIndex = i * 2 + 1;
    27.         int rightChildIndex = i * 2 + 2;
    28.         if (leftChildIndex <= endIndex) {
    29.             biggestIndex = nums[biggestIndex] > nums[leftChildIndex] ? biggestIndex : leftChildIndex;
    30.         }
    31.         if (rightChildIndex <= endIndex) {
    32.             biggestIndex = nums[biggestIndex] > nums[rightChildIndex] ? biggestIndex : rightChildIndex;
    33.         }
    34.         swap(nums, biggestIndex, i); // 调整堆，确保最大元素位于堆顶
    35.     }
    36. }
    37.  
    38. /**
    39.  * 交换数组中两个元素的位置
    40.  * @param nums 数组
    41.  * @param i 索引1
    42.  * @param j 索引2
    43.  */
    44. private static void swap(int[] nums, int i, int j) {
    45.     int temp = nums[i];
    46.     nums[i] = nums[j];
    47.     nums[j] = temp;
    48. }

    4.5.2 复杂度

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

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

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

    稳定性：不稳定的 

    4.6 归并排序

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

    4.6.1 代码

    1. // 归并排序的主方法
    2. private static void mergeSort(int[] nums, int beginIndex, int endIndex) {
    3.     // 如果起始索引大于等于结束索引，表示只有一个元素或没有元素，不需要排序
    4.     if (beginIndex >= endIndex) {
    5.         return;
    6.     }
    7.     
    8.     // 计算数组的中间索引
    9.     int mid = beginIndex + (endIndex - beginIndex) / 2;
    10.     
    11.     // 递归排序左半部分
    12.     mergeSort(nums, beginIndex, mid);
    13.     
    14.     // 递归排序右半部分
    15.     mergeSort(nums, mid + 1, endIndex);
    16.     
    17.     // 合并左右两部分
    18.     merge(nums, beginIndex, mid, endIndex);
    19. }
    20.  
    21. // 合并函数，用于将左右两部分合并成一个有序的数组
    22. private static void merge(int[] nums, int beginIndex, int mid, int endIndex) {
    23.     int left = beginIndex;
    24.     int right = mid + 1;
    25.     int[] newArrays = new int[endIndex - beginIndex + 1];
    26.     int newArraysIndex = 0;
    27.  
    28.     // 比较左右两部分的元素，将较小的元素放入新数组
    29.     while (left <= mid && right <= endIndex) {
    30.         newArrays[newArraysIndex++] = nums[left] <= nums[right] ? nums[left++] : nums[right++];
    31.     }
    32.  
    33.     // 将剩余的左半部分元素复制到新数组
    34.     while (left <= mid) {
    35.         newArrays[newArraysIndex++] = nums[left++];
    36.     }
    37.  
    38.     // 将剩余的右半部分元素复制到新数组
    39.     while (right <= endIndex) {
    40.         newArrays[newArraysIndex++] = nums[right++];
    41.     }
    42.  
    43.     // 将合并后的新数组复制回原数组
    44.     for (int i = 0; i < newArrays.length; i++) {
    45.         nums[beginIndex + i] = newArrays[i];
    46.     }
    47. }

    4.6.2 复杂度

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

    空间复杂度：N

    稳定性：稳定的 

     4.7 希尔排序

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

    4.7.1 代码

    1. private static void quickSort(int[] nums) {
    2. //        int gap = nums.length / 2;
    3. //        while (gap > 0) {
    4.         for (int i = 1; i < nums.length; i++) {
    5.             int temp = nums[i];
    6.             int j;
    7.             for (j = i - 1; j >= 0 && temp < nums[j]; j--) {
    8.                 nums[j + 1] = nums[j];
    9.             }
    10.             nums[j + 1] = temp;
    11.         }
    12. //        gap = gap / 2;
    13. //        }
    14.     }
    15.  
    16.     // 把上面的快速排序改成shell排序，只需要把间隔1 改成gap
    17.     private static void shellSort(int[] nums) {
    18.         int gap = nums.length / 2;
    19.         while (gap > 0) {
    20.             for (int i = gap; i < nums.length; i++) {
    21.                 int temp = nums[i];
    22.                 int j;
    23.                 for (j = i - gap; j >= 0 && temp < nums[j]; j = j - gap) {
    24.                     nums[j + gap] = nums[j];// 如果当前元素比待插入元素大，将当前元素向后移动
    25.                 }
    26.                 nums[j + gap] = temp; // 因为上边 j=j-gap退出的时候，j已经被剪掉1次了，可能小于0了
    27.             }
    28.             gap = gap / 2;
    29.         }
    30.     }

    4.7.2 复杂度

    时间复杂度： N Log N 

    空间复杂度：1

    稳定性：不稳定的 

     4.8 计数排序

    前提：

    1、数组规模不大，比如统计中国各个年龄的人数（因为年龄顶多就是0-150岁）

    4.8.2 代码

    1. public static void main(String[] args) {
    2.     int[] nums = {10, 18, 18, 18, 18, 18, 18, 20, 20, 20, 20, 2, 8, 3, 4, 1, 2, 3, 4};
    3.     int[] ageCount = new int[200];
    4.     for (int i = 0; i < nums.length; i++) {
    5.         ageCount[nums[i]]++;
    6.     }
    7.     for (int i = 1; i < ageCount.length; i++) {
    8.         int count = ageCount[i];
    9.         for (int j = 0; j < count; j++) {
    10.             System.out.print(i + ",");
    11.         }
    12.     }
    13. }

    4.8.2 复杂度

    时间复杂度： N  （N是数组长度）

    空间复杂度：K

    稳定性：稳定的 

     4.9 基数排序

    4.9.1 代码

    如何取到指定位置的数字？

    1.     public static void main(String[] args) {
    2.         int number = 1234;
    3.         // 1234 如何取到个位数 4，1234 % 10 = 4 ，4/1 = 4
    4.         // 1234 如何取到十位数 3，1234 % 100 = 34 ，34/10 = 3
    5.         // 1234 如何取到百位数 2，1234 % 1000 = 234 ，234/100 = 2
    6.         // 1234 如何取到千位数 1，1234 % 10000 = 1234 ，234/1000 = 1
    7.         for (int i = 0; i < getDigitLength(number); i++) {
    8.             int num = (int) (number % Math.pow(10, i + 1) / Math.pow(10, i));
    9.             System.out.println(num);
    10.         }
    11.     }
    12.  
    13.     // 1 就是1位数
    14.     // 10 就是2位数
    15.     // 100 就是3位数
    16.     // 1000 就是4位数
    17.     public static int getDigitLength(int number) {
    18.         int length = 1;
    19.         while (number / 10 > 0) { // 100
    20.             length++;
    21.             number = number / 10;
    22.         }
    23.         return length;
    24.     }

    基数排序算法：

    1. public static void main(String[] args) {
    2.  
    3.         int[] array = {13, 100, 17, 12, 25};
    4.         Map> bucketMap = new HashMap<>();
    5.         for (int i = 0; i < 10; i++) {
    6.             bucketMap.put(i, new ArrayList<>());
    7.         }
    8.  
    9.         int maxDigitLength = 0;
    10.         for (int i = 0; i < array.length; i++) {
    11.             maxDigitLength = getDigitLength(array[i]) > maxDigitLength ? getDigitLength(array[i]) : maxDigitLength;
    12.         }
    13.         for (int i = 0; i < maxDigitLength; i++) { // 从后往前取数值
    14.             for (int j = 0; j < array.length; j++) {
    15.                 int iValue = (int) (array[j] % Math.pow(10, i + 1) / Math.pow(10, i));
    16.                 bucketMap.get(iValue).add(array[j]); // 入桶
    17.             }
    18.  
    19.             int arrayIndex = 0;
    20.             for (int j = 0; j < 10; j++) {
    21.                 List bucketList = bucketMap.get(j);
    22.                 for (Integer num: bucketList) {
    23.                     array[arrayIndex++] = num; //倒出来
    24.                 }
    25.                 bucketMap.put(j,new ArrayList<>()); // 清空桶
    26.             }
    27.             System.out.println(JSON.toJSONString(array));
    28.  
    29.         }
    30.     }
    31.  
    32.  
    33.     // 1 就是1位数
    34.     // 10 就是2位数
    35.     // 100 就是3位数
    36.     // 1000 就是4位数
    37.     public static int getDigitLength(int number) {
    38.         int length = 1;
    39.         while (number / 10 > 0) { // 100
    40.             length++;
    41.             number = number / 10;
    42.         }
    43.         return length;
    44.     }

    4.9.2 复杂度

    时间复杂度： N * d  （N是数组长度，d是最大位数，对于整数排序的话，d = log N 级别，因此整体是 N Log N）

    空间复杂度：N

    稳定性：稳定的 

  • 相关阅读:
    使用CFimagehost源码搭建无需数据库支持的PHP免费图片托管私人图床
    Vuex使用一文搞懂
    副业教程之如何通过出售API赚取美元含数据集和训练教程
    运行报错（三）git bash报错fatal: detected dubious ownership in repository at
    php程序设计的基本原则
    Ubuntu Studio 23.10发布
    MongoDB单实例安装(Linux)
    在游戏博弈中才是博弈游戏的最佳实践
    【计算机网络】IP协议第二讲（Mac帧、IP地址、碰撞检测、ARP协议介绍）
    了解什么是JDBC
  • 原文地址：https://blog.csdn.net/Sword52888/article/details/134252267