常见的五大类排序

骑猪看日落 2021-12-17 09:21 193阅读 0赞

### 初始化一个数组： ###

//初始化数组，类型为引用包装类型 Integer
    private static final Integer[] array = {2, 4, 6, 1, 3, 8, 7, 10, 9, 5};

### （1）冒泡排序的基本思想：重复的走过要排序的数列，一次比较两个元素，相邻两个元素进行交换，直到没有在需要交换为止。 ###

a）比较相邻的元素。如果第一个比第二个大，就交换他们两个；

b）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数；

c）针对所有的元素重复以上的步骤，除了最后一个；

d）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较；

/**
         * 冒泡排序
         */
        public static void bubbleSort() {
            int temp;
            int change = 1; //降低排序无用次数
            for (int i = 0; i < array.length - 1 && change == 1; i++) {
                change = 0;
                for (int j = 0; j < array.length - i - 1; j++) {
                    if (array[j] > array[j+1]) {
                        temp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = temp;
                        change = 1;
                    }
                }
            }
        }

### （2）简单选择排序的基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，才放在序列的起始位置，直到全部待排序的数据元素排完为止！ ###

/**
         * 简答选择排序
         */
        public static void changeSort() {
            int temp;
            for (int i = 0; i < array.length - 1; i++) {
                for (int j = i + 1; j < array.length; j++) {
                    if(array[i] > array[j]) {
                        temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                    }
                }
            }
        }

### （3）插入排序的基本思想：每步将一个待排序的记录，按其关键码值的大小插入前面已经排好序的数组中适当位置，直到全部插入为止！ ###

/**
         * 插入排序
         */
        public static void insertSort() {
            int j, temp;
            for (int i = 1; i < array.length; i++) {
                temp = array[i];
                for (j = i - 1; j >= 0 && array[j] > temp; j--) {
                    array[j+1] = array[j];
                }
                array[j+1] = temp;
            }
        }

### （4）二路归并排序的基本思想：采用分治算法来对其一个数组进行划分合并，直到划分的组中只有一个数组元素为止！ ###

/**
         * 二路归并排序
         * @param array
         * @param left
         * @param right
         */
        public static void mergeSort(Integer[] array, int left, int right) {
            if (left == right) {
                return;
            }
            int mid = (left + right) / 2;
            mergeSort(array, left, mid);            //左边递归求解
            mergeSort(array, mid + 1, right);  //右边递归求解
    
            int[] tempArray = new int[array.length];
            int i = left;
            int j = mid + 1;
            int k = left;
            while(i <= mid || j <= right) {
                //当右区间比较完毕，或者左区间的值存在并且比右区间的值小
                if (j > right || (i <= mid && array[i] < array[j])) {
                    tempArray[k++] = array[i++];    //将左区间的值放入临时数组中
                } else {
                    tempArray[k++] = array[j++];    //右区间的值存在，且比左区间的值小，放入临时数组中
                }
            }
    
            //将临时数组中的值拷贝到原来数组中
            for (k = left; k <= right; k++) {
                array[k] = tempArray[k];
            }
        }

### （5）快速排序的基本思想：采用分治算法通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这部分数据进行快速排序，整个排序过程可以递归进行，依此达到整个数据编程有序序列！ ###

/**
         * 快速排序
         * @param array
         * @param left
         * @param right
         */
        public static void quickSort(Integer[] array, int left, int right) {
            if (left >= right) {    //如果left >= right就说明已经整理完一个组
                return;
            }
            int i = left;
            int j = right;
            int temp = array[left];    //找出一个枢纽存储值
            while (i < j) {
                while (i < j && array[j] >= temp) {
                    j--;
                }
                array[i] = array[j];
                while(i < j && array[i] <= temp) {
                    i++;
                }
                array[j] = array[i];
            }
            array[i] = temp;
    
            quickSort(array, left, i);              //左边递归
            quickSort(array, i + 1, right);    //右边递归
        }

### （6）输出代码： ###

public static void main(String[] args) {
    //        ManySort.bubbleSort();
    //        changeSort();
    //        insertSort();
    //        mergeSort(array, 0, array.length - 1);
            quickSort(array, 0, array.length - 1);
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
            System.out.println();
        }

每天进步一点，往大公司奋斗，大家继续前进！

转载于:https://www.cnblogs.com/blogtech/p/11109559.html