一分钟带你快速了解快速排序算法(八种经典排序算法总结)

前言

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

一、冒泡排序

思路:

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

动画演示:

一分钟带你快速了解快速排序算法(八种经典排序算法总结)(1)

实现代码:

/** * @author Ye Hongzhi 公众号:java技术爱好者 * @name BubbleSort * @date 2020-09-05 21:38 **/ public class BubbleSort extends BaseSort { public static void main(String[] args) { BubbleSort sort = new BubbleSort(); sort.printNums(); } @Override protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } for (int i = 0; i < nums.length - 1; i ) { for (int j = 0; j < nums.length - i - 1; j ) { if (nums[j] > nums[j 1]) { int temp = nums[j]; nums[j] = nums[j 1]; nums[j 1] = temp; } } } } } //10万个数的数组,耗时:21554毫秒

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

空间复杂度:O(1)

算法稳定性:稳定

二、插入排序

思路:

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

动画演示:

一分钟带你快速了解快速排序算法(八种经典排序算法总结)(2)

实现代码:

/** * @author Ye Hongzhi 公众号:java技术爱好者 * @name InsertSort * @date 2020-09-05 22:34 **/ public class InsertSort extends BaseSort { public static void main(String[] args) { BaseSort sort = new InsertSort(); sort.printNums(); } @Override protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } for (int i = 0; i < nums.length - 1; i ) { //当前值 int curr = nums[i 1]; //上一个数的指针 int preIndex = i; //在数组中找到一个比当前遍历的数小的第一个数 while (preIndex >= 0 && curr < nums[preIndex]) { //把比当前遍历的数大的数字往后移动 nums[preIndex 1] = nums[preIndex]; //需要插入的数的下标往前移动 preIndex--; } //插入到这个数的后面 nums[preIndex 1] = curr; } } } //10万个数的数组,耗时:2051毫秒

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

空间复杂度:O(1)

算法稳定性:稳定

三、选择排序

思路:

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

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

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

动画演示:

一分钟带你快速了解快速排序算法(八种经典排序算法总结)(3)

实现代码:

/** * @author Ye Hongzhi 公众号:java技术爱好者 * @name SelectSort * @date 2020-09-06 22:27 **/ public class SelectSort extends BaseSort { public static void main(String[] args) { SelectSort sort = new SelectSort(); sort.printNums(); } @Override protected void sort(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; } } if (minIndex != i) { int temp = nums[i]; nums[minIndex] = temp; nums[i] = nums[minIndex]; } } } } //10万个数的数组,耗时:8492毫秒

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

四、希尔排序

思路:

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

动画演示:

一分钟带你快速了解快速排序算法(八种经典排序算法总结)(4)

实现代码:

/** * @author Ye Hongzhi 公众号:java技术爱好者 * @name SelectSort * @date 2020-09-06 22:27 **/ public class ShellSort extends BaseSort { public static void main(String[] args) { ShellSort sort = new ShellSort(); sort.printNums(); } @Override protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } int length = nums.length; int temp; //步长 int gap = length / 2; while (gap > 0) { for (int i = gap; i < length; i ) { temp = nums[i]; int preIndex = i - gap; while (preIndex >= 0 && nums[preIndex] > temp) { nums[preIndex gap] = nums[preIndex]; preIndex -= gap; } nums[preIndex gap] = temp; } gap /= 2; } } } //10万个数的数组,耗时:261毫秒

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

五、快速排序

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

思路:

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

动画演示:

一分钟带你快速了解快速排序算法(八种经典排序算法总结)(5)

实现代码:

/** * @author Ye Hongzhi 公众号:java技术爱好者 * @name SelectSort * @date 2020-09-06 22:27 **/ public class QuickSort extends BaseSort { public static void main(String[] args) { QuickSort sort = new QuickSort(); sort.printNums(); } @Override protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } quickSort(nums, 0, nums.length - 1); } private void quickSort(int[] nums, int star, int end) { if (star > end) { return; } int i = star; int j = end; int key = nums[star]; while (i < j) { while (i < j && nums[j] > key) { j--; } while (i < j && nums[i] <= key) { i ; } if (i < j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } nums[star] = nums[i]; nums[i] = key; quickSort(nums, star, i - 1); quickSort(nums, i 1, end); } } //10万个数的数组,耗时:50毫秒

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

六、归并排序

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

思路:

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

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

动画演示:

一分钟带你快速了解快速排序算法(八种经典排序算法总结)(6)

实现代码:

/** * @author Ye Hongzhi 公众号:java技术爱好者 * @name MergeSort * @date 2020-09-08 23:30 **/ public class MergeSort extends BaseSort { public static void main(String[] args) { MergeSort sort = new MergeSort(); sort.printNums(); } @Override protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } //归并排序 mergeSort(0, nums.length - 1, nums, new int[nums.length]); } private void mergeSort(int star, int end, int[] nums, int[] temp) { //递归终止条件 if (star >= end) { return; } int mid = star (end - star) / 2; //左边进行归并排序 mergeSort(star, mid, nums, temp); //右边进行归并排序 mergeSort(mid 1, end, nums, temp); //合并左右 merge(star, end, mid, nums, temp); } private void merge(int star, int end, int mid, int[] nums, int[] temp) { int index = 0; int i = star; int j = mid 1; while (i <= mid && j <= end) { if (nums[i] > nums[j]) { temp[index ] = nums[j ]; } else { temp[index ] = nums[i ]; } } while (i <= mid) { temp[index ] = nums[i ]; } while (j <= end) { temp[index ] = nums[j ]; } //把临时数组中已排序的数复制到nums数组中 if (index >= 0) System.arraycopy(temp, 0, nums, star, index); } } //10万个数的数组,耗时:26毫秒

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

七、堆排序

大顶堆概念:每个节点的值都大于或者等于它的左右子节点的值,所以顶点的数就是最大值。

一分钟带你快速了解快速排序算法(八种经典排序算法总结)(7)

思路:

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

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

动画演示:

一分钟带你快速了解快速排序算法(八种经典排序算法总结)(8)

实现代码:

/** * @author Ye Hongzhi 公众号:java技术爱好者 * @name HeapSort * @date 2020-09-08 23:34 **/ public class HeapSort extends BaseSort { public static void main(String[] args) { HeapSort sort = new HeapSort(); sort.printNums(); } @Override protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } heapSort(nums); } private void heapSort(int[] nums) { if (nums == null || nums.length < 2) { return; } //构建大根堆 createTopHeap(nums); int size = nums.length; while (size > 1) { //大根堆的交换头尾值,固定最大值在末尾 swap(nums, 0, size - 1); //末尾的索引值往左减1 size--; //重新构建大根堆 updateHeap(nums, size); } } private void createTopHeap(int[] nums) { for (int i = 0; i < nums.length; i ) { //当前插入的索引 int currIndex = i; //父节点的索引 int parentIndex = (currIndex - 1) / 2; //如果当前遍历的值比父节点大的话,就交换值。然后继续往上层比较 while (nums[currIndex] > nums[parentIndex]) { //交换当前遍历的值与父节点的值 swap(nums, currIndex, parentIndex); //把父节点的索引指向当前遍历的索引 currIndex = parentIndex; //往上计算父节点索引 parentIndex = (currIndex - 1) / 2; } } } private void updateHeap(int[] nums, int size) { int index = 0; //左节点索引 int left = 2 * index 1; //右节点索引 int right = 2 * index 2; while (left < size) { //最大值的索引 int largestIndex; //如果右节点大于左节点,则最大值索引指向右子节点索引 if (right < size && nums[left] < nums[right]) { largestIndex = right; } else { largestIndex = left; } //如果父节点大于最大值,则把父节点索引指向最大值索引 if (nums[index] > nums[largestIndex]) { largestIndex = index; } //如果父节点索引指向最大值索引,证明已经是大根堆,退出循环 if (largestIndex == index) { break; } //如果不是大根堆,则交换父节点的值 swap(nums, largestIndex, index); //把最大值的索引变成父节点索引 index = largestIndex; //重新计算左节点索引 left = 2 * index 1; //重新计算右节点索引 right = 2 * index 2; } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } //10万个数的数组,耗时:38毫秒

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

八、桶排序

思路:

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

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

动画演示(来源于五分钟学算法,侵删):

一分钟带你快速了解快速排序算法(八种经典排序算法总结)(9)

实现代码:

/** * @author Ye Hongzhi 公众号:java技术爱好者 * @name BucketSort * @date 2020-09-08 23:37 **/ public class BucketSort extends BaseSort { public static void main(String[] args) { BucketSort sort = new BucketSort(); sort.printNums(); } @Override protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } bucketSort(nums); } public void bucketSort(int[] nums) { if (nums == null || nums.length < 2) { return; } //找出最大值,最小值 int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for (int num : nums) { min = Math.min(min, num); max = Math.max(max, num); } int length = nums.length; //桶的数量 int bucketCount = (max - min) / length 1; int[][] bucketArrays = new int[bucketCount][]; //遍历数组,放入桶内 for (int i = 0; i < length; i ) { //找到桶的下标 int index = (nums[i] - min) / length; //添加到指定下标的桶里,并且使用插入排序排序 bucketArrays[index] = insertSortArrays(bucketArrays[index], nums[i]); } int k = 0; //合并全部桶的 for (int[] bucketArray : bucketArrays) { if (bucketArray == null || bucketArray.length == 0) { continue; } for (int i : bucketArray) { //把值放回到nums数组中 nums[k ] = i; } } } //每个桶使用插入排序进行排序 private int[] insertSortArrays(int[] arr, int num) { if (arr == null || arr.length == 0) { return new int[]{num}; } //创建一个temp数组,长度是arr数组的长度 1 int[] temp = new int[arr.length 1]; //把传进来的arr数组,复制到temp数组 for (int i = 0; i < arr.length; i ) { temp[i] = arr[i]; } //找到一个位置,插入,形成新的有序的数组 int i; for (i = temp.length - 2; i >= 0 && temp[i] > num; i--) { temp[i 1] = temp[i]; } //插入需要添加的值 temp[i 1] = num; //返回 return temp; } } //10万个数的数组,耗时:8750毫秒

算法复杂度:O(M N)

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

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

总结

一分钟带你快速了解快速排序算法(八种经典排序算法总结)(10)

动画演示来源于算法学习网站:https://visualgo.net

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

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

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

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

建议大家看完之后,能找时间动手写一下,加深理解。

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

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页