史上最全经典排序算法总结(Java实现)

查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以Java
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码 


查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只要熟悉了思想,灵活运用也不是难事。一般在面试中最常考的是快速排序和归并排序,并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。面试官对于这些排序可能会要求比较各自的优劣、各种算法的思想及其使用场景。还有要会分析算法的时间和空间复杂度。通常查找和排序算法的考察是面试的开始,如果这些问题回答不好,估计面试官都没有继续面试下去的兴趣都没了。所以想开个好头就要把常见的排序算法思想及其特点要熟练掌握,有必要时要熟练写出代码。下面主要介绍经典排序算法。

0、排序算法说明

0.1 排序的定义

对一序列对象根据某个关键字进行排序。

0.2 术语说明

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
  • 不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;
  • 内排序:所有排序操作都在内存中完成;
  • 外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
  • 时间复杂度: 一个算法执行所耗费的时间。
  • 空间复杂度:运行完一个程序所需内存的大小。

0.3 算法总结

在这里插入图片描述

图片名词解释:

  • n: 数据规模
  • k: “桶”的个数
  • In-place: 占用常数内存,不占用额外内存
  • Out-place: 占用额外内存

0.4 算法分类

在这里插入图片描述

0.5 比较和非比较的区别

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位置。
冒泡排序之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中,问题规模通过分治法消减为logN次,所以时间复杂度平均O(nlogn)
比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序。可以说,比较排序适用于一切需要排序的情况。

计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前,应该有多少个元素来排序。针对数组arr,计算arr[i]之前有多少个元素,则唯一确定了arr[i]在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决。算法时间复杂度O(n)
非比较排序时间复杂度底,但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

1、冒泡排序(Bubble Sort)

冒泡排序

2、选择排序(Selection Sort)

选择排序

3、插入排序(Insertion Sort)

插入排序

4、希尔排序(Shell Sort)

希尔排序

5、归并排序(Merge Sort)

归并排序

6、快速排序(Quick Sort)

快速排序

7、堆排序(Heap Sort)

堆排序

8、计数排序(Counting Sort)

计数排序

9、桶排序(Bucket Sort)

桶排序

10、基数排序(Radix Sort)

基数排序

本文来源ThinkWon的博客,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/1599

发表评论