Java 排序算法:归并排序、阶乘、直接插入排序、冒泡排序、选择排序等算法

朱雀 2021-03-16 15:35 714阅读 0赞

**图解**

![495676-20170310141521373-669264928.png][]

--------------------

# 1. 选择排序 #

/*
         * 选择排序 
         * 
         * 在未排序序列中找到最小元素，存放到排序序列的起始位置 再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。
         * 以此类推，直到所有元素均排序完毕。
         */
        int[] num = {2,3,1,5,4};
        //控制遍历次数
        for (int i = 0; i < num.length-1; i++) {
            //记录每次遍历的起始下标位置，默认为最小值
            int minIndex = i;
            for (int j = i+1; j < num.length; j++) {
                if (num[j]<num[minIndex]) {
                    minIndex = j;
                }
            }
            //每次遍历结束，最小值和起始位置互换值
            int temp = num[i];
            num[i] = num[minIndex];
            num[minIndex] = temp;
        }
        //打印输出
        for (int i : num) {
            System.out.print(i+"\t");
        }

--------------------

# 2. 冒泡排序 #

/*
         * 冒泡排序
         * 
         * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
         * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
         * 针对所有的元素重复以上的步骤，除了最后一个。 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
         */
        int[] num1 = {1,3,4,6,2,11,19,2,7,0};
        // 控制遍历次数
        for (int i = 0; i < num1.length-1; i++) {
            int temp = 0;
            //控制每次遍历比较次数
            for (int j = 0; j < num1.length-1; j++) {
                //如果后一个数更小就和前一个数交换值
                if (num1[j+1]<num1[j]) {
                    temp = num1[j];
                    num1[j] = num1[j+1];
                    num1[j+1] = temp;
                }
            }
            //打印每次遍历之后的数组
            System.out.println("第"+(i+1)+"次遍历后的数组：");
            for (int j : num1) {
                System.out.print(j+" ");
            }
            System.out.println();
        }
        //输出
        System.out.println("经过冒泡排序后的数组：");
        for (int i : num1) {
            System.out.print(i+" ");
        }

--------------------

# 3. 直接插入排序 #

/*
         * 直接插入排序 
         * 
         * 从第一个元素开始，该元素可以认为已经被排序
         * 取出下一个元素，在已经排序的元素序列中从后向前扫描
         * 如果前面元素大，则前面元素向后移一位
         * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
         * 将新元素插入到该位置中
         * 重复步骤2
         */
        int[] num2 = {3, 4, 2, 1, 5, 6, 9, 8, 7, 0 };
        //控制遍历次数
        for (int i = 1; i < num2.length; i++) {
            int temp = num2[i];
            int j = i;
            for (j = i; j > 0 && temp < num2[j-1]; j--) {
                //num[2] = 2时
                //j=2;num2[2]=num2[1];3 4 4 ...;j=1;继续内层循环
                //j=1;num2[1]=num2[0];3 3 4 ...;j=0;跳出内层循环
                num2[j] = num2[j-1];
            }
            //j=0;num[0]=2;2,3,4...
            num2[j] = temp;
            //打印每次移动后的数组
            System.out.println("第"+i+"次移动后的数组:");
            for (int k : num2) {
                System.out.print(k+" ");
            }
            System.out.println();
        }
        //输出
        System.out.println("经过直接插入排序之后的数组：");
        for (int i : num2) {
            System.out.print(i+" ");
        }

--------------------

# 4. 阶乘 #

/*
     * 阶乘的方法递归算法
     * 
     * 1!   = 1 
     * 2!   = 2 x 1             = 2 x 1！ 
     * 3!   = 3 x 2 x 1         = 3 x 2! 
     * 4!   = 4 x 3 x 2 x 1     = 4 x 3! 
     * ......
     */ 
    static int factorial(int n) {
        // return n*(n-1)!
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }

--------------------

# 5. 归并排序 #

![05145558-282c2629e8a4428281a65f25603d8895.jpg][]

/*    
        （1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 
        （2）设定两个指针，最初位置分别为两个已经排序序列的起始位置 
        （3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 
        （4）重复步骤3直到某一指针达到序列尾 
        （5）将另一序列剩下的所有元素直接复制到合并序列尾
    */
    public static void merge(int[] num, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int left = low;// 左边数组的起始位置
        int right = mid + 1;// 右边数组的起始位置
        int index = 0;
        // 比较拆分的两个子数组，依次取最小值，放入新数组,并移动指针到后一位
        while (left <= mid && right <= high) {
            if (num[left] < num[right]) {
                temp[index++] = num[left++];
            } else {
                temp[index++] = num[right++];
            }
        }
        // 把左边剩余的数移入数组
        while (left <= mid) {
            temp[index++] = num[left++];
        }
        // 把右边边剩余的数移入数组
        while (right <= high) {
            temp[index++] = num[right++];
        }
        // 把新数组中的数覆盖nums数组
        for (int i = 0; i < temp.length; i++) {
            num[i + low] = temp[i];
        }
        System.out.println(Arrays.toString(temp));
    }
    
    public static int[] mergeSort(int[] num, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            // 递归拆分左边
            mergeSort(num, low, mid);
            // 递归拆分右边
            mergeSort(num, mid + 1, high);
            // 左右归并,将拆分的有序数组排序
            merge(num, low, mid, high);
            System.out.println(Arrays.toString(num));
        }
        return num;
    }
    
    public static void main(String[] args) {
        int[] num3 = {14,12,15,13,11,16};
        int[] num0 = mergeSort(num3, 0, num3.length-1);
        System.out.println("排序结果：" + Arrays.toString(num0));
    }

[495676-20170310141521373-669264928.png]: /images/1615908845391.png
[05145558-282c2629e8a4428281a65f25603d8895.jpg]: /images/1615908864443.jpg