单链表实现直接插入排序算法
一、算法原理
插入排序属于稳定排序法,是一种常用的排序算法。直接插入排序算法可以利用静态数组来实现,也可以使用静态链表或者单链表来实现。本文给出了直接插入算法的单链表实现方法。
其基本原理就是把一个数据插入到一组已经排好序的数列中,得到仍是有序的数列。
例如:已经有如下排好序的数组:
如果将数据6插入到该数组中得到新数组,即将6插入到数组下标为4的位置。
下面例子演示了使用单链表来实现直接插入排序算法的过程。
Demo:
假设一组散乱数据:{ 4,3,5 }
使用单链表实现直接插入排序的过程如下:
Step1 :创建单链表表头,并把元素4存入单链表
Step2 : 将元素3插入单链表,这时只需要将3插入到节点4之前,修改指针的指向即可,不需要移位操作。
Step3 : 将元素5插入单链表,这时只需要将5插入到节点4之后。
二、基于单链表的直接插入排序的C程序
1. 基于单链表的直接插入排序函数
//基于单链表的直接插入排序算法
void InsertSortSingleLink( int arr[], int length )
{
LinkList *h, *p, *q, *s;
int i;
//h表示单链表的表头节点
h = ( LinkList * )malloc( sizeof(LinkList) );
//s是存储每一个新加入元素的节点
s = ( LinkList * )malloc( sizeof(LinkList) );
s->data = arr[0];
s->next = NULL;
h->next = s;
//从数组的第二个元素开始执行插入排序,p为前驱,q为后继
//每次新加入的元素与q中元素进行比较。
for( i = 1; i < length; i )
{
p = h;
q = p->next;
s = ( LinkList * )malloc( sizeof(LinkList) );
s->data = arr[i];
//找到插入位置,如果新来的元素比q中的大,则向后查找,
//直到q的指针域为空。
while( s->data > q->data && q->next != NULL)
{
p = q;
q = q->next;
}
//新来的元素大,则插入到q之后
if( q->next == NULL && s->data > q->data )
{
s->next = NULL;
q->next = s;
}
else//新来的元素小,则插入到p之后,即q之前
{
p->next = s;
s->next = q;
}
}
//把单链表中的元素存到数组arr中,
p = h->next;
for( i = 0; i < length; i )
{
arr[i] = p->data;
p = p->next;
}
//释放单链表
p = h;
q = p->next;
while( p->next != NULL )
{
free(p);
p = q;
q = q->next;
}
free(q);
}
2.测试代码(仅供参考)
#include"stdio.h"
#include"malloc.h"
typedef struct node
{
int data;
struct node *next;
}LinkList;
void InsertSortSingleLink( int arr[], int length );
int main()
{
int arr[] = { 4, 3, 5, 6, 1, 2 };
int length = 6;
int i;
printf( " initial array: " ) ;
for( i = 0; i < length; i )
{
printf( "]", arr[i] );
}
printf( "\n" );
InsertSortSingleLink( arr, length );
printf( " sort result : " ) ;
for( i = 0; i < length; i )
{
printf( "]", arr[i] );
}
printf( "\n" );
return 0;
}
//基于单链表的直接插入排序算法
void InsertSortSingleLink( int arr[], int length )
{
LinkList *h, *p, *q, *s;
int i;
//h表示单链表的表头节点
h = ( LinkList * )malloc( sizeof(LinkList) );
//s是存储每一个新加入元素的节点
s = ( LinkList * )malloc( sizeof(LinkList) );
s->data = arr[0];
s->next = NULL;
h->next = s;
for( i = 1; i < length; i )
{
p = h;
q = p->next;
s = ( LinkList * )malloc( sizeof(LinkList) );
s->data = arr[i];
while( s->data > q->data && q->next != NULL)
{
p = q;
q = q->next;
}
if( q->next == NULL && s->data > q->data )
{
s->next = NULL;
q->next = s;
}
else
{
p->next = s;
s->next = q;
}
}
p = h->next;
for( i = 0; i < length; i )
{
arr[i] = p->data;
p = p->next;
}
//释放单链表
p = h;
q = p->next;
while( p->next != NULL )
{
free(p);
p = q;
q = q->next;
}
free(q);
}
3.运行结果
测试一:
测试二(有相同数据):
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfijcjg
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13