Java常见排序算法详解：快速排序、插入排序与冒泡排序

在程序设计中，排序是最基本的操作之一。Java提供了多种排序算法，今天我们将介绍三种常见的排序方法：快速排序、插入排序和冒泡排序。我们不仅会分析它们的基本原理，还会提供实际的代码实现，帮助大家更好地理解并应用这些排序算法。

一、快速排序（Quick Sort）

快速排序是一种分治法的排序算法，其基本思想是选择一个"基准"元素，将数组分成两部分，一部分的元素都小于基准元素，另一部分的元素都大于基准元素。然后递归地对这两部分分别进行排序。由于分治法的高效性，快速排序通常在很多实际应用中表现出色。

快速排序实现

public class Arrar02 {
    public static void main(String[] args) {
        int[] arr = new int[]{42,53,72,93,15,72};
        //快速排序
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    private static void quickSort(int[] arr, int left, int right) {
        int i,j,temp,t;
        if(left>=right)
            return;
         temp=arr[left];
        i=left;
        j=right;
        while (i<j){
            while (i<j&&temp <= arr[j]) {
                j--;
            }
            while (i<j&&temp>=arr[i])
            {
                i++;
            }

            if(i<j){
                t=arr[i];
                arr[i]=arr[j];
                arr[j]=t;
            }
        }
        arr[left]=arr[i];
        arr[i]=temp;
        quickSort(arr, left,i-1);
        quickSort(arr,i+1,right);
    }
}

  结果展示：

15 42 53 72 72 93 

快速排序解析

• 基准选择：通常，我们选择数组的第一个元素作为基准，但也可以选择其他位置的元素（例如随机选择）。
• 分治法：通过一个循环，将数组分成两部分，使得左边部分的所有元素都比基准元素小，右边部分的所有元素都比基准元素大。
• 递归排序：递归地对两部分数组进行排序，直到每部分数组的元素都已经有序。

时间复杂度

• 最优时间复杂度：O(n log n)
• 最差时间复杂度：O(n²)，发生在数组已经接近有序时（例如，始终选择数组的第一个元素作为基准）。

二、插入排序（Insertion Sort）

插入排序是一种简单的排序算法，它通过将一个元素插入到已经排好序的部分，直到所有元素都有序。对于数据量较小的数组，插入排序的效率较高。

插入排序实现

public class TestBubbleSort {
    public static void main(String[] args) {

        int[] arr = {450, 34, 25, 73, 83, 16};
        insertSort(arr);
    }
 private static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > temp) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp;
        }
        for (int ele : arr
        ) {
            System.out.print(ele + "\t");
        }

    }
}

 结果展示： 

16	25	34	73	83	450

插入排序解析

• 插入操作：从第二个元素开始，依次将每个元素与前面的元素进行比较，找到其合适的位置并插入。
• 时间复杂度：最坏情况下（数组逆序），时间复杂度为O(n²)，但对于接近有序的数组，插入排序非常高效，时间复杂度接近O(n)。

时间复杂度

• 最优时间复杂度：O(n)（当数组已经排好序时）
• 最差时间复杂度：O(n²)

三、冒泡排序（Bubble Sort）

冒泡排序是一种简单的交换排序算法，其基本思想是通过不断交换相邻元素的顺序，逐步将最大（或最小）的元素“冒泡”到数组的一端。虽然冒泡排序的实现简单，但它并不是非常高效。

冒泡排序实现

public class TestBubbleSort {
    public static void main(String[] args) {

        int[] arr = {450, 34, 25, 73, 83, 16};
        bubbleSort(arr);
    }
//冒泡排序
    private static void bubbleSort(int[] arr) {
        int temp = 0;
        //比较arr.length-1轮
        for (int i = 0; i < arr.length - 1; i++) {
            //每轮比较arr.length-1-i次
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }

        }
        for (int ele : arr
        ) {
            System.out.print(ele + "\t");
        }
    }
}

 结果展示：

16	25	34	73	83	450

冒泡排序解析

• 交换过程：每一轮比较相邻元素，如果它们的顺序错误就交换它们的位置。每一轮循环结束后，最大的元素会“冒泡”到数组的末端。
• 优化：冒泡排序的一个常见优化是，如果在某一轮比较中没有发生任何交换，说明数组已经有序，可以提前退出循环。

时间复杂度

• 最优时间复杂度：O(n)（当数组已经排好序时）
• 最差时间复杂度：O(n²)

四、总结

我们介绍了三种常见的排序算法：快速排序、插入排序和冒泡排序。每种算法都有其特点和适用场景：

1. 快速排序：适用于大规模数据的排序，平均时间复杂度为O(n log n)，性能较优。
2. 插入排序：适用于数据量较小或接近有序的情况，简单易懂，但在大规模数据时效率较低。
3. 冒泡排序：简单易实现，但性能较差，特别是对于大量数据时，时间复杂度为O(n²)。

理解这些排序算法对于编写高效的程序非常重要，尤其在处理大量数据时，选择合适的排序算法能够显著提高性能。在实际应用中，我们常常会根据数据的特点选择合适的排序方法。