什么是排序？
排序：将一组杂乱无章的数据按一定规律顺次排列起来。
学习内容
按排序依据原则
- 插入排序：直接插入排序、折半插入排序、希尔排序
- 交换排序：冒泡排序、快速排序
- 选择排序：简单选择排序、堆排序
- 归并排序：2-路归并排序
- 基数排序
按排序所需工作量
- 简单排序方法：T(n)=O(n*n)
- 基数排序：T(n)=O(d.n)
- 先进的排序方法：T(n)=O(nlogn)
#define MAXSIZE 20 //设记录不超过20个
typedef int KeyType; //设关键字为整型
Typedef struct{ //定义每个记录(数据元素)的结构
KeyType key; //关键字
InfoType otherinfo; //其他数据项
}RedType;
Typedef struct{ //定义顺序表的结构
RedType r [MAXSIZE+1] //存储顺序表的向量
//r[0]一般作哨兵或缓冲区
int length; //顺序表的长度
}SqlList
8.1 插入排序
插入排序的种类
直接插入排序原始的直接插入排序
使用哨兵的直接插入排序
void InsertSort(SqList &L){
int i,j;
for(i=2;i
性能分析
时间复杂度结论
原始数据越接近有序，排序速度越快
最坏情况下（输入数据是逆有序的） Tw(n)=O(n*n)
平均情况下，耗时差不多是最坏情况的一半 Te(n)=O(n*n)
要提高查找速度
- 减少元素的比较次数
- 减少元素的移动次数
折半插入排序
算法分析：
折半插入排序的对象移动次数与直接插入排序相同，依赖于对象初始排列
- 减少了比较次数，但没有减少移动次数
- 平均性能优于直接插入排序
时间复杂度为O(n*n)
空间复杂度O(1)
是一种稳定的排序方法
希尔排序
基本思想：先讲整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行依次直接插入排序。
希尔排序算法特点：
- 缩小增量
- 多变插入排序
希尔排序特点：
- 一次移动，移动位置较大，跳跃式地接近排序后的最终位置
- 最后依次只需要少量移动
- 增量序列必须是递减的，最后一个必须是1
- 增量序列应该是互质的
算法
算法分析
希尔排序算法的稳定性
8.2 交换排序
8.2.1 冒泡排序
总结：n个记录，总共需要n-1趟。第m趟需要比较n-m次
算法：
void bubble_sort(SqList &L){//冒泡排序算法
int m,j,i; RedType x; //交换时临时存储
for(m=1;m<=n-1;m++){//总共需m趟
for(j=1;j<=n-m;j++)
if(L.r[j].key>L.r[j+1].key){//发生逆序
x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x;//交换
}
}
}
优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；
如何提高效率？
一旦某一趟比较时不出现记录交换，说明已经排序好了，就可以结束算法。
改进的冒泡排序算法
void bubble_sort(SqList &L){//改进冒泡排序算法
int m,j,i,flag=1; RedType x; //flag作为是否有交换的标记
for(m=1;m<=n-1 && flag=1;m++){
flag=0;
for(j=1;j<=m;j++)
if(L.r[j].key>L.r[j+1].key){//发生逆序
flag=1;//发生交换，flag为1，若没发生交换，flag为0
x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x;//交换
}
}
}
冒泡排序的算法评价
冒泡排序最好时间复杂度是O(n)
冒泡排序最坏时间复杂度是O(n*n)
冒泡排序平均时间复杂度是O(n*n)
冒泡排序算法中增加一个辅助空间temp，辅助空间为S(n)=O(1)
冒泡排序是稳定的
时间复杂度
8.2.2 快速排序
——改进的交换排序
基本思想：
- 任取一个元素（如：第一个）为中心
- 所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表
- 对各子表重新选择中心元素并以此规则调整
- 直到每个子表的元素只剩一个
- 每一趟的子表的形成是采用从两头向中间交替式逼近法
- 优于每趟中对各子表的 *** 作都相似，可采用递归算法
算法：
void main(){
QSort(L,1,L.length)
}
void QSort(SqList &L,int low, int high){//对顺序表L快速排序
if(low=pivotkey)
--high;
L.r[low] = L.r[high];
while(low
快速排序算法分析
时间复杂度：可以证明，平均计算时间是O(nlog2n)
QSort()(nlog2n)
Partition()(n)
实验结果表明：就平均计算时间而言，快速排序是我们所有讨论中排序方法最好的一个。
空间复杂度：快速排序不是原地排序
由于程序使用了递归，需要栈空间，在平均情况下：需要O(nlogn)的栈空间，最坏情况下：栈空间可达O(n)
稳定性：快速排序是一种不稳定的排序方法
快速排序不适于对原本有序或基本有序的记录序列进行排序。
划分元素的选取是影响时间性能的关键
输入数据次序越乱，所选划分元素的随机性越好，排序速度越快，快速排序不是自然排序方法。
改变划分元素的选取方法，至多只能改变算法平均情况下的时间性能，无法改变最坏情况下的时间性能。即最坏情况下，快速排序的时间复杂度总是O(n*n)
8.3 选择排序
8.3.1 简单选择排序
基本思想：在待排序的数据中选出最大（小）的元素放在其最终的位置
基本 *** 作：
- 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换
- 再先通过n-2次关键字比较，从n-1个记录中找出关键字最小的记录，将它与第二个记录交换
- 重复上面过程，共进行n-1趟排序后，排序结束
void selectsort(sqlist &K){
for(i=1;i L.r[K] //交换
}
}
时间复杂度：
- 记录移动次数
- 最好情况：0
- 最坏情况：3(n-1)
- 比较次数：无论待排序列处于什么状态，选择排序所需进行的比较次数都相同
算法稳定性
简单选择排序是不稳定排序，可以通过修改算法，变成稳定的排序
8.3.2 堆排序
从堆的定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于（大于）它的孩子结点
堆排序
若在输入堆顶的最小值（最大值）后，使得剩余n-1个元素的序列又建成一个堆，则得到n个元素的次小值（次大值）…如此反复，便能得到一个有序序列，这个过程称之为堆排序
实现堆排序需解决两个问题：
- 如何由一个无序序列建成一个堆？
- 如何在输入堆顶元素后，调整剩余元素为一个新的堆？
堆的调整(问题2)
小根堆：
- 输出堆顶元素之后，以堆中最后一个元素替代之
- 然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换。
- 重复上述 *** 作，直至叶子结点，将得到新的堆，称这个从堆顶到叶子的调整过程为 “筛选”
可以看出：
对一个无序序列反复 “筛选” 就可以得到一个堆；
即：从一个无序序列建堆的过程就是反复 “筛选” 的过程
那么：如何由一个无序序列建成一个堆？（问题1）
显然：
单结点的二叉树是堆。
在完全二叉树中所有以叶子结点（序号i> n/2）为根的子树是堆。
这样，我们只需要依次将序号为n/2，n/2-1，… ，1的结点为根的子树均调整为堆即可。
即：对应由n个元素组成的无序序列， “筛选” 只需从第n/2个元素开始
从最后一个非叶子结点开始，以此向前调整：
- 调整从第n/2个元素开始，将以该元素为根的二叉树调整为堆
- 将以序号为n/2-1的结点为根的二叉树调整为堆
- 将以序号为n/2-2的结点为根的二叉树调整为堆
- 将以序号为n/2-3的结点为根的二叉树调整为堆
实质上，堆排序就是利用完全二叉树中父结点与孩子结点直接的内在关系来排序的
堆排序算法：
void heapsort(elem R[]){//对R[1]到R[n]进行堆排序
int i;
for(i= n/2;i>=1;i--)
HeapAdjust(R,i,n);//建初始堆
for(i=n;i>1;i--){//进行n-1趟排序
Swap(R[1],R[i]);//根与最后一个元素交换
HeapAdjust(R,1,i-1);//对R[1]到R[n-1]重新建堆
}
}
算法性能分析：
初始堆化所需时间不超过O(n)
排序阶段：
- 依次重新堆化所需时间不超过O(logn)
- n-1次循环所需时间不超过O(nlogn)
T=O(n)+O(nlogn)=O(nlogn)
堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复筛选上。堆排序在最坏情况下，其时间复杂度也为O(nlog2n)，这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列，都不会使堆排序处于“最好”或“最坏”的状态。
另外，堆排序仅需一个记录大小供交换用的辅助存储空间。
然而堆排序是一种不稳定的排序方法，它不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。
8.4 归并排序
算法：有兴趣自己了解
8.5 基数排序
8.6 各种排序方法比较
总的比较
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）