选择排序,归并排序

《选择排序,归并排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、冒泡排序，选择排序冒泡排序依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数……第一趟n-1次排序后，最大的排到了最后。再第二趟n-2次，第二大的排倒数第二……类推至全部排好。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序起泡排序（BubbleSort）：初始①②③④⑤⑥493838383813133849494913272765656513273838977613274949761327494913274

2、9652749764997选择排序选择排序（SelectionSort）的基本思想：每一趟在n－i＋1（i＝1，2，……，n－1）个记录中选取关键字最小的记录作为有序序列中第i个记录。初始①②③④⑤⑥⑦49131313131313133838272727272727656565383838383897979797494949497676767676494949134949499797656527273865656597764949494949767697例如：算法性能分析：1.比较次数：n（n－1）/2即时间复杂度T（n）＝

3、O（n2）2.空间复杂度：O（1）3.稳定性：冒泡排序：稳定选择排序：不稳定归并排序归并排序（MergingSort）：将两个或两个以上的有序表合并成一个新的有序表。113242621527381132426215273811132426215273812113242621527381213T(1)=1;T(N)=2T(N/2)+N两边处于NT(N)/N=T(N/2)/(N/2)+1T(N/2)/N=T(N/4)/(N/4)+1……T(2)/2=T(1)/(1)+1两边相加叠缩：T(N)/N=T(1)/(1)+logN所以T

4、(N)=NlogN+N=O(NlogN)算法性能分析：需要和待排序记录等数量的辅助存储空间。时间复杂度为O（nlog2n）。归并排序是稳定的排序。小结各种内部排序方法的比较讨论：排序方法平均时间最坏情况辅助存储简单排序O（n2）O（n2）O（1）快速排序O（nlogn）O（n2）O（logn）堆排序O（nlogn）O（nlogn）O（1）归并排序O（nlogn）O（nlogn）O（n）基数排序O(d(n＋rd))O(d(n＋rd))O(rd)从平均性能来看，快速排序最佳。但在最坏的情况下，不如堆排序和归并排序。而在n较大时，

5、归并排序的时间优于堆排序，但空间开销较大。“简单排序”包括除希尔排序之外所有的插入排序、起泡排序和简单选择排序。当序列中的记录“基本有序”时，直接插入排序最佳。基数排序适用于n很大，关键字较小的序列。所有时间复杂度为O（n2）的排序和基数排序都是稳定的排序，时间性能较好的快速排序、堆排序和归并排序都是不稳定的排序。一般来说，“比较”是在“相邻的两个记录关键字”间进行的排序方法是稳定的。没有哪种排序方法是最优的，实用时需根据不同情况选择。