常用的排序算法(Java版)

客官°小女子只卖身不卖艺 2022-11-21 11:49 140阅读 0赞

package algorithm.datastructure.sort;
    import java.util.HashSet;
    import java.util.Random;
    import java.util.Set;
    public class SeqList { 
    
        private int[] table;//数组
        private Set<Integer> set = new HashSet<>();//集合，用来判断重复元素
        private static final int INITIAL_MAX_NUM = 10;//默认生成的数范围0-9
        private static final int DEFAULT_CAPACITY = 10;//默认数组大小
    
        public SeqList() { 
            table = new int[DEFAULT_CAPACITY];
            for (int i = 0; i < DEFAULT_CAPACITY; i++) { 
                table[i] = getRandomNum(true, INITIAL_MAX_NUM);
            }
        }
    
        public SeqList(int capacity) { 
            table = new int[capacity];
            for (int i = 0; i < capacity; i++) { 
                table[i] = getRandomNum(true, 100);
            }
        }
    
        public SeqList(Boolean isRepeatable) { 
            table = new int[DEFAULT_CAPACITY];
            for (int i = 0; i < DEFAULT_CAPACITY; i++) { 
                table[i] = getRandomNum(isRepeatable, INITIAL_MAX_NUM);
            }
        }
    
        public SeqList(Boolean isRepeatable, int maxNum) { 
            table = new int[DEFAULT_CAPACITY];
            for (int i = 0; i < DEFAULT_CAPACITY; i++) { 
                table[i] = getRandomNum(isRepeatable, maxNum);
            }
        }
    
        public SeqList(int capacity, Boolean isRepeatable, int maxNum) { 
            table = new int[capacity];
            for (int i = 0; i < capacity; i++) { 
                table[i] = getRandomNum(isRepeatable, maxNum);
            }
        }
        private static int[] getRandomArray(int num) { 
            Random random = new Random();
            int[] arr = new int[num];
            for (int i = 0; i < num; i++) { 
                arr[i] = random.nextInt(num);
            }
            return arr;
        }
    
        /* * 获取随机数 * @isRepeatable Boolean 是否可重复 * @maxNum int 最大数字 * */
        private int getRandomNum(Boolean isRepeatable, int maxNum) { 
            Random random = new Random();
            if (!isRepeatable) { 
                int num = random.nextInt(maxNum);
                while (set.contains(num)) { 
                    num = random.nextInt(maxNum);
                }
                set.add(num);
                return num;
            } else { 
                return random.nextInt(maxNum);
            }
        }
        
        public void bubbleSort() { 
            bubbleSort(table);
        }
    
        public void selectSort() { 
           selectSort(table);
        }
    
    
        public void insertSort() { 
          insertSort(table);
        }
    
        public void binInsertSort() { 
            binInsertSort(table);
        }
    
        public void shellSort() { 
            shellSort(table);
        }
    
    
        public void quickSort(int i, int j) { 
            quickSort(table, i, j);
        }
    
        /* * 冒泡排序 * 1 7 8 9 0 2 7 * 交换相邻的，前面元素比后面元素大就交换到后面 * 第一趟交换结果 1 7 8 0 9 2 7 1 7 8 0 2 9 7 1 7 8 0 2 7 9 * 第二趟交换结果 1 7 0 8 2 7 9 1 7 0 2 8 7 9 1 7 0 2 7 8 9 * 第三趟交换结果 1 0 7 2 7 8 9 1 0 2 7 7 8 9 * 第四趟交换结果 0 1 2 7 7 8 9 * */
        public static void bubbleSort(int[] arr) { 
            long start = System.nanoTime();
            for (int i = 0; i < arr.length; i++) { //i的作用仅仅是记录一个编号
                boolean flag = true;//设置一个是否有序标志
                for (int j = 0; j < arr.length - 1 - i; j++) { //遍历当前无序序列
                    if (arr[j] > arr[j + 1]) { //大的交换到后面，一次循环交换使得当前无序序列最后一个元素arr[arr.length-1-i]变为最大的
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                        flag = false;
                    }
                }
                if (flag) { //如果没有交换元素，说明该序列有序，提取终止循环
                    break;
                }
            }
            long end = System.nanoTime();
            System.out.println("冒泡排序时间:" + (end - start));
        }
    
    
        /* * 插入排序 * 查找第i个元素时候，假设前面为排好序的 * 1 7 0 2 9 3 5 * 没有元素,直接插入 [1] 7 0 2 9 3 5 * 插入7，[1] 7>2 [1,7] 0 2 9 3 5 * 插入0, [1,7] 0<1 [0,1,7] 2 9 3 5 * 插入2,[0,1,7] 1<2<7 [0,1,2,7] 9 3 5 * 插入9,[0,1,2,7] 9>7 [0,1,2,7,9] 3 5 * 插入3,[0,1,2,7,9] 2<3<7 [0,1,2,3,7,9] 5 * 插入5,[0,1,2,3,7,9] 3<5<7 [0,1,2,3,5,7,9] * */
        public static void insertSort(int[] arr) { 
            long start = System.nanoTime();
            for (int i = 1; i < arr.length; i++) { 
                int j = i - 1;
                int key = arr[i];//保存当前要比较的元素
                while (arr[j] > key) { //前面的元素如果比当前元素小
                    arr[j + 1] = arr[j];//前面的元素后移
                    j--;
                    if (j < 0) { //如果移到最前面
                        // arr[0]=key;
                        break;
                    }
                }
                arr[j + 1] = key;
            }
            long end = System.nanoTime();
            System.out.println("插入排序时间:" + (end - start));
        }
    
        /* * 折半插入排序 * 通过折半查找找到插入位置low，然后把后移i-1到插入位置low的元素，然后把设置low位置的元素 * 首先插入第一个元素插入 1 * 然后当前遍历要插入的元素,用i记录当前要插入的元素 * 假设前面已经插入了元素1,2,8,9,10,11,当前要插入9 * [1,2,8,9,10,11] 9 i=6 arr[i]=9,j=5,key=arr[6],low=0,high=i-1=5,mid=(low+high)/2=2 * arr[2]=8, arr[2]<9, low=3,mid=4,arr[4]=10,arr[4]>9,high=3,mid=3,arr[2]<9,low=4 * arr[5]到arr[4]后移 arr[j]到arr[low]后移 arr[6]=arr[5]=11 arr[5]=arr[4]=10 * arr[low]=key=9 arr[4]=9 * [1,2,8,9,9,10,11] * * */
        public static void binInsertSort(int[] arr) { 
            long start = System.nanoTime();
            for (int i = 1; i < arr.length; i++) { 
                int key = arr[i];
                int j = i - 1;
                int low = 0, high = j, mid;
                while (low <= high) { 
                    mid = (low + high) / 2;
                    if (arr[mid] <= key) { 
                        low = mid + 1;
                    } else if (arr[mid] > key) { 
                        high = mid - 1;
                    }
                }
                for (j = i - 1; j >= low; j--) { 
                    arr[j + 1] = arr[j];
                }
                arr[low] = key;
            }
            long end = System.nanoTime();
            System.out.println("折半插入排序时间:" + (end - start));
        }
    
        /* * 希尔排序 * 48 16 92 65 32 65 27 23 * d1=4，分为四组 * 48 32 * 16 65 * 92 27 * 65 23 * 对每一组进行直接插入排序 * 第一趟排序结果 32 16 27 23 48 65 92 65 * d2=2，分为两组 * 32 27 48 92 * 16 23 65 65 * 对每一组进行直接插入排序 * 第二趟排序结果27 16 32 23 48 65 92 65 * d1=1分一组 * 第三趟排序结果16 23 27 32 48 65 65 92 * * */
        public static void shellSort(int[] arr) { 
            //这里设置d初始大小为数组长度的一般，每次变为原来的一半
            long start = System.nanoTime();
            int d = arr.length / 2;
            while (d >= 1) { 
                int k = 0;
                while (k < d) { 
                    for (int i = k; i < arr.length; i = i + d) { //起始元素下标为k,每个元素下标间隔d
                        if (i != k) { //当前不是第一个元素
                            int j = i - d;//获取上一个元素下标
                            int key = arr[i];//保存当前要比较的元素
                            while (arr[j] > key) { //当前要比较的元素key<arr[j]
                                arr[j + d] = arr[j];//arr[j]后移d位
                                j = j - d;
                                if (j < 0) { //如果移到最前面
                                    break;
                                }
                            }
                            arr[j + d] = key;//插入元素
                        }
                        // System.out.print(arr[i] + " ");
                    }
                    //System.out.println();
                    k++;
                }
                d = d / 2;//d变为原来一半
            }
            long end = System.nanoTime();
            System.out.println("希尔排序时间:" + (end - start));
        }
    
        /* * 快速排序的分割算法 * 通过分割算法获取的序列，元素<枢纽元素下标，该元素比枢纽元素小， 元素>枢纽元素下标，该元素比枢纽元素大， * 46 16 89 65 34 65* 23 28 i=0,j=8 arr[i]=49 arr[j]=28 pivot=46 * * 当前arr[j]与枢纽元素比较，如果arr[j]比枢纽元素大，j=j-1,直到找到枢纽元素小的，arr[i]=arr[j] * 当前arr[i]与枢纽元素比较，如果arr[i]比枢纽元素小，i=i+1,直到找到枢纽元素大的，arr[j]=arr[i] * * 46 16 89 65 34 65* 23 28 * i j * 28 16 89 65 34 65* 23 28 * i j * * 第一次循环, * arr[j]与pivot比较 * 46 16 89 65 34 65* 23 28 28 16 89 65 34 65* 23 28 * i j i j * arr[i]与pivot比较 * 28 16 89 65 34 65* 23 89 28 16 89 65 34 65* 23 28 28 16 89 65 34 65* 23 89 * i j i j i j * 第二次循环, * arr[j]与pivot比较 * 28 16 89 65 34 65* 23 89 28 16 23 65 34 65* 23 89 * i j i j * arr[i]与pivot比较 * 28 16 23 65 34 65* 23 89 28 16 23 65 34 65* 65 89 * i j i j * 第三次循环, * arr[j]与pivot比较 * 28 16 23 65 34 65* 65 89 28 16 23 65 34 65* 65 89 28 16 23 34 34 65* 65 89 * i j i j i j * arr[i]与pivot比较 * 28 16 23 34 34 65* 65 89 * ij * * arr[i]=46 * 28 16 23 34 46 65* 65 69 * * */
        private static int partition(int[] arr, int i, int j) { 
            int pivot = arr[i];//第一个元素设置为枢纽元素
            while (i < j) { 
                while (i < j && arr[j] >= pivot)//如果arr[j]枢纽元素大，j=j-1
                    j--;
                arr[i] = arr[j];//找到比枢纽元素小的，arr[i]=arr[j]
                while (i < j && arr[i] <= pivot)//如果arr[i]枢纽元素小，i=i+1
                    i++;
                arr[j] = arr[i];//找到比枢纽元素大的，arr[j]=arr[i]
            }
            //当i==j时候，这时候左边的元素都比枢纽元素小，右边的元素都比枢纽元素大
            arr[i] = pivot;//i就是枢纽元素的位置
            return i;
        }
    
        /* * 快速排序 * 通过分割算法获取枢纽元素位置，通过分割算法获得的序列,[i,pivot-1]为枢纽元素小的，[pivot+1,j]为比枢纽元素大的 * 这样对左边序列进行快速排序，再对右边序列进行快速排序，直到所有递归的快速排序的i都等于j,这时候排序完成 * */
        public static void quickSort(int[] arr, int i, int j) { 
            if (i < j) { 
                int pivot = partition(arr, i, j);//找到枢纽元素位置
                quickSort(arr, i, pivot - 1);//递归左区间
                quickSort(arr, pivot + 1, j);//递归右区间
            }
    
        }
    
        /* * 选择排序 * 1 7 8 9 0 2 6 * 1与后面的元素比较,后面元素比1小，交换到1的位置，确定第一个元素位置，第二次确定第二个元素位置。 * 第一趟排序结果 0 7 8 9 1 2 6 * 第二趟排序结果 0 1 8 9 7 2 6 * 第三趟排序结果 0 1 7 9 8 2 6 0 1 2 9 8 7 6 * 第四趟排序结果 0 1 2 8 9 7 6 0 1 2 7 9 8 6 0 1 2 6 9 8 7 * 第五趟排序结果 0 1 2 6 7 9 8 * 第六趟排序结果 0 1 2 6 7 8 9 * */
        public static void selectSort(int[] arr) { 
            long start = System.nanoTime();
            for (int i = 0; i < arr.length - 1; i++) { //遍历arr.length-1次
                boolean flag = true;//判断是否有序
                for (int j = i + 1; j < arr.length; j++) { //遍历下标i+1到arr.length-1
                    if (arr[j] < arr[i]) { //如果当前元素arr[j]比arr[i]小,与arr[i]交换
                        int temp = arr[j];
                        arr[j] = arr[i];
                        arr[i] = temp;
                        flag = false;
                    }
                    //这样经过一次循环得到的arr[i]为序列的最小值
                }
                if (flag) { //如果没有交换元素，说明序列有序
                    break;
                }
            }
            long end = System.nanoTime();
            System.out.println("选择排序时间:" + (end - start));
        }
    
    
        //堆排序，待完善
        public static void heapSort(int[] arr) { 
    
    
        }
    
        //归并排序，待完善
        public static void mergeSort(int[] arr) { 
    
        }
    
        public static int[] copyArray(int arr[]) { 
            int arr2[] = new int[arr.length];
            for (int i = 0; i < arr.length; i++) { 
                arr2[i] = arr[i];
            }
            return arr2;
        }
    
    
        public void traverse() { 
            System.out.println("遍历数组");
            for (int value : table) { 
                System.out.println(value);
            }
        }
    
        public static void main(String[] args) { 
    // SeqList seqList = new SeqList(10000, true, 10000);
    //
    // seqList.bubbleSort();
    // seqList.traverse();
    
    // seqList.selectSort();
    // seqList.traverse();
    //
    // seqList.insertSort();
    // seqList.traverse();
    
    // seqList.binInsertSort();
    // seqList.traverse();
    // seqList.shellSort();
    // seqList.traverse();
    // seqList.quickSort(0, 9999);
    // seqList.traverse();
    //
    //
            int[] arr = getRandomArray(5000);
            int[] arr2 = copyArray(arr);
            int[] arr3 = copyArray(arr);
            int[] arr4 = copyArray(arr);
            int[] arr5 = copyArray(arr);
            int[] arr6 = copyArray(arr);
            selectSort(arr);
            bubbleSort(arr2);
            insertSort(arr3);
            binInsertSort(arr4);
            shellSort(arr5);
            long start = System.nanoTime();
            quickSort(arr6, 0, arr6.length - 1);
            System.out.println("快速排序时间:" + (System.nanoTime() - start));
            // quickSort(new int[]{46, 16, 89, 65, 34, 65, 23, 28}, 0, 7);
    
    
        }
    }

待完善。。。