Java实现八大常见排序算法示例

优化后的冒泡排序

冒泡排序通过重复遍历数组，比较相邻元素并交换顺序错误的值。优化版本引入 flag 布尔变量来检测循环中是否发生交换：若某趟遍历无交换，说明数组已有序，提前终止以提升性能。

package com.yzh.sort;
@SuppressWarnings({"all"})
public class BubbleSort {

    public static void BubbleSort(int[]a){
        for (int i = 0; i <a.length-1 ; i++) {
            boolean flag=true;
            for (int j = 0; j <a.length-i-1 ; j++) {
                if(a[j]>a[j+1]){
                    int temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                    flag=false;
                }
            }
            if(flag) break;
        }
    }

}

选择排序

选择排序每次从待排序部分选出最小元素，将其放到已排序部分的末尾。核心在于维护一个 index 标记当前未排序区间的极小值位置，遍历结束后执行一次交换操作。

package com.yzh.sort;
@SuppressWarnings({"all"})
public class SelectSort {

    public static void SelectSort(int[]a) {
        for (int i = 0; i < a.length - 1; i++) {
            int index = i;//标记为待比较的数
            for (int j = i + 1; j < a.length; j++) { //然后从后面遍历与第一个数比较
                if (a[j] < index[index]) {  //如果小,就交换最小值
                    index = j;//保存最小元素的下标
                }
            }
            //找到最小值后，将最小的值放到第一的位置，进行下一遍循环
            int temp = a[index];
            a[index] = a[i];
            a[i] = temp;
        }
    }
}

插入排序

插入排序将数组视为“已排序”和“未排序”两部分。每次取出未排序部分的第一个元素，在已排序部分从右向左扫描，找到合适位置插入。使用 insertValue 暂存值，移动大于它的元素以腾出空间。

package com.yzh.sort;
@SuppressWarnings({"all"})
/*
插入排序
 */
public class InsertSort {

    public static void InsertSort(int[]a){
        for (int i = 0; i < a.length; i++) {
            //定义待插入的数
            int insertValue=a[i];
            //找到待插入数的前一个数的下标
            int insertIndex=i-1;
            while (insertIndex>=0 && insertValue <a[insertIndex]) {//拿a[i]前面的数比较
                a[insertIndex+1]=a[insertIndex];
                insertIndex--;
            }
            a[insertIndex+1]=insertValue;
        }
    }
}

希尔排序

希尔排序是插入排序的高效改进版，通过将数组按间隔 gap 分组进行预排序。初始 gap 为长度一半，每次减半直至为1。这种缩小增量策略使较大元素能较快移至前端。

package com.yzh.sort;

/*
希尔排序
 */
@SuppressWarnings({"all"})
public class ShellSort {

    public static void ShellSort(int[] a){
        for (int gap=a.length / 2; gap > 0; gap = gap / 2) {
            //将整个数组分为若干个子数组
            for (int i = gap; i < a.length; i++) {
                //遍历各组的元素
                for (int j = i - gap; j>=0; j=j-gap) {
                    //交换元素
                    if (a[j]>a[j+gap]) {
                        int temp=a[j];
                        a[j]=a[j+gap];
                        a[j+gap]=temp;
                    }
                }
            }
        }
    }
}

快速排序

快速排序采用分治法，选定基准位（通常为第一个元素），将小于基准的放左边，大于的放右边，然后递归处理左右子区间。此版本使用双指针 i 和 j 从两端向中间逼近。

package com.yzh.sort;
@SuppressWarnings({"all"})
/*
随机化快速排序
 */
public class QuickSort {

    public static void QuickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>=high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位
        temp = arr[low];
        while (i<j) {
            //先看右边，依次往左递减
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //如果满足条件则交换
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //递归调用左半数组
        QuickSort(arr, low, j-1);
        //递归调用右半数组
        QuickSort(arr, j+1, high);
    }
}

随机化快速排序

为解决标准快排在特定数据分布下的退化问题，引入 Random 库随机选取主元并交换至末尾，从而平衡划分效率。

package com.yzh.sort;

import java.util.Random;
import java.util.Scanner;

@SuppressWarnings({"all"})
public class RandQuickSort {

    public static void randsort(int[] arr, int left, int right) {
        if(left>=right)
            return;
        Random random = new Random();
        int randIndex = random.nextInt(right-left)+left;  //选取随机主元
        //把随机主元放到数组尾部
        int temp = arr[randIndex];
        arr[randIndex] = arr[right];
        arr[right] = temp;
        //数组中元素与主元比较
        int i = left-1;//注意
        for(int j = left;j<=right;j++) {
            if(arr[j]<arr[right]) {
                i++;
                int temp1 = arr[i];
                arr[i] = arr[j];
                arr[j] = temp1;
            }
        }
        //最后把主元放到适当位置
        int temp2 = arr[i+1];
        arr[i+1] = arr[right];
        arr[right] = temp2;

        randsort(arr,left,i);
        randsort(arr,i+2,right);
    }
}

归并排序

归并排序基于分治思想，先递归分解直到子数组长度为1（天然有序），再通过 merge 函数合并两个有序序列。合并过程需要辅助数组 temp 暂存结果，最后拷贝回原数组。

package com.yzh.sort;

@SuppressWarnings({"all"})
/*
归并排序
 */
public class MergeSort {

    private static void mergesort(int[] a, int left, int right, int[] temp) {
        //分解
        if (left<right) {
            int mid=((right-left)>>1)+left;
            //向左递归进行分解
            mergesort(a, left, mid, temp);
            //向右递归进行分解
            mergesort(a, mid+1, right, temp);
            //每分解一次便合并一次
            merge(a,left,right,mid,temp);
        }
    }

    private static void merge(int[] a, int left, int right, int mid, int[] temp) {
        int i=left; //初始i，左边有序序列的初始索引
        int j=mid+1;//初始化j，右边有序序列的初始索引
        int t=0;//指向temp数组的当前索引

        //先把左右两边的数据（已经有序）按规则填充到temp数组
        while (i<=mid && j<=right) {
            if (a[i]<=a[j]) {
                temp[t++]=a[i++];
            }else {
                temp[t++]=a[j++];
            }
        }
        //把剩余数据的一边的元素填充到temp中
        while (i<=mid) {
            temp[t++]=a[i++];
        }
        while (j<=right) {
            temp[t++]=a[j++];
        }
        //将temp数组的元素复制到原数组
        t=0;
        int tempLeft=left;
        while (tempLeft<=right) {
            a[tempLeft++]=temp[t++];
        }
    }
}

可处理负数的基数排序

基数排序通常针对非负整数，此处提供改进版：首先找出最大/最小值。若存在负数，将所有元素加上偏移量转为正数处理；排序结束后再减去相同的偏移量还原，从而实现混合正负数排序。

package com.yzh.sort;

public class RadixSort{

    public static int[] RadixSort(int[] arr){
        //最大值，用来计算需要找多少次
        int max = Integer.MIN_VALUE;
        //用来判断是否是负数
        int min = Integer.MAX_VALUE;
        //从该数组中找到最大\最小值
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        //如果最小值小于0，那么把每个数都减去最小值，这样可以保证最小的数是0
        if (min<0) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] -= min;
            }
            //max也要处理
            max -= min;
        }
        //计算最大值有几位数
        int maxLength = (max+"").length();
        //定义十个桶，每个桶就是一个一维数组
        int[][] bucket = new int[10][arr.length];
        //记录每个桶中实际存放了多少个数据
        int[] bucketElementCount = new int[10];
        //根据最大长度数，决定比较次数
        for (int i = 0 ,n = 1 ; i < maxLength ; i++,n*=10) {
            //每一个数字分别计算余数
            for (int j = 0; j < arr.length ; j++) {
                int value = arr[j]/n % 10;
                //把当前遍历的数放到指定的位置
                bucket[value][bucketElementCount[value]] = arr[j];
                //该位置加一，为下一个值进来做准备
                bucketElementCount[value]++;
            }
            //记录arr的位置
            int index = 0;
            //遍历取出第n次排序的值
            for (int j = 0; j < bucketElementCount.length ; j++) {
                if (bucketElementCount[j]!=0){
                    //遍历取出数据并放到原来的arr中
                    for (int k = 0; k < bucketElementCount[j]; k++) {
                        arr[index] = bucket[j][k];
                        index++;
                    }
                }
                //把数量置为零，因为还有n轮
                bucketElementCount[j] = 0;
            }
        }
        //把排序好的arr重新加上减去的值
        if (min<0){
            for (int i = 0; i < arr.length ; i++) {
                arr[i] += min;
            }
        }
        return arr;
    }

}