526互联

Java中常用排序算法及示例-冒泡排序、希尔排序、选择排序、插入排序、合并排序、基数排序、快速排序、堆积树排序

发布时间 2023-04-14 14:18:35作者: 霸道流氓

场景

Java中需要对数据进行排序处理，常用的排序算法以及示例进行归纳整理。

注：

博客：
https://blog.csdn.net/badao_liumang_qizhi

实现

1、冒泡排序

冒泡排序法又称为交换排序法，原理是从第一个元素开始，比较相邻元素的大小，若大小顺序有误，

则对调后再进行下一个元素的比较。如此扫描一次之后就可以确保最后一个元素位于正确的顺序，

接着逐步进行第二次扫描，直到所有元素的排序为止。n个算法必须执行n-1次扫描。

示例代码:

public class MaoPao {
    static int data[] = {7,3,8,4,2,6};

    public static void showData(){
        int i;
        for (i =0;i<6;i++){
            System.out.print(data[i]+" ");
        }
    }
    public static void bubble(){
        int i,j,tmp;
        //扫描次数
        for(i=5;i>0;i--){
            //比较、交换次数
            for(j=0;j<i;j++){
                //比较相邻两数，若第一个数较大则交换，即让最大的数往右移动
                if(data[j]>data[j+1]){
                    //data[j]和data[j+1]交换
                    tmp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = tmp;
                }
            }
            //将各次扫描后的结果打印输出
            System.out.print("第"+(6-i)+"次排序后:");
            showData();
            System.out.println();
        }
    }
    public static void main(String[] args) {
        System.out.print("原始数据为:");
        showData();
        System.out.println();
        bubble();
        System.out.print("排序后的结果:");
        showData();
        System.out.println();
    }

    //原始数据为:7 3 8 4 2 6
    //第1次排序后:3 7 4 2 6 8
    //第2次排序后:3 4 2 6 7 8
    //第3次排序后:3 2 4 6 7 8
    //第4次排序后:2 3 4 6 7 8
    //第5次排序后:2 3 4 6 7 8
    //排序后的结果:2 3 4 6 7 8
}

2、冒泡排序优化-添加岗哨

n个算法必须执行n-1次扫描。传统冒泡排序法有个缺点，就是不管数据是否已经排序完成都会固定执行n(n-1)/2次。

可使用岗哨的概念改进冒泡排序，提高执行的效率。

优化算法:

public class MaoPaoYouHua {
    static int data[] = {6,5,3,7,8,9};

    public static void showData(){
        int i;
        for (i =0;i<6;i++){
            System.out.print(data[i]+" ");
        }
    }
    public static void bubble(){
        int i,j,tmp,flag;
        //扫描次数
        for(i=5;i>0;i--){
            flag=0;
            //比较、交换次数
            for(j=0;j<i;j++){
                //比较相邻两数，若第一个数较大则交换，即让最大的数往右移动
                if(data[j]>data[j+1]){
                    //data[j]和data[j+1]交换
                    tmp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = tmp;
                    //如果执行过交换，则flag不为0
                    flag++;
                }
            }
            if(flag == 0){
                break;
            }
            //将各次扫描后的结果打印输出
            System.out.print("第"+(6-i)+"次排序后:");
            showData();
            System.out.println();
        }
    }
    public static void main(String[] args) {
        System.out.print("原始数据为:");
        showData();
        System.out.println();
        bubble();
        System.out.print("排序后的结果:");
        showData();
        System.out.println();
    }

    //原始数据为:6 5 3 7 8 9
    //第1次排序后:5 3 6 7 8 9
    //第2次排序后:3 5 6 7 8 9
    //排序后的结果:3 5 6 7 8 9
}

3、插入排序

插入排序法是将数组中的元素逐一与已排序好的数据进行比较，先将前两个元素排序，再将第三个元素插入到适当的位置，重复次步骤。

示例代码:

public class ChaRu {
    static int data[] = {7,3,8,4,2,6};

    public static void showData(){
        int i;
        for (i =0;i<6;i++){
            System.out.print(data[i]+" ");
        }
    }
    public static void insert(){
        int i,j,tmp;
        for(i=1;i<6;i++){
            tmp = data[i];
            j=i-1;
            //如果第二个元素小于第一个元素
            while (j>=0 && tmp<data[j])
            {
                //就把所有元素往后推一个位置
                data[j+1] = data[j];
                j--;
            }
            //最小的元素放到第一个位置
            data[j+1] = tmp;
            System.out.print("第"+i+"次排序后:");
            showData();
            System.out.println();
        }
    }
    public static void main(String[] args) {
        System.out.print("原始数据为:");
        showData();
        System.out.println();
        insert();
        System.out.print("排序后的结果:");
        showData();
        System.out.println();
    }
    //原始数据为:7 3 8 4 2 6
    //第1次排序后:3 7 8 4 2 6
    //第2次排序后:3 7 8 4 2 6
    //第3次排序后:3 4 7 8 2 6
    //第4次排序后:2 3 4 7 8 6
    //第5次排序后:2 3 4 6 7 8
    //排序后的结果:2 3 4 6 7 8
}

4、快速排序

快速排序法又称为分割交换排序法，是目前公认的最佳排序法，也是使用分而治之的的方式，会先在数据中找到一个虚拟的中间值，并按照此中间值
将所有打算排序的数据分成两部分。其中小于中间值的数据放在左边，而大于中间值的数据放在右边，再以同样的方式分别处理左右两边的数据，直到排序完成
示意过程
(5,2,7,3,9,10,8,6,1,4)
以4为基准进行分解
(2,3,1)(4)(5,7,9,10,8,6)
再以每组最右边的值为基准进行分解
(1)(2,3)(4)(5)(6)(7,9,10,8)
(1)(2)(3)(4)(5)(6)(7)(8)(9,10)
(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)

示例代码:

public class KuaiSu {
    public static void main(String[] args){
        Integer[] arr = {5,2,7,3,9,10,8,6,1,4};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    //排序方法-假设从小到大排序
    public static void quickSort(Integer[] arr,int low,int high){
        if(low < high){
            int part=partition(arr,low,high);
            //递归调用
            quickSort(arr,low,part-1);
            quickSort(arr,part+1,high);
        }
    }

    //划分方法
    private static int partition(Integer[] arr,int low,int high){
        //使用 r[low]作为枢轴元素
        int pivot = arr[low];
        //从两端交替向内扫描
        while(low < high){
            while(low<high && arr[high] >= pivot) {high--;}
            //将比 pivot 小的元素移向低端
            arr[low] = arr[high];
            while(low<high && arr[low] <= pivot){low++;}
            //将比 pivot 大的元素移向高端
            arr[high] = arr[low];
        }
        //设置枢轴
        arr[low]=pivot;
        //返回枢轴元素位置
        return low;
    }

    //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
}

5、选择排序

选择排序法，就是反复从未排序的数列中取出最小的元素，加入到另一个数列中，

最后的结果即为已经排序的数列。若从大到小排序，则将最大值放入第一个位置;若从小到大排序，

则将最大值放在最后一个位置。

示例代码:

public class XuanZe {
    static int data[] = {7,3,8,4,2,6};

    public static void showData(){
        int i;
        for (i =0;i<6;i++){
            System.out.print(data[i]+" ");
        }
    }
    public static void select(){
        int smallest,temp,j,index;
        //扫描次数
        for(int i=0;i<5;i++){
            smallest = data[i];
            index = i;
            //由i+1比较起，比较5次
            for(j=i+1;j<6;j++){
                //比较第i个和第j个
                if(smallest>data[j]){
                    smallest = data[j];
                    index=j;
                }
            }
            //将最小的与当前data[i]互换
            temp =data[index];
            data[index]=data[i];
            data[i]=temp;
            //将各次扫描后的结果打印输出
            System.out.print("第"+(i+1)+"次排序后:");
            showData();
            System.out.println();
        }
    }
    public static void main(String[] args) {
        System.out.print("原始数据为:");
        showData();
        System.out.println();
        select();
        System.out.print("排序后的结果:");
        showData();
        System.out.println();
    }

    //原始数据为:7 3 8 4 2 6
    //第1次排序后:2 3 8 4 7 6
    //第2次排序后:2 3 8 4 7 6
    //第3次排序后:2 3 4 8 7 6
    //第4次排序后:2 3 4 6 7 8
    //第5次排序后:2 3 4 6 7 8
    //排序后的结果:2 3 4 6 7 8

}

6、基数排序

基数排序并不需要元素之间的比较操作，而是属于一种分配模式排序方式
基数排序法的方向可分为最高位优先和最低位优先两种，以最低位优先为例。
将三位数的整数数据加以排序(按个位数、十位数、百位数来进行排序)
 75,3,18,46,21,16,188,256
把每个整数按个位数字放到列表中
个位数字 0  1   2   3   4   5   6          7   8       9
           21      3       75  16,46,256      18,188
合并后   21 3 75 16 46 256 18 188
按十位数字 0   1       2   3   4   5    6     7   8   9
         3    16,18  21      46  256        75   188
合并后   3 16 18 21 46 256 75 188
按百位数字 0                   1     2   3    4   5   6    7   8   9
         3,16,18,21,46,75    188    256
最后合并即完成排序  3 16 18 21 46 75 188 256

示例代码

public class JiShu {
    static int data[] = {75,3,18,46,21,16,188,256};
    static int size = 8;
    public static void showData(){
        int i;
        for (i =0;i<size;i++){
            System.out.print(data[i]+" ");
        }
    }
    public static void radix(){
        int i,j,k,n,m;
        for (n=1;n<=100;n=n*10)  //n为基数，从个位数开始排序
        {
            //设置暂存数组，[0~9位数][数据个数]，所有内容均为0
            int tmp[][]=new int[10][100];
            for (i=0;i<size;i++)  //对比所有数据
            {
                m=(data[i]/n)%10;  //m为n位数的值，如36取十位数(36/10)%10=3
                tmp[m][i]=data[i];  //把data[i]的值暂存于tmp中
            }

            k=0;
            for (i=0;i<10;i++)
            {
                for(j=0;j<size;j++)
                {
                    if(tmp[i][j] != 0)  //因一开始设置tmp={0}，故不为0者即为
                    {
                        //data暂存在tmp 中的值，把tmp中的值放回data[ ]中
                        data[k]=tmp[i][j];
                        k++;
                    }
                }
            }
            System.out.print("经过"+n+"位数排序后：");
            showData();
            System.out.println();
        }
    }
    public static void main(String[] args) {
        System.out.print("原始数据为:");
        showData();
        System.out.println();
        radix();
        System.out.print("排序后的结果:");
        showData();
        System.out.println();
    }

    //原始数据为:75 3 18 46 21 16 188 256
    //经过1位数排序后：21 3 75 46 16 256 18 188
    //经过10位数排序后：3 16 18 21 46 256 75 188
    //经过100位数排序后：3 16 18 21 46 75 188 256
    //排序后的结果:3 16 18 21 46 75 188 256
}

7、希尔排序

希尔排序法
当原始记录的键值大部门已经排好序的情况下插入排序法会非常有效，因为不需要执行太多的数据搬移操作。
希尔排序法就是将数据区分成特定间隔的几个小区块，以插入排序法排完区块内的数据后再渐渐减少间隔的操作。
以数列(59,95,36,45,12,4,58,25)从小到大的排序过程来说明希尔排序法的演算过程
1、首先将所有数据划分成4份，分别是
(59,12)(95,4)(36,58)(45,25)
2、再分别进行插入排序
(12,59)(4,95)(36,58)(25,45)
3、接着缩小间隔为2份
(12,4,36,25)(59,95,58,45)
4、再进行插入排序
(4,12,25,36)(45,58,59,95)
5、再缩小间隔为1份对每一个元素进行排序
(4,12,25,36,45,58,59,95)

所以这种情况适合大部分数据都已经排序的情况

示例代码:

public class XiEr {
    static int data[] = {59,95,36,45,12,4,58,25};
    static int size=8;
    public static void showData(){
        int i;
        for (i =0;i<size;i++){
            System.out.print(data[i]+" ");
        }
    }
    public static void xiEr(){
        int i;        //i为扫描次数
        int j;        //以j来定位比较的元素
        int k=1;      //k打印计数
        int tmp;      //tmp用来暂存数据
        int jmp;      //设置间距位移量
        jmp=size/2;
        while (jmp != 0)
        {
            for (i=jmp ;i<size ;i++)
            {
                tmp=data[i];
                j=i-jmp;
                while(j>=0 && tmp<data[j])  //插入排序法
                {
                    data[j+jmp] = data[j];
                    j=j-jmp;
                }
                data[jmp+j]=tmp;
            }
            System.out.print("第"+ (k++) +"次排序：");
            System.out.println();
            showData();
            System.out.println();
            jmp=jmp/2;    //控制循环数
        }

    }
    public static void main(String[] args) {
        System.out.print("原始数据为:");
        showData();
        System.out.println();
        xiEr();
        System.out.print("排序后的结果:");
        showData();
        System.out.println();
    }

    //原始数据为:59 95 36 45 12 4 58 25
    //第1次排序：
    //12 4 36 25 59 95 58 45
    //第2次排序：
    //12 4 36 25 58 45 59 95
    //第3次排序：
    //4 12 25 36 45 58 59 95
    //排序后的结果:4 12 25 36 45 58 59 95

}

8、合并排序

合并排序法是针对已经排序好的两个或两个以上的数列，通过合并的方式将其组合成一个大的且已经排好序的数列。
(4,2,6,3,5,1,9,7)
(2,4)(3,6)(1,5)(7,9)
(2,3,4,6)(1,5,7,9)
(1,2,3,4,5,6,7,9)

示例代码

public class HeBing {
    public static void main(String[] args) {
        int[] arr1 = {4,2,6,3,5,1,9,7};
        System.out.println(Arrays.toString(arr1));
        mergeSort(arr1,0,arr1.length-1);
        System.out.println(Arrays.toString(arr1));
    }

    public static void mergeSort(int[] arr,int l,int r) {
        if (l<r) {
            int q = (l+r)/2;
            mergeSort(arr,l,q);
            mergeSort(arr,q+1,r);
            merge(arr,l,q,r);
        }
    }

    /**
     *
     * @param arr  排序数组
     * @param l    数组最左边下标
     * @param q    数组中间位置下标
     * @param r    数组最右位置下标
     */
    public static void merge(int[] arr, int l, int q, int r) {
        /**因为每次切割后左边下标都是（l,q），右边数组的下标是(q+1,r)
         * 所以左边数组的元素个数就是q - l + 1
         * 右边的数组元素个数就是r - q
         * **/
        final int n1 = q-l+1;//切割后左边数组的数据长度
        final int n2 = r-q;//切割后右边数组的数据长度
        /**创建两个新数组将切割后的数组分别放进去，长度加1是为了放置无穷大的数据标志位**/
        final int[] left = new int[n1+1];//加一操作是增加无穷大标志位
        final int[] right = new int[n2+1];//加一操作是增加无穷大标志位
        //两个循环将数据添加至新数组中
        /**左边的数组下标是从l到q**/
        /**遍历左边的数组*/
        for (int i = 0; i < n1; i++) {
            left[i] = arr[l+i];
        }
        for (int i = 0; i < n2; i++) {
            right[i] = arr[q+1+i];
        }

        //将最大的正整数放在两个新数组的最后一位
        left[n1] = Integer.MAX_VALUE;
        right[n2] = Integer.MAX_VALUE;

        int i = 0,j = 0;
        //谁小谁放在前面
        for (int k = l; k <= r; k++) {
            if (left[i]<=right[j]) {
                arr[k] = left[i];
                i = i+1;
            } else {
                arr[k] = right[j];
                j = j+1;
            }
        }
    }
}

9、堆积树排序

堆积树排序是选择排序法的改进版，可以减少再选择排序法中的比较次数，进而减少排序时间。
堆积树是一种特殊的二叉树，可分为最大堆积树和最小堆积树两种。
最大堆积树:它是一颗完全二叉树。所有节点的值都大于或等于它左右子节点的值。树根是堆积树中最大的。
最小堆积树:它是一颗完全二叉树。所有节点的值都小于或等于它左右子节点的值。树根是堆积树中最小的。
堆积树排序的基本思想：

（1）将待排序的序列构造成一个大顶堆；

（2）此时，整个序列最大的值就是堆顶的根节点；

（3）将其与末尾元素进行交换，此时末尾就成了最大值；

（4）然后将剩余的 n-1 个元素重新构造称为一个堆，这样会得到 n 个元素的次大（小）值；

（5）如此反复执行就能得到一个有序序列。

示例代码:

public class DuiJiShu {
    public static void main(String args[]) throws IOException
    {
        int i,size,data[]={0,5,6,4,8,3,2,7,1}; //原始数组内容
        size=9;
        System.out.print("原始数组：");
        for(i=1;i<size;i++)
            System.out.print("["+data[i]+"] ");
        DuiJiShu.heap(data,size);      //建立堆积树
        System.out.print("\n排序结果：");
        for(i=1;i<size;i++)
            System.out.print("["+data[i]+"] ");
        System.out.print("\n");
    }

    public static void heap(int data[] ,int size)
    {
        int i,j,tmp;
        for(i=(size/2);i>0;i--)    //建立堆积树节点
            DuiJiShu.ad_heap(data,i,size-1);
        System.out.print("\n堆积内容：");
        for(i=1;i<size;i++)       //原始堆积树内容
            System.out.print("["+data[i]+"] ");
        System.out.print("\n");
        for(i=size-2;i>0;i--)         //堆积排序
        {
            tmp=data[i+1];          //头尾节点交换
            data[i+1]=data[1];
            data[1]=tmp;
            DuiJiShu.ad_heap(data,1,i); //处理剩余节点
            System.out.print("\n处理过程：");
            for(j=1;j<size;j++)
                System.out.print("["+data[j]+"] ");
        }
    }

    public static void ad_heap(int data[],int i,int size)
    {
        int j,tmp,post;
        j=2*i;
        tmp=data[i];
        post=0;
        while(j<=size && post==0)
        {
            if(j<size)
            {
                if(data[j]<data[j+1])   //找出最大节点
                    j++;
            }
            if(tmp>=data[j])   //若树根较大，结束比较过程
                post=1;
            else
            {
                data[j/2]=data[j];  //若树根较小，则继续比较
                j=2*j;
            }
        }
        data[j/2]=tmp;     //指定树根为父节点
    }
}