Java的六大排序 | Yaml墨韵

一、冒泡排序（Bubble Sort）

1. 基本思想：

比较相邻的元素。如果第一个比第二个大（升序情况，降序则相反），就交换它们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这样在经过一轮比较后，最大的元素就会 “浮” 到数组的末尾。
针对所有的元素重复以上的步骤，除了已经排序好的最后一个元素（因为它已经是最大的了），直到整个数组都有序。

2. 示例代码：

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        // 外层循环控制排序轮数，一共需要n - 1轮
        for (int i = 0; i < n - 1; i++) {
            // 内层循环控制每一轮比较的次数，每一轮比较次数逐渐减少
            for (int j = 0; j < n - 1 - i; j++) {
                // 如果当前元素大于下一个元素，则交换它们的位置
                if (arr[j] > arr[j + 1]) {
                    // 交换 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 = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        // 输出排序后的数组
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3. 注释说明：

外层循环的i从0到n - 1，每一轮确定一个最大的数放到数组末尾，所以一共需要n - 1轮排序。
内层循环的j从0到n - i - 1，因为每一轮排序后，末尾已经排好序的元素就不需要再参与比较了，所以每一轮比较次数逐渐减少。
当arr[j] > arr[j + 1]时，通过临时变量temp交换两个元素的位置，实现将较大的数往后 “冒泡”。

二、选择排序（Selection Sort）

1. 基本思想：

首先在未排序序列中找到最小（升序情况，降序则找最大）的元素，存放到排序序列的起始位置。
然后，再从剩余未排序元素中继续寻找最小（或最大）元素，放到已排序序列的末尾。
重复以上步骤，直到所有元素均排序完毕。

2. 示例代码：

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

        // 外层循环控制选择的轮数，一共需要n - 1轮
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;

            // 内层循环用于找到当前未排序部分的最小值的索引
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }

            // 如果找到的最小值索引不是当前轮的起始索引，就交换这两个位置的元素
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3. 注释说明：

外层循环同样控制排序轮数，i从0到n - 1，每一轮确定一个最小的数放到数组开头（已排序部分的末尾），所以需要n - 1轮。
内层循环从i + 1到n，用于在当前未排序部分找到最小值的索引minIndex。
如果minIndex不等于当前轮的起始索引i，则通过临时变量temp交换这两个位置的元素，将最小值放到正确的位置

三、插入排序（Insertion Sort）

1. 基本思想：

把待排序的元素插入到已经排序好的部分序列中的合适位置，使得插入后的序列仍然有序。
从第二个元素开始，将其与前面已排序的元素依次比较，找到合适的插入位置并插入。

2. 示例代码：

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;

            // 在已排序部分中查找插入位置，将大于key的元素往后移
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }

            // 将key插入到合适的位置
            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 + " ");
        }
    }
}

3. 注释说明：

外层循环从第二个元素（索引为1）开始，因为第一个元素默认是已排序的。
对于每一个要插入的元素key（即arr[i]），内层循环while从已排序部分的末尾（i - 1）开始往前找插入位置，只要当前元素arr[j]大于key，就将arr[j]往后移一位（arr[j + 1] = arr[j]），同时j减1。
当找到合适的插入位置（arr[j] <= key或者j < 0）时，将key插入到j + 1的位置（arr[j + 1] = key）。

四、希尔排序（Shell Sort）

1. 基本思想：

希尔排序是插入排序的一种改进版本。它先将整个待排序的记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行一次直接插入排序。
分割子序列的方法是按照一定的间隔（称为增量）来选取元素，增量会逐渐减小，直到最后一次排序时增量为 1。

2. 示例代码：

public class ShellSort {
    public static void shellSort(int[] arr) {
        int n = arr.length;
        // 初始步长，一般取数组长度的一半
        int gap = n / 2;
        while (gap > 0) {
            // 对每个步长进行插入排序
            for (int i = gap; i < n; i++) {
                int key = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > key) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = key;
            }
            // 缩小步长，一般取上一轮步长的一半
            gap = gap / 2;
        }
    }

    public static void main(String[] args) {
        int[] arr = {15, 74, 53, 42, 91};
        shellSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3. 注释说明：

首先确定初始步长gap，一般取数组长度的一半。然后通过循环，每次对步长为gap的子序列进行插入排序。
在对步长为gap的子序列进行插入排序时，原理和普通插入排序类似，只是比较和移动元素的间隔是gap。
每完成一轮步长为gap的插入排序后，将步长缩小为上一轮步长的一半，继续下一轮排序，直到步长为0为止。

五、快速排序（Quick Sort）

1. 基本思想：

选择一个基准元素，通常选择数组的第一个元素（也可以选择其他元素）。
通过一趟排序将待排序的数据分割成两部分，其中一部分的所有元素都比基准元素小，另一部分的所有元素都比基准元素大。
然后对这两部分数据分别进行快速排序，直到整个数组有序

2. 示例代码：

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {

            // 划分操作，获取分区点索引
            int pi = partition(arr, low, high);

            // 对分区点左边的子数组进行快速排序
            quickSort(arr, low, pi - 1);

            // 对分区点右边的子数组进行快速排序
            quickSort(arr, pi + 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++;

                // 交换arr[i]和arr[j]的位置
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 交换arr[i + 1]和arr[high]的位置，将分区点放到正确位置
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 79, 48, 29, 91, 53};
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3. 注释说明：

quickSort方法是快速排序的主方法，通过递归调用对数组进行排序。首先判断low是否小于high，如果是，则进行划分操作找到分区点pivotIndex，然后分别对分区点左右两边的子数组进行快速排序。
partition方法用于实现划分操作。选择数组的最后一个元素pivot作为分区点，通过循环比较将小于等于pivot的元素放到左边，大于pivot的元素放到右边，最后将分区点放到正确的位置并返回其索引。

六、归并排序（Merge Sort）

1. 基本思想：

采用分治策略，将待排序序列分成两部分，分别对这两部分进行排序，然后将排序好的两部分合并成一个有序序列。
不断重复这个过程，直到整个序列都有序

2. 示例代码：

public class MergeSort {
    public static void mergeSort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            // 对左半部分数组进行归并排序
            mergeSort(arr, low, mid);
            // 对右半部分数组进行归并排序
            mergeSort(arr, mid + 1, high);
            // 合并左右两部分已排序的数组
            merge(arr, low, mid, high);
        }
    }

    private static void merge(int[] arr, int low, int mid, int high) {
        // 分别创建左右两个临时数组来存储左右两部分已排序的数组
        int[] leftArray = new int[mid - low + 1];
        int[] rightArray = new int[high - mid];

        // 将原数组的左半部分复制到leftArray
        for (int i = 0; i < mid - low + 1; i++) {
            leftArray[i] = arr[low + i];
        }

        // 将原数组的右半部分复制到rightArray
        for (int i = 0; i < high - mid; i++) {
            rightArray[i] = arr[mid + 1 + i];
        }

        int i = 0;
        int j = 0;
        int k = low;

        // 比较左右两个临时数组的元素，将较小的元素依次放回原数组
        while (i < leftArray.length && j < rightArray.length) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        // 将leftArray中剩余的元素放回原数组
        while (i < leftArray.length) {
            arr[k] = leftArray[i];
        k++;
        i++;
        }

        // 将rightArray中剩余的元素放回原数组
        while (j < rightArray.joinsort>
            arr[k] = rightArray[j];
            k++;
            j++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {85, 43, 39, 92, 61};
        mergeSort(arr, 0, arr.length - 1);
        // 输出排序后的数组
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3. 注释说明：

mergeSort方法通过递归调用对数组进行排序。首先判断low是否小于high，如果是，则将数组分成左右两部分，分别对左右两部分进行归并排序，然后再将两部分已排序的数组合并。
merge方法用于实现合并操作。先创建左右两个临时数组来存储左右两部分已排序的数组，然后通过比较将较小的元素依次放回原数组，最后将剩余的元素也放回原数组。