文档介绍：算法与数据结构
阙夏制作
§7 排序
§ 概述
排序:将数据表(R1,R2,…,Rn)调整为新表(R1’,R2’,…,Rn’),使得R1’≤R2’≤…≤Rn’或R1’≥R2’≥…≥Rn’。
从序列大小看:
增排序:从小到大;
减排序:从大到小;
§ 概述
从元素移动上看:
稳定排序: 排序过程中相对位置不变;
不稳定排序:排序过程中相对位置有改变;
从数据存储看:
内部排序:所有数据在内存中;
外部排序:一部分在内存,一部分在外存;
§ 概述
按基本思想分类:
(1)插入排序
(2)交换排序
(3)选择排序
(4)归并排序
(5)基数排序
评价:
时间:比较、移动、交换次数;
空间:辅助空间;
§ 插入排序
一、直接插入排序:
1、基本思想:
将数据表看做左右两部分,左边是有序区,右边是无序区,整个排序的过程就是将右边的元素逐个插入左边,从而构成有序区。
2、实例
用直接插入排序算法对数据表A=(12,5,4,9,5)从小到大进行排序。
(12 5 4 9 5)
解:
5
( 4 9 5)
12
12
5
( 9 5)
12
5
4
12
5
4
( 4 5 5)
9
( 4 5 )
12
5
9
12
12
9
12
9
5
3、算法实现:
viod insert_sort(elementtype A[n+1])
{ for(i=2,i<=n,i++)
{
A[0]=A[i]; j=i-1;
while(A[j]>A[0])
{A[j+1]=A[j];j--;}
A[j+1]=A[0];
}
}
A[0]=A[i];
j=i-1;
A[j]>A[0]
Y
A[j+1]=A[j];
j--;
N
A[j+1]=A[0]
4、讨论:
稳定性:稳定;
空间性能:1个辅助空间。
时间性能:与数据表初始状态有关:
最好(有序) 最坏(逆序)
比较: n-1 (n+2)(n-1)/2
移动: 2(n-1) (n+4)(n-1)/2
平均O(n2)
适用于基本有序,规模小的数据;