当前位置：首页 > article >正文

Java实现三种排序方式

article 2025/3/11 9:23:09

这篇文章将详细介绍冒泡排序、插入排序和快速排序这三种经典排序算法的原理以及Java实现。

冒泡排序

冒泡排序是一种简单的排序算法，它重复地使用要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来，直到排序完成
*这个算法的名字由来是因为小的元素会经由交换慢慢“浮”到数列的顶端（升序排列时）。

以下是一个冒泡排序示例：

public class Main {
    public static void main(String[] args) {
        int arr[] = {5,7,1,68,34};
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换元素
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

在该示例中，外层循环for (int i = 0; i < n - 1; i++)控制排序的轮数，内层循环for (int j = 0; j < n - i - 1; j++)用于比较相邻的元素，在每一轮排序中，由于最大的元素会“浮”到数组的末尾，所以下一轮比较的元素个数会减少1。
当 arr[j] > arr[j + 1] 时，说明这两个相邻元素的顺序不符合升序要求，通过一个临时变量 temp 来交换这两个元素的位置。

时间复杂度

最坏：当数组是倒序排列时，每一轮比较都需要交换元素，总共需要进行n(n - 1)/2次比较，所以时间复杂度为O(n^2)。
最好：当数组已经是正序排列时，只需要进行n - 1次比较，没有元素交换，时间复杂度为O(n)。
平均情况：时间复杂度为O(n^2)，因为平均情况下，需要n(n-1)/4次操作。

插入排序

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，以下为一个插入排序示例：

public class Main {
    public static void main(String[] args) {
        int arr[] = {5,7,1,68,34};
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

外层循环for (int i = 1; i < n; i++)从数组的第二个元素开始，因为第一个元素可以看作已经排好序了。
对于每一个未排序的元素key = arr[i] ，内层的while循环while(j >=0 && arr[j] > key)在已排序的序列中从后向前扫描，当arr[j] > key时，说明当前元素 arr[j] 的位置应该在key之后，所以将arr[j]向后移动一位，然后 j 减1，继续向前比较，当找到合适的位置（arr[j] <= key 或者 j < 0）时，将key插入到该位置。

时间复杂度

最坏：当数组是倒序排列时，对于第 i 个元素，需要比较 i 次才能插入到正确的位置，总共需要进行n(n - 1)/2次比较，时间复杂度为O(n^2)。
最好：当数组已经是正序排列时，每次插入只需要比较一次，时间复杂度为O(n)。
平均情况：时间复杂度为O(n^2)。

快速排序

速排序是一种分治算法，它会选择一个基准元素，将数组分为两部分，左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素，然后对这两部分分别进行快速排序，直到整个数组有序，以下为快速排序示例：

public class Main {
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            // 选择最左边元素作为基准元素
            int pivot = arr[left];
            int i = left;
            int j = right;
            while (i < j) {
                // 从右往左找第一个小于基准元素的数
                while (i < j && arr[j] >= pivot) {
                    j--;
                }
                if (i < j) {
                    // 找到后将其放到左边位置（也就是i指向的位置）
                    arr[i] = arr[j];
                    i++;
                }
                // 从左往右找第一个大于基准元素的数
                while (i < j && arr[i] <= pivot) {
                    i++;
                }
                if (i < j) {
                    // 找到后将其放到右边位置（也就是j指向的位置）
                    arr[j] = arr[i];
                    j--;
                }
            }
            // 把基准元素放到最终正确的位置（i和j相遇的位置）
            arr[i] = pivot;

            // 对基准元素左边的子数组进行快速排序
            quickSort(arr, left, i - 1);
            // 对基准元素右边的子数组进行快速排序
            quickSort(arr, i + 1, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = {66,55,133,54,12};
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

先从右往左通过内层的while循环找第一个小于基准元素pivot的数，不断让 j往左移动，直到找到这样的数或者i 和 j相遇了，找到这个数后把它放到i 指向的位置，然后i指针往右移动一位。
从左往右找第一个大于基准元素的数，同样通过内层 while 循环让i不断往右移动，直到找到或者 i 和 j 相遇，找到后把这个数放到 j 指向的位置。
最终 i 和 j 会相遇，这个相遇的位置就是基准元素最终应该放置的正确位置。

时间复杂度

最坏：当每次选择的基准元素都是数组中的最大或最小元素时，快速排序会退化为冒泡排序，时间复杂度为O(n^2)，当数组已经是正序或倒序排列时再进行快排时会出现这种情况。
最好：当每次划分都能将数组分为两个大小相等的子数组时，时间复杂度为O(nlogn)。
平均情况：时间复杂度为O(nlogn)，因为在大多数情况下，划分操作能够比较均匀地将数组分为两部分。