排序算法总结（C++语言）

//按名次排序
template 
  
   
void Rearrange(T a[],int n,int r[])
{
	//按序重排数组a中的元素，使用附加数组u
	T *u=new T[n+1];
	//在u中移动到正确的位置
	for(int i=1;i
   
     void SelectionSort(T a[],int n) { //对数组a[0:n-1]中的n个元素进行排序 for(int size=n;size>1;size--) { int j=Max(a,size); Swap(a[j],a[size-1]); } } //冒泡排序 template 
    
      void Bubble(T a[],int n) { //把数组a[0:n-1]中最大的元素冒泡移到右边 for(int i=n;i>1;i--) for(int j=0;j
     
      a[j+1]) Swap(a[j],a[j+1]); } //向一个有序数组中插入元素 template 
      
        void Insert(T a[],int& n,const T& x) { //向有序数组a中插入元素x //假定a的大小超过n int i; for(i=n-1;i>=0&&x
       
         void SelectionSort(T a[],int n) { //及时终止的选择排序 bool sorted=false; for(int size=n;!sorted&&(size>1);size--) { int pos=0; sorted=true; //找最大元素 for(int i=1;i
        
          void BubbleSort(T a[],int n) { //及时终止的冒泡排序 bool swapped=FALSE; for(int i=n;i>1&&!swapped;i--) { swapped=true; for(int j=0;j
         
          a[j+1]) { Swap(a[j],a[j+1]); swapped=false; } } } //插入排序 template 
          
            void InsertionSort(T a[],int n) { for(int i=1;i
           
            =0&&t
            
              void shellsort(vector
             
              & a) { for(int gap = a.size()/2;gap>0;gap /= 2) for(int i = gap;i < a.size();i++) { T tmp = a[i]; int j = i; for(j=i;j>=gap&&tmp
              
                void HeapSort(T a[],int size,int n) {//利用堆排序算法对a[1:n]进行排序 //创建一个最大堆 // MaxHeap
               
                 H(1); // H.Initialize(a,n,n); delete [] heap; heap = a; currentsize = size; for(int i = currentsize/2;i>=1;i--) { T y = heap[i]; int c = 2*i; while(c<=currentsize) { if(c
                
                  heap[c]) break; heap[c/2] = heap[c]; c*=2; } heap[c/2] = y; } //从最大堆中逐个抽取元素 T x; for(int i = n-1;i >= 1;i--) { H.DeleteMax(x); a[i+1] = x; } //在堆的析构函数中保存数组a H.Deactivate(); } //快速排序(递归方法) void quickSort(T a[],int l,int r) { if (l > r) return; if (r-l
                 






                  pivot); if(i>=j) break; Swap(a[i],a[j]); } a[l]=a[j]; a[j]=pivot; quickSort(a,l,j-1); quickSort(a,j+1,r); } //快速排序（堆栈方法） void swap(int *a,int *b) { int t = *a; *a = *b; *b = t; } struct Param { int *a; int n; }; void sort(int *a,int n) { stack
                   sp; Param pm; for( ; ; ) { if (n <= 2)//不超过两个数据就处理完毕 { if(n == 2 && a[1] < a[0]) swap(a,a+1); if (sp.empty()) break;//如果栈中没有待排序数据就退出 pm = sp.top();//如果栈中有待排序数据就取出最后入栈的一段 sp.pop(); a = pm.a; n = pm.n; continue; } swap(a,a+(n>>1));//把中间的那个数据交换到最前面 int pivot = *a;//以现在最前面的数据作为分界值 int *l = a+1;//左边第二个数据 int *r = a+n-1;//右边最后一个数据 while (l < r) { //小于分界值的留在左边，遇到不小于的停止 while(l < r && *l < pivot) l++; //不小于分界值的留在右边，遇到小于的停止 while(r > a && *r >= pivot) r--; //交换这两个数据 if(l < r) swap(l,r); } //把分界值交换回中间位置 if(*a > *r) swap(a,r); //对左右两组分别非递归排序 pm.a = r+1; pm.n = n-(r-a+1); sp.push(pm); n = r-a; } } //一种分而治之排序算法 template
                  
                    MergeSort(T a[],int left,int right) { if(left
                   
                     void MergeSort(T a[],int n) { //使用归并排序算法对a[0:n-1]进行排序 T*b=new T[n]; int s=1;//段的大小 while (s
                    
                      void MergePass(T a[],T b[],int s,int n) { int i=0; while (i<=n-2*s) { Merge(a,b,i,i+s-1,i+2*s-1); i=i+2*s; } if(i+s
                     
                       void Merge(T a[],T b[],int l,int m,int r) { int i=l,//第一段的游标 j=m+1,//第二段的游标 k=l;//结果的游标 //只要在段中存在i和j，则不断进行合并 while (i<=m&&j<=r) { if(a[i]<=a[j]) b[k++]=a[i++]; else b[k++]=a[j++]; } //考虑余下的部分 if(i>m) for(int q=j;q<=r;q++) b[k++]=a[q]; else for(int q=i;q<=m;q++) b[k++]=a[q]; }