i=4 1621 525 08 Exchang 2 3 5 起泡排序的算法 typedef int SortData; void BubbleSort( SortData VI, int n)( int i=l; int exchange=I while (i< n & exchange ) exchange=0;/标志置为0,假定未交换 for( intj=n-1; j>=1;j--) if(V-1]>V){∥逆序
26 25* 0 1 2 3 4 5 i = 4 49 16 Exchang=0 08 21 25 起泡排序的算法 typedef int SortData; void BubbleSort ( SortData V[ ], int n ) { int i = 1; int exchange = 1; while ( i < n && exchange ){ exchange = 0; //标志置为0,假定未交换 for ( int j = n-1; j >= i; j-- ) if ( V[j-1] > V[j] ) { //逆序
Swap(Vj-1],Vi]);,∥交换 exchange=1;/标志置为1,有交换 1++ 第趟对待排序对象序列Vi-1,i,n-11 进行排序,结果将该序列中排序码最小的对 象交换到序列的第一个位置(1),其它对象 也都向排序的最终位置移动。在个别情形 对象可能在排序中途向相反的方向移动。 27
27 Swap ( V[j-1], V[j] );, //交换 exchange = 1; //标志置为1,有交换 } i++; } } ◼ 第i趟对待排序对象序列V[i-1],V[i],,V[n-1] 进行排序, 结果将该序列中排序码最小的对 象交换到序列的第一个位置(i-1), 其它对象 也都向排序的最终位置移动。在个别情形, 对象可能在排序中途向相反的方向移动
最多做n-1趟起泡就能把所有对象排好序。 在对象的初始排列已经按排序码从小到大排 好序时此算法只执行一趟起泡做n-1次排序 码比较不移动对象。这是最好的情形。 。最坏的情形是算法执行n-1趟起泡第趟(1≤ ⅸn)做n-i次排序码比较,执行ni次对象交 换。这样在最坏情形下总的排序码比较次数 KCN和对象移动次数RMN为: KCN=∑(n-) 1 n(n-1) 2 3 RMN=3∑(n-i n(n-1 28
28 ◼ 最多做n-1趟起泡就能把所有对象排好序。 ◼ 在对象的初始排列已经按排序码从小到大排 好序时,此算法只执行一趟起泡,做n-1次排序 码比较,不移动对象。这是最好的情形。 ◼ 最坏的情形是算法执行n-1趟起泡,第i趟 (1 i n) 做 n- i 次排序码比较, 执行 n-i 次对象交 换。这样在最坏情形下总的排序码比较次数 KCN和对象移动次数RMN为： − = − = = − = − = − = − 1 1 1 1 1 2 3 3 1 2 1 n i n i RMN n i n n KCN n i n n ( ) ( ) ( ) ( )
起泡排序需要一个附加对象以实现对象值的 对换 起泡排序是一个稳定的排序方法。 快速排序( Quick Sort 基本思想是任取待排序对象序列中的某个对象 (例如取第一个对象)作为基准,按照该对象的 排序码大小,将整个对象序列划分为左右两 个子序列:
29 快速排序 (Quick Sort) ◼ 基本思想是任取待排序对象序列中的某个对象 (例如取第一个对象) 作为基准, 按照该对象的 排序码大小, 将整个对象序列划分为左右两 个子序列： ◼ 起泡排序需要一个附加对象以实现对象值的 对换。 ◼ 起泡排序是一个稳定的排序方法
左侧子序列中所有对象的排序码都小于 或等于基准对象的排序码 右侧子序列中所有对象的排序码都大于 基准对象的排序码 基准对象则排在这两个子序列中间这也是 该对象最终应安放的位置)。 然后分别对这两个子序列重复施行上述方 法,直到所有的对象都排在相应位置上为 止
30 ◆ 左侧子序列中所有对象的排序码都小于 或等于基准对象的排序码 ◆ 右侧子序列中所有对象的排序码都大于 基准对象的排序码 ◼ 基准对象则排在这两个子序列中间(这也是 该对象最终应安放的位置)。 ◼ 然后分别对这两个子序列重复施行上述方 法，直到所有的对象都排在相应位置上为 止