中国科学技术大学：《数据结构及算法》课程教学资源（PPT课件讲稿）第8章 排序

S 选择排序 void SelectSort(SqTable &L){ RcdType W; for (i=1;i<L.len;++i) j=i; for k=i+1;k<=L.len;k++) if (L.r[k].key<L.r[j].key)j=k SelectPass if(i=j){W=Lr[];L.r[j=L.r[];L.[]=W;} }∥SelectSort ypb@ustc.edu.cn 6 中国科学技术大学

ypb@ustc.edu.cn 6 中国科学技术大学 选择排序 void SelectSort (SqTable &L) { RcdType W； for (i=1; i<L.len; ++i) { j = i； for ( k=i+1; k<=L.len; k++ ) if ( L.r[k].key < L.r[j].key ) j =k ； if ( i!=j ) { W=L.r[j];L.r[j] =L.r[i];L.r[i] = W;} } } // SelectSort SelectPass

起泡排序 void BubbleSort(SqTable&L)复杂度On2) 有序序列的比较次数是n-1次 -逆序序列的比较次数是n(n-1)/2;移动次数3n(n-1)/2 是稳定排序 R[i] 无序序列R1. 有序序列R[什1.n] 无序序列R1.i 有序序列R[i.n] Moosoft P威灯片故 ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 7 中国科学技术大学 void BubbleSort（SqTable &L）复杂度 O(n2 ) –有序序列的比较次数是n-1次 – 逆序序列的比较次数是 n(n-1)/2；移动次数3n(n-1)/2 – 是稳定排序 R[i] 无序序列R[1..i] 有序序列R[i+1..n] 无序序列R[1..i-1] 有序序列R[i..n] 起泡排序

S void BubbleSort(SqTable &L){ i=L.len; while (i>1){ lastExchangeIndex =1; for (j=1;j<i;j++){ if (L.r[j+1].key <L.r[j].key){ W=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=W; lastExchangeIndex j; llif //for i=lastExchangeIndex; }∥while }/∥BubbleSort ypb@ustc.edu.cn 8 中国科学技术大学

ypb@ustc.edu.cn 8 中国科学技术大学 void BubbleSort(SqTable &L ){ i = L.len; while (i >1) { lastExchangeIndex = 1; for (j = 1; j < i; j++){ if (L.r[j+1].key < L.r[j].key) { W=L.r[j]；L.r[j] =L.r[j+1]；L.r[j+1] = W； lastExchangeIndex = j; } //if } //for i = lastExchangeIndex; } // while } // BubbleSort

对比 void bubble sort(int a[],int n) for (i=n-1,change=TRUE;i>0&&change;--i){ change FALSE; for (j-0;j<i;++j) if (a[j]>a[+1]) w=a[j];a[j]=a[j+1];a[j+1]=w;change TRUE ypb@ustc.edu.cn 9 中国科学技术大学

ypb@ustc.edu.cn 9 中国科学技术大学 对比 void bubble_sort(int a[], int n){ for (i=n-1, change=TRUE; i>0 && change; --i) { change = FALSE; for (j=0; j<i; ++j) if (a[j] > a[j+1]) { w = a[j]; a[j]= a[j+1]; a[j+1]= w; change = TRUE } } }

插入排序 void InsertPass(SqTable&L,inti)复杂度0(n) void InsertSort(SqTable&L)复杂度0(n2) 数据的有序性影响算法最差比较移动(n+4)(n-1)/2 -是稳定排序 R[的 有序序列R[1.i-1 无序序列Ri.n 有序序列R[1.i] 无序序列R[+1.n可 ypb@ustc.edu.cn 10 中国科学技术大学

ypb@ustc.edu.cn 10 中国科学技术大学 void InsertPass(SqTable &L,int i)复杂度 O(n) void InsertSort(SqTable &L) 复杂度 O(n2) –数据的有序性影响算法 最差比较移动 (n+4)(n-1)/2 –是稳定排序 R[i] 有序序列R[1..i-1] 无序序列R[i..n] 有序序列R[1..i] 无序序列R[i+1..n] 插入排序