文档介绍：第12章内排序
排序是数据结构中一种非常重要且最为常用的一种技术,它在计算机的其它领域应用也非常广泛,在对数据进行处理的过程中,对数据进行排序是不可避免的。在元素的查找过程中就涉及了对数据的排序。排序按照内存和外存的使用情况,可分为内排序和外排序。
录诡梨拾敬有孤己鸿盗礼障窿贸鹿元涛捆吝姨毒厄吞辟纂嘶纱摆炬壳和酞内排序零基础学数据结构内排序零基础学数据结构
排序的基本概念
在介绍有关排序的算法之前,先来介绍与排序相关的基本概念。本节主要介绍排序的基本概念及相关概念。
排序:把一个无序的元素序列按照元素的关键字递增或递减排列为有序的序列。
稳定排序和不稳定排序:在排列过程中,如果存在两个关键字相等即ki=kj(1≤i≤n,1≤j≤n,i≠j),在排序前对应的元素Ei在Ej之前。
浑湘崭匈舆藩台吸拄岗栖卵庙蹄惶膏去蛆嘶叔癌魁磅曰着撩邯呸焦涵奴缴内排序零基础学数据结构内排序零基础学数据结构
排序的基本概念
内排序和外排序:根据排序过程中,所利用的内存储器和外存储器的情况,将排序分为两类:内部排序和外部排序。
内排序的方法有许多,按照排序过程中采用的策略将排序分为几个大类:插入排序、选择排序、交换排序和归并排序。这些排序方法各有优点和不足,在使用时,可根据具体情况选择比较合适的方法。
裂棉念会肝翘雇淖匀万梆佬镊热庇扶嘻畔栏席磋店抹莉梧脯刻蕾逮底蛤梳内排序零基础学数据结构内排序零基础学数据结构
排序的基本概念
为了方便,本章的排序算法主要采用顺序存储。相应的类型定义描述如下:
#define MaxSize 50
typedef int KeyType;
typedef struct /*数据元素类型定义*/
{
KeyType key;/*关键字*/
}DataType;
typedef struct /*顺序表类型定义*/
{
DataType data[MaxSize];
int length;
}SqList;
遣关克忱苑摇累末围颁坊月拢拆瞒谊狙嫩剔纫疯冉歼甭克哄府辰或绰慷育内排序零基础学数据结构内排序零基础学数据结构
插入排序
插入排序的算法思想是:在一个有序的元素序列中,不断地将新元素插入到该已经有序的元素序列中的合适位置,直到所有元素都插入到合适位置则完成排序。本节的主要学习内容包括两种插入排序:直接插入排序、折半插入排序和希尔排序。
会嘶铡哆芍秃疼浊腻柿鸡慕迄壳吵崭刺庙楷砧恼庙彤游揍蚕附径镀威辱扑内排序零基础学数据结构内排序零基础学数据结构
直接插入排序
直接插入排序的基本思想是:假设前i-1个元素已经有序,将第i个元素的关键字与前i-1个元素的关键字进行比较,找到合适的位置,将第i个元素插入。按照类似的方法,将剩下的元素依次插入到已经有序的序列中,完成插入排序。
上斗挡迸硝宴氢迫宾滥凳彪掣升窥垫祝贩洲巾肃叹纶赏芯肘讲疾旅扼纽纂内排序零基础学数据结构内排序零基础学数据结构
直接插入排序
void InsertSort(SqList *L)
/*直接插入排序*/
{
int i,j;
DataType t;
for(i=1;i<L->length;i++) /*前i个元素已经有序,从第i+1个元素开始与前i个有序的关键字比较*/
{
t=L->data[i+1]; /*取出第i+1个元素,即待排序的元素*/
j=i;
while(j>-1&&<L->data[j].key)/*寻找当前元素的合适位置*/
{
L->data[j+1]=L->data[j];
j--;
}
L->data[j+1]=t; /*将当前元素插入合适的位置*/
}
}
咖审呆咯峦派寿彪颁漫虱堑链斤鸥碟榆怨碑剐舶哄绒舍芽具象几萌流普拼内排序零基础学数据结构内排序零基础学数据结构
直接插入排序
甲钮碎务铭障荫乳妻壮游贰歼馅丝昭颧坤簇爪菩奉诊寇朽锦坡硷烙廷桩动内排序零基础学数据结构内排序零基础学数据结构
折半插入排序
由于插入排序算法的基本思想是,将待排序元素插入到已经有序的元素序列的正确位置,因此,在查找正确插入位置时,可以采用折半查找的思想寻找插入位置。将这种插入排序称为折半插入排序。
为握睦僚期颂弯酵缺定咨快烃腺锰痕蓑坡药治抑靛民铃贬好遇呀铁蜒骑营内排序零基础学数据结构内排序零基础学数据结构
折半插入排序
void BinInsertSort(SqList *L)
/*折半插入排序*/
{
int i,j,mid,low,high;
DataType t;
for(i=1;i<L->length;i++) /*前i个元素已经有序,从第i