1.插入排序
void INSERTSORT(KEYTYPE k[], int n)
{ int i,j; keytype temp; for (i = 2; i<n;i++) { temp = k[i]; j = i - 1; while (j> 0 && temp<k[j]) k[j+ 1]=k[j--]; k[j+ 1]=temp; } }
2.折半插入排序算法
void BIN_INSERTSORT(keytype K[], int n)
{ int i,j,high,mid; keytype temp; for (i= 2; i<=n; i++) { temp = K[i]; low = 1; high = i- 1; while (low<=high) { mid = (low + high)/ 2; if (temp<K[mid]) high=mid- 1; else low=mid+ 1; } for (j=i- 1; j>=low; j--) K[j+ 1]=K[j]; k[low]=temp; } }
3.选择排序
void SELECTSORT(keytype K[],int n)
{ int i,j,d; keytype temp; for (i= 1; i<=n- 1; i++) { d=i; for (j=i+ 1; j<=n; j++) if(K[j]<K[d]) d=j; if (d!=i) { temp=k[d]; K[d]=K[i]; K[i]=temp; } } }
4.泡排序
void BUBBLESORT(keytype k[],int n)
{ int i,j,flag= 1; keytype temp; i=n- 1; while (i> 0 && flag== 1) { flag= 0; for (j= 1; j<=i; j++) if (k[j]>k[j+ 1]) { temp=k[j]; k[j]=k[j+ 1]; k[j+ 1]=temp; flag= 1; } i--; } }
5.谢尔排序
void SHELLSORT(keytype k[],int n)
{ int i,j,flag,gap=n; keytype temp; while (gap> 1) { gap=gap/ 2; do{ flag= 0; for (i= 1; i<n-gap; i++) { j=i+gap; if (k[i]>k[j]) { temp=k[i]; k[i]=k[j]; k[j]=temp; flag= 1; } } } while (flag!= 0); } }
6.快速排序
void QUICK(keytype k[],int s,int t)
{ int i,j; if (s<t) { i=s; j=t+ 1; while ( 1) { do i++; while (!(k[s]<=k[i] || i==t)); do j--; while (!(k[s]<=k[i] || j==s)); if (i<j) SWAP(k[i],k[j]); else break; } SWAP(k[s],k[j]); QUICK(k,s,j- 1); QUICK(k,j+ 1,t); } } void QUICKSORT(keytype k[], int n) { QUICK(k, 1,n); }
7.堆积排序
注：调用一次ADJUST子算法，就把以序号为i的节点作为根节点的二叉树调整为堆积
void ADJUST(keytype k[],int i,int n)
{ int j; keytype temp; j= 2*i; while (j<=n) { if(j<n && k[j]<k[j+ 1]) j++; if (temp>=k[j]) break; k[j/ 2]=k[j]; j= 2*j; } k[j/ 2]=temp; }
堆排序算法
void HEAPSORT(keytype k[], int n) { int i; keytype temp; for (i=n/ 2; i>= 1; i--) ADJUST(k,i,n); for (i=n- 1; i>= 1; i--) { temp=k[i+ 1]; k[i+ 1]=k[ 1]; k[ 1]=temp; ADJUST(k, 1,i); }
}
8.二路归并排序
7.1 一趟归并扫描子算法
7.2二路归并排序算法
8.基数排序