首页 > 代码库 > 直接插入排序(Straight Insertion Sort)
直接插入排序(Straight Insertion Sort)
直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。
/* 对顺序表L作直接插入排序 */
void InsertSort(SqList *L);
直接插入排序代码:
// test.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; #define MAXSIZE 10000 /* 用于要排序数组个数最大值,可根据需要修改 */ typedef struct { int r[MAXSIZE+1]; /* 用于存储要排序数组,r[0]用作哨兵或临时变量 */ int length; /* 用于记录顺序表的长度 */ }SqList; void print(SqList L) { int i; for(i=1;i<L.length;i++) printf("%d,",L.r[i]); printf("%d",L.r[i]); printf("\n"); } /* 交换L中数组r的下标为i和j的值 */ void swap(SqList *L,int i,int j) { int temp=L->r[i]; L->r[i]=L->r[j]; L->r[j]=temp; } /* 对顺序表L作直接插入排序 */ void InsertSort(SqList *L) { int i,j; for(i=2;i<=L->length;i++) { if (L->r[i]<L->r[i-1]) /* 需将L->r[i]插入有序子表 */ { L->r[0]=L->r[i]; /* 设置哨兵 */ for(j=i-1;L->r[j]>L->r[0];j--) L->r[j+1]=L->r[j]; /* 记录后移 */ L->r[j+1]=L->r[0]; /* 插入到正确位置 */ } } } #define N 9 int _tmain(int argc, _TCHAR* argv[]) { int d[N]={9,1,5,8,3,7,4,6,2}; SqList L0; int i; for(i=0;i<N;i++) L0.r[i+1]=d[i]; L0.length=N; printf("排序前:\n"); print(L0); InsertSort(&L0); printf("排序后:\n"); print(L0); getchar(); return 0; }
首先默认第一个元素L->r[1]元素组成的序列已经有序,然后依次往这个有序表中插入数据,直到最终完成排序。
循环控制:i=2->Length;
若当前元素L->r[i]小于有序表中最后一个元素L->r[i-1],则进进行插入排序。否则,当前元素位置不变,有序表加1;
进入直接插入排序后:
step1:设置哨兵,令L->r[0]=L->r[i];
step2:将第一个不小于哨兵的元素至第i-1个元素依次后移一个位置(循环j=1-1,j--);
step3:在空出的位置上插入哨兵元素,L->r[j+1]=L->r[0]; /* 插入到正确位置 */
直接插入排序(Straight Insertion Sort)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。