Java 中常见的各种排序算法汇总

2021-12-01 01:27:27

排序，有内排序和外排序

内排序，是在内存中进行

外排序，是在磁盘上进行

内排序根据是否使用比较大小的方法，又分比较排序和非比较排序

首先，Java中自已是有排序的

说明：
(1)Arrays类中的sort()使用的是“经过调优的快速排序法”;
(2)比如int[]，double[]，char[]等基数据类型的数组，Arrays类之只是提供了默认的升序排列，没有提供相应的降序排列方法。
(3)要对基础类型的数组进行降序排序，需要将这些数组转化为对应的封装类数组，如Integer[]，Double[]，Character[]等，对这些类数组进行排序。(其实还不如先进行升序排序，自己在转为将序)。

import java.util.Arrays;

public class TestSort {

    int a[] = {1, 2, 3, 4, 5, 6, 7};

    int temp;

    @Test(priority = 1, description = "利用Arrays中的Sort函数排序")

    public void ArraysSort() {

        Arrays.sort(a);

        for (int i = 0; i < a.length; i++) {

            System.out.println(a[i]);

        }

    }

}

Step01：冒泡排序

原理：比较两个相邻的元素，将值大的元素交换至一端。

思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。
即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。
然后比较第2个数和第3个数，将小数放前，大数放后，
如此继续，直至比较最后两个数，将小数放前，大数放后。

重复第一趟步骤，直至全部排序完成。

public class Sort01_BubbleSort {

    public static void main(String agrs[]) {

        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};

        System.out.println("\n"+arr.length);

        System.out.println("before sort:");

        for (int num : arr) {

            System.out.print(num + " ");

        }

        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]) {//if 后一位的数小，将被往前移动

                    int temp = arr[j];

                    arr[j] = arr[j + 1];

                    arr[j + 1] = temp;

                }

                System.out.println("\n"+"---第"+(i+1)+"轮第"+(j+1)+"次-----");

                for (int num : arr) {

                    System.out.print(num + " ");

                }

            }

        }

        System.out.println("\n"+"---");

        System.out.println("after sort:");

        for (int num : arr) {

            System.out.print(num + " ");

        }

    }

}

　　查看具体执行的过程：

"C:\Program Files\Java\jdk1.8.0_161\bin\java" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2018.1\lib\idea_rt.jar=55246:C:\Program Files\JetBrains\IntelliJ IDEA 2018.1\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_161\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\rt.jar;D:\00M_IDEA_Project\mavenDemo_idea01\target\classes" Sort01_BubbleSort

10

before sort:

1 2 3 4 5 6 7 8 9 0

---第1轮第1次-----

1 2 3 4 5 6 7 8 9 0

---第1轮第2次-----

1 2 3 4 5 6 7 8 9 0

---第1轮第3次-----

1 2 3 4 5 6 7 8 9 0

---第1轮第4次-----

1 2 3 4 5 6 7 8 9 0

---第1轮第5次-----

1 2 3 4 5 6 7 8 9 0

---第1轮第6次-----

1 2 3 4 5 6 7 8 9 0

---第1轮第7次-----

1 2 3 4 5 6 7 8 9 0

---第1轮第8次-----

1 2 3 4 5 6 7 8 9 0

---第1轮第9次-----

1 2 3 4 5 6 7 8 0 9

---第2轮第1次-----

1 2 3 4 5 6 7 8 0 9

---第2轮第2次-----

1 2 3 4 5 6 7 8 0 9

---第2轮第3次-----

1 2 3 4 5 6 7 8 0 9

---第2轮第4次-----

1 2 3 4 5 6 7 8 0 9

---第2轮第5次-----

1 2 3 4 5 6 7 8 0 9

---第2轮第6次-----

1 2 3 4 5 6 7 8 0 9

---第2轮第7次-----

1 2 3 4 5 6 7 8 0 9

---第2轮第8次-----

1 2 3 4 5 6 7 0 8 9

---第3轮第1次-----

1 2 3 4 5 6 7 0 8 9

---第3轮第2次-----

1 2 3 4 5 6 7 0 8 9

---第3轮第3次-----

1 2 3 4 5 6 7 0 8 9

---第3轮第4次-----

1 2 3 4 5 6 7 0 8 9

---第3轮第5次-----

1 2 3 4 5 6 7 0 8 9

---第3轮第6次-----

1 2 3 4 5 6 7 0 8 9

---第3轮第7次-----

1 2 3 4 5 6 0 7 8 9

---第4轮第1次-----

1 2 3 4 5 6 0 7 8 9

---第4轮第2次-----

1 2 3 4 5 6 0 7 8 9

---第4轮第3次-----

1 2 3 4 5 6 0 7 8 9

---第4轮第4次-----

1 2 3 4 5 6 0 7 8 9

---第4轮第5次-----

1 2 3 4 5 6 0 7 8 9

---第4轮第6次-----

1 2 3 4 5 0 6 7 8 9

---第5轮第1次-----

1 2 3 4 5 0 6 7 8 9

---第5轮第2次-----

1 2 3 4 5 0 6 7 8 9

---第5轮第3次-----

1 2 3 4 5 0 6 7 8 9

---第5轮第4次-----

1 2 3 4 5 0 6 7 8 9

---第5轮第5次-----

1 2 3 4 0 5 6 7 8 9

---第6轮第1次-----

1 2 3 4 0 5 6 7 8 9

---第6轮第2次-----

1 2 3 4 0 5 6 7 8 9

---第6轮第3次-----

1 2 3 4 0 5 6 7 8 9

---第6轮第4次-----

1 2 3 0 4 5 6 7 8 9

---第7轮第1次-----

1 2 3 0 4 5 6 7 8 9

---第7轮第2次-----

1 2 3 0 4 5 6 7 8 9

---第7轮第3次-----

1 2 0 3 4 5 6 7 8 9

---第8轮第1次-----

1 2 0 3 4 5 6 7 8 9

---第8轮第2次-----

1 0 2 3 4 5 6 7 8 9

---第9轮第1次-----

0 1 2 3 4 5 6 7 8 9

---

after sort:

0 1 2 3 4 5 6 7 8 9

Process finished with exit code 0

Step02：选择排序

原理：每一趟从待排序的记录中选出最小的元素，放到一端。

思路：第一次从记录中选择最小的数放到一端，第二次动剩下的记录中选择最小的，放到第二位

依次往下，直到全部排序完成。

public class Sort02_SelectionSort {

    public static void main(String[] args) {

        int[] arr = {4,13,2,1};

        System.out.println("\n" + arr.length);

        System.out.println("交换之前：");

        for (int num : arr) {

            System.out.print(num + " ");

        }

        //选择排序

        for (int i = 0; i < arr.length - 1; i++) {

            int k = i;

            for (int j = k + 1; j < arr.length; j++) {

                if (arr[j] < arr[k]) {

                    k = j; //记下目前找到的最小值所在的位置

                }

            }

            //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换

            if (i != k) {  //交换a[i]和a[k]

                int temp = arr[i];

                arr[i] = arr[k];

                arr[k] = temp;

            }

            System.out.println("\n"+"---第"+(i+1)+"轮找到最小数的位置是第"+(k+1)+"个数-----");

            for (int num : arr) {

                System.out.print(num + " ");

            }

        }

        System.out.println();

        System.out.println("交换后：");

        for (int num : arr) {

            System.out.print(num + " ");

        }

    }

}

查看具体执行过程

"C:\Program Files\Java\jdk1.8.0_161\bin\java" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2018.1\lib\idea_rt.jar=57407:C:\Program Files\JetBrains\IntelliJ IDEA 2018.1\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_161\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_161\jre\lib\rt.jar;D:\00M_IDEA_Project\mavenDemo_idea01\target\classes" Sort02_SelectionSort

4

交换之前：

4 13 2 1

---第1轮找到最小数的位置是第4个数-----

1 13 2 4

---第2轮找到最小数的位置是第3个数-----

1 2 13 4

---第3轮找到最小数的位置是第4个数-----

1 2 4 13

交换后：

1 2 4 13

Process finished with exit code 0

Step03：直接插入排序

直接插入排序是将未排序的数据插入至已排好序序列的合适位置。

思路：具体流程如下：

　　1、首先比较数组的前两个数据，并排序；

　　2、比较第三个元素与前两个排好序的数据，并将第三个元素放入适当的位置；

　　3、比较第四个元素与前三个排好序的数据，并将第四个元素放入适当的位置；

　　 ......

　　4、直至把最后一个元素放入适当的位置。

import java.util.Arrays;

public class Sort03_InsertSort {

    public static void main(String[] args) {

        int[] arr = {4, 13, 2, 1};

        System.out.println("\n" + arr.length);

        System.out.println("交换之前：");

        for (int num : arr) {

            System.out.print(num + " ");

        }

        System.out.println("\n");

        int tmp;

        for (int i = 1; i < arr.length; i++) {

            // 待插入数据

            tmp = arr[i];

            int j;

            for (j = i - 1; j >= 0; j--) {

                // 判断是否大于tmp，大于则后移一位

                if (arr[j] > tmp) {

                    arr[j + 1] = arr[j];

                } else {

                    break;

                }

            }

            arr[j + 1] = tmp;

            System.out.println(i + ":" + Arrays.toString(arr));

        }

    }

}

private void quickSort(int[] arr, int low, int high) {

        int i,j,temp,t;

        if(low>high){

            return;

        }

        i=low;

        j=high;

        //temp就是基准位

        temp = arr[low];

        while (i<j) {

            //先看右边，依次往左递减

            while (temp<=arr[j]&&i<j) {

                j--;

            }

            //再看左边，依次往右递增

            while (temp>=arr[i]&&i<j) {

                i++;

            }

            //如果满足条件则交换

            if (i<j) {

                t = arr[j];

                arr[j] = arr[i];

                arr[i] = t;

            }

        }

        //最后将基准为与i和j相等位置的数字交换

        arr[low] = arr[i];

        arr[i] = temp;

        //递归调用左半数组

        quickSort(arr, low, j-1);

        //递归调用右半数组

        quickSort(arr, j+1, high);

    }

快速排序

import java.util.Arrays;

/**

 * 快速排序的测试

 *

 */

public class TestSort {

    public int[] arr = new int[] { 7, 2, 4, 6, 0, 0, 0, 1, 6 };

    public int[] sort2(int[] datas, int low, int high) {

        int i = low, j = high, key = datas[low], tmp;

        while (i < j) {

            while (i < j && datas[j] >= key) {

                j--;

            }

            while (i < j && datas[i] < key) {

                i++;

            }

            if (i < j) {

                tmp = datas[i];

                datas[i] = datas[j];

                datas[j] = tmp;

            }

        }

        if (i - low > 0) {

            sort2(datas, low, i);

        }

        if (high - i > 1) {

            sort2(datas, i + 1, high);

        }

        return datas;

    }

    /**

     * 测试主方法

     *

     * @param args

     */

    public static void main(String args[]) {

        TestSort q = new TestSort();

        int[] t = q.arr;

        q.sort2(t, 0, t.length - 1);

        System.out.println(Arrays.toString(t));

    }

}

码农公寓

相关文章