十大经典排序算法（Java实现） |
您所在的位置：网站首页 › java简单的整人代码有哪些方法 › 十大经典排序算法（Java实现） |
十大经典排序算法（Java实现）
|
排序算法的重要性不言而喻，为了加深对这十种算法的理解，固写此文。 目录 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）11、总结 首先排序算法可以分为内部排序算法和外部排序算法：在内存中进行的称为内部排序算法，也就是这里所说的这十种算法；相应的，当数据量很大时无法全部拷贝到内存需要使用外存，称为外部排序算法。接下来我们可用如下表来简单概括这十种算法： 十大经典排序算法平均时间复杂度最好时间复杂度最坏时间复杂度空间复杂度排序方式稳定性冒泡排序 O \Omicron O(n2) O \Omicron O(n) O \Omicron O(n2) O \Omicron O(1)In-place稳定选择排序 O \Omicron O(n2) O \Omicron O(n2) O \Omicron O(n2) O \Omicron O(1)In-place不稳定插入排序 O \Omicron O(n2) O \Omicron O(n) O \Omicron O(n2) O \Omicron O(1)In-place稳定希尔排序 O \Omicron O(n1.3) O \Omicron O(n) O \Omicron O(n2) O \Omicron O(1)In-place不稳定归并排序 O \Omicron O(n log \log log2n) O \Omicron O(n log \log log2n) O \Omicron O(n log \log log2n) O \Omicron O(n)Out-place稳定快速排序 O \Omicron O(n log \log log2n) O \Omicron O(n log \log log2n) O \Omicron O(n2) O \Omicron O( log \log log2n)In-place不稳定堆排序 O \Omicron O(n log \log log2n) O \Omicron O(n log \log log2n) O \Omicron O(n log \log log2n) O \Omicron O(1)In-place不稳定计数排序 O \Omicron O(n+k) O \Omicron O(n+k) O \Omicron O(n+k) O \Omicron O(k)Out-place稳定桶排序 O \Omicron O(n+k) O \Omicron O(n+k) O \Omicron O(n2) O \Omicron O(n+k)Out-place稳定基数排序 O \Omicron O(n*k) O \Omicron O(n*k) O \Omicron O(n*k) O \Omicron O(n+k)Out-place稳定表中数据说明： 稳定：如果A原本在B前面，而A=B，排序之后A仍然在B的前面；不稳定：如果A原本在B的前面，而A=B，排序之后A可能会出现在B的后面；时间复杂度： 描述一个算法执行所耗费的时间；空间复杂度：描述一个算法执行所需内存的大小；n：数据规模；k：“桶”的个数；In-place：占用常数内存，不占用额外内存；Out-place：占用额外内存。该十种排序算法可分为如下所示的两大类 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(n log \log logn)，因此也称为非线性时间比较类排序。非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
1、冒泡排序（Bubble Sort）
算法步驟 比较相邻的元素，如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的比价，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；针对所有的元素重复以上的步骤，除了数组最后已经排好序的数组；重复步骤1~3，直到排序完成。
代码实现 public class BubbleSort { public static void bubbleSort(int[] arr) { int len = arr.length; for (int i = 0; i |
【本文地址】
今日新闻 |
推荐新闻 |