直接插入排序【从0-1学数据结构】

文章目录

- - 💗 直接插入排序
  - Java代码
  - C代码
  - JavaScript代码
  - 稳定性
  - 时间复杂度
  - 空间复杂度

我们先来学习直接插入排序, 直接排序算是所有排序中最简单的了,代码也非常好实现,尽管直接插入排序很简单,但是我们依旧不可以上来就直接写代码,一定要分析之后才开始写,这样可以提高自己写代码的准确率,整体流程下来,对知识的理解也会加深.

💗 直接插入排序

默认第一个元素为有序的,然后从无序序列中的最左边取元素,从有序序列的右到左依次比较,直到找到合适的位置,然后插入. (简言之: 从无序序列取第一个元素从左到右比较插入到有序序列合适的位置)

用生活中的例子来描述直接插入排序理解起来会更加容易,所以我们这里就用一个生活中常发生的事来类比学习吧,如果我们把直接插入排序用打扑克牌来模拟,会是怎样的效果呢?

现在就来试试吧~

使用玩扑克牌的例子来模拟直接插入排序是一个很好的主意，这个例子非常贴近直接插入排序的实际操作过程。让我们详细地通过这个例子来理解直接插入排序：

初始状态：你的手中还没有牌，而洗好的牌堆是无序的。
拿起第一张牌：从牌堆中拿起最上面的一张牌，这是你手中的第一张牌，所以它自然就是有序的。
继续摸牌：再次从牌堆中拿起最上面的一张牌。
比较和插入：
- 将这张新拿到的牌与手中已有的牌从右到左进行比较。
- 如果新牌比正在比较的牌小，就将手中的这张牌向右移动一个位置，为新牌腾出空间。
- 继续这个过程，直到找到一个牌位，那里的牌比新牌小或者没有牌了（也就是这张新牌是目前最小的）。
插入新牌：将新牌放入这个位置。
重复过程：继续从牌堆中拿牌，并重复上述比较和插入的过程，直到牌堆中的所有牌都被拿完并按顺序排列在手中。

这个过程很好地模拟了直接插入排序的逻辑。在每一步中，你都保证了手中的牌是有序的，通过找到合适的位置为新牌插入。这就是直接插入排序的精髓：一步步构建有序序列，直到所有元素都被正确地插入。

我们把上面的操作用图示来演示一下,进一步加深理解 , 假设现在的洗好的扑克牌为一组无序序列 : {6,4,9,1,10,2,8}

好,可以开始打牌了~

Java代码

package src.boke;

public class InsertSort {
    public static void main(String[] args){
       //无序序列
        int[] arr = {6,4,9,1,10,2,8};
        //调用直接排序方法
        insertSort(arr);
        //打印有序序列
        printArray(arr);

    }

    /**
     * 直接插入排序方法实现
     * @param arr 待排序序列/无序序列
     */
    public static void insertSort(int[] arr){
        //对传进来的无序序列进行直接插入排序操作
        for (int i = 1; i < arr.length; i++) {
            //接收int[i] ,即摸到的牌
            int key = arr[i];
            int j  = i-1;
            for (; j >=0 ; j--) {
                if(arr[j]>key){
                    arr[j+1] = arr[j];
                }else{
                    break;
                }
            }
        arr[j+1] = key;
        }
    }

    /**
     * 打印素组的方法
     */
    public static void printArray(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] +" ");
        }
            }
}

C代码

#include <stdio.h>

void insertSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        // 将大于 key 的元素向右移动一个位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {6, 4, 9, 1, 10, 2, 8};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertSort(arr, n);
    printArray(arr, n);

    return 0;
}

JavaScript代码

function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

function printArray(arr) {
    console.log(arr.join(" "));
}

// 测试
let arr = [6, 4, 9, 1, 10, 2, 8];
insertSort(arr);
printArray(arr);

稳定性

排序稳定性是排序算法的一个重要特性，它涉及相等元素的相对顺序在排序前后是否保持不变。

具体来说：

稳定排序：如果一个排序算法在排序后保持了相等元素在原序列中的相对顺序，那么这个算法是稳定的。换句话说，如果两个具有相等关键字的元素在排序前是以某种顺序排列的，那么在排序后它们仍然以同样的顺序排列，这样的排序算法就被认为是稳定的。
不稳定排序：如果排序算法不能保证相等元素的相对顺序，则称这种排序是不稳定的。在这种情况下，相等的元素可能会因排序过程而交换位置。

稳定性的重要性主要体现在当元素有多个字段进行排序时。在某些情况下，维持数据的初始顺序是重要的。例如，在对一组人按照出生日期排序后，可能需要对结果按姓名排序，如果使用稳定排序算法，那么同一天出生的人将按照他们原始的顺序（即按姓名的顺序）排列。

通过上述测试我们可以知道,当我们在比较key和arr[j] 的时候,如果取了等号 ,那么此时就是不稳定的,如果没有取等号就是稳定的,所以直接插入排序是稳定的吗?

让我们详细解释一下为什么这样会发生：

当使用 arr[j] > key 进行比较时，如果 arr[j] 等于 key，那么循环会停止，key 将被插入到 arr[j] 的后面。因此，原始数组中顺序相邻的、值相等的元素在排序后仍将保持相同的顺序，这保证了排序的稳定性。
然而，如果使用 arr[j] >= key 进行比较，当 arr[j] 等于 key 时，排序过程仍会继续，尝试找到更前面的位置插入 key。这可能导致 key 被插入到其他相等元素的前面，从而改变了这些元素的相对顺序，这破坏了排序的稳定性。

结论 : 一个本身就稳定的排序你可以将其实现为不稳定的,但是一个本身就不稳定的排序你无法将其变成稳定的. 所以 : 直接插入排序是稳定的排序

时间复杂度

直接插入排序的时间复杂度是 O(n^2)

直接插入排序的时间复杂度分析涉及到最好情况、平均情况和最坏情况。

最好情况时间复杂度：当输入数组已经是有序的，每次比较都不需要进行移位操作（因为每个元素已经是在其正确的位置上），直接插入排序只需要进行一次遍历来确认所有元素都已排序。因此，在这种情况下，时间复杂度是 O(n)，其中 n 是数组的长度。
最坏情况时间复杂度：在最坏的情况下，数组完全逆序，即每次插入都需要将元素移动到数组的最前面。这就需要对于每个元素进行从 1 到 i（其中 i 是当前元素的索引）的比较和移动，因此需要的操作数接近于 1+2+3+…+(n−1)，这是一个等差数列求和，总和是 O(n^2)。
平均情况时间复杂度：在平均情况下，元素需要移动的次数大约是数组长度的一半，因此平均情况时间复杂度也是O(n^2)。