前言:
眼前你们对“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语言直接插入排序