【JAVA】七大排序算法(图解)_java快速排序图解

稳定性： 待排序的序列中若存在值相同的元素，经过排序之后，相等元素的先后顺序不发生改变，称为排序的稳定性。

思维导图：

（排序名称后面蓝色字体为时间复杂度和稳定性）

---

1.直接插入排序

核心思路

每次从无序区间中选择第一个元素，插入到有序区间的合适位置，直到整个数组有序。

排序步骤

1. 定义下标 i 为当前无序区间的第一个元素， i-1 表示有序区间的最大值，下标 j 从后往前遍历有序区间。
2. 有序区间：[0…i)
3. 无序区间：[i…n)
4. 若arr[i]>arr[i-1]，直接将arr[i]纳入有序区间即可。
5. 若arr[i]<arr[i-1]，交换arr[i]和arr[i-1]，i- -继续比较。

代码

    public static void insert(int[]arr){
        //有序区间：[0,i)
        //无序区间：[i,n)
        int n=arr.length;
        //i指向当前无序区间的第一个元素
        for (int i = 1; i < n; i++) {
            for (int j = i; j >=1 && arr[j]<arr[j-1]; j--) {
                    int temp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

优点

插入排序再近乎有序的集合上性能非常好！！！

只有当前一个元素大于后一个元素时，才需要交换，若前一个元素小于后一个元素，则不需要走第二层循环。

---

2.希尔排序

核心思路

希尔排序其实是对插入排序的一种优化。

先将待排序的数组分为若干个子数组。将子数组调整为有序状态，不断变大这个分组长度，当最终分组长度为1时，整个数组接近有序。最后来一次插入排序即可。

排序步骤

我们来举一个实例：

1. 首先gap取5，此时相隔距离为5的元素分到了一组（一共五组，每组两个元素），然后对每一组分别进行插入排序

2. gap折半为2，此时相隔距离为2的元素被分到了一组（一共两组，每组五个元素），然后对每一组分别进行插入排序

3. gap再次折半为1，此时所有元素被分到了一组，对它进行插入排序，至此插入排序完成
   

本例中前两趟就是希尔排序的预排序，最后一趟就是希尔排序的插入排序。

代码

    private static void insertionSortByGap(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j-gap>=0 && arr[j]<arr[j-gap]; j-=gap) {
                int temp=arr[j];
                arr[j]=arr[j-gap];
                arr[j-gap]=temp;
            }
        }
    }
1
2
3
4
5
6
7
8
9

---

3.直接选择排序

核心思路

直接选择排序：每次在无序区间中选择最小值与无序区间的第一个元素交换，直到整个数组有序。

排序步骤

1. 定义下标 i 为当前无序区间的第一个元素，下标 min 为无序区间的最小值，下标 j 遍历无序区间。
2. 有序区间：[0…i)
3. 无序区间：[i…n)
4. j 遍历无序数组，若 j 指向的元素小于min指向的元素，则min指向此元素。
5. 遍历完之后，将min指向的元素与 i 指向的元素交换。
   

代码

    public static void select(int[] arr){
        //有序区间：[0,i)
        //无序区间：[i,n)
        int n=arr.length;
        //当无序区间只剩下一个元素时，已经不用再排了
        for (int i=0; i < n-1 ; i++) {
            //min指向无序区间的最小值
            int min=i;
            for (int j = i+1 ; j < n ; j++) {
                if(arr[j]<arr[min]){
                    min=j;
                }
            }
            //此时min一定指向无序区间的最小值
            int temp=arr[i];
            arr[i]=arr[min];
            arr[min]=temp;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

缺点

无论数组是否接近有序，直接选择排序都会执行一遍内部的排序流程，对数据不敏感。

---

4.堆排序