选择排序 void SelectPass(SqList &L,int i ) RcdType W: ij=i; for k=i+1;K<=L.length;K++) if (L.r[k].key L.r[].key j=k if (il=j) W=L.rj];L.rj]=L.r[i];L.r[i]W; }/SelectPass
选择排序 void SelectPass( SqList &L, int i ) { RcdType W； j = i； for ( k=i+1; k<=L.length; 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；} } // SelectPass
选择排序 void SelectSort(SqList &L){ RcdType W; for (i=1;i<L.length;++i){ j=i; for k=i+1;K<=L.length;k++) if L.r[k].key L.r[j].key j=k if (i!=j){W=L.r];L.rj]=L.r[i];L.rti]W;) }/SelectSort
选择排序 void SelectSort (SqList &L) { RcdType W； for (i=1; i<L.length; ++i) { j = i； for ( k=i+1; k<=L.length; 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
插入排序 void InsertPass(SqList &L,int i){ L.r[o]L.r[i]; 川复制为哨兵 for j=i-1;L.r[o].key L.r[j].key;-j) L.rj+1]L.r[j]; W记录后移 L.rj+1]=L.r[0]; 川插入到正确位置 }/InsertPass
插入排序 void InsertPass( SqList &L, int i ) { L.r[0] = L.r[i]; // 复制为哨兵 for ( j=i-1; L.r[0].key < L.r[j].key; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; // 插入到正确位置 } // InsertPass
插入排序 void InsertSort SqList &L){ 川对顺序表L作插入排序 for i=2;i<=L.length;++i if L.r[i].key L.r[i-1].key L.r[o]L.r[i]; 川复制为哨兵 for j=i-1;L.r[o].key L.r[j].key;--j) L.r+1]=L.r]; ∥记录后移 L.rj+1]=L.r[0] 川插入到正确位置 lif }/InsertSort
void InsertSort ( SqList &L) { // 对顺序表 L作插入排序 for ( i=2; i<=L.length; ++i ) if ( L.r[i].key < L.r[i-1].key ) L.r[0] = L.r[i]; // 复制为哨兵 for ( j=i-1; L.r[0].key < L.r[j].key; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; // 插入到正确位置 } // if } // InsertSort 插入排序
起泡排序 void BubbleSort(SqList &L){ RcdType W: i L.length; while (i >1){ lastExchangelndex 1; for (j=1;j<i;j++) if (L.r[j+1].key L.r[j].key){ W=L.r[];L.r[]=L.r[+1];L.r[j+1]W; lastExchangelndex j; l/if }//for i lastExchangelndex; }/while }/BubbleSort
起泡排序 void BubbleSort( SqList &L ){ RcdType W； i = L.length; 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
快速排序 int Partition(RcdType R[],int low,int high){ R[0]R[low]; ∥将枢轴记录移至数组的闲置分量 pivotkey=Rlow.key;I∥枢轴记录关键字 while(low=pivotkey) --high; R[low++]=R[high]; ∥将比枢轴记录小的记录移到低端 while (low<high&&R[low].key<=pivotkey) ++loW; R[high--]R[low]; ∥将比枢轴记录大的记录移到高端 }//while R[low]R[O]; ∥枢轴记录移到正确位置 return low; ∥返回枢轴位置 }l∥Partition
快速排序 int Partition ( RcdType R[], int low, int high) { R[0] = R[low]; // 将枢轴记录移至数组的闲置分量 pivotkey = R[low].key; // 枢轴记录关键字 while (low=pivotkey) --high; R[low++] = R[high]; // 将比枢轴记录小的记录移到低端 while (low<high && R[low].key<=pivotkey) ++low; R[high--] = R[low]; // 将比枢轴记录大的记录移到高端 } //while R[low] = R[0]; // 枢轴记录移到正确位置 return low; // 返回枢轴位置 } // Partition
快速排序 void QSort(RedType R[],int s,int t){ ∥对记录序列R[s.t进行快速排序 if(s<t-1){ 川长度大于1 pivotloc Partition(R,s,t);//R[s..t] QSort(R,s,pivotloc-1); 川对低子序列递归排序 QSort(R,pivotloc+1,t); 川对高子序列递归排序 if }/Qsort void QuickSort(SqList L){ QSort(L.r,1,L.length); }∥QuickSort
快速排序 void QSort (RedType R[], int s, int t ) { // 对记录序列R[s..t]进行快速排序 if (s < t-1) { // 长度大于1 pivotloc = Partition(R, s, t);// 对 R[s..t] QSort(R, s, pivotloc-1); // 对低子序列递归排序 QSort(R, pivotloc+1, t); // 对高子序列递归排序 } // if } // Qsort void QuickSort( SqList & L) { QSort(L.r, 1, L.length); } // QuickSort
归并排序 void Merge(RcdType SR[],RcdType TR[],int i,int m,int n) ∥将有序的SR[i.m和SR[m+1.n]归并为有序的TRi.n] for (j=m+1,k=i;i<=m &j<=n;++k){ if(SR[i].key<=SR[j].key)TR[k]SR[i++]; else TR[k]SR[++]; while (i<=m)TR[k++]=SR[i++] while (j<=n)TR[k++]SR[j++]; }∥Merge
归并排序 void Merge (RcdType SR[], RcdType TR[], int i, int m, int n) { // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] for (j=m+1, k=i; i<=m && j<=n; ++k) { if (SR[i].key<=SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; } while (i<=m) TR[k++] = SR[i++]; while (j<=n) TR[k++] = SR[j++]; } // Merge
归并排序 void Msort RcdType SR[],RcdType TR1[],int s,int t){ ∥对SR[st]进行归并排序，排序后的记录存入TR1[s.t]。 RcdType TR2[t-s+1]; if (s==t)TR1[s]SR[s]; else m=(s+t)/2; Msort (SR,TR2,s,m); Msort(SR,TR2,m+1,t); Merge(TR2,TR1,s,m,t); }/else }/MSort void MergeSort (SqList &L){ MSort(L.r,L.r,1,L.length); }/MergeSort
归并排序 void Msort ( RcdType SR[], RcdType TR1[], int s, int t ) { // 对SR[s..t]进行归并排序，排序后的记录存入TR1[s..t]。 RcdType TR2[t-s+1]; if (s==t) TR1[s] = SR[s]; else { m = (s+t)/2; Msort (SR, TR2, s, m); Msort (SR, TR2, m+1, t); Merge (TR2, TR1, s, m, t); } // else } // MSort void MergeSort (SqList &L) { MSort(L.r, L.r, 1, L.length); } // MergeSort
二路归并 void mergepass(RcdType SR[],RcdType TR[],int s,int n) { i=1; while(i+2s-1<=n){ merge(SR,TR,i,i+s-1,i+2*s-1); i+=2*S; } if(i+s-1<n)/最后还有两个集合，但不等长 merge(SR,TR,i,i+s-1,n); else∥最后还有一个集合 while(i<=n){TR[i]=SR[i];i++); }
二路归并 void mergepass(RcdType SR[],RcdType TR[],int s,int n) { i=1; while(i+2s-1<=n) { merge(SR,TR,i,i+s-1,i+2*s-1); i +=2*s; } if(i+s-1<n) //最后还有两个集合，但不等长 merge(SR,TR,i,i+s-1,n); else //最后还有一个集合 while(i<＝n){TR[i]=SR[i];i++}; }
