java实现冒泡排序，直接插入排序，选择排序，希尔排序，以及求出它们的时间复杂度O(n)

傷城~ 2023-07-08 10:27 6阅读 0赞

package com.yg.sort;/*
    @author  GeQiLin
    @date    2020/2/25  16:53
    */
    
    import java.util.Arrays;
    
    public class Sort1 {
        private static int max =80000;
        private static int arr[];
    
        public static void main(String[] args) {
            //用于计算算法运行时间
            long t1, t2;
            //初始化数组
            setArr();
            System.out.println("无序数组：");
           // printfArr(arr);
            t1 = System.currentTimeMillis();
            //排序算法
            //shellSort(arr);数据量大优于冒泡，小的时候差不多
           // insertSort(arr);
           // insertSort2(arr);性能较快
            //bubbleSort(arr);
            shellSort2(arr);
            t2 = System.currentTimeMillis();
            System.out.println("有序数组：");
           //printfArr(arr);
            showExecuteTime(t1, t2);
    
        }
    
        private static void printfArr(int[] arr) {
            for (int item : arr) {
                System.out.print(item + " ");
            }
            System.out.println();
        }
    
        //冒泡排序
        /*
        相邻位置比较,如果是逆序就交换,
        交换后继续与下一个相邻位置的元素比较,直至比较数组大小减一次
        上述循环每次可确定最大的数,第二大的数,第三大的数。。。。
        重复循环数组大小-1次得到最终排序
        * */
        private static void bubbleSort(int[] arr) {
            int tem = 0;
            boolean flag = false;
            for (int i = 0; i < arr.length - 1; i++) {
                for (int j = 0; j < arr.length - 1 - i; j++) {
                    //如果是逆序就交换
                    if (arr[j] > arr[j + 1]) {
                        flag = true;
                        tem = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = tem;
                    }
    
                }
                if (!flag) {
                    break;
                } else {
                    flag = false;
                }
            }
    
        }
    
        //构建数组大小和值
        public static void setArr() {
            arr = new int[max];
            for (int i = 0; i < max; i++) {
                arr[i] = (int) (Math.random() * max);
            }
        }
    
        //测试算法执行时间
        public static void showExecuteTime(long t1, long t2) {
            System.out.println("排序所需时间：" + (t2 - t1) + "ms");
        }
    
        //选择排序
        /*
        第一次在arr[0]到arr[n-1]中选出最小的数和arr【0】交换
        第二次在arr【1】到arr【n-1】中选出最小的和arr【1】交换
        。。。以此类推
        选n-1次
        * */
        public static void selectSort(int[] arr) {
            //存放最小值索引
            int minIndex = 0;
            //存放最小值
            int min = 0;
            for (int i = 0; i < arr.length - 1; i++) {
                min = arr[i];
                minIndex = i;
                for (int j = i; j < arr.length - 1; j++) {
                    if (min > arr[j + 1]) {
                        min = arr[j + 1];
                        minIndex = j + 1;
    
                    }
                }
                //将最小值和arr【i】交换
                if (minIndex != i) {
                    arr[minIndex] = arr[i];
                    arr[i] = min;
    
                }
    
            }
        }
    
        //插入排序
        /*
         * 默认第1个元素在有序序列，第2到n个元素无序
         * 依次将第2到第n个元素加入到第一个元素所在的有序序列
         * */
        public static void insertSort2(int[] arr) {
            for (int i = 1; i < arr.length; i++) {
                int insertVal = arr[i];
                int insertIndex = i - 1;
                //insertVal < arr[insertIndex] 当待插入元素大于有序序列最后一个元素时说明待插入元素此时相对于有序序列已经是有序的所以不用遍历比较
                while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                //更新有序序列中元素的新位置
                    arr[insertIndex + 1] = arr[insertIndex];
                    insertIndex--;
                }
    				//确认待插入元素在有序序列的位置
                    arr[insertIndex + 1] = insertVal;
    
    
            }
        }
    
        //这种写法效率不高有序序列
        //因为无论当前待插入元素是否小于有序序列的最后一个元素，它都会便利
        public static void insertSort(int[] arr) {
            int tem=0;
            for (int i = 1; i < arr.length; i++) {
                for (int j = i-1; j >=0 ; j--) {
                    if(arr[j+1]<arr[j]){
                        tem=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=tem;
                    }
                }
            }
        }
    
        //希尔排序 交换法 效率不高，低于直接插入
        /*如果有n个元素
         * 每次将序列分为n/2组，然后将每组进行直接插入排序
         * 当n/2==1时序列大致有序，然后对整个序列采用希尔排序
         * */
        public static void shellSort(int[] arr) {
            int tem=0;
            //循环到只分一组使整个序列大致有序
            for (int gap = arr.length / 2; gap > 0; gap /= 2) {
                //此for循环决定进行插入排序的次数
                for (int i = gap; i < arr.length; i++) {
                    //此for循环决定将要插入的元素需要和同组有序序列元素进行比较的次数
                    for (int j = i - gap; j >= 0; j -= gap) {
                        if (arr[j] > arr[j +gap]) {
                                tem=arr[j];
                                arr[j]=arr[j+gap];
                                arr[j+gap]=tem;
                        }
                    }
                }
            }
        }
    
        //希尔排序移位法，效率高
        /*
        先分组，然后采用直接插入
        * */
        public static void shellSort2(int []arr){
            int tem,j;
            for (int gap = arr.length/2 ; gap >0 ; gap/=2) {
                for (int i = gap  ; i <arr.length ; i++) {
                    j=i;
                    tem=arr[j];
                     if(arr[j]<arr[j-gap]){
                        while (j-gap>=0 && tem<arr[j-gap]){
                            arr[j]=arr[j-gap];
                            j-=gap;
                        }
                        arr[j]=tem;
                     }
                    }
                }
            }
        }