直接插入排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include<iostream> using namespace std; void insertsort(int a[],int n){ int i,j,tmp; for(int i=1;i<n;i++){ tmp=a[i]; for(j=i;j>0&&a[j-1]>tmp;j--) a[j]=a[j-1]; a[j]=tmp; }} int main(){ int a[10]={2,3,5,1,4,8,6,9,7,0}; insertsort(a,10); for(int i=0;i<10;i++) cout<<a[i]<<" "; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include "seqlist.cpp" void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序 { int i, j; RecType tmp; for (i=1;i<n;i++) { if (R[i].key<R[i-1].key) //反序时 { tmp=R[i]; j=i-1; do //找R[i]的插入位置 { R[j+1]=R[j]; //将关键字大于R[i].key的记录后移 j--; } while (j>=0 && R[j].key>tmp.key); R[j+1]=tmp; //在j+1处插入R[i] } printf(" i=%d: ",i); DispList(R,n); } } int main() { int n=10; RecType R[MAXL]; KeyType a[]={9,8,7,6,5,4,3,2,1,0}; CreateList(R,a,n); printf("排序前:"); DispList(R,n); InsertSort(R,n); printf("排序后:"); DispList(R,n); return 1; } |
折半插入排序
折半插入排序和直接插入排序差不多,只是当我们把需要排序的数插入已经排序好的组中,直接插入排序是顺序查找位置,折半插入排序则是二分法查找位置,下面贴出教材的代码。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include "seqlist.cpp" void BinInsertSort(RecType R[],int n) { int i, j, low, high, mid; RecType tmp; for (i=1;i<n;i++) { if (R[i].key<R[i-1].key) //反序时 { tmp=R[i]; //将R[i]保存到tmp中 low=0; high=i-1; while (low<=high) //在R[low..high]中查找插入的位置 { mid=(low+high)/2; //取中间位置 if (tmp.key<R[mid].key) high=mid-1; //插入点在左半区 else low=mid+1; //插入点在右半区 } //找位置high for (j=i-1;j>=high+1;j--) //集中进行元素后移 R[j+1]=R[j]; R[high+1]=tmp; //插入tmp } printf(" i=%d: ",i); DispList(R,n); } } int main() { int n=10; RecType R[MAXL]; KeyType a[]={9,8,7,6,5,4,3,2,1,0}; CreateList(R,a,n); printf("排序前:"); DispList(R,n); BinInsertSort(R,n); printf("排序后:"); DispList(R,n); return 1; } |
希尔排序
希尔排序就是在直接插入排序外面套一层循环。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
//Shell排序算法 #include "seqlist.cpp" void ShellSort(RecType R[],int n) //希尔排序算法 { int i,j,d; RecType tmp; d=n/2; //增量置初值 while (d>0) { for (i=d;i<n;i++) //对所有组采用直接插入排序 { tmp=R[i]; //对相隔d个位置一组采用直接插入排序 j=i-d; while (j>=0 && tmp.key<R[j].key) { R[j+d]=R[j]; j=j-d; } R[j+d]=tmp; } printf(" d=%d: ",d); DispList(R,n); d=d/2; //减小增量 } } int main() { int n=10; RecType R[MAXL]; KeyType a[]={9,8,7,6,5,4,3,2,1,0}; CreateList(R,a,n); printf("排序前:"); DispList(R,n); ShellSort(R,n); printf("排序后:"); DispList(R,n); return 1; } |