七大基本比较排序算法（上）

✨hello，愿意点进来的小伙伴们，你们好呐！
✨ 🐻🐻系列专栏：【数据结构】
🐲🐲本篇内容： 插入排序算法 && 选择排序算法
🐯🐯作者简介:一名现大二的三非编程小白

基本概要

排序：就是将一组数据按照一定的比较规则，将其递增或者递减排列起来的一种操作。
我要介绍的比较排序算法大致可以分为四种：

1. 插入排序：
直接插入排序 ， 希尔排序
2. 选择排序：
直接选择排序，堆排序
3. 交换排序：
4. 归并排序：

在介绍排序算法的同时也会对其进行分析：
时间复杂度，空间复杂度，稳定性

时间复杂度与空间复杂度相信不用我多说吧，那让我先来介绍一下算法稳定性是什么？

算法稳定性介绍

排序算法稳定性的简单形式化定义为：如果arr[i] = arr[j]，排序前arr[i]在arr[j]之前，排序后arr[i]还在arr[j]之前，则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。

举个例子吧：
就像 小明和小红在一场考试中的成绩是相等的，但是小明的提交试卷的速度比小红快。那么在排序后，若小明的排名在小红前面，就该排序为稳定的。若相反，则为不稳定。

了解了稳定性后，让我们来对排序算法进行分析吧

1. 插入排序：

插入排序分为直接插入排序和希尔排序两种。

1.1 直接插入排序：

算法思路：

直接插入的排序就像玩斗地主时候的插入扑克牌。

1. 从第一个元素开始，该元素可以看作已经排好序；
2. 将第一个索引指向第二个元素，并将该索引的元素记录起来。第二个索引指向第一个索引前一个位置的元素。
3. 然后第二个索引往前扫描，如果该索引的元素大于第一个索引的元素，则该元素往后移动一位。
4. 扫描完数组后，就将第一个索引往后移动，重复以上操作，直到第一个索引扫描完数组。

接下来来看看图解：

1.

2.

3.

4.

5.

6.

7.

8.

9.

通过图解我们可以更清楚的认识到算法的流程是什么样的，那么现在让我来实现代码。

Java代码实现：

public class Sort {
    public static void main(String[] args) {
        int[] array = {9,8,7,6,5,4,3,2,1};
        insertSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void insertSort(int[] array){
        for(int i = 1;i < array.length;i++){
            int j = i - 1;
            int tmp = array[i];
            for(;j >= 0;j--){
                if(array[j] > tmp){
                    array[j + 1] = array[j];
                }else{

                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

算法分析：

时间复杂度：

最坏情况下就是当元素逆序时，这时候时间复杂度为 首项为1，尾项为 n - 1，差为1的等差数列的和，那么该算法的时间复杂度为 ： O(N ^ 2)

空间复杂度：

O(1)

稳定性：

稳定的 ,一个本身是稳定的排序可以变成不稳定

1.2 希尔排序：

希尔排序法又称缩小增量法。
思路：

1. 先选定一个整数gap，把待排序文件中所有记录分成个组。
2. 所有距离为的记录分在同一组内，并对每一组内的记录进行排序。
3. 然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

下面让我们来看看图解：
1.先按gap=5分组

2. 然后将所分好的组两两进行比较插入

3.然后再缩小gap的值，进行分组

4.然后再继续进行分组后的两两比较插入

这时候，你会发现经过两次分组后的比较插入后的结果已经趋近于有序，那么只要当gap等于 0 后，进行最后一个比较插入排序后，该数据就会有序。

5.

在该算法中，gap的确定是比较复杂的，以下我就以 【除以2】，来确定gap。
然后插入排序的思路与直接插入排序类似。

接下来来看看代码实现：

Java代码实现：

public class Sort {
    public static void main(String[] args) {
        int[] array = {9,8,7,6,5,4,3,2,1};
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void shell(int[] array, int gap){
        for(int i = gap;i < array.length;i++){
            int j = i - gap;
            int tmp = array[i];
            for(;j >= 0;j -= gap){
                if(array[j] > tmp){
                    array[j + gap] = array[j];
                }else{
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            gap /= 2;
            shell(array,gap);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

算法分析：

时间复杂度：

希尔排序的时间复杂度计算涉及到很高深的数学知识，我们就记住该算法的时间复杂度为 ：O（N^1.3）

空间复杂度：

O(1)

稳定性：

不稳定 因为是跳跃式分组来插入排序

2. 选择排序：

选择排序分为直接选择排序与堆排序：

2.1 直接选择排序：

思路：

1. 我们将下标i指向数组开头进行扫描。
2. 将下标 i 的数值记录下来。
3. 在元素个数为n的集合在array【i】 - array【n - 1】中寻找是否有元素比 i 下标的元素小，若有，则记录下该下标。
4. 最后交换下标i与记录下到的下标的元素
5. 重复以上步骤，直到 i 扫描接收。

下面我们来图解思路：

1.

2.

3. j遍历完，找到最小元素下标

4. 交换元素

5.重复上述步骤

接下来来看看代码实现：

Java代码实现：

public class Sort {
    public static void main(String[] args) {
        int[] array = {9,8,7,6,5,4,3,2,1};
        selectSort(array);
        System.out.println(Arrays.toString(array));
    }

    
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for(int j = i + 1;j < array.length;j++){
                if(array[minIndex] > array[j]){
                    minIndex = j;
                }
            }
            //当minIndex有变化就要交换
            if(minIndex != i){
                int tmp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = tmp;
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

直接选择排序还有另一种代码思路：

public class Sort {
    public static void main(String[] args) {
        int[] array = {9,8,7,6,5,4,3,2,1};
        selectSort2(array);
        System.out.println(Arrays.toString(array));
    }


    public static void selectSort2(int[] array){
        int left = 0;
        int right = array.length - 1;
        while(left < right){
            int minIndex = left;
            int maxIndex = left;
            for (int i = left + 1; i <= right; i++) {
                //找到最小
                if(array[i] < array[minIndex]){
                    minIndex = i;
                }
                //找到最大
                if(array[i] > array[maxIndex]){
                    maxIndex = i;
                }
            }

            swap(array,minIndex,left);//最小的交换到前面

            if(maxIndex == left){//
                maxIndex = minIndex;
            }

            swap(array,maxIndex,right);//最大的到后面
            left++;
            right--;
        }
    }
    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

算法分析：

时间复杂度：

O（N^2）

空间复杂度：

O(1)

稳定性：

不稳定

2.2 堆排序：

思路：
在这里我们用大根堆来实现递增的数据。

1. 首先先建立一个大根堆。
2. 然后将堆顶的元素与堆底的元素交换。
3. 然后调整下标为 0 的树使又成为大根堆。
4. 依次按照该步骤去交换元素，直到有序。

下面上图解：
1.创建大根堆
**

2.交换元素

3.调整堆

4.继续交换元素

5.调整堆

接下来就如此反复下去，直到end为0

下面看代码实现：

Java代码实现：

public class Sort {
    public static void main(String[] args) {
        int[] array = {9,8,7,6,5,4,3,2,1};
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }


    public static void heapSort(int[] array){
        //建立大根堆
        createBigHeap(array);

        int end = array.length - 1;
        while(end > 0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

    public static void createBigHeap(int[] array){
        for(int parent = (array.length - 1 - 1) / 2;parent >= 0;parent--){
            shiftDown(array,parent,array.length);
        }
    }
    public static void shiftDown(int[] array,int parent,int len){
        int child =( 2 * parent) + 1;
        while(child < len){
            //找到孩子节点最大的元素
            if(child + 1 < len && array[child] < array[child + 1]){
                child++;
            }
            if(array[child] > array[parent]){
                swap(array,child,parent);
                parent = child;
                child = (2 * parent) + 1;
            }else{
                break;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

算法分析：

时间复杂度：

O(N*logN)）

空间复杂度：

O(1)

稳定性：

不稳定