【java-数据结构】七大排序 “华山论剑”：谁才是时间复杂度的王者？，从初学者到高手必备技巧。

一、引言

在计算机编程的世界里，排序算法是基础且至关重要的一部分。不同的排序算法在时间复杂度、空间复杂度和稳定性等方面各有优劣。本文将详细介绍七种常见的排序算法，包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、希尔排序，还会提及非基于比较的排序（以计数排序为例），同时，我们会分析它们的时间复杂度，探寻谁才是时间复杂度上的“王者”，也会分享从初学者到高手使用这些算法的必备技巧。

二、七大排序算法 Java 实现

排序：所谓排序，就是使⼀串记录，按照其中的某个或某些关键字的⼤⼩，递增或递减的排列起来的 操作。

1. 冒泡排序

冒泡排序是一种简单直观的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i  arr[j + 1]) {
                    // 交换 arr[j+1] 和 arr[j]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

时间复杂度分析：最坏和平均情况下为 O ( n 2 ) O(n^2) O(n2)，最好情况下（数组已经有序）为 O ( n ) O(n) O(n)

空间复杂度：O(1)

稳定性：稳定。

2. 选择排序

2.1 基本思想：

每⼀次从待排序的数据元素中选出最⼩（或最⼤）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

2.2 直接选择排序

• 在元素集合array[i]–array[n-1]中选择关键码最⼤(⼩)的数据元素

• 若它不是这组元素中的最后⼀个(第⼀个)元素，则将它与这组元素中的最后⼀个（第⼀个）元素交

换

• 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个

元素

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i  
时间复杂度分析：无论数组初始状态如何，时间复杂度都为  
     
      
       
       
         O 
        
       
         ( 
        
        
        
          n 
         
        
          2 
         
        
       
         ) 
        
       
      
        O(n^2) 
       
      
    O(n2)。
 
3. 插入排序
 
3.1 基本思想：
 
 
 
直接插⼊排序是⼀种简单的插⼊排序法，其基本思想是：把待排序的记录按其关键码值的⼤⼩逐个插⼊到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列 。
 
 
实际中我们玩扑克牌时，就⽤了插⼊排序的思想。
 
public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i = 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
 
时间复杂度分析：最坏和平均情况下为  
     
      
       
       
         O 
        
       
         ( 
        
        
        
          n 
         
        
          2 
         
        
       
         ) 
        
       
      
        O(n^2) 
       
      
    O(n2)，最好情况下（数组已经有序）为  
     
      
       
       
         O 
        
       
         ( 
        
       
         n 
        
       
         ) 
        
       
      
        O(n) 
       
      
    O(n)。
 
4. 归并排序
 
 
 
归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divideand Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。 归并排序采用分治法，将一个数组分成两个子数组，对这两个子数组分别进行排序，然后将排好序的子数组合并成一个最终的有序数组。归并排序核⼼步骤：
 
 
 
4.1海量数据的排序问题
 
 
 
外部排序：排序过程需要在磁盘等外部存储进⾏的排序 前提：内存只有 1G，需要排序的数据有 100G
 
 
因为内存中因为⽆法把所有数据全部放下，所以需要外部排序，⽽归并排序是最常⽤的外部排序
 
 
 
先把⽂件切分成 200 份，每个 512 M
分别对 512 M 排序，因为内存已经可以放的下，所以任意排序⽅式都可以
进⾏ 2路归并，同时对 200 份有序⽂件做归并过程，最终结果就有序了
public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length 
            return;
        }
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left  temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {12, 34, 54, 2, 3};
        shellSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
 
时间复杂度分析：希尔排序的时间复杂度与所选择的增量序列有关，希尔排序时间复杂度不好计算，因为 gap 的取值很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。
 
8、其他非基于比较的排序：计数排序、基数排序、桶排序
 
这些排序算法的共同特点是，它们不依赖于比较元素的大小，而是通过其他方式来决定排序结果。它们在某些特定条件下比基于比较的排序算法（如快速排序、归并排序）更高效，特别是当元素范围较小或数据类型特定时。
 

8.1总结：非基于比较的排序算法的优势

这些排序算法的优势在于它们不依赖于比较，而是通过计数、按位处理或者分桶的方式来进行排序，因此在特定的条件下，它们比基于比较的排序算法（如快速排序、归并排序）更高效。适用于已知范围、特定数据类型（如整数、固定长度的字符串）和均匀分布的数据。但它们也有一些局限性，尤其是在数据范围较大或数据分布不均匀的情况下，可能会失去优势。

三、排序算法复杂度及稳定性分析

四、时间复杂度 “王者” 之争

从上述时间复杂度分析来看，在大多数情况下，归并排序、快速排序和堆排序的时间复杂度表现较好，尤其是在处理大规模数据时，它们的平均时间复杂度为 O ( n l o g n ) O(n log n) O(nlogn)。而归并排序在最坏情况下也能保证 O ( n l o g n ) O(n log n) O(nlogn) 的时间复杂度，相对更加稳定。不过，快速排序在实际应用中，由于其常数因子较小，通常速度更快，但要注意避免最坏情况的发生。

非基于比较的排序算法（如计数排序）在特定场景下（数据范围较小）能达到线性时间复杂度 O ( n + k ) O(n + k) O(n+k)，是时间复杂度方面的佼佼者，但它的适用范围相对较窄，需要满足一定的条件。

对比七大排序算法的特点、时间复杂度、应用场景和优缺点：

五、从初学者到高手的必备技巧

初学者

• 理解基本概念：先从简单的排序算法（如冒泡排序、选择排序、插入排序）入手，理解排序的基本思想和实现过程。
• 多写代码：通过手动实现代码，加深对算法的理解，同时注意边界条件的处理。
• 分析复杂度：学习分析算法的时间复杂度和空间复杂度，了解不同算法在性能上的差异。

  进阶者

  • 掌握分治法和递归思想：深入理解归并排序和快速排序的分治策略和递归实现，这对于解决其他复杂问题也很有帮助。
  • 优化算法：尝试对已有的算法进行优化，例如快速排序中选择更好的基准元素，减少最坏情况的发生。
  • 学习数据结构：了解堆这种数据结构，掌握堆排序的原理和实现。

    高手

    • 应用场景分析：根据不同的应用场景选择合适的排序算法，考虑数据规模、数据特点（如是否接近有序）等因素。
    • 研究算法变体：探索排序算法的各种变体和优化方案，进一步提升算法的性能。
    • 性能测试和调优：通过性能测试工具，对不同算法进行实际测试和调优，确保在实际应用中达到最佳性能。

      六、总结：选择最适合你的排序算法

      • 小数据量：冒泡排序、选择排序、插入排序。
      • 大数据量：快速排序、归并排序、堆排序。
      • 特定数据类型：计数排序、基数排序、桶排序（适用于整数或范围小的数据）。
      • 外部排序：归并排序。

        七、最后在加上一些题目：

        1. 快速排序算法是基于(A的⼀个排序算法。

           A：分治法 B：贪⼼法 C：递归法 D：动态规划法

        2.对记录（54,38,96,23,15,72,60,45,83）进⾏从⼩到⼤的直接插⼊排序时，当把第8个记录45插 ⼊到有序表时，为找到插⼊位置需⽐较(C)次？（采⽤从后往前⽐较）

        A: 3 B: 4 C: 5 D: 6

        3.以下排序⽅式中占⽤O(n)辅助存储空间的是(D)

        A: 简单排序 B: 快速排序 C: 堆排序 D: 归并排序

        4.下列排序算法中稳定且时间复杂度为O(n^2)的是(B)

        A: 快速排序 B: 冒泡排序 C: 直接选择排序 D: 归并排序

        5.关于排序，下⾯说法不正确的是(D)

        A: 快排时间复杂度为O(N*logN)，空间复杂度为O(logN)

        B: 归并排序是⼀种稳定的排序,堆排序和快排均不稳定

        C: 序列基本有序时，快排退化成 “冒泡排序”，直接插⼊排序最快

        D: 归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)

        6.设⼀组初始记录关键字序列为(65,56,72,99,86,25,34,66)，则以第⼀个关键字65为基准⽽得到的 ⼀趟快速排序结果是（A）

        A: 34，56，25，65，86，99，72，66 B: 25，34，56，65，99，86，72，66

        C:34，56，25，65，66，99，86，72 D: 34，56，25，65，99，86，72，66