插入排序的简单介绍

今天给大家简单介绍一下插入排序。

插入排序，其基本思想是将未排序的数据逐步插入到已排序序列中的合适位置，从而使整个序列逐渐有序。

下面我们看一个排序的过程（升序），给定一个int类型的数组，利用插入排序的方法将这个数组排成升序。思想就是将第一个数据（或者已经有序的几个数据如下图的第2，3，4步）看成是有序的数据，然后利用后一个数据和前一个数据进行对比，若后一个数据比前一个大则不需要改变他们在数组的位置位置，若后一个数据比前一个数据大，那就将他们交换位置，一直循环比较下去直到数组排成升序或者降序。

看下图，我们首先写出假设数组已经有序的情况下的单趟插入排序：

给定一个数组元素为6，end为4，此时若插入为0，比较end位置的数据与0比较，0比end位置的数据小那么0放到end位置，end位置的数据8放到end+1（0的位置）然后end--，依次往前比较直到end<0时结束。若插入为9则不需要挪动数据。

下面为单趟排序代码

int temp = arr[end + 1];// 保存end+1位置的数据以免后面被覆盖了导致数据丢失
while (end >= 0)
{if (temp < arr[end]){arr[end + 1] = arr[end];end--;}else// 不满足则跳出循环{break;}
}
// 不管是循环结束还是break跳出都是往end+1处插入这个数据
arr[end + 1] = temp;

那现在给定一个乱序的数组，我们将第一个数据看成是有序数据，然后让它和他后面一个数据进行比较，那么写一个循环来重复此比较

// 插入排序
void InsertSort(int* arr, int n)
{for (int i = 0;i < n - 1;i++) // 注意结束条件{int end = i;// i=0为第一个数据int temp = arr[end + 1];// 保存end+1位置的数据以免后面被覆盖了导致数据丢失while (end >= 0){if (temp < arr[end]){arr[end + 1] = arr[end];end--;}else{break;}}// 不管是循环结束还是break跳出都是往end+1处插入这个数据arr[end + 1] = temp;}
}

测试排序代码

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>// 插入排序
void InsertSort(int* arr, int n)
{for (int i = 0;i < n - 1;i++) // 注意结束条件{int end = i;// i=0为第一个数据int temp = arr[end + 1];// 保存end+1位置的数据以免后面被覆盖了导致数据丢失while (end >= 0){if (temp < arr[end]){arr[end + 1] = arr[end];end--;}else{break;}}// 不管是循环结束还是break跳出都是往end+1处插入这个数据arr[end + 1] = temp;}
}void Printarry(int* arr, int n)
{for (int i = 0;i < n;i++){printf("%d ", arr[i]);}printf("\n");
}void TestInsertSort() 
{int arr[] = { 3,1,4,2,8,4,9,6,0,7 };Printarry(arr, sizeof(arr) / sizeof(arr[0]));InsertSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}int main()
{TestInsertSort();return 0;
}

结论：插入排序是一种简单排序算法，其核心思想是将未排序元素逐个插入到已排序序列的正确位置。算法实现时，首先将第一个元素视为有序序列，然后依次将后续元素（temp）与已排序元素从后往前比较，若temp较小则后移已排序元素，直至找到合适位置插入。文中给出了单趟排序的实现代码和完整插入排序函数，并通过测试用例验证了算法的正确性，成功将无序数组{3,1,4,2,8,4,9,6,0,7}排序为升序序列。

PS：后面补充堆排序和二叉树