Java实现常见排序算法

Java实现常见排序算法

排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。排序的分类：

1. 内部排序:指将需要处理的所有数据都加载到内部存储器中进行排序。

2. 外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。

3. 常见的排序算法分类(见下图):
   

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	In-place	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	In-place	不稳定
插入排序	O(n^2)	O(n)	O(n^2)	O(1)	In-place	稳定
希尔排序	O(n log n)	O(n log^2 n)	O(n log ^2n)	O(1)	In-place	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	Out-place	稳定
快速排序	O(n log n)	O(n log n)	O(n^2)	O(1)	In-place	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	In-place	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	Out-place	稳定
桶排序	O(n+k)	O(n+k)	n^2	O(n+k)	Out-place	不稳定
基数排序	O(n x k)	O(n x k)	O(n x k)	O(n+k)	Out-place	稳定

时间复杂度:一个算法执行所耗费的时间。空间复杂度: 运行完一个程序所需内存的大小

稳定: 如果 a 原本在 b 前面，而 a=b，排序之后 a仍然在 的前面; 不稳定: 如果 a 原本在 b 的前面，而 a=b，排序之后 a可能会出现在 b 的后面

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

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的两个元素，并根据需要交换它们的位置，直到整个列表排序完成。冒泡排序的基本思想是将较大的元素逐渐“浮”到列表的末尾。冒泡排序的时间复杂度为O(n^2)，在大型列表和实际应用中效率低下

1. 从列表的第一个元素开始，依次比较相邻的两个元素。

2. 如果前一个元素大于后一个元素，则交换它们的位置。

3. 继续向后遍历，重复执行步骤 1 和步骤 2，直到遍历到列表末尾。

4. 重复上述步骤，每次遍历都将最大的元素“浮”到列表末尾。

5. 重复执行 n-1 次（n 是列表长度），直到整个列表排序完成。

下面是使用 Java 编写冒泡排序算法的示例代码：

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        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;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 3, 5, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

上面代码可以优化：在内层循环中如果发生了交换操作，则将 flag 设置为 true。在内层循环结束后，检查 flag 的值来判断是否发生了交换操作。如果没有发生交换，则说明列表已经有序，可以提前结束排序过程。
这样修正后的冒泡排序算法可以更准确地判断列表是否已经有序，并在有序时提前结束排序过程，提高了算法的效率。

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean flag = false;
    for (int i = 0; i < n - 1; i++) {
        flag = false; // 将 flag 初始化为 false
        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;
                flag = true; // 设置 flag 为 true
            }
        }
        if (!flag) {
            break;
        }
    }
}

选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，它的基本思想是每次从未排序的部分中选择最小（或最大）的元素，并将其与当前位置进行交换，这样，每一轮遍历都会将一个元素放到正确的位置上，逐渐形成有序序列。通过不断重复这个过程，直到整个列表排序完成。时间复杂度为O(n^2)

以下是选择排序算法的基本步骤：

1. 遍历列表，将第一个元素视为已排序部分。

2. 在未排序部分中找到最小（或最大）的元素。

3. 将找到的最小（或最大）元素与已排序部分末尾的元素进行交换。

4. 将已排序部分末尾向后移动一个位置。

5. 重复上述步骤，直到整个列表排序完成。

示例代码：

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        // 外层循环控制当前待填入的位置
        for (int i = 0; i < n - 1; i++) {
             // 假设当前位置为最小元素的位置
            int minIndex = i;
            // 内层循环找到未排序部分中最小元素的索引
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换最小元素和当前位置元素
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

选择排序是一种原地、稳定、比较类的排序算法。它不需要额外空间，并且对于小型数据集或部分有序的数据集，它可能比其他复杂度较低但需要额外空间的算法更快。然而，选择排序的时间复杂度为 O(n^2)，因此在处理大型数据集时效率较低。比冒泡排序是要快一些

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，其基本思想是将一个元素插入到已排序部分的正确位置中，通过不断地扩大已排序部分的范围，最终完成整个列表的排序。插入排序的时间复杂度为O(n^2)，因此在处理大型数据集时效率较低

以下是插入排序算法的基本步骤：

1. 将列表分为已排序部分和未排序部分。初始时，已排序部分只包含第一个元素，而未排序部分包含剩余的元素。

2. 从未排序部分中取出第一个元素，并将其插入到已排序部分的正确位置中。为了找到正确位置，可以从已排序部分的末尾开始向前比较，并将较大（或较小）的元素向后移动。

3. 重复步骤 2，直到未排序部分中所有元素都被插入到已排序部分中。

4. 整个列表完成排序。

插入排序算法的示例代码：

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        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--;
            }
            // 将待插入元素放入正确的位置
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        insertionSort(arr);
        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

希尔排序

希尔排序（Shell Sort）是一种基于插入排序的排序算法，也被称为“缩小增量排序”（Diminishing Increment Sort）。它通过将整个列表分割成多个较小的子序列，并对这些子序列进行插入排序，从而逐步减少排序的范围，最终完成整个列表的排序。希尔排序在提供了一种平衡了性能和简单性的排序方法。

希尔排序的基本思想是通过预排序来减小逆序数的数量。逆序数是指在一个列表中，有两个元素的相对顺序与期望的排序顺序不符的情况。通过首先以较大的步长进行预排序，可以显著减少逆序数的数量，从而提高后续插入排序的效率。

以下是希尔排序算法的基本步骤：

1. 选择一个增量序列（通常为一个递减的数列），用来分割原始列表。

2. 对每个增量分割出的子序列进行插入排序，也就是将子序列的元素按照插入排序的方式排好序。

3. 逐步缩小增量，重复步骤 2，直到增量为 1，此时整个列表被排序完成。

希尔排序算法的示例代码：

public class Shell {
     public static void shellSort(int[] arr) {
        int n = arr.length;

        // 选择增量序列，通常为 n/2，n/4，...，1
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 对每个子序列进行插入排序
            for (int i = gap; i < n; i++) {
                // 当前待插入元素
                int temp = arr[i];
                int j = i;

                // 插入排序步骤
                while (j >= gap && arr[j - gap] > temp) {
                    // 向后移动元素
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                // 将待插入元素放入正确位置
                arr[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
        shellSort(arr);
        System.out.println("排序后的数组：");
        System.out.print(Arrays.toString(arr));
    }
}

在这段代码中，我们定义了一个 shellSort 方法来执行希尔排序。在每次排序中，我们根据增量序列将列表分割成多个子序列，并对每个子序列进行插入排序。逐步减小增量，直至增量为 1，完成整个排序过程。

希尔排序的时间复杂度取决于所选择的增量序列，通常在平均情况下为 O(nlogn)。尽管希尔排序并不是最快的排序算法，但在某些情况下，特定的增量序列可以使其性能相当不错。希尔排序是一种原地、不稳定、比较类的排序算法，在一些特定场景下可以提供较好的性能。

快速排序

快速排序（Quick Sort）是一种高效的排序算法，它采用分治策略，通过将一个大问题分解为小问题来排序整个数组。快速排序的基本思想是选择一个“基准”元素，然后将数组分成两个子数组，一个子数组中的所有元素小于基准，另一个子数组中的所有元素大于基准。然后，递归地对这两个子数组进行排序，最终得到有序的数组。

快速排序的基本步骤如下：

1. 选择基准元素：从待排序数组中选择一个元素作为基准（pivot）。通常情况下，可以选择第一个元素、最后一个元素或者中间元素作为基准。

2. 分割操作：将数组分割成两个子数组，一个子数组中的所有元素小于基准，另一个子数组中的所有元素大于基准。这个过程称为分割操作。

3. 递归排序：对两个子数组递归地应用快速排序算法。即对小于基准的子数组和大于基准的子数组分别进行快速排序。

4. 合并结果：将经过排序的两个子数组合并成最终的有序数组。

快速排序的关键在于选择合适的基准元素和分割操作。通过不断地将数组分割成较小的子数组，并对子数组进行排序，最终实现整个数组的有序性。快速排序平均时间复杂度为O(nlogn)，性能比冒泡排序和插入排序要好得多。

代码示例

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 找到基准元素的正确位置并进行分割
            int pivotIndex = partition(arr, low, high);

            // 递归地对基准元素的左右子数组进行排序
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        // 选择基准元素（可以选择第一个元素、最后一个元素或中间元素）
        int pivot = arr[high];

        // 初始化分割索引
        int i = low - 1;

        // 遍历数组，将小于基准的元素移到分割索引的左侧
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // 交换元素，将小于基准的元素移到分割索引的左侧
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 将基准元素放入正确的位置
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        // 返回基准元素的位置
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        int n = arr.length;

        quickSort(arr, 0, n - 1);

        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

先定义了一个quickSort函数，它接受一个数组和两个表示要排序部分的开始和结束的索引。然后，它调用partition函数，该函数选择一个基准元素并将所有比它小的元素移动到其左边，比它大的元素移动到其右边。然后，quickSort函数对基准的左右两侧分别进行独立的相同操作。最后，主函数创建了一个需要排序的数组，并调用quickSort函数进行排序，然后打印出排序后的数组

归并排序

归并排序是一种经典的排序算法，它采用分治法的思想，将一个大问题分解为多个小问题，然后将小问题的解合并起来得到最终的解。归并排序的基本思想是将待排序的数组不断地二分，直到每个子数组只有一个元素，然后再将这些子数组两两合并成一个有序的数组，最终得到完全有序的数组。

归并排序的步骤如下：

1. 分割阶段：

   • 将待排序的数组从中间分成两个子数组，分别是左子数组和右子数组。

   • 递归地对左子数组和右子数组进行分割，直到每个子数组只剩一个元素。

2. 合并阶段：

   • 对已经分割好的子数组进行合并，将它们合并成一个有序的数组。

   • 创建一个临时数组，用来存放合并后的结果。

   • 初始化三个指针：一个指向左子数组的当前元素，一个指向右子数组的当前元素，一个指向临时数组的当前位置。

   • 依次比较左右子数组的当前元素，将较小的元素放入临时数组，并将相应的指针向后移动。

   • 重复上述步骤，直到某个子数组的元素全部放入临时数组中。

3. 复制剩余元素：

   • 当某个子数组的元素全部放入临时数组后，可能另一个子数组还有剩余元素。

   • 将剩余元素依次复制到临时数组的末尾。

4. 拷贝回原数组：

   • 合并完成后，临时数组中存放着完全有序的元素。

   • 将临时数组中的元素拷贝回原始数组的相应位置，完成排序。

5. 递归终止：

   • 继续递归地分割和合并，直到所有子数组都变成只有一个元素，此时排序完成。

代码示例

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right){
            int mid = (left + right) / 2; // 计算中间索引
            mergeSort(arr, left, mid);// 对左半部分进行递归排序
            mergeSort(arr, mid + 1, right);// 对右半部分进行递归排序
            merge(arr,left,mid,right);// 合并左右两部分的有序子数组
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1; // 左子数组的长度
        int n2 = right - mid; // 右子数组的长度
        int[] leftArr = new int[n1];// 创建左子数组
        int[] rightArr = new int[n2];// 创建右子数组

        // 将原始数组中的元素复制到左子数组
        for (int i = 0; i < n1; i++) {
           leftArr[i] = arr[left + i];
        }

        // 将原始数组中的元素复制到右子数组
        for (int j = 0; j < n2; j++) {
            rightArr[j] = arr[mid + 1 + j];
        }

        int i = 0,j = 0; // 初始化左子数组和右子数组的索引
        int k = left; // 初始化原始数组的索引，从左边界开始

        // 比较左右两个子数组的元素，并将较小的元素放入原始数组中
        while (i < n1 && j < n2){
            if (leftArr[i] <= rightArr[j]){
                arr[k] = leftArr[i];
                i++;
            }else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        // 如果左子数组还有剩余元素，将其全部复制到原始数组中
        while (i < n1){
          arr[k] = leftArr[i]; // 将剩余的左子数组元素复制到原始数组中
          i++;
          k++;
        }
        // 如果右子数组还有剩余元素，将其全部复制到原始数组中
        while (j < n2){
            arr[k] = rightArr[j];// 将剩余的右子数组元素复制到原始数组中
            j++;
            k++;
        }

    }
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 0, 4, 6, 5 ,10,89,69,19};
        int n = arr.length;

        mergeSort(arr, 0, n - 1);

        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

归并排序可以看作是先递归地将待排序数组切割成多个小块（每个小块只有一个元素），然后再逐步合并这些小块，最终得到完全有序的结果。

归并排序具有稳定性和时间复杂度为 O(nlogn)的优点，但它需要额外的空间来存储临时数组。在实际应用中，归并排序常用于对链表和外部排序等场景

基数排序

基数排序是一种非比较的排序算法，它根据元素的位数进行排序。基数排序的基本思想是将待排序的元素按照个位、十位、百位等位数进行分组，然后依次对每个位数进行稳定的排序。通过多次按位排序，最终得到完全有序的结果。它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用，是桶排序的扩展。时间复杂度为 O(d * (n + k))，其中 k 表示每个桶的平均大小，元素个数（n）、元素的位数（d），是经典的空间换时间的方式，占用内存很大，当对海量数据排序时容易造成 OOM

以下是基数排序的算法步骤：

1. 找到数组中最大值，并确定最大值的位数。

2. 创建桶数组和桶计数数组。桶数组用于存放待排序元素，桶计数数组用于记录每个桶中元素的个数。

3. 从个位开始，按照当前位上的数字将元素分配到对应的桶中。

4. 将每个桶中的元素按顺序收集到原始数组中。

5. 重复步骤 3 和 4，直到遍历完所有位数。

6. 完成排序后，原始数组即为有序结果。

代码示例:

public class RadixSort {

    public static void radixSort(int[] arr) {

        // 找到数组中位数最大的数,假设第一个就是最大的
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }
        // 得到最大位数
        int maxLength = (max + "").length();

        // 定义一个二维数组表示桶，10个桶表示位数（0123456789）
        int[][] bucket = new int[10][arr.length];

        //记录桶里面存了多少个数据，定义一个数组表示个数
        int[] bucketElementCounts = new int[10];


        for (int i = 0,n = 1; i < maxLength; i++,n *= 10) {
            // 对每个位数的数据进行排序，第一次个位，2次百位，以此类推
            for (int j = 0; j < arr.length; j++) {
                // 取出每个元素对应位的值
                int digitOfElement = arr[j] / n % 10;
                // 放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            // 按照桶的顺序进行排序 一维数组的下标依次取出数据，放入原来数组
            int index = 0;
            // 遍历每一个桶，放入原来的数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                // 如果桶中有数据，放入到原数组
                if (bucketElementCounts[k] != 0){
                    // 循环该桶即第k个桶(即第k个一维数组), 放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                // 每一轮清空桶
                bucketElementCounts[k] = 0;
            }

        }

    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};

        System.out.println("原始数组：" + Arrays.toString(arr));

        radixSort(arr);

        System.out.println("排序后数组：" + Arrays.toString(arr));
    }

}

堆排序

堆排序是利用堆这个数据结构实现的，堆本质是一个完全二叉树（Complete Binary Tree）：除了最后一层外，其他层的节点都是满的，并且最后一层的节点都尽可能地靠左排列。

堆分为两种类型：

最大堆：任何一个父节点的值，都大于或等于左、右孩子节点的值。

最小堆：任何一个父节点的值，都小于或等于它左右孩子节点的值。

二叉堆的根节点叫作堆顶，最大堆和最小堆的特点决定了: 最大堆的堆顶是整个堆中的最大元素最小堆的堆顶是整个堆中的最小元素。

我们还需要明确一点:二叉堆虽然是一个完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。换句话说，二叉堆的所有节点都存储在数组中。

左孩子下标就是 2xparent+1

右孩子下标就是 2xparent+2

堆的最后一个非叶子节点的计算公式为 (n/2) - 1，其中 n 是堆中元素的总数。

理解以上就可以实现一个堆排序，步骤如下：

1.构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)

2.排序。将最大堆中的根节点（最大值）与数组中未排序部分的最后一个元素交换位置，将最大元素"沉"到数组末端;重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序

代码实现：

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;
        // 构建最大堆
        buildMaxHeap(arr, n);
        // 逐步取出最大元素并调整堆
        for (int i = n - 1; i > 0; i--) {
            // 将当前根节点（最大值）与末尾元素交换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // 调整堆
            heapify(arr, i, 0);
        }
    }
    private static void buildMaxHeap(int[] arr, int n) {
        // 从最后一个非叶子节点开始，依次向前调整堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
    }
    private static void heapify(int[] arr, int n, int root) {
        while (true) {
            int largest = root; // 初始化根节点为最大值
            int leftChild = 2 * root + 1;
            int rightChild = 2 * root + 2;
            // 如果左子节点比根节点大，则更新最大值索引
            if (leftChild < n && arr[leftChild] > arr[largest]) {
                largest = leftChild;
            }
            // 如果右子节点比当前最大值大，则更新最大值索引
            if (rightChild < n && arr[rightChild] > arr[largest]) {
                largest = rightChild;
            }
            // 如果最大值索引不是根节点，则交换根节点和最大值节点，并继续循环调整堆
            if (largest != root) {
                int temp = arr[root];
                arr[root] = arr[largest];
                arr[largest] = temp;
                root = largest;
            } else {
                break;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {9, 4, 2, 7, 1, 5, 8, 3, 6};
//        int[] arr = {4,6,8,5,9};
        heapSort(arr);
        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}