当前位置：首页 > news >正文

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

news 来源：原创 2024/7/7 23:21:02

文章目录

- - 💗 直接插入排序
  - 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)。