[数据结构与算法]2021-07-31

java实现的冒泡、插入、快排、二分归并排序算法

四种排序算法的类：

package sort_algorithm;

public class SortAlgorithm {

        //冒泡排序
        public void bubble(int []arr) {
            int len=arr.length;

            //每次找到一个最大的数
            for(int i=0;i<len;i++) {

                // -1 的原因 当最后一个元素的时候， 继续和下一个元素比较， 下一个元素没有， 会越界
                // -i 的原因是 每遍历一次会少一个
                for(int j=0;j<len-1-i;j++) {

                    if(arr[j]>arr[j+1]) {
                        //做交换
                        int t=arr[j+1];
                        arr[j+1]=arr[j];
                        arr[j]=t;
                    }
                }
            }
        }

        //插入排序
        public void insert(int []arr) {
            int len=arr.length;
            //中间变量
            int t,j;
            for(int i=1;i<len;i++) {
                j=i;
                t=arr[i];
                //后面的数比前面小，前面的数一次后移
                while(j>0 && arr[j]<arr[j-1]) {
                    arr[j]=arr[j-1];
                    j--;
                    //最后面的数，移到前面
                    arr[j]=t;
                }

            }
        }

        //快速排序
        public void quicksort(int arr[], int start, int end) {
            int i, j, t;
            if (start > end) {
                return;
            }
            i = start;
            j = end;
            t = arr[i]; // 用数组的第一个记录做基准
            while (i < j) { // 从表的两端交替向中间扫描
                while (i < j && arr[j] >= t)
                    j--;
                if (i < j)
                    arr[i++] = arr[j];// 用比基准小的记录替换低位记录
                while (i < j && arr[i] < t)
                    i++;
                if (i < j) // 用比基准大的记录替换高位记录
                    arr[j--] = arr[i];
            }
            arr[i] = t;// 将基准数值替换回 a[i]
            quicksort(arr, start, i - 1); // 对低子表进行递归排序
            quicksort(arr, i + 1, end); // 对高子表进行递归排序

        }

        //二分归并排序
        public void binaryMerge(int []arr) {
            binary(arr,0,arr.length-1);
        }

        //二分
        public void binary(int[]arr,int start,int end) {
            //二分到极致退出二分(左右两边各只有一个元素)
            if(start>=end) {
                return;
            }
            int mid=(start+end)/2;
            //先二分
            binary(arr, start, mid);
            binary(arr, mid+1, end);
            //再归并
            merge(arr,start,mid,end);

        }
        //归并
        public void merge(int []arr,int start,int mid,int end) {
            //左边最开始的元素
            int i=start;
            //右边最开始的元素
            int j=mid+1;
            //存储排好序元素的数组
            int t[]=new int[end - start + 1];
            int k=0;
            //当左右边都有元素时，按从小到大放进数组t中
            while(i<=mid && j<=end) {
                if(arr[i]>arr[j]) {
                    t[k++]=arr[j++];
                }else {
                    t[k++]=arr[i++];
                }

            }
            //当右边没有元素，将左边的所有元素放进数组t
            while (i <= mid) {
                t[k++] = arr[i++];
            }
            //当左边没有元素，将右边的所有元素放进数组t
            while (j <= end) {
                t[k++] = arr[j++];
            }
            for(int m=start;m<=end;m++) {
                //每次t都是从0下边开始存排好序的，而arr是从二分的地方开始，故arr从start下标开始，t从m-start开始
                arr[m]=t[m-start];
            }
        }

 }

测试类：

package sort_algorithm;

import java.util.Arrays;
import java.util.Scanner;

public class Test {
    public static void main(String[] args) {

        int n;
        while(true) {
            Scanner scanner=new Scanner(System.in);
            System.out.println("请输入生成随机数组的长度：");
            n=scanner.nextInt();
            //声明需要排序的数组
            int[]arr= new int[n];

            for(int i=0;i<n;i++) {
                //随机产生一个0-n的随机数放进数组中
                arr[i]=(int)(Math.random()*n);
            }

            System.out.println("随机生成的数组："+ Arrays.toString(arr));

            SortAlgorithm sortAlgorithm=new SortAlgorithm();
            long startTime,endTime;


            //测试
            System.out.println("请输入排序方法的编号：1.冒泡法  2.插入法  3.快速排序  4.二分归并");
            int choice=scanner.nextInt();
            switch (choice) {
                case 1:
                    startTime=System.currentTimeMillis();//获取程序开始运行时间
                    sortAlgorithm.bubble(arr);
                    endTime=System.currentTimeMillis();//获取程序运行结束时间
                    System.out.println("排序后的数组："+Arrays.toString(arr));
                    System.out.println("耗时："+(endTime-startTime)+"ms");
                    break;
                case 2:
                    startTime=System.currentTimeMillis();
                    sortAlgorithm.insert(arr);
                    endTime=System.currentTimeMillis();
                    System.out.println("排序后的数组："+Arrays.toString(arr));
                    System.out.println("耗时："+(endTime-startTime)+"ms");
                    break;
                case 3:
                    startTime=System.currentTimeMillis();
                    sortAlgorithm.quicksort(arr，0，arr.length-1);
                    endTime=System.currentTimeMillis();
                    System.out.println("排序后的数组："+Arrays.toString(arr));
                    System.out.println("耗时："+(endTime-startTime)+"ms");
                    break;
                case 4:
                    startTime=System.currentTimeMillis();
                    sortAlgorithm.binaryMerge(arr);
                    endTime=System.currentTimeMillis();
                    System.out.println("排序后的数组："+Arrays.toString(arr));
                    System.out.println("耗时："+(endTime-startTime)+"ms");
                    break;
                default:
                    System.out.println("没有此选项！");
                    break;
            }

        }
    }
}