数据结构清华大学出版社严蔚敏吴伟民编著

由天下分享时间：2024/9/11 4:16:31 加入收藏我要投稿点赞

4、交换排序 1）冒泡排序冒泡排序的算法实现

void Bubblesort( NODE array[],int n) { int i, j, flag; //当flag为0则停止排序 NODE temp;

for ( i=1; i=i; j--)

if (array[j].key

if(flag==0) break; } }

例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。下面用图10-3给出冒泡排序算法的执行过程。

冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。

因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法。 2）快速排序

快速排序（Quick Sorting）是迄今为止所有内排序算法中速度最快的一种。

快速排序的算法实现

void quicksort(NODE array[],int start , int end) { int i , j; NODE mid; if (start>=end) return; i=start;j=end;mid=array[i]; while (i

{ while (imid.key) j--; if (i

while (i

if (i

array[i]=mid;

quicksort(array,start,i-1); //递归调用左子区间 quicksort(array,i+1,end); }//递归调用右子区间

例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图10-4所示。

快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。

快速排序是一种不稳定的排序方法。 5、选择排序

1）直接选择排序

例如，给定n=8，数组R中的8个元素的排序码为：（8，3，2，1，7，4，6，5），则直接选择排序过程如图7-5所示。直接选择排序的时间复杂度为O(n2)数量级 2）树形选择排序

例如，给定排序码头 50，37，66，98，75，12，26，49，树形选择排序过程见图7-7。 3）堆排序

例如，给定排序码49，38，65，97，76，13，27，70，建立初始堆的过程如图7-8所示。

按层次遍历完全二叉树，得到一个由大到小排列的有序序列： 97，76，70，65，49，38，27，13

每次筛选运算的时间复杂度为O(log2n)，故整个堆排序过程的时间复杂度为O(nlog2n)。 5、归并排序

例如，给定排序码46，55，13，42，94，05，17，70，二路归并排序过程如图7-10所示。

二路归并排序的时间复杂度为O(nlog2n)。 6、各种内排序方法的比较和选择 1）从时间复杂度比较

从平均时间复杂度来考虑，直接插入排序、冒泡排序、直接选择排序是三种简单的排序方法，时间复杂度都为O(n2)，而快速排序、

堆排序、二路归并排序的时间复杂度都为O(nlog2n)，希尔排序的复杂度介于这两者之间。若从最好的时间复杂度考虑，则直接插入排序和冒泡排序的时间复杂度最好，为O(n)，其它的最好情形同平均情形相同。若从最坏的时间复杂度考虑，则快速排序的为O(n2)，直接插入排序、冒泡排序、希尔排序同平均情形相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情形对直接选择排序、堆排序和归并排序影响不大。 2）从空间复杂度比较

归并排序的空间复杂度最大，为O(n)，快速排序的空间复杂度为O(log2n)，其它排序的空间复杂度为O（1）。 3）从稳定性比较

直接插入排序、冒泡排序、归并排序是稳定的排序方法，而直接选择排序、希尔排序、快速排序、堆排序是不稳定的排序方法。 4）从算法简单性比较

直接插入排序、冒泡排序、直接选择排序都是简单的排序方法，算法简单，易于理解，而希尔排序、快速排序、堆排序、归并排序都是改进型的排序方法，算法比简单排序要复杂得多，也难于理解。 8、各种内排序方法的选择

1）从时间复杂度选择

对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选简单的排序方法。

2）从空间复杂度选择

尽量选空间复杂度为O（1）的排序方法，其次选空间复杂度为O(log2n)的快速排序方法，最后才选空间复杂度为O（n）二路归并排序的排序方法。

3）一般选择规则

? 当待排序元素的个数n较大，排序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜。

? 当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜。

? 当待排序元素的个数n大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜。

? 当待排序元素的个数n小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序为宜。