六大排序算法超详细理解-EW帮帮网

1. 主类与主方法

import java.util.Arrays;  // 导入Arrays工具类，用于数组操作

public class SortingAlgorithms {  // 定义排序算法类
    public static void main(String[] args) {  // 主方法，程序入口
        // 定义原始数组
        int[] array = {64, 34, 25, 12, 22, 11, 90};
        // 打印原始数组：将数组转换为字符串输出
        System.out.println("原始数组: " + Arrays.toString(array));
        
        // 冒泡排序演示
        // 复制原始数组（避免排序影响原数组）
        int[] bubbleSortArray = Arrays.copyOf(array, array.length);
        // 调用冒泡排序方法
        bubbleSort(bubbleSortArray);
        // 打印排序结果
        System.out.println("冒泡排序结果: " + Arrays.toString(bubbleSortArray));
        
        // 选择排序演示（同上，复制数组→排序→打印）
        int[] selectionSortArray = Arrays.copyOf(array, array.length);
        selectionSort(selectionSortArray);
        System.out.println("选择排序结果: " + Arrays.toString(selectionSortArray));
        
        // 插入排序演示
        int[] insertionSortArray = Arrays.copyOf(array, array.length);
        insertionSort(insertionSortArray);
        System.out.println("插入排序结果: " + Arrays.toString(insertionSortArray));
        
        // 希尔排序演示
        int[] shellSortArray = Arrays.copyOf(array, array.length);
        shellSort(shellSortArray);
        System.out.println("希尔排序结果: " + Arrays.toString(shellSortArray));
        
        // 快速排序演示（需要传入起始和结束索引）
        int[] quickSortArray = Arrays.copyOf(array, array.length);
        quickSort(quickSortArray, 0, quickSortArray.length - 1);
        System.out.println("快速排序结果: " + Arrays.toString(quickSortArray));
        
        // 归并排序演示（需要传入起始和结束索引）
        int[] mergeSortArray = Arrays.copyOf(array, array.length);
        mergeSort(mergeSortArray, 0, mergeSortArray.length - 1);
        System.out.println("归并排序结果: " + Arrays.toString(mergeSortArray));
    }

主方法逻辑说明：

先定义一个原始数组{64, 34, 25, 12, 22, 11, 90}
对每种排序算法，都先复制原始数组（避免排序操作修改原数组）
调用对应排序方法，最后打印排序结果
这样可以保证 6 种排序算法都基于同一个原始数组进行测试，便于对比结果

2. 冒泡排序（Bubble Sort）

/**
 * 冒泡排序
 * 思路：重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来
 */
public static void bubbleSort(int[] arr) {
    int n = arr.length;  // 获取数组长度
    // 外层循环：控制需要比较的轮次（n-1轮即可）
    for (int i = 0; i < n - 1; i++) {
        // 标记本轮是否有交换，如果没有则说明数组已排序完成
        boolean swapped = false;
        // 内层循环：每轮比较的范围（随着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;
                swapped = true;  // 标记有交换
            }
        }
        // 如果本轮没有交换，说明数组已有序，提前退出循环
        if (!swapped) break;
    }
}

逐行执行流程（以数组[64, 34, 25, 12, 22, 11, 90]为例）：

n = 7（数组长度为 7）
外层循环i=0（第一轮）：
- swapped = false
- 内层循环j从 0 到 5（n-i-1=6）：
  - j=0：64 > 34 → 交换 → 数组变为[34, 64, 25, 12, 22, 11, 90]，swapped=true
  - j=1：64 > 25 → 交换 → [34, 25, 64, 12, 22, 11, 90]
  - j=2：64 > 12 → 交换 → [34, 25, 12, 64, 22, 11, 90]
  - j=3：64 > 22 → 交换 → [34, 25, 12, 22, 64, 11, 90]
  - j=4：64 > 11 → 交换 → [34, 25, 12, 22, 11, 64, 90]
  - j=5：64 < 90 → 不交换
- 第一轮结束后，最大元素90已 "冒泡" 到末尾（位置 6）
后续轮次以此类推，每轮将剩余元素中的最大值移到对应位置
当某轮没有交换时（swapped=false），说明数组已有序，直接退出

3. 选择排序（Selection Sort）

/**
 * 选择排序
 * 思路：每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置
 */
public static void selectionSort(int[] arr) {
    int n = arr.length;  // 获取数组长度
    // 外层循环：控制当前需要填充的位置（0到n-2）
    for (int i = 0; i < n - 1; i++) {
        // 假设当前位置i的元素是最小值，记录其索引
        int minIndex = i;
        // 内层循环：从i+1开始寻找比当前最小值更小的元素
        for (int j = i + 1; j < n; j++) {
            // 如果找到更小的元素，更新minIndex
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 交换：将找到的最小值放到位置i
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

逐行执行流程：

n = 7
外层循环i=0（第一个位置）：
- minIndex = 0（初始假设arr[0]=64是最小值）
- 内层循环j从 1 到 6：
  - j=1：34 < 64 → minIndex=1
  - j=2：25 < 34 → minIndex=2
  - j=3：12 < 25 → minIndex=3
  - j=4：22 > 12 → 不变
  - j=5：11 < 12 → minIndex=5
  - j=6：90 > 11 → 不变
- 找到最小值11（索引 5），与arr[0]交换 → 数组变为[11, 34, 25, 12, 22, 64, 90]
外层循环i=1（第二个位置）：
- 从j=2开始寻找最小值，最终找到12（索引 3），与arr[1]交换 → [11, 12, 25, 34, 22, 64, 90]
以此类推，每轮确定一个位置的元素，直到排序完成

4. 插入排序（Insertion Sort）

/**
 * 插入排序
 * 思路：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
 */
public static void insertionSort(int[] arr) {
    int n = arr.length;  // 获取数组长度
    // 外层循环：从第二个元素开始（索引1），认为第一个元素已有序
    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--;  // 继续向前比较
        }
        // 将key插入到正确位置
        arr[j + 1] = key;
    }
}

逐行执行流程：

n = 7
外层循环i=1（待插入元素arr[1]=34）：
- key = 34，j = 0（arr[0]=64）
- arr[j]=64 > key=34 → arr[1] = 64，j=-1
- 退出循环，arr[0] = key=34 → 数组变为[34, 64, 25, 12, 22, 11, 90]
外层循环i=2（待插入元素arr[2]=25）：
- key=25，j=1（arr[1]=64）
- 64 > 25 → arr[2]=64，j=0
- 34 > 25 → arr[1]=34，j=-1
- 插入key=25到j+1=0 → [25, 34, 64, 12, 22, 11, 90]
以此类推，每轮将一个元素插入到前面的有序序列中，最终整个数组有序

5. 希尔排序（Shell Sort）

/**
 * 希尔排序
 * 思路：插入排序的改进版，先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
 */
public static void shellSort(int[] arr) {
    int n = arr.length;  // 获取数组长度
    
    // 初始步长设为n/2，之后每次减半（步长序列）
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个子序列进行插入排序（从gap位置开始）
        for (int i = gap; i < n; i++) {
            int temp = arr[i];  // 记录当前元素
            int j;  // 用于子序列中比较的索引
            
            // 子序列中，将大于temp的元素向前移动gap位
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            // 将temp放到子序列中的正确位置
            arr[j] = temp;
        }
    }
}

逐行执行流程：

n = 7，初始gap = 7/2 = 3（第一步长）
按gap=3分组，子序列为：
- 组 1：arr[0], arr[3], arr[6] → 64, 12, 90
- 组 2：arr[1], arr[4] → 34, 22
- 组 3：arr[2], arr[5] → 25, 11
对每个子序列进行插入排序后，数组变为[12, 22, 11, 64, 34, 25, 90]
下一轮gap = 3/2 = 1（步长为 1，相当于普通插入排序）
对整个数组进行插入排序，最终得到有序数组

6. 快速排序（Quick Sort）

/**
 * 快速排序
 * 思路：选择一个基准元素，将数组分为两部分，小于基准的放左边，大于基准的放右边，然后递归排序子数组
 */
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);
    }
}

// 快速排序的分区操作
private static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];  // 选择最右边的元素作为基准
    int i = (low - 1);  // 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;
        }
    }
    
    // 将基准元素放到正确位置（i+1）
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    
    return i + 1;  // 返回基准元素的索引
}

逐行执行流程：

初始调用quickSort(arr, 0, 6)（数组[64, 34, 25, 12, 22, 11, 90]）
low=0 < high=6，调用partition(arr, 0, 6)：
- pivot = arr[6] = 90（基准元素）
- i = -1
- 遍历j=0到5：
  - 所有元素都<=90，每次i递增并交换，最终i=5
- 交换arr[6]和arr[6]（基准位置不变），返回pi=6
递归调用quickSort(arr, 0, 5)（左子数组）和quickSort(arr, 7, 6)（右子数组，不执行）
对左子数组[64, 34, 25, 12, 22, 11]重复上述过程，直到所有子数组排序完成

7. 归并排序（Merge Sort）

/**
 * 归并排序
 * 思路：将数组分成两半，对每一半递归排序，然后将排序好的两半合并
 */
public static void mergeSort(int[] arr, int left, int right) {
    // 如果左索引小于右索引，说明数组长度大于1，需要继续分割
    if (left < right) {
        // 找到中间点（避免溢出：等价于(left+right)/2）
        int mid = left + (right - left) / 2;
        
        // 递归排序左半部分（left到mid）
        mergeSort(arr, left, mid);
        // 递归排序右半部分（mid+1到right）
        mergeSort(arr, mid + 1, right);
        
        // 合并两个排序好的子数组
        merge(arr, left, mid, right);
    }
}

// 归并排序的合并操作
private static void merge(int[] arr, int left, int mid, int right) {
    // 计算两个子数组的大小
    int n1 = mid - left + 1;  // 左子数组长度
    int n2 = right - mid;     // 右子数组长度
    
    // 创建临时数组存储左右子数组
    int[] L = new int[n1];
    int[] R = new int[n2];
    
    // 复制数据到临时数组
    System.arraycopy(arr, left, L, 0, n1);  // 左子数组：arr[left..mid] → L[0..n1-1]
    for (int j = 0; j < n2; ++j) {
        R[j] = arr[mid + 1 + j];  // 右子数组：arr[mid+1..right] → R[0..n2-1]
    }
    
    // 合并临时数组
    
    // 初始化临时数组的索引
    int i = 0, j = 0;
    
    // 合并后数组的起始索引
    int k = left;
    
    // 比较两个临时数组的元素，按从小到大放入原数组
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    // 复制左子数组剩余元素（如果有）
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    // 复制右子数组剩余元素（如果有）
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

逐行执行流程：

初始调用mergeSort(arr, 0, 6)（数组[64, 34, 25, 12, 22, 11, 90]）
left=0 < right=6，mid = 0 + (6-0)/2 = 3
递归调用mergeSort(arr, 0, 3)（左半部分[64,34,25,12]）和mergeSort(arr,4,6)（右半部分[22,11,90]）
左半部分继续分割为[64,34]和[25,12]，直到每个子数组长度为 1
右半部分分割为[22]和[11,90]，[11,90]再分割为[11]和[90]
开始合并：
- 合并[11]和[90] → [11,90]
- 合并[22]和[11,90] → [11,22,90]
- 左半部分合并后得到[12,25,34,64]
- 最终合并[12,25,34,64]和[11,22,90] → 有序数组

总结

这六种排序算法各有特点：

冒泡 / 选择 / 插入排序：时间复杂度 O (n²)，适合小规模数据
希尔排序：时间复杂度 O (n^1.3)，是插入排序的改进
快速排序：平均时间复杂度 O (nlogn)，实际应用中最快
归并排序：时间复杂度 O (nlogn)，稳定但需要额外空间

通过逐行解释和流程模拟，希望能帮助你理解每种算法的执行细节。如果需要更深入分析某一步，可以进一步提问。

六大排序算法超详细理解

1. 主类与主方法

2. 冒泡排序（Bubble Sort）

3. 选择排序（Selection Sort）

4. 插入排序（Insertion Sort）

5. 希尔排序（Shell Sort）

6. 快速排序（Quick Sort）

7. 归并排序（Merge Sort）

总结

网站公告

今日签到

热门文章

最新发布