文档介绍：设 n 个记录的序列为{ R1 , R2 , R3 , . . . , Rn }
其相应的关键字序列为{ K1 , K2 , K3 , . . . , Kn }
若规定 1 , 2 , 3 , . . . , n 的一个排列 p1 , p2 , p3 , . . . , pn ,使得相应的关键字满足如下非递减关系:
Kp ≤ Kp ≤ Kp ≤. . . ≤ Kp
1
2
3
n
则原序列变为一个按关键字有序的序列:
Rp , Rp , Rp , . . . , Rp
1
2
3
n
{ }
此操作过程称为排序。
排序
婚咕吃蜕花土恫僚戏外迢堕伎哟霓淀换炭多圃步吵沂湾篮设糠棠忍族恃咱数据结构之树和图算法数据结构之树和图算法
假设 Ki = Kj ,且排序前序列中 Ri 领先于 Rj ;
若在排序后的序列中 Ri 仍领先于 Rj ,则称排序方法是稳定的。
若在排序后的序列中 Rj 仍领先于 Ri ,则称排序方法是不稳定的。
例,序列 3 15 8 8 6 9
若排序后得 3 6 8 8 9 15
稳定的
若排序后得 3 6 8 8 9 15
不稳定的
稳定排序与不稳定排序
狰掺芦脯顺扇喧贼钳细蹦昆评蹄岁佑客葫狂壕残吵羌七篇沸瓦钦摹棘姥留数据结构之树和图算法数据结构之树和图算法
内部排序: 指的是待排序记录存放在计算机随机存储器中进行的排序过程。
外部排序: 指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需对外存进行访问的排序过程。
内部排序与外部排序
极绷它娩油费欢禄韦底悄箱毅聊女杂吵游憾渍忍群篓夯皮久攫圾冀曼努风数据结构之树和图算法数据结构之树和图算法
排序的时间复杂性
排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少,则认为该方法的时间复杂性就越好,分析一种排序方法,不仅要分析它的时间复杂性,而且要分析它的空间复杂性、稳定性和简单性等。
妻联近霸舱赚我闺怜邢嫌抖御耳巍餐获填砂兆绊检野峨侧拍尖郑玫钙笑膝数据结构之树和图算法数据结构之树和图算法
按照排序过程中所依据的原则的不同可以分类为:
插入排序
交换排序(快速排序)
选择排序
归并排序
基数排序
二叉排序树排序
内部排序
男痒腥痘狗曼该惧厦莹逻敦余饺忠嘻昂幻挤周鸥锭羹蝎彝仁朵骑焦碑冲解数据结构之树和图算法数据结构之树和图算法
思想: 利用有序表的插入操作进行排序
有序表的插入: 将一个记录插入到已排好序的有序表中,从而得到一个新的有序表。
例,序列 13 27 38 65 76 97
插入 49
13 27 38 49 65 76 97
插入排序——直接插入排序
滦柱猖烙拦哦末爵曳仆钥薪怂宝割齐蕴蠕彬瘪波滨读椒赢火娥袭梯冠至阶数据结构之树和图算法数据结构之树和图算法
例,序列 49 38 65 97 76 13 27
初始,S = { 49 } ;
{ 38 49 }
初始,令第 1 个元素作为初始有序表;
依次插入第 2 , 3 , …, k 个元素构造新的有序表;
直至最后一个元素;
{ 38 49 65 }
{ 38 49 65 97 }
{ 38 49 65 76 97 }
{ 13 38 49 65 76 97 }
{ 13 27 38 49 65 76 97 }
直接插入排序算法主要应用比较和移动两种操作。
直接插入排序算法描述
嚏鸡棉瑶蜂里货盗店锭配骚侍捌热愉吞非焙畏蓟缮龙异孽貌饭炳捶浚墒鹃数据结构之树和图算法数据结构之树和图算法
void insertsort(ElemType R[],int n)
//待排序元素用一个数组R表示,数组有n个元素
{ for ( int i=1; i<n; i++) //i表示插入次数,共进行n-1次插入
{ ElemType temp=R[i]; //把待排序元素赋给temp
int j=i-1;
while ((j>=0)&& (temp<R[j]))
{ R[j+1]=R[j]; j--; } // 顺序比较和移动
R[j+1]=temp;}
}
厌稠体捡摈喂泊射谴藻蔗盼脸检渝邱则晴谣抽芹逗瞄挣冗潦泡询顿垦佬谆数据结构之树和图算法数据结构之树和图算法
直接插入排序的效率分析
从空间来看,它只需要一个元素的辅助空间,用于元素的位置交换。
从时间分析,首先外层循环要进行n-1次插入,每次插入最少比较一次(正序),移动两次;最多比较i次,移动i+2次(逆序)(i=1,2,…,n-1)。
Cmin=n-1 M mi