4、 交换排序 1)冒泡排序 冒泡排序的算法实现
void Bubblesort( NODE array[],int n) { int i, j, flag; //当flag为0则停止排序 NODE temp;
for ( i=1; i
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 (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小,元素基本有序或分布较随机,且要求稳定时,则采用直接插入排序为宜。 ? 当待排序元素的个数n小,对稳定性不做要求时,则采用直接选择排序为宜,若排序码不接近逆序,也可以采用直接插入排序。冒泡排序一般很少采用。 第9章 查找 1、顺序表的查找(顺序查找) 顺序查找的缺点是平均查找长度较大,特别是当n很大时,查找效率低。然而,它有很大的优点是:算法简单且适应面广。 2、有序表的查找(折半查找) 算法实现:假设表长为n,low、high和mid分别指向待查元素所在
数据结构 清华大学出版社 严蔚敏吴伟民编著
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)