112.【C语言】数据结构之排序(详解插入排序)

目录

1.排序定义

2.插入排序

"插入"的含义

代码

函数框架

函数设计思路

以升序为例,分析插入的三种可能

单趟排序代码

优化后

将单趟排序代码嵌入到循环中

错误代码

两种改法

运行结果

 时间复杂度

---

1.排序定义

使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作

2.插入排序

"插入"的含义

例如对于一个升序数列:3,4,5,11;现在要求插入7使得数列还能满足升序

显然改动后的数列应该是3,4,5,7,11

算法:设要插入的数字为k,从数列的最后一个元素开始,依次向前比较,直到满足

时,向原数列插入k

代码

小提示:写排序代码时,先写单趟排序,之后将其嵌入循环内,能较容易写出

函数框架

void InsertSort(int* a, int n)
{}

函数设计思路

设tmp为要插入的数字,end为有序数组的最后一个元素的下标,n为无序数组元素的个数,a为数组指针,将tmp插入到[0,end]的区间中,构成有序数列

以升序为例,分析插入的三种可能

①tmp大于所有已经排序的数

②tmp大小介于已经排序的数之间

③tmp小于所有已经排序的数

①tmp大于所有已经排序的数

例如有序数列int arr[]={1,3,5,8,10,21,37,40},此时arr[end]==40;现插入tmp==50,

第一次循环:tmp>arr[end],直接arr[end+1]=tmp,循环结束

②tmp大小介于已经排序的数之间

例如有序数列int arr[]={1,3,5,8,10,21,37,40},此时arr[end]==40;现插入tmp==22

第一次循环:arr[end]==40,tmp<a[end],于是arr[end+1]=arr[end],end--,准备下一次循环

第二次循环:arr[end]==37,tmp<arr[end],于是arr[end+1]=arr[end],end--,准备下一次循环

第三次循环:arr[end]==21,tmp>arr[end],满足条件,arr[end+1]=tmp,循环结束

③tmp小于所有已经排序的数

例如有序数列int arr[]={1,3,5,8,10,21,37,40},此时arr[end]==40;现插入tmp==0

省略前几次循环,第?循环,arr[end]==1,tmp<arr[end],于是arr[end+1]=arr[end],end--,准备下一次循环

如果进行了下次循环,end==-1,会造成越界访问,此时应该立即退出循环!执行arr[end+1]=tmp

显然退出循环有两种情况:1.end<0,即end==-1时 2.tmp>arr[end]

因此将所有可能的情况讨论全,循环退出的条件才能写全

单趟排序代码

	int end;int tmp;while (end >= 0){if (tmp > arr[end]){arr[end + 1] = arr[end];end--;}else{arr[end + 1] = tmp;break;}}if (end == -1){arr[end + 1] = tmp;}

 上面这样写略显麻烦,无论满足什么条件退出循环,最后都执行arr[end + 1] = tmp;

优化后

	while (end >= 0){if (tmp > arr[end]){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;

将单趟排序代码嵌入到循环中

main.c写入

int main()
{int arr[] = { 1,6,2,4,7,3,9,0,-1,5 };printf("排序前:");PrintSort(arr, sizeof(arr) / sizeof(arr[0]));InsertSort(arr,sizeof(arr)/sizeof(arr[0]));printf("排序后:");PrintSort(arr, sizeof(arr) / sizeof(arr[0]));return 0;

错误代码

void InsertSort(int* arr, int n)
{for (int i = 0; i < n; i++){int end = i;int tmp = arr[i + 1];while (end >= 0){if (tmp < arr[end]){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}

问题出在越界访问,当i==n-1时,执行int tmp = arr[i + 1];就越界了(arr的最后一个元素是arr[n-1])!!

两种改法

改法1:改for的循环条件

for (int i = 0; i < n-1; i++)

改法2:改tmp和end赋的初始值

	for (int i = 0; i < n; i++){int end = i-1;int tmp = arr[i];//省略......}

备注:循环的一开始,无序数组的首元素可构成一个有序数组,后面的数依次插入有序数组

运行结果

 时间复杂度

最坏情况,每次内循环结束条件都为end==-1,时间复杂度

最好情况:提供的数组恰好是有序的,时间复杂度

结论:从时间复杂度来看,数组越接近有序,插入排序的时间复杂度越低,而希尔排序就是基于这个结论设计的,有关希尔排序的内容参见下篇文章