1 // ALLKindsOfSorts.cpp : 定义控制台应用程序的入口点。  2 //  3   4 #include "stdafx.h"  5 #include<iostream>  6 #include<vector>  7 #include<bitset>  8   9 using namespace std; 10  11 ////////////////////////////////////////所有的排序总结//////////////////////////////////// 12  13 //1、冒泡排序(O(n*n)) 14  void MaopaoSort(int *a,int len) 15  { 16      //这里要明白 17     for(int i=0;i<len-1;i++)////这层循环控制的是需要排序的数的个数，即控制扫面的轮数 18     { 19         bool  IsChange=false;//这是冒泡改进的地方，增加一个标志来判断是否已经提前排好序了 20         //这里要注意由于比较的是在一个循环下前一个数跟后一个数比较 21         for(int j=0;j<len-i-1;j++)//这层循环是控制每一轮扫描之后，将最大的数放在最右边 22         {//这里的j<len-i-1要注意边界的原因，所以是j<len-i-1 23             if(a[j]>a[j+1])//相邻元素比较 24             { 25                 //交换 26                 int temp=a[j]; 27                 a[j]=a[j+1]; 28                 a[j+1]=temp; 29                 IsChange=true;//如果一次扫描完之后都没发生任何的交换，则表明已经排好序了 30             } 31         } 32         if(!IsChange) 33         { 34             cout<<"提前结束排序"<<endl; 35             return; 36         } 37     } 38  } 39  40  //2、插入排序(O(n*n)) 41 void InsertSort(int *a,const int len) 42  { 43  44     for(int i=1;i<len;i++)//扫描无序的数组 45     { 46         //记住：将第一个数作为已排序的数，从第二个数开始所有的数作为无序的数 47         if(a[i-1]>a[i])//跟已排序好的数进行比较，找出合适的位置 48         {         49             int temp= a[i];//将需要插入的无序数保存起来，并将所有都大于该需要插入的无序数的数后移 50             int j=i-1; 51             while(j>=0&&a[j]>temp)//从后往前扫描（j>=0是边界条件），判断已排序的数是否大于需要插入的无序数 52             { 53                 a[j+1]=a[j];//如果不是合适的位置就往后移动，腾出位置出来 54                 j--; 55             } 56             a[j+1]=temp;//找到了合适的位置，执行插入 57         } 58     } 59  60  } 61  62 //3、归并排序O(nlog(n)) 63 void MeageSort(int *result,int* a,int len1,int* b,int len2) 64 { 65     if(a==NULL||b==NULL||len1<=0||len2<=0) 66         return ; 67     int i=0,j=0; 68     while(i<len1&&j<len2) 69     { 70         if(a[i]<b[j])//比较两个指针指向的元素的大小 71         { 72             *(result++)=a[i]; 73             i++; 74         } 75         else 76         { 77             *(result++)=a[j]; 78             j++; 79         } 80     } 81     if(i<len1)//若序列1比序列2长，将序列1剩下的元素都复制到合并的空间中 82     { 83         while(i<len1) 84         { 85             *(result++)=a[i++]; 86         } 87     } 88     if(j<len2)//若序列2比序列1长，将序列2剩下的元素都复制到合并的空间中 89     { 90         while(j<len2) 91         { 92             *(result++)=b[j++]; 93         } 94     } 95  96     //for (int i=0;i<15;i++) 97     //    cout<<*(--result)<<" "; 98     //cout<<endl; 99 100 }101 102 //4、桶排序O(n)103  //桶排序用到插入排序(O(n*n))104 void InsertSort(vector<int>&a,const int len)105  {106 107     for(int i=1;i<len;i++)//扫描无序的数组108     {109         //记住：将第一个数作为已排序的数，从第二个数开始所有的数作为无序的数110         if(a[i-1]>a[i])//跟已排序好的数进行比较，找出合适的位置111         {        112             int temp= a[i];//将需要插入的无序数保存起来，并将所有都大于该需要插入的无序数的数后移113             int j=i-1;114             while(j>=0&&a[j]>temp)//从后往前扫描（j>=0是边界条件），判断已排序的数是否大于需要插入的无序数115             {116                 a[j+1]=a[j];//如果不是合适的位置就往后移动，腾出位置出来117                 j--;118             }119             a[j+1]=temp;//找到了合适的位置，执行插入120         }121     }122 123  }124 125 //由于桶排序需要将数据分成n等份的范围，每个范围的个数不一样，因此每个桶里面装的数的个数不相同，126 //因此选用容器作为桶的数据结构127 void BucketSort(vector<int> &result,int *Data,int len)128 {129     if(Data=http://www.mamicode.com/=NULL||len<=0)130         return ;131     //求原始数据的最大值与最小值132     int max_value=http://www.mamicode.com/Data[0];133     int min_value=http://www.mamicode.com/Data[0];134     for (int i=0;i<len;i++)135     {136         if(Data[i]>max_value)137             max_value=http://www.mamicode.com/Data[i];138         if(Data[i]<min_value)139             min_value=http://www.mamicode.com/Data[i];140     }141     //将数据分成n等份范围的桶142     int k=(max_value-min_value+1)/10+1;//10个桶范围143     vector<int > Bucket[10];144     //将数据分别装入相应的桶中145     for (int i=0;i<len;i++)146     {147         for(int j=0;j<10;j++)148         {149             if(Data[i]<min_value+(j+1)*k)150             {151                 Bucket[j].push_back(Data[i]);152                 break;//将某数放进桶内后进行下一个数153             }154         }155     }156     //分别对每一个桶内部进行排序，选用的方法是插入排序157     for (int i=0;i<10;i++)158     {159         InsertSort(Bucket[i],Bucket[i].size());160     }161     //依次输出每一个桶中的元素162     for(int i=0;i<10;i++)163     {164         for (vector<int>::size_type it=0;it<Bucket[i].size();it++)165         {166             result.push_back(Bucket[i][it]);167             //cout<<Bucket[i][it]<<" ";168         }169     }170 171 }172 173 //5、基数排序 O(max) max是最大值的位数174 int GetPos(int a,int pos)175 {176     int temp=1;177     for (int i=1;i<pos;i++)178         temp*=10;179     return (a/temp)%10;180 }181 182 183 void RadixSort(int *a,int len,int pos)184 {185     if(a==NULL||len<=0)186         return ;187     vector<int> temp[10];//10表示十进制188 189     //将数据放入桶中190     for (int i=0;i<len;i++)191     {192         //a[i]%10表示的是0-9的数193         temp[GetPos(a[i],pos)].push_back(a[i]);194     }195 196     //按桶的顺序输出数据197     for(int i=0;i<10;i++)198     {199         for (vector<int>::size_type it=0;it<temp[i].size();it++)200         {201             *(a++)=temp[i][it];202         }203     }204 }205 206 void RadisSort( int *a,int len)207 {208     if(a==NULL||len<=0)209         return ;210     int max=a[0];211     for(int i=0;i<len;i++)//求出最大值，就可以知道需要排序的次数，即排序的次数等于最大值的位数212     {213         if(a[i]>max)214             max=a[i];215     }216     int pos=1;//用来指定按哪一位来排序，最初是右边第一位217     do218     {219         //RadixSort(a,len,pos);//也可以采用函数调用的方式，避免调整指针的指向，因为在调用函数时，指针进行了复制，原始指针并没有改变220 221         vector<int> temp[10];//10表示十进制222 223         //将数据放入桶中224         for (int i=0;i<len;i++)225         {226             //a[i]%10表示的是0-9的数227             temp[GetPos(a[i],pos)].push_back(a[i]);228         }229 230         //按桶的顺序输出数据231         for(int i=0;i<10;i++)232         {233             for (vector<int>::size_type it=0;it<temp[i].size();it++)234             {235                 *(a++)=temp[i][it];//这里要注意修改了指针本身的值236             }237         }238         //因此这里要重新调整指针指向第一个元素239         for(int i=0;i<len;i++)//求出最大值，就可以知道需要排序的次数，即排序的次数等于最大值的位数240         {241             a--;242         }243 244         pos++;245     }246     while(max=max/10);247 248 }249 250 251 252 //////////////以下是不稳定的排序//////////////////////////////////253 //6、选择排序O(n*n)254 void swap(int &a,int&b)255 {256     int temp;257     temp=a;258     a=b;259     b=temp;260 }261 void SelectSort(int *a,int len)262 {263     if(a==NULL||len<=0)264         return ;265     for (int i=0;i<len;i++)//需要选择n次266     {267         //a[i]每次选择的临时选择的最小值268         //将临时最小值跟后面的数进行比较，判断是否是真的最小值269         for(int j=i;j<len;j++)270         {271             if(a[j]<a[i])//如果发现比最小值还小的元素则进行交换272                 swap(a[i],a[j]);273         }274     }275 }276 277 //7、希尔排序 O(n*n)278 279 void ShellSort(int *a,int len)280 {281     if(a==NULL||len<=0)282         return ;283     for (int i=len/2-1;i>=1;i--)//控制增量的循环284     {285         for (int j=i;j<len;j=j+i)//控制需要插入元素的个数286         {287             int temp=a[j];//待插入的元素288             int k=j-i;289             if(a[k]>temp)290             {291                 while(k>=0&&a[k]>temp)//查找合适的位置292                 {293                     a[k+i]=a[k];//按照增量的方式，将大的数按照增量的大小往后移增量个位置294                     k=k-i;//按照增量的方式递减295                 }296                 //找到合适的位置后，执行插入操作297                 a[k+i]=temp;298             }299         }300     }301 }302 303 //8、快速排序304 305 void QuickSort(int *a,int left,int right)306 {307     if(a==NULL||left<0||right<0)308         return ;309     int i=left,j=right;310     if(left<right)311     {312         //每次都是取第一个数来作为基准，并把它拿出来，腾出一个空位用作排序313         int temp=a[i];//这里可以改进：就是选取中值或平均值作为基准，只需将它们跟第一个数进行交换位置即可，在按照相同的办法进行314         while(i<j)//当i=j时，表明一次排序已经结束，此时对应的i的位置就是315         {316             //由于开始状态是第一个位置作为第一个空位子317             //从右向左找出比基准小的数318             while(i<j&&a[j]>=temp)//若退出循环就是找到了比基准小的数319             {320                 j--;321             }322             if(i<j)323             {324                 a[i]=a[j];//发现右边存在比基准小的数，则将右边的数放到左边来，留下一个位置325             }326             //由于a[j]是右边留下的一个位置，因此可以从左边找出一个比基准大的数来填327             //从左向右找出比基准大的数328             while(i<j&&a[i]<=temp)//若退出循环就是找到了比基准大的数329             {330                 i++;331             }332             if(i<j)333             {334                 a[j]=a[i];335             }336         }337         //此时i表示原来第一个元素应该放置的正确的位置338         a[i]=temp;//将原来假设第一个位置放到他正确的位置上339         ////一次排序结束，即已经将基准值放到正确的位置上了，下面是递归排序左右两边的序列340         QuickSort(a,left,i-1);341         QuickSort(a,i+1,right);342     }343 }344 345 //9、堆排序346 //通过比较二叉树父节点和左右节点的大小来调整347 void HeapAdjust(int *a,int i,int size)  //调整堆 i>=1,size是序列长度348 {349     int lchild=2*i;       //i的左孩子节点序号 350     int rchild=2*i+1;     //i的右孩子节点序号 351     int max=i;            //父节点 352     if(i<=size/2)          //如果i是叶节点就不用进行调整 353     {354         //判断父节点和左右之节点的大小，找出最大值355         if(lchild<=size&&a[lchild]>a[max])356         {357             max=lchild;358         }    359         if(rchild<=size&&a[rchild]>a[max])360         {361             max=rchild;362         }363         //如果最大值不是父节点364         if(max!=i)365         {366             swap(a[i],a[max]);//则进行交换367             //继续比较，直到所有的父节点都比较完为止368             HeapAdjust(a,max,size);//由于max的值没变，因此最大值就是根节点  369         }370     }        371 }372 373 void BuildHeap(int *a,int size)    //建立堆 374 {375     //由于需要确保最后根节点是最大值，因此是从下往上开始建堆376     for(int i=size/2;i>=1;i--)    //非叶节点最大序号值为size/2 377     {378         HeapAdjust(a,i,size);379         for(int i=1;i<=10;i++)380             cout<<a[i]<<" ";381         cout<<endl;382     }    383 } 384 385 void HeapSort(int *a,int size)    //堆排序 386 {387     BuildHeap(a,size);//首先建堆388     //再排序389     for(int i=size;i>=1;i--)390     {//每次将最大值放入最后一个位置中，对剩下的进行调整391         swap(a[1],a[i]);//交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面 392         HeapAdjust(a,1,i-1);//重新调整堆顶节点成为大顶堆393     }394 } 395 396 397 398 int _tmain(int argc, _TCHAR* argv[])399 {400     //int a[10]={0,11,21,31,41,56,6,7,8,9};401     //int b[5]={1,2,3,4,5};402     //cout<<"排序之前的值："<<endl;403     //for (int i=0;i<10;i++)404     //    cout<<a[i]<<" ";405     //cout<<endl;406     //vector<int> c;407     //MeageSort(c,a,10,b,5);408 409     //BucketSort(c,a,10);410     //RadisSort( a,10);411 412     //cout<<"排序之后的值："<<endl;413     //for (int i=0;i<10;i++)414     //    cout<<a[i]<<" ";415     //cout<<endl;416     /*417     float a=1.0f;418     cout<<sizeof(a)<<endl;419     cout<<(int)a<<endl;420     cout<<&a<<endl;421     cout<<(int &)a<<endl;422     cout<<boolalpha<<((int)a==(int&)a)<<endl;423     424     float b=0.0f;425     cout<<sizeof(b)<<endl;426     cout<<(int)b<<endl;427     cout<<&b<<endl;428     cout<<(int &)b<<endl;429     cout<<boolalpha<<((int)b==(int&)b)<<endl;430     431     int a[10]={0,11,21,31,41,56,6,7,8,9};432     for (int i=0;i<10;i++)433         cout<<a[i]<<" ";434     cout<<endl;435     QuickSort(a,0,9);436     for (int i=0;i<10;i++)437         cout<<a[i]<<" ";438          //int a[]={0,16,20,3,11,17,8};*/439     //这里需要注意，对排序是从a[1]开始排序，因此，待排序的数要从a[1]开始440     int a[11]={0,11,21,31,41,56,6,7,8,9,10};441     HeapSort(a,10);442     for(int i=1;i<=10;i++)443         cout<<a[i]<<" ";444     cout<<endl;445   446     return 0;447 }