文档介绍：数据结构课件
内部排序
第一讲
2004年12月
第十章内部排序
插入排序:直插入排序,希尔排序
交换排序:冒泡排序,霍尔快速排序
选择排序:简单选择排序,堆排序
归并排序
基数排序
§10-1排序的基本概念
一、排序:将若干数据元素构成的一个任意序列,重新排成按关键字有序序列的过程。
二、关于排序的稳定性: 若排序之前Ki=Kj ,并且Ri领先Rj (i<j),排序后仍Ri领先于Rj,则排序是稳定的, 否则排序是不稳定的。
三、排序方法分类:
1 内排序:在内存进行;
2 外排序:在内存进行,同时访问外存;
§10-1排序的基本概念
四、存储结构:顺序存储结构,常称为表。
#define MAXSIZE 30; /*表中记录的个数*/
Typedef struct
{ int key; /* 或其他类型*/
... /* 其他次关键字域*/
}ElemType;
typedef ElemType listtp[MAXSIZE];
§10-2 插入排序
一、直接插入排序:
思路:通过不断的将某记录插入到
一个已经有序的表中来实现。
有一组关键字{49,38,76,27,49};
i=2 (49) 38, 76, 27, 49
┏━┛
i=3 (38, 49),76, 27, 49
i=4 (38, 49, 76),27, 49
┏━━━━━┛
i=5 (27, 38, 49, 76),49
┏━┛
end. (27, 38, 49, 49, 76)
-直接插入排序算法
void straisort(listtp r);
{ for(i=2; i<=n; i++)
{ r[0]=r[i]; /* 设置监视哨*/
j=i-1; k=r[i].key;
while( r[j].key>k)/* 大值的记录后移*/
{ r[j+1]=r[j]; j--; }
r[j+1]=r[0]; /*插入位置*/
}
} /* straisort */
-直接插入排序算法
算法分析:
排序是稳定的;
原来: (49,38,76,27,49)
排序后: (27, 38, 49, 49, 76)
排时间复杂度为:T(n)=O(n2)
§10-3 交换排序
一、起泡排序(由小到大)
思路:
第1趟aj与aj+1比,较大数=>aj+1 (j=1,...n-1)
第2趟aj与aj+1比,较大数=>aj+1 (j=1,...n-2)
第n-1趟a1与a2比,较大数=>a2 (j=1,n-(n-1))
一、起泡排序(由小到大)
算法描述:(1)
void buble_sort(listtp r)
{ for (i=1; i<=n-1; i++) /* 共计n-1趟*/
for (j=1; j<=n-i ; j++)
if (r[j].key>r[j+1].key)
{ x=r[j]; r[j]=r[j+1] r[j+1]=x;}
} /* bubble_sort */