直接排序法,折半插入法,希尔排序法,快速排序法(c语言实现)

//void InserSort(SqList &L)// #include<stdio.h> #define LENGTH 9 #define DltaLength 3 /* //直接排序法 void InsertSort(int *p) { int i; int j; for(i=2;i<LENGTH;++i)//i<LENGTH //0位做哨兵位，先比较1和2两个元素，所以i=2,i-1=1，所以从i=2开始，i<LENGTH结束 if (*(p+i)<*(p+i-1)) { p[0]=p[i];//复制为哨兵 p[i]=p[i-1]; //用<的好处是，使原来排序前Ri领先于Rj，排序后依然Ri领先于Rj，即使排序方法稳定。 for(j=i-2;p[0]<p[j];j--) p[j+1]=p[j]; p[j+1]=p[0]; } } */ /* //折半( 二分法)插入法 void BInsertSort(int *p) { int low,high,middle,i,j,num; for(i=2;i<LENGTH;++i) { p[0]=p[i]; num=p[0]; low=1; high=i-1; // 二分法查找插入位置，肯定用这个，反复查找，直到左(low or left)指针 //大于右指针(high or right)时停止。 while(low<=high) { middle=(low+high)/2;//折半，二分法 if(num<p[middle]) high=middle-1;//插入点在高半区， else low=middle+1;//插入点在低半区， }//while for(j=i-1;j>=low;--j) //记录后移 p[j+1]=p[j]; p[low]=p[0];//插入 }//for }//BInsertSort */ //shell排序,(希尔排序) /* void ShellInsert(int *p,int dk) { int i,j; for (i=dk+1;i<LENGTH;i++)//p[0]是暂存单元，所以从i=dk+1开始 {//只要p[i]<p[i-dk]，则要进行插入，否则不用插入，i++，进行下一个元素的比较 if (p[i]<p[i-dk]) { p[0]=p[i];//暂存p[i]到p[0] for (j=i-dk;j>0&&(p[0]<p[j]);j-=dk) p[j+dk]=p[j];//记录后移，查找插入位置p[j+dk] p[j+dk]=p[0];//插入 } } } */ //快速排序 int Partition(int *p, int low, int high) { int pivotkey; p[0]=p[low];//用子表的第一个记录作枢轴记录，且暂存在p[0]内， pivotkey=p[low]; while(low<high) { while(low<high&&p[high]>=pivotkey) --high; p[low]=p[high];//将比枢轴记录小的记录移到低端 while(low<high&&p[low]<=pivotkey) --low; p[high]=p[low];//将比枢轴记录大的记录移到高端 } p[low]=p[0]; return p[low]; } void QSort(int *p,int low,int high) { // int low_now, high_now; int pivotloc; // low_now=low; // high_now=high; if (low<high) { pivotloc=Partition(p,low,high); QSort(p,low,pivotloc-1); QSort(p,pivotloc+1,high); } } main() { int i,k; int low=1,high=(LENGTH-1); int num[LENGTH]={0,49,38,65,97,76,13,27,49}; int *p=num;//数组名就是数组首地址 int dlta[DltaLength]={5,3,1}; for(i=1;i<LENGTH;i++) printf("%d ",*(p+i)); // BInsertSort(p); /*for(k=0;k<DltaLength;++k) ShellInsert(p,dlta[k]);*/ //QuickSort(p); QSort(p,low,high); printf("\n\nthe stored num is:\n"); for(i=1;i<LENGTH;i++) printf("%d ",*(p+i)); }