- //选择排序法
- template<typename T>
- void selectSort(T * arr,int n)
- {
- for(int i=0;i<n;i++)
- {
- int min=i;
- for(int j=i;j<n;j++)
- {
- //内循环找最小的那个值
- if(arr[j]<arr[min])
- {
- min=j;
- }
- }
- if(i!=min)
- {
- swap(arr[i],arr[min]);
- }
- }
- }
- //插入排序版本1,性能略差
- void insertSort1(int * arr,int n)
- {
- for(int i=1;i<n;i++)
- {
- for(int j=i;j>0&&arr[j]<arr[j-1];j--)
- {
- swap(arr[j],arr[j-1]);
- }
- }
- }
- void __insertSort(int * arr,int left,int right)
- {
- for(int i=left;i<=right;i++)
- {
- int data=arr[i];
- int j=i;
- for(;j>0&&arr[j-1]>data;--j)
- arr[j]=arr[j-1];
- arr[j]=data;
- }
- }
- //插入排序版本2,性能强多了
- void insertSort2(int * arr,int n)
- {
- __insertSort(arr,0,n);
- }
- //归并排序核心逻辑部分,这里需要将arr[left]-arr[mid]的区域和arr[mid+1]-arr[right]进行合并
- template<typename T>
- void __merge(T* arr,int left,int mid,int right)
- {
- T arrns[right-left+1];//相当于是arr[数组长度]的情况,创建一个新的数组用来存放合并后的结果
- for(int i=left;i<=right;i++)
- {
- //先将数据都拷贝到新的数组中
- arrns[i-left]=arr[i];
- }
- //左边数组的开始位置
- int l=left;
- //右边数组的开始位置
- int r=mid+1;
- for(int i=left;i<=right;i++)
- {
- //如果左边的数组已经全部合并完了,则将右边的下一个节点直接添加上去
- if(l>mid)
- {
- arr[i]=arrns[r-left];
- r++;
- continue;
- }
- //如果右边的数组已经全部合并完了,则将左边的下一个节点添加上去
- else if(r>right)
- {
- arr[i]=arrns[l-left];
- l++;
- continue;
- }
- //如果左边列表当前节点小于右边列表当前节点。则将左边的节点添加上去
- if(arrns[l-left]<arrns[r-left])
- {
- arr[i]=arrns[l-left];
- l++;
- }
- else
- {
- //否则将右边的节点添加上去
- arr[i]=arrns[r-left];
- r++;
- }
- }
- }
- //归并排序私有函数
- template<typename T>
- void __mergeSort(T *arr,int left,int right)
- {
- if(left>=right)
- return;
- int m=(left+right)/2;
- __mergeSort(arr,left,m);
- __mergeSort(arr,m+1,right);
- __merge(arr,left,m,right);
- }
- //归并排序优化版本2
- template<typename T>
- void __mergeSort2(T *arr,int left,int right)
- {
- //将数量小于15的分治排序使用插入排序算法进行处理
- if(right-left<=15)
- {
- __insertSort(arr,left,right);
- return;
- }
- int m=(left+right)/2;
- __mergeSort(arr,left,m);
- __mergeSort(arr,m+1,right);
- //如果不符合说明右边的第一个值比左边的最后一个值都大,则可以无需归并
- if(arr[m]>arr[m+1])
- {
- __merge(arr,left,m,right);
- }
- }
- //归并排序
- void mergeSort(int* arr,int n)
- {
- __mergeSort(arr,0,n-1);
- }
- //归并排序自底向上
- void mergeSortByU(int* arr,int n)
- {
- for(int sz=1;sz<=n;sz+=sz)
- {
- for(int sk=0;sk+sz<n;sk+=sz+sz)
- {
- __merge(arr,sk,sk+sz-1,min(sk+sz+sz-1,n-1));
- }
- }
- }
- //单路快排关键部分
- template<typename T>
- int __partition(T *arr,int left,int right)
- {
- //随机一个有效范围的值
- int idx=rand()%(right-left+1)+left;
- //将第一个值和随机的交换,这样避免了在近乎有序的情况下使用快排太慢的情况
- swap(arr[idx],arr[left]);
- T data=arr[left];
- int gidx=left;
- for(int i=left+1;i<=right;i++)
- {
- if(arr[i]>=data)
- swap(arr[++gidx],arr[i]);
- }
- swap(arr[left],arr[gidx]);
- return gidx;
- }
- //单路快排,快排的最初版本,效率还达不到我们的期望
- template<typename T>
- void __quickSortSig(T* arr,int left,int right)
- {
- //同样可以优化为当需要排序的长度小于15个时使用插入算法排序
- if(right-left<=15)
- {
- __insertSort(arr,left,right);
- return;
- }
- int idx=__partition(arr,left,right);
- __quickSortSig(arr,left,idx-1);
- __quickSortSig(arr,idx+1,right);
- }
- //快速排序,现今最快的排序,最开始的单路排序
- void quickSortSig(int* arr,int n)
- {
- srand(time(NULL));
- __quickSortSig(arr,0,n-1);
- }
- template<typename T>
- int __partition_double(T *arr,int left,int right)
- {
- //随机一个有效范围的值
- int idx=rand()%(right-left+1)+left;
- //将第一个值和随机的交换,这样避免了在近乎有序的情况下使用快排太慢的情况
- swap(arr[idx],arr[left]);
- T data=arr[left];
- int gtidx=left+1;
- int ltidx=right;
- while(true)
- {
- while(arr[gtidx]<data&>idx<=right)
- gtidx++;
- while(arr[ltidx]>data&<idx>=left+1)
- ltidx--;
- if(gtidx>ltidx)
- break;
- swap(arr[gtidx],arr[ltidx]);
- gtidx++;
- ltidx--;
- }
- swap(arr[left],arr[gtidx]);
- return gtidx;
- }
- //双路快排版本
- void __quickSortDouble(int* arr,int left,int right)
- {
- if(right-left<=10)
- {
- __insertSort(arr,left,right);
- return;
- }
- int idx=__partition_double(arr,left,right);
- __quickSortDouble(arr,left,idx-1);
- __quickSortDouble(arr,idx+1,right);
- }
- //快速排序,现今最快的排序,双路快排版本
- void quickSortDouble(int* arr,int n)
- {
- srand(time(NULL));
- __quickSortDouble(arr,0,n-1);
- }
- //三路快排版本
- template<typename T>
- void __quickSortThree(T* arr,int left,int right)
- {
- if(right-left<=15)
- {
- __insertSort(arr,left,right);
- return;
- }
- //随机一个有效范围的值
- int ridx=rand()%(right-left+1)+left;
- //将第一个值和随机的交换,这样避免了在近乎有序的情况下使用快排太慢的情况
- swap(arr[ridx],arr[left]);
- T data=arr[left];
- int gtidx=left; //left+1~gtidx 的值小于data
- int ltidx=right+1; //ltidx~right的值大于data
- int idx=left+1; //gtidx+1~idx的值等于data
- while(idx<ltidx)
- {
- if(arr[idx]<data)
- {
- swap(arr[idx],arr[gtidx+1]);
- gtidx++;
- idx++;
- }
- else if(arr[idx]>data)
- {
- swap(arr[idx],arr[ltidx-1]);
- ltidx--;
- }
- else
- {
- idx++;
- }
- }
- swap(arr[left],arr[gtidx]);
- __quickSortDouble(arr,left,gtidx-1);
- __quickSortDouble(arr,ltidx,right);
- }
- //三路快排法
- void quickSortThree(int* arr,int n)
- {
- srand(time(NULL));
- __quickSortThree(arr,0,n-1);
- }
来源: http://www.bubuko.com/infodetail-1952328.html