1 #include<iostream> 2 #include<cstdlib> 3 #include<ctime> 4 using namespace std; 5 const int len = 20;//待排序數組元素的個數，下標從1開始 6 //1、冒泡排序 7 void Bubble_sort(int s[],int len){ 8 bool flag; 9 for(int i=1;i<len-1;++i){ 10 flag=false; 11 for(int j=1;j<=len-i;++j) 12 if(s[j]>s[j+1]){flag=true;swap(s[j],s[j+1]);} 13 if(!flag)break; 14 } 15 } 16 //2、選擇排序 17 void Select_sort(int s[],int len){ 18 int k; 19 for(int i=1;i<len;++i){ 20 k=i; 21 for(int j=i+1;j<=len;++j) 22 if(s[k]>s[j])k=j; 23 if(k!=i)swap(s[i],s[k]); 24 } 25 } 26 //3、插入排序 27 void Insert_sort(int s[],int len){ 28 int tmp,j; 29 for(int i=2;i<=len;++i){ 30 tmp=s[i]; 31 for(j=i-1;j>0&&tmp<s[j];--j); 32 for(int k=i;k>j+1;--k)s[k]=s[k-1]; 33 s[j+1]=tmp; 34 } 35 } 36 //4、快速排序 37 int Quick_sort(int s[],int low,int high){ 38 int tmp=s[low];//首元素是樞軸 39 while(low<high){//待排序序列長度大于1 40 while(low<high&&tmp<=s[high])--high;//大于樞軸的元素依舊在右邊 41 s[low]=s[high];//將小于樞軸的元素放左邊 42 while(low<high&&tmp>=s[low])++low;//小于樞軸的元素依舊在左邊 43 s[high]=s[low];//將大于樞軸的元素放右邊 44 } 45 s[low]=tmp;//樞軸記錄到位 46 return low;//返回樞軸的位置，表示該位置已經排好序 47 } 48 void Qsort(int s[],int low,int high){ 49 if(low<high){ 50 int key=Quick_sort(s,low,high); // 第key個元素已經排好序，繼續兩邊搜索排序 51 Qsort(s,low,key-1); 52 Qsort(s,key+1,high); 53 } 54 } 55 //5、希爾排序(采用直接插入) 56 void Shell_sort(int s[],int len){ 57 int tmp,j; 58 for(int step=len/2;step>0;step/=2){//設置步長 59 for(int i=step;i<=len;++i){ 60 tmp=s[i]; 61 for(j=i-step;j>0&&tmp<s[j];j-=step); 62 for(int k=i;k>j+step;k-=step)s[k]=s[k-step]; 63 s[j+step]=tmp; 64 } 65 } 66 } 67 //6、歸并排序 68 void Merge(int s[],int t[],int low,int mid,int high){ 69 int i=low,j=mid+1,k=low; 70 while(i<=mid&&j<=high){ 71 if(s[i]<=s[j])t[k++]=s[i++]; 72 else t[k++]=s[j++]; 73 } 74 while(i<=mid)t[k++]=s[i++]; 75 while(j<=high)t[k++]=s[j++]; 76 for(int i=low;i<=high;++i)s[i]=t[i];//將區間[low,high]拷貝到原來數組s對應的位置，表示該區間元素已排好序 77 } 78 void Merge_sort(int s[],int t[],int low,int high){ 79 if(low<high){ 80 int mid=(low+high)/2; 81 Merge_sort(s,t,low,mid);//遞歸分成左部分 82 Merge_sort(s,t,mid+1,high);//遞歸分成右部分 83 Merge(s,t,low,mid,high);//將兩部分歸并 84 } 85 } 86 //7、堆排序(大根堆實現升序排序) 87 void Heap_Adjust(int s[],int cur,int len){ 88 int tmp=s[cur];//先取出當前元素cur 89 for(int j=2*cur;j<=len;j*=2){//向下篩選 90 if(j<len&&s[j]<s[j+1])++j; 91 if(tmp>=s[j])break; 92 s[cur]=s[j];cur=j;//將子節點j值賦給父節點cur（不用進行交換） 93 } 94 s[cur]=tmp; 95 } 96 void Heap_sort(int s[],int len){ 97 //1、構建大根堆 98 for(int i=len/2;i>0;--i)Heap_Adjust(s,i,len); 99 //2.調整堆結構+交換堆頂元素與末尾元素 100 for(int i=len;i>1;--i){ 101 swap(s[i],s[1]); 102 Heap_Adjust(s,1,i-1);//將[1,i-1]重新調整為大根堆 103 } 104 } 105 //8、基數排序 106 int Max_bit(int s[],int len){//獲取數組中最大值的位數 107 int dit=1,p=10; 108 for(int i=1;i<=len;++i) 109 while(s[i]>=p){++dit;p*=10;} 110 return dit; 111 } 112 void Radix_sort(int s[],int len){ 113 int exp=1,dit=Max_bit(s,len),*cnt=new int[10],*tmp=new int[len+1]; 114 for(int j=1;j<=dit;++j){ 115 for(int i=0;i<10;++i)cnt[i]=0; 116 for(int i=1;i<=len;++i)cnt[s[i]/exp%10]++; 117 for(int i=1;i<10;++i)cnt[i]+=cnt[i-1];//疊加元素個數 118 for(int i=len;i>0;--i)tmp[cnt[s[i]/exp%10]--]=s[i];//將桶中元素倒出來 119 for(int i=1;i<=len;++i)s[i]=tmp[i];//將倒出來的元素依次放到原數組中去 120 exp*=10; 121 } 122 delete[]cnt;//釋放內存 123 delete[]tmp; 124 } 125 //打印數組元素值 126 void print(int s[],int len){ 127 for(int i=1;i<=len;++i) 128 cout<<s[i]<<(i==len?"\n":" "); 129 } 130 int main(){ 131 int *s=new int[len+1]; 132 int *t=new int[len+1];//t為輔助數組 133 srand((unsigned)time(NULL)); 134 for(int i=1;i<=len;++i)s[i]=rand(); 135 cout<<"排序前："<<endl; 136 print(s,len);//打印原數組 137 /*1、冒泡排序 138 Bubble_sort(s,len);*/ 139 /*2、選擇排序 140 Select_sort(s,len);*/ 141 /*3、插入排序 142 Insert_sort(s,len);*/ 143 /*4、快速排序 144 Qsort(s,1,len);*/ 145 /*5、希爾排序 146 Shell_sort(s,len);*/ 147 /*6、歸并排序 148 Merge_sort(s,t,1,len);*/ 149 /*7、堆排序 150 Heap_sort(s,len);*/ 151 /*8、基數排序 152 Radix_sort(s,len); 153 cout<<"排序后："<<endl;*/ 154 print(s,len);//打印排序后的數組元素 155 156 delete[]s;//釋放內存 157 delete[]t; 158 return 0; 159 }

?

轉載于:https://www.cnblogs.com/acgoto/p/9211511.html

總結

以上是生活随笔為你收集整理的八种排序算法模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。