《基础算法数据排序》由会员分享，可在线阅读，更多相关《基础算法数据排序（49页珍藏版）》请在金锄头文库上搜索。
1、基础算法基础算法 数据排序数据排序 PPT模板下载： 行业PPT模板： 节日PPT模板： PPT素材下载： PPT背景图片： PPT图表下载： 优秀PPT下载： PPT教程： Word教程： Excel教程： 资料下载： PPT课件下载： 范文下载： 试卷下载： 教案下载： PPT论坛： 0101 基本概念基本概念 0202 简单选择排序简单选择排序 0404 桶排序桶排序 0505 插入排序插入排序 0606 快速排序快速排序PPT模板下载： 行业PPT模板： 节日PPT模板： PPT素材下载： PPT背景图片： PPT图表下载： 优秀PPT下载： PPT教程： Word教程： Excel教
2、程： 资料下载： PPT课件下载： 范文下载： 试卷下载： 教案下载： PPT论坛： 0707 归并排序归并排序 PPT模板下载： 行业PPT模板： 节日PPT模板： PPT素材下载： PPT背景图片： PPT图表下载： 优秀PPT下载： PPT教程： Word教程： Excel教程： 资料下载： PPT课件下载： 范文下载： 试卷下载： 教案下载： PPT论坛： 0303 冒泡排序冒泡排序 1.排序排序 排序(Sorting) ： 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素 （或记录）的任意序列，重新排列成一个关键字有序的序列。 两个基本操作： 比较两个关键字大小 将记录从一
3、个位置移动到另一个位置 排序的稳定性： 待排序列a1,a2, an，其相应的关键字序列k1,k2, kn，假设ki= kj( 1i, jn且i j)，且在排序前的序列中ai领 先于aj。 若在排序后的序列中ai仍领先于aj，则称所用的排序方法是稳 定的，反之，则称其是不稳定的。 假设排序过程中，待排记录序列的状态为： 有序序列有序序列L.r 1i-1无序序列无序序列 L.r in 第 i 趟 简单选择排序 从中选出 关键字最小的记录 有序序列L.r1i无序序列 L.ri+1n 2. 简单选择排序简单选择排序基本思想和过程基本思想和过程 2.直接选择排序直接选择排序 又称为简单选择排序，是一种简
4、单直观的排序方法。 排序过程 第一趟扫描所有待排序元素，找出关键字最小的元素并将它与第 一个元素进行交换； 第i趟，扫描待排序列中剩余n - i + 1个元素，找出关键字最小的元 素与序列中第i个位置上的元素交换 重复上述操作,直到所有的元素都放到正确的位置上为止 简单选择排序例 34 28 81 22 79 22 28 81 34 79 22 28 34 81 79 22 28 34 81 79 初始 22 28 81 34 79 第一趟第二趟第三趟第四趟 void selectsort(int r ) /对r1n进行直接选择排序 for (int i=1;in; for( i=1;ik;
5、bk+; /将关键字等于k的值全部装入第k桶 for( i=0; i0) coutai; sort(a+0,a+10); for (int i=0;ib 则返回1 ，否则返回 0 int main() for (int i=0;iai; sort(a+0,a+10,my_comp); for (int i=0;in; for (int i=0;iai.name; cinai.score; sort(a+0,a+n,score_comp); for (int i=0;in; for(i=1;iai;/读入读入n个待排序数据个待排序数据 mergesort(1,n); /对对1,n区间的无序数据进
6、行归并排序区间的无序数据进行归并排序 for (i = 1;i=n;i+)/输出输出n个有序的数据个有序的数据 coutai“ “ ; coutendl; 8.8.各种排序算法的比较各种排序算法的比较 1.稳定性比较 插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排 序是稳定的。 选择排序、希尔排序、快速排序、堆排序是不稳定的。 2.时间复杂性比较 插入排序、冒泡排序、选择排序的时间复杂性为O(n2)；快速排序、 堆排序、归并排序的时间复杂性为O(nlog2n)；桶排序的时间复杂性为 O(n); 若从最好情况考虑，则直接插入排序和冒泡排序的时间复杂度最 好，为O(n)，其它算法的最好情
7、况同平均情况相同；若从最坏情况考虑， 则快速排序的时间复杂度为O(n2)，直接插入排序和冒泡排序虽然平均情 况相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情况对直 接选择排序、堆排序和归并排序影响不大。 由此可知，在最好情况下，直接插入排序和冒泡排序最快；在平 均情况下，快速排序最快；在最坏情况下，堆排序和归并排序最快。 3.辅助空间的比较 桶排序、二路归并排序的辅助空间为O(n)，快速排序的辅助空间为 O(log2n)，最坏情况为O(n)，其它排序的辅助空间为O(1); 4.其它比较 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这 种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。 当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用 插入或冒泡排序。 若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排 序。 当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。 当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜 用堆排序 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的 关键字是随机分布时，快速排序的平均时间最短； 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情 况。这两种排序都是不稳定的。
