devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

八种经典排序算法总结_排序算法空间复杂度最小的

作者：我家小花儿 | 2024-06-26 15:26:40

赞

踩

排序算法空间复杂度最小的

前言

算法和数据结构是一个程序员的内功，所以经常在一些笔试中都会要求手写一些简单的排序算法，以此考验面试者的编程水平。下面我就简单介绍八种常见的排序算法，一起学习一下。

一、冒泡排序

思路：

  • 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；
  • 排除最大的数，接着下一轮继续相同的操作，确定第二大的数...
  • 重复步骤1-3，直到排序完成。

动画演示：

在这里插入图片描述

实现代码：

  1. /**
  2.  * @author Ye Hongzhi 公众号：java技术爱好者
  3.  * @name BubbleSort
  4.  * @date 2020-09-05 21:38
  5.  **/
  6. public class BubbleSort extends BaseSort {
  7.     
  8.     public static void main(String[] args) {
  9.         BubbleSort sort = new BubbleSort();
  10.         sort.printNums();
  11.     }
  12.     
  13.     @Override
  14.     protected void sort(int[] nums) {
  15.         if (nums == null || nums.length < 2) {
  16.             return;
  17.         }
  18.         for (int i = 0; i < nums.length - 1; i++) {
  19.             for (int j = 0; j < nums.length - i - 1; j++) {
  20.                 if (nums[j] > nums[j + 1]) {
  21.                     int temp = nums[j];
  22.                     nums[j] = nums[j + 1];
  23.                     nums[j + 1] = temp;
  24.                 }
  25.             }
  26.         }
  27.     }
  28. }
  29. //10万个数的数组，耗时：21554毫秒

平均时间复杂度：O(n²)

空间复杂度：O(1)

算法稳定性：稳定

二、插入排序

思路：

  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素，在前面已排序的元素序列中，从后向前扫描；
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；
  6. 重复步骤2~5。

动画演示：

在这里插入图片描述

实现代码：

  1. /**
  2.  * @author Ye Hongzhi 公众号：java技术爱好者
  3.  * @name InsertSort
  4.  * @date 2020-09-05 22:34
  5.  **/
  6. public class InsertSort extends BaseSort {
  7.     public static void main(String[] args) {
  8.         BaseSort sort = new InsertSort();
  9.         sort.printNums();
  10.     }
  11.     @Override
  12.     protected void sort(int[] nums) {
  13.         if (nums == null || nums.length < 2) {
  14.             return;
  15.         }
  16.         for (int i = 0; i < nums.length - 1; i++) {
  17.             //当前值
  18.             int curr = nums[i + 1];
  19.             //上一个数的指针
  20.             int preIndex = i;
  21.             //在数组中找到一个比当前遍历的数小的第一个数
  22.             while (preIndex >= 0 && curr < nums[preIndex]) {
  23.                 //把比当前遍历的数大的数字往后移动
  24.                 nums[preIndex + 1] = nums[preIndex];
  25.                 //需要插入的数的下标往前移动
  26.                 preIndex--;
  27.             }
  28.             //插入到这个数的后面
  29.             nums[preIndex + 1] = curr;
  30.         }
  31.     }
  32. }
  33. //10万个数的数组，耗时：2051毫秒

平均时间复杂度：O(n²)

空间复杂度：O(1)

算法稳定性：稳定

三、选择排序

思路：

第一轮，找到最小的元素，和数组第一个数交换位置。

第二轮，找到第二小的元素，和数组第二个数交换位置...

直到最后一个元素，排序完成。

动画演示：
在这里插入图片描述
实现代码：

  1. /**
  2.  * @author Ye Hongzhi 公众号：java技术爱好者
  3.  * @name SelectSort
  4.  * @date 2020-09-06 22:27
  5.  **/
  6. public class SelectSort extends BaseSort {
  7.     public static void main(String[] args) {
  8.         SelectSort sort = new SelectSort();
  9.         sort.printNums();
  10.     }
  11.     @Override
  12.     protected void sort(int[] nums) {
  13.         for (int i = 0; i < nums.length; i++) {
  14.             int minIndex = i;
  15.             for (int j = i + 1; j < nums.length; j++) {
  16.                 if (nums[j] < nums[minIndex]) {
  17.                     minIndex = j;
  18.                 }
  19.             }
  20.             if (minIndex != i) {
  21.                 int temp = nums[i];
  22.                 nums[minIndex] = temp;
  23.                 nums[i] = nums[minIndex];
  24.             }
  25.         }
  26.     }
  27. }
  28. //10万个数的数组，耗时：8492毫秒

算法复杂度：O(n²)
算法空间复杂度：O(1)
算法稳定性：不稳定

四、希尔排序

思路：

把数组分割成若干(h)个小组(一般数组长度length/2)，然后对每一个小组分别进行插入排序。每一轮分割的数组的个数逐步缩小，h/2->h/4->h/8，并且进行排序，保证有序。当h=1时，则数组排序完成。

动画演示：
在这里插入图片描述
实现代码：

  1. /**
  2.  * @author Ye Hongzhi 公众号：java技术爱好者
  3.  * @name SelectSort
  4.  * @date 2020-09-06 22:27
  5.  **/
  6. public class ShellSort extends BaseSort {
  7.  
  8.     public static void main(String[] args) {
  9.         ShellSort sort = new ShellSort();
  10.         sort.printNums();
  11.     }
  12.  
  13.     @Override
  14.     protected void sort(int[] nums) {
  15.         if (nums == null || nums.length < 2) {
  16.             return;
  17.         }
  18.         int length = nums.length;
  19.         int temp;
  20.         //步长
  21.         int gap = length / 2;
  22.         while (gap > 0) {
  23.             for (int i = gap; i < length; i++) {
  24.                 temp = nums[i];
  25.                 int preIndex = i - gap;
  26.                 while (preIndex >= 0 && nums[preIndex] > temp) {
  27.                     nums[preIndex + gap] = nums[preIndex];
  28.                     preIndex -= gap;
  29.                 }
  30.                 nums[preIndex + gap] = temp;
  31.             }
  32.             gap /= 2;
  33.         }
  34.     }
  35. }
  36. //10万个数的数组，耗时：261毫秒

算法复杂度：O(nlog2n)
算法空间复杂度：O(1)
算法稳定性：稳定

五、快速排序

快排，面试最喜欢问的排序算法。这是运用分治法的一种排序算法。

思路：

  1. 从数组中选一个数做为基准值，一般选第一个数，或者最后一个数。
  2. 采用双指针(头尾两端)遍历，从左往右找到比基准值大的第一个数，从右往左找到比基准值小的第一个数，交换两数位置，直到头尾指针相等或头指针大于尾指针，把基准值与头指针的数交换。这样一轮之后，左边的数就比基准值小，右边的数就比基准值大。
  3. 对左边的数列，重复上面1，2步骤。对右边重复1，2步骤。
  4. 左右两边数列递归结束后，排序完成。

动画演示：
在这里插入图片描述
实现代码：

  1. /**
  2.  * @author Ye Hongzhi 公众号：java技术爱好者
  3.  * @name SelectSort
  4.  * @date 2020-09-06 22:27
  5.  **/
  6. public class QuickSort extends BaseSort {
  7.  
  8.     public static void main(String[] args) {
  9.         QuickSort sort = new QuickSort();
  10.         sort.printNums();
  11.     }
  12.  
  13.     @Override
  14.     protected void sort(int[] nums) {
  15.         if (nums == null || nums.length < 2) {
  16.             return;
  17.         }
  18.         quickSort(nums, 0, nums.length - 1);
  19.     }
  20.  
  21.     private void quickSort(int[] nums, int star, int end) {
  22.         if (star > end) {
  23.             return;
  24.         }
  25.         int i = star;
  26.         int j = end;
  27.         int key = nums[star];
  28.         while (i < j) {
  29.             while (i < j && nums[j] > key) {
  30.                 j--;
  31.             }
  32.             while (i < j && nums[i] <= key) {
  33.                 i++;
  34.             }
  35.             if (i < j) {
  36.                 int temp = nums[i];
  37.                 nums[i] = nums[j];
  38.                 nums[j] = temp;
  39.             }
  40.         }
  41.         nums[star] = nums[i];
  42.         nums[i] = key;
  43.         quickSort(nums, star, i - 1);
  44.         quickSort(nums, i + 1, end);
  45.     }
  46. }
  47. //10万个数的数组，耗时：50毫秒

算法复杂度：O(nlogn)
算法空间复杂度：O(1)
算法稳定性：不稳定

六、归并排序

归并排序是采用分治法的典型应用，而且是一种稳定的排序方式，不过需要使用到额外的空间。

思路：

  1. 把数组不断划分成子序列，划成长度只有2或者1的子序列。
  2. 然后利用临时数组，对子序列进行排序，合并，再把临时数组的值复制回原数组。
  3. 反复操作1~2步骤，直到排序完成。

归并排序的优点在于最好情况和最坏的情况的时间复杂度都是O(nlogn)，所以是比较稳定的排序方式。

动画演示：
在这里插入图片描述
实现代码：

  1. /**
  2.  * @author Ye Hongzhi 公众号：java技术爱好者
  3.  * @name MergeSort
  4.  * @date 2020-09-08 23:30
  5.  **/
  6. public class MergeSort extends BaseSort {
  7.  
  8.     public static void main(String[] args) {
  9.         MergeSort sort = new MergeSort();
  10.         sort.printNums();
  11.     }
  12.  
  13.     @Override
  14.     protected void sort(int[] nums) {
  15.         if (nums == null || nums.length < 2) {
  16.             return;
  17.         }
  18.         //归并排序
  19.         mergeSort(0, nums.length - 1, nums, new int[nums.length]);
  20.     }
  21.  
  22.     private void mergeSort(int star, int end, int[] nums, int[] temp) {
  23.         //递归终止条件
  24.         if (star >= end) {
  25.             return;
  26.         }
  27.         int mid = star + (end - star) / 2;
  28.         //左边进行归并排序
  29.         mergeSort(star, mid, nums, temp);
  30.         //右边进行归并排序
  31.         mergeSort(mid + 1, end, nums, temp);
  32.         //合并左右
  33.         merge(star, end, mid, nums, temp);
  34.     }
  35.  
  36.     private void merge(int star, int end, int mid, int[] nums, int[] temp) {
  37.         int index = 0;
  38.         int i = star;
  39.         int j = mid + 1;
  40.         while (i <= mid && j <= end) {
  41.             if (nums[i] > nums[j]) {
  42.                 temp[index++] = nums[j++];
  43.             } else {
  44.                 temp[index++] = nums[i++];
  45.             }
  46.         }
  47.         while (i <= mid) {
  48.             temp[index++] = nums[i++];
  49.         }
  50.         while (j <= end) {
  51.             temp[index++] = nums[j++];
  52.         }
  53.         //把临时数组中已排序的数复制到nums数组中
  54.         if (index >= 0) System.arraycopy(temp, 0, nums, star, index);
  55.     }
  56. }
  57. //10万个数的数组，耗时：26毫秒

算法复杂度：O(nlogn)
算法空间复杂度：O(n)
算法稳定性：稳定

七、堆排序

大顶堆概念：每个节点的值都大于或者等于它的左右子节点的值，所以顶点的数就是最大值。
在这里插入图片描述
思路：

  1. 对原数组构建成大顶堆。
  2. 交换头尾值，尾指针索引减一，固定最大值。
  3. 重新构建大顶堆。
  4. 重复步骤2~3，直到最后一个元素，排序完成。

构建大顶堆的思路，可以看代码注释。

动画演示：
在这里插入图片描述
实现代码：

  1. /**
  2.  * @author Ye Hongzhi 公众号：java技术爱好者
  3.  * @name HeapSort
  4.  * @date 2020-09-08 23:34
  5.  **/
  6. public class HeapSort extends BaseSort {
  7.  
  8.     public static void main(String[] args) {
  9.         HeapSort sort = new HeapSort();
  10.         sort.printNums();
  11.     }
  12.  
  13.     @Override
  14.     protected void sort(int[] nums) {
  15.         if (nums == null || nums.length < 2) {
  16.             return;
  17.         }
  18.         heapSort(nums);
  19.     }
  20.  
  21.     private void heapSort(int[] nums) {
  22.         if (nums == null || nums.length < 2) {
  23.             return;
  24.         }
  25.         //构建大根堆
  26.         createTopHeap(nums);
  27.         int size = nums.length;
  28.         while (size > 1) {
  29.             //大根堆的交换头尾值，固定最大值在末尾
  30.             swap(nums, 0, size - 1);
  31.             //末尾的索引值往左减1
  32.             size--;
  33.             //重新构建大根堆
  34.             updateHeap(nums, size);
  35.         }
  36.     }
  37.  
  38.     private void createTopHeap(int[] nums) {
  39.         for (int i = 0; i < nums.length; i++) {
  40.             //当前插入的索引
  41.             int currIndex = i;
  42.             //父节点的索引
  43.             int parentIndex = (currIndex - 1) / 2;
  44.             //如果当前遍历的值比父节点大的话，就交换值。然后继续往上层比较
  45.             while (nums[currIndex] > nums[parentIndex]) {
  46.                 //交换当前遍历的值与父节点的值
  47.                 swap(nums, currIndex, parentIndex);
  48.                 //把父节点的索引指向当前遍历的索引
  49.                 currIndex = parentIndex;
  50.                 //往上计算父节点索引
  51.                 parentIndex = (currIndex - 1) / 2;
  52.             }
  53.         }
  54.     }
  55.  
  56.     private void updateHeap(int[] nums, int size) {
  57.         int index = 0;
  58.         //左节点索引
  59.         int left = 2 * index + 1;
  60.         //右节点索引
  61.         int right = 2 * index + 2;
  62.         while (left < size) {
  63.             //最大值的索引
  64.             int largestIndex;
  65.             //如果右节点大于左节点，则最大值索引指向右子节点索引
  66.             if (right < size && nums[left] < nums[right]) {
  67.                 largestIndex = right;
  68.             } else {
  69.                 largestIndex = left;
  70.             }
  71.             //如果父节点大于最大值，则把父节点索引指向最大值索引
  72.             if (nums[index] > nums[largestIndex]) {
  73.                 largestIndex = index;
  74.             }
  75.             //如果父节点索引指向最大值索引，证明已经是大根堆，退出循环
  76.             if (largestIndex == index) {
  77.                 break;
  78.             }
  79.             //如果不是大根堆，则交换父节点的值
  80.             swap(nums, largestIndex, index);
  81.             //把最大值的索引变成父节点索引
  82.             index = largestIndex;
  83.             //重新计算左节点索引
  84.             left = 2 * index + 1;
  85.             //重新计算右节点索引
  86.             right = 2 * index + 2;
  87.         }
  88.     }
  89.  
  90.     private void swap(int[] nums, int i, int j) {
  91.         int temp = nums[i];
  92.         nums[i] = nums[j];
  93.         nums[j] = temp;
  94.     }
  95. }
  96. //10万个数的数组，耗时：38毫秒

算法复杂度：O(nlogn)
算法空间复杂度：O(1)
算法稳定性：不稳定

八、桶排序

思路：

  1. 找出最大值，最小值。
  2. 根据数组的长度，创建出若干个桶。
  3. 遍历数组的元素，根据元素的值放入到对应的桶中。
  4. 对每个桶的元素进行排序(可使用快排，插入排序等)。
  5. 按顺序合并每个桶的元素，排序完成。

对于数组中的元素分布均匀的情况，排序效率较高。相反的，如果分布不均匀，则会导致大部分的数落入到同一个桶中，使效率降低。

动画演示(来源于五分钟学算法，侵删)：
在这里插入图片描述
实现代码：

  1. /**
  2.  * @author Ye Hongzhi 公众号：java技术爱好者
  3.  * @name BucketSort
  4.  * @date 2020-09-08 23:37
  5.  **/
  6. public class BucketSort extends BaseSort {
  7.  
  8.     public static void main(String[] args) {
  9.         BucketSort sort = new BucketSort();
  10.         sort.printNums();
  11.     }
  12.  
  13.     @Override
  14.     protected void sort(int[] nums) {
  15.         if (nums == null || nums.length < 2) {
  16.             return;
  17.         }
  18.         bucketSort(nums);
  19.     }
  20.  
  21.     public void bucketSort(int[] nums) {
  22.         if (nums == null || nums.length < 2) {
  23.             return;
  24.         }
  25.         //找出最大值，最小值
  26.         int max = Integer.MIN_VALUE;
  27.         int min = Integer.MAX_VALUE;
  28.         for (int num : nums) {
  29.             min = Math.min(min, num);
  30.             max = Math.max(max, num);
  31.         }
  32.         int length = nums.length;
  33.         //桶的数量
  34.         int bucketCount = (max - min) / length + 1;
  35.         int[][] bucketArrays = new int[bucketCount][];
  36.         //遍历数组，放入桶内
  37.         for (int i = 0; i < length; i++) {
  38.             //找到桶的下标
  39.             int index = (nums[i] - min) / length;
  40.             //添加到指定下标的桶里，并且使用插入排序排序
  41.             bucketArrays[index] = insertSortArrays(bucketArrays[index], nums[i]);
  42.         }
  43.         int k = 0;
  44.         //合并全部桶的
  45.         for (int[] bucketArray : bucketArrays) {
  46.             if (bucketArray == null || bucketArray.length == 0) {
  47.                 continue;
  48.             }
  49.             for (int i : bucketArray) {
  50.                 //把值放回到nums数组中
  51.                 nums[k++] = i;
  52.             }
  53.         }
  54.     }
  55.  
  56.     //每个桶使用插入排序进行排序
  57.     private int[] insertSortArrays(int[] arr, int num) {
  58.         if (arr == null || arr.length == 0) {
  59.             return new int[]{num};
  60.         }
  61.         //创建一个temp数组，长度是arr数组的长度+1
  62.         int[] temp = new int[arr.length + 1];
  63.         //把传进来的arr数组，复制到temp数组
  64.         for (int i = 0; i < arr.length; i++) {
  65.             temp[i] = arr[i];
  66.         }
  67.         //找到一个位置，插入，形成新的有序的数组
  68.         int i;
  69.         for (i = temp.length - 2; i >= 0 && temp[i] > num; i--) {
  70.             temp[i + 1] = temp[i];
  71.         }
  72.         //插入需要添加的值
  73.         temp[i + 1] = num;
  74.         //返回
  75.         return temp;
  76.     }
  77. }
  78. //10万个数的数组，耗时：8750毫秒

算法复杂度：O(M+N)

算法空间复杂度：O(M+N)

算法稳定性：稳定(取决于桶内的排序算法，这里使用的是插入排序所以是稳定的)。

总结

在这里插入图片描述
动画演示来源于算法学习网站：https://visualgo.net

讲完这些排序算法后，可能有人会问学这些排序算法有什么用呢，难道就为了应付笔试面试？平时开发也没用得上这些。

我觉得我们应该换个角度来看，比如高中时我们学物理，化学，数学，那么多公式定理，现在也没怎么用得上，但是高中课本为什么要教这些呢？

我的理解是：第一，普及一些常识性的问题。第二，锻炼思维，提高解决问题的能力。第三，为了区分人才。

回到学排序算法有什么用的问题上，实际上也一样。这些最基本的排序算法就是一些常识性的问题，作为开发者应该了解掌握。同时也锻炼了编程思维，其中包含有双指针，分治，递归等等的思想。最后在面试中体现出来的就是人才的划分，懂得这些基本的排序算法当然要比不懂的人要更有竞争力。

 

 

原文链接
本文为阿里云原创内容，未经允许不得转载。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/759746
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号