#include<stdio.h> #include<windows.h> #include<assert.h> #include"Stack.h" typedef int DataType; void SortPrint(DataType*a,size_t n){ size_t i; for(i=0;i<n;i++) printf("%d ",a[i]); printf("\n"); } void Swap(DataType* x,DataType* y){ DataType tmp=*x; *x=*y; *y=tmp; } void InsertSort(DataType *a,size_t n){ DataType tmp; int i,end; for(i=0;i<n-1;i++){ end=i; tmp=a[end+1]; while(end>=0&&a[end]>tmp){ a[end+1]=a[end]; --end; } a[end+1]=tmp; } } void ShellSort(DataType *a,size_t n){ int i,end,tmp; size_t gap=n; while(gap>1){ gap=gap/3+1; for(i=0;i<n-gap;i++){ end=i; tmp=a[end+gap]; while(end>=0&&a[end]>tmp){ a[end+gap]=a[end]; end-=gap; } a[end+gap]=tmp; } printf("gap[%d]=> ",gap); SortPrint(a,n); } } void SelectSort(DataType* a,size_t n){ size_t left,right,i,min,max; left=0; right=n-1; while(left<right){ min=left; max=left; for(i=left;i<=right;i++) if(a[min]>a[i]) min=i; for(i=left;i<=right;i++) if(a[max]<a[i]) max=i; Swap(&a[left],&a[min]); if(max==left) max=min; Swap(&a[right],&a[max]); ++left; --right; SortPrint(a,n); } } void AdjustDown(DataType* a,size_t n,int parent){ int child; assert(a); child=parent*2+1; while(child<n){ child=parent*2+1; if(child+1<n&&a[child]<a[child+1]) ++child; if(child<n&&a[parent]<a[child]){ Swap(&a[parent],&a[child]); parent=child; } else break; } } void HeapSort(DataType* a,size_t n){ int i; for(i=(n-2)/2;i>=0;i--){ AdjustDown(a,n,i); } SortPrint(a,n); for(i=n-1;i>0;i--){ Swap(&a[0],&a[i]); AdjustDown(a,i,0); SortPrint(a,n); } } void BubbleSort(DataType* a,size_t n){ int i,j,flag; for(i=0;i<n-1;i++){ flag=0; for(j=0;j<n-i-1;j++){ if(a[j]>a[j+1]){ flag=1; Swap(&a[j],&a[j+1]); } } if(flag==0) return; } } //QuickSort int FindMidNum(DataType* a,int left,int right){ int mid; DataType tmp; assert(a); mid=left+((right-left)>>1); if(a[left]>a[mid]){ if(a[mid]>a[right]) return mid; else if(a[left]<a[right]) return left; else return right; } else{ if(a[left]>a[right]) return left; else if(a[mid]<a[right]) return mid; else return right; } } //int partion(DataType* a,int left,int right){ // int begin,end; // DataType tmp=a[right]; // begin=left; // end=right; // while(begin<end){ // while(begin<end&&a[begin]<=tmp) // ++begin; // while(begin<end&&a[end]>=tmp) // --end; // Swap(&a[begin],&a[end]); // } // Swap(&a[begin],&a[right]); // return begin; //} //左右指针法 int ParSort1(DataType* a, int left, int right){ int begin,end,mid; DataType key; //三数取中，优化快排 mid = FindMidNum(a,left,right); Swap(&a[mid],&a[right]); key = a[right]; begin=left; end=right; while(begin<end){ while(begin<end && a[begin]<=key) begin++; while(begin<end && a[end]>=key) end--; Swap(&a[begin],&a[end]); } Swap(&a[begin],&a[right]); return begin; } //挖坑法 int ParSort2(DataType* a, int left, int right){ int begin, end,mid; DataType key; assert(a); begin=left; end=right; mid=FindMidNum(a,left,right); Swap(&a[mid],&a[right]); key=a[right]; while(begin<end){ while(begin<end&&a[begin]<=key) ++begin; a[end]=a[begin]; while(begin<end&&a[end]>=key) --end; a[begin]=a[end]; } a[begin]=key; return begin; } //前后指针法 int ParSort3(DataType* a,int left,int right){ int prev,cur,mid; assert(a); mid=FindMidNum(a,left,right); Swap(&a[mid],&a[right]); prev=left-1; cur=left; while(cur<right){ if(a[cur]<=a[right]&&++prev!=cur) Swap(&a[cur],&a[prev]); ++cur; } Swap(&a[++prev],&a[right]); return prev; } void QuickSort(DataType* a,int left,int right){ int div; if(right-left+1<5){ InsertSort(a+left,right-left+1); return; } if(left<right){ div=ParSort3(a,left,right); QuickSort(a,0,div-1); QuickSort(a,div+1,right); } } void QuickSortNOR(DataType* a,int left,int right){ int begin,end,div; Stack s; StackInit(&s); StackPush(&s,0); StackPush(&s,right); while(StackEmpty(s)!=0){ end=StackTop(&s); StackPop(&s); begin=StackTop(&s); StackPop(&s); div = ParSort3(a, begin, end); if (begin < div-1){ StackPush(&s, begin); StackPush(&s, div - 1); } if (end > div + 1){ StackPush(&s, div + 1); StackPush(&s, end); } } } //归并排序 void Merge(DataType *a, int left, int mid, int right){ int begin1,end1,begin2,end2,index; DataType* tmp; tmp=(DataType*)malloc(sizeof(DataType)*(right-left+1)); begin1=left; end1=mid; begin2=mid+1; end2=right; index=0; while(begin1<=end1&&begin2<=end2){ if(a[begin1]<=a[begin2]) tmp[index++]=a[begin1++]; else tmp[index++]=a[begin2++]; } while(begin1<=end1) tmp[index++]=a[begin1++]; while(begin2<=end2) tmp[index++]=a[begin2++]; index=0; while(index<right-left+1){ a[index+left]=tmp[index]; index++; } free(tmp); } void MergeSort(DataType *a,int left,int right){ int mid; assert(a); if(left>=right) return; if(right-left+1>5){ mid = left + ((right-left)>>1) ; MergeSort(a,left,mid); MergeSort(a,mid+1,right); Merge(a, left, mid, right); } else //优化 InsertSort(a+left,right-left+1); } //CountSort void CountSort(DataType* a, size_t n){ int min, max, i, j, m; DataType* counts; assert(a); min=max=0; for(i=0;i<n;i++){ if(a[i]>a[max]) max=i; if(a[i]<a[min]) min=i; } printf("max:%d, min:%d\n",a[max],a[min]); m=a[max]-a[min]+1; counts=(DataType*)malloc(sizeof(DataType)*m); memset(counts,0,sizeof(DataType)*m); //printf("m==%d\n",m); for(i=0;i<m;++i){ for(j=0;j<n;j++){ if(i==a[j]-a[min]) counts[i]++; } } for(i=0;i<m;i++){ if(counts[i]>0){ printf("[%d]:%d ",i+a[min],counts[i]); } } printf("\n"); } / void TestInsertSort(){ // DataType a[]={8,4,3,7,6,5,9,2,1,0}; DataType a[]={9,8,7,6,5,4,3,2,1,0}; printf("直接插入法排序\n"); InsertSort(a,sizeof(a)/sizeof(a[0])); SortPrint(a,sizeof(a)/sizeof(a[0])); printf("\n"); } void TestShellSort(){ DataType a[]={9,8,7,6,5,4,3,2,1,0}; printf("希尔排序\n"); ShellSort(a,sizeof(a)/sizeof(a[0])); SortPrint(a,sizeof(a)/sizeof(a[0])); printf("\n"); } void TestSelectSort(){ DataType a[]={9,8,7,6,5,4,3,2,1,0}; printf("选择排序\n"); SelectSort(a,sizeof(a)/sizeof(a[0])); printf("\n"); } void TestHeapSort(){ // DataType a[]={0,1,2,3,4,5,6,7,8,9}; DataType a[]={8,4,3,7,6,5,9,2,1,0}; printf("堆排序\n"); HeapSort(a,sizeof(a)/sizeof(a[0])); printf("\n"); } void TestBubbleSort(){ DataType a[]={8,4,3,7,6,5,9,2,1,0}; printf("冒泡排序\n"); BubbleSort(a,sizeof(a)/sizeof(a[0])); SortPrint(a,sizeof(a)/sizeof(a[0])); printf("\n"); } void TestQuickSort(){ DataType a[]={8,4,3,7,6,5,9,2,1,0}; // DataType a[]={9,8,7,6,5,4,3,2,1,0}; printf("快速排序\n"); QuickSort(a,0,9); SortPrint(a,sizeof(a)/sizeof(a[0])); printf("\n"); } void TestQuickSortNOR(){ // DataType a[]={8,4,3,7,6,5,9,2,1,0}; DataType a[]={9,8,7,6,5,4,3,2,1,0}; printf("快速排序NOR\n"); QuickSortNOR(a,0,9); SortPrint(a,sizeof(a)/sizeof(a[0])); printf("\n"); } void TestMergeSort(){ DataType a[]={9,8,7,6,5,4,3,2,1,0}; printf("MergeSort\n"); MergeSort(a,0,9); SortPrint(a,sizeof(a)/sizeof(a[0])); printf("\n"); } void TestCountSort(){ DataType a[]={9,8,7,6,5,4,3,2,4,4,4,20,15,6,6,6,6,50}; CountSort(a,sizeof(a)/sizeof(a[0])); }
