龙空技术网

学习笔记-详解直接插入排序

不穿格子衫的程序猿 348

前言:

眼前你们对“c语言直接插入排序”大约比较看重,我们都需要知道一些“c语言直接插入排序”的相关知识。那么小编在网上搜集了一些关于“c语言直接插入排序””的相关资讯,希望姐妹们能喜欢,同学们一起来了解一下吧!

本文目的

上一章节已经详细的向大家介绍过排序的相关概念学习笔记-排序简单介绍,本文旨在为大家详细的介绍直接插入排序。

直接插入排序

直接插入排序(Straight Insertion Sort)是一种简单的排序方法,是一种插入类排序。其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的、记录数量增1的有序表。

算法原理

将一个记录插入到已排好序的序列中,从而得到一个新的有序序列(将序列的第一个数据看成是一个有序的子序列,然后从第二个记录逐个向该有序的子序列进行有序的插入,直至整个序列有序)

算法流程

当插入第i(i >= 1)时,前面的V[0],V[1],……,V[i-1]已经排好序。这时,用V[I]的排序码与V[i-1],V[i-2],…的排序码顺序进行比较,找到插入位置即将V[i]插入,原来位置上的元素向后顺移。

算法实现

算法思路(从小到大排序):

1、一组数据a[N],设置变量i , j , temp,i 是待插入元素的下标,将a[i]赋值给temp,j是用来搜索比较

2、i 的初始值为1,即从第二个元素开始,一个元素认为是已经排好序的,所以从第二个元素开始,j的初始值为i-1

3、将i前面的数据都与temp比较,即与待插入数据进行比较,用 j 来移动下标,直到找到一个比temp小的或等于的值,亦或者找到了该序列的尽头(即下标为0)停止,将temp放到j+1的位置,即将待插入的数据插入到j+1的位置,该待插入数据就已经插入到了正确的位置

4、然后将i=2,从第三个元素开始,j=i-1,执行temp=a[i],重复步骤3,直到 i==N-1停止,即所有数据都已经放到了正确的位置上,该序列称为有序序列

#include <stdio.h> #define elemType int /*元素类型*/int k=1;//轮次记录 void Print (elemType arr[], int len){		int i;		for (i=0; i<len; i++){		printf ("%d\t", arr[i]);	}            printf("\n");}void Sort(elemType a[], int len){	int i,j;    for(i=1;i<len;i++)      //循环从第2个元素开始    {        if(a[i]<a[i-1])        {            int temp=a[i];            for(j=i-1;j>=0 && a[j]>temp;j--)            {                a[j+1]=a[j];            }            a[j+1]=temp;          //此处就是a[j+1]=temp;        }            printf("第===%d===轮排序后结果如下:\n",k);		Print (a, 9);		k=k+1;    }} int main() {		int i;    elemType arr[9] = {94,19,29,9,11,1,14,13,29};    printf("待排序的序列为:\n");    Print(arr, 9);      printf("\n\n");        Sort (arr,9);    printf("\n\n");    printf("排好序的结果如下:\n");    Print(arr, 9);   }
算法分析

时间复杂度

最好情况:当初始序列为正序时,只需要外循环n-1次,每次进行一次比较,无需移动元素。此时比较次数Cmin=n-1和移动次数Mmin=0达到最小值。此时时间复杂度为O(n)。

最差情况:当初始序列为反序时,需要外循环n-1次,每次排序中待插入的元素都要和[0,i-1]中的i个元素进行比较且要将这i个元素后移i次,加上tmp=arr[i]与arr[j]=temp的两次移动,每趟移动次数为i+2,此时比较次数和移动次数达到最大值。此时时间复杂度O(n²)

平均时间复杂度O(n²)

空间复杂度

在直接插入排序中只使用了i,j,tmp这三个辅助元素,与问题规模无关,空间复杂度为O(1)。

排序稳定性

相同元素的相对位置不变,如果两个元素相同,插入元素放在相同元素后面。是一种稳定排序

本文的初衷为学习笔记的分享,部分图文来源于网络,如侵,联删。

标签: #c语言直接插入排序