【常见排序算法】java 代码实现

直插排序

public static void straight_insert_sort(int[] r, int n) {
    // 直接插入排序：将未排序元素逐个插入到已排序序列的适当位置
    // 假设数组索引从1开始，r[0]作为哨兵，不参与排序
    
    int i, j;
    
    // 从第2个元素开始，逐个插入到前面已排序部分
    for (i = 2; i <= n; i++) {
        r[0] = r[i];  // 将当前待插入元素暂存到哨兵位置
        j = i - 1;    // 已排序部分的最后一个元素
        
        // 从后向前查找插入位置，同时移动元素
        while (r[0] < r[j]) {
            r[j + 1] = r[j];  // 元素后移一位
            j--;              // 继续向前比较
        }
        
        // 找到插入位置，将暂存的元素插入
        r[j + 1] = r[0];
    }
}

二分插入排序

public static void binary_insert_sort(int[] r) {
    // 二分插入排序：结合二分查找优化的插入排序
    // 假设数组索引从1开始，r[0]作为哨兵，不参与排序
    
    int i, j, low, high, mid;
    
    // 从第2个元素开始，逐个插入到前面已排序部分
    for (i = 2; i < r.length; i++) {
        r[0] = r[i];  // 将当前待插入元素暂存到哨兵位置
        low = 1;      // 已排序部分的起始位置
        high = i - 1; // 已排序部分的结束位置
        
        // 二分查找插入位置
        while (low <= high) {
            mid = (low + high) / 2;  // 计算中间位置
            
            if (r[0] < r[mid]) {     // 插入位置在左半部分
                high = mid - 1;
            } else {                 // 插入位置在右半部分
                low = mid + 1;
            }
        }
        
        // 找到插入位置后，将元素后移
        for (j = i - 1; j >= high + 1; j--) {
            r[j + 1] = r[j];  // 元素后移一位
        }
        
        // 在找到的位置插入元素
        r[high + 1] = r[0];
    }
}

希尔排序

public static void shell_sort(int[] r) {
    // 希尔排序：基于插入排序的改进算法
    // 通过设置不同的间隔(d)，将数组分成多个子序列进行排序
    // 随着间隔逐渐减小，数组逐渐接近有序，最终间隔为1时完成排序
    
    int d, i, j;
    
    // 初始间隔为数组长度的一半，然后每次减半
    for (d = r.length / 2; d >= 1; d = d / 2) {
        
        // 对每个子序列进行插入排序
        for (i = d + 1; i < r.length; i++) {
            r[0] = r[i];  // 暂存当前元素
            j = i - d;    // 子序列的前一个元素
            
            // 在子序列中向前查找插入位置
            while (j > 0 && r[0] < r[j]) {
                r[j + d] = r[j];  // 元素后移d个位置
                j = j - d;        // 继续向前查找
            }
            
            // 插入元素
            r[j + d] = r[0];
        }
    }
}

冒泡排序

public static void bubbleSort(int[] r, int n) {
    int exchange, bound;
    // exchange: 记录最后一次交换的位置
    // bound: 每轮比较的右边界
    
    exchange = n;  // 初始时，整个数组都需要排序
    while (exchange != 0) {  // 只要还有交换发生，就继续排序
        bound = exchange;  // 上一轮最后一次交换的位置，作为本轮的右边界
        exchange = 0;  // 重置交换位置，准备记录本轮的最后一次交换
        
        for (int j = 1; j < bound; j++) {  // 只需要比较到上一轮最后交换的位置
            if (r[j] > r[j + 1]) {  // 如果前一个元素比后一个大，就交换
                r[0] = r[j];  // 交换元素
                r[j] = r[j + 1];
                r[j + 1] = r[0];
                exchange = j;  // 记录最后一次交换的位置
            }
        }
        // 循环结束后，bound之后的元素已经有序，下一轮只需比较到bound位置
    }
}

快速排序

public static void quickSort(int[] r, int first, int end) {
    // 快速排序的递归实现
    // 参数：
    //   r: 待排序数组
    //   first: 当前子数组的起始索引
    //   end: 当前子数组的结束索引
    
    if (first < end) {  // 递归终止条件：子数组长度大于1
        // 分区操作：将数组分为两部分
        // 左边部分 <= 基准，右边部分 >= 基准
        // pivot 是基准元素最终所在的位置
        int pivot = partition(r, first, end);
        
        // 递归排序左半部分
        quickSort(r, first, pivot - 1);
        
        // 递归排序右半部分
        quickSort(r, pivot + 1, end);
    }
    // 当 first >= end 时，子数组长度为0或1，已经有序，直接返回
}

public static int partition(int[] r, int first, int end) {
    // 以第一个元素为基准，将数组分为两部分
    // 左边部分 <= 基准，右边部分 >= 基准
    // 返回基准元素最终所在的位置
    
    int i = first, j = end, temp;  // i: 左指针，j: 右指针
    
    while (i < j) {  // 当左右指针未相遇时，继续分区
        // 从右向左找第一个小于基准的元素
        while (i < j && r[i] <= r[j]) j--;
        
        if (i < j) {  // 如果找到，交换左右指针所指元素
            temp = r[i];
            r[i] = r[j];
            r[j] = temp;
            i++;  // 左指针右移
        }
        
        // 从左向右找第一个大于基准的元素
        while (i < j && r[i] <= r[j]) i++;
        
        if (i < j) {  // 如果找到，交换左右指针所指元素
            temp = r[i];
            r[i] = r[j];
            r[j] = temp;
            j--;  // 右指针左移
        }
    }
    
    // 当i=j时，分区完成，返回基准元素的位置
    return i;
}

归并排序

public static void mergesort(int[] r, int s, int t) {
    // 参数：
    //   r: 待排序数组
    //   s: 当前子数组的起始索引
    //   t: 当前子数组的结束索引
    
    int i, m;
    
    // 递归终止条件：当子数组只有一个元素时，直接返回
    if (s == t) return;
    
    // 计算中间位置，将数组分成两部分
    m = (s + t) / 2;
    
    // 递归排序左半部分
    mergesort(r, s, m);
    
    // 递归排序右半部分
    mergesort(r, m + 1, t);
    
    // 合并已排序的两部分
    merge(r, s, m, t);
}


public static void merge(int[] r, int s, int m, int t) {
    // 参数：
    //   r: 待合并数组
    //   s: 左子数组的起始索引
    //   m: 左子数组的结束索引（也是中间位置）
    //   t: 右子数组的结束索引
    
    // 创建辅助数组，用于临时存储合并结果
    int[] r1 = new int[t + 1];
    
    // i: 左子数组的当前索引
    // j: 右子数组的当前索引
    // k: 辅助数组的当前索引
    int i = s, j = m + 1, k = s;
    
    // 同时遍历左右子数组，将较小的元素放入辅助数组
    while (i <= m && j <= t) {
        if (r[i] <= r[j]) {
            r1[k++] = r[i++];  // 左子数组元素较小，放入辅助数组
        } else {
            r1[k++] = r[j++];  // 右子数组元素较小，放入辅助数组
        }
    }
    
    // 处理左子数组剩余元素
    while (i <= m) {
        r1[k++] = r[i++];
    }
    
    // 处理右子数组剩余元素
    while (j <= t) {
        r1[k++] = r[j++];
    }
    
    // 将辅助数组中的元素复制回原数组
    for (i = s; i <= t; i++) {
        r[i] = r1[i];
    }
}