排序方法总结

这里面包含了所有常见的排序操作

1.性能等比较分析

2.代码实现

sort.h

 

//各种排序方法总结

#ifndef SORT_H
#define SORT_H

template<class T>
class Sort{
	public:
		void insertSort(T r[], int n);                  //直接顺序排序
		void shellSort(T r[], int n);                   //希尔排序
		void bubbleSort(T r[], int n);                  //起泡排序
		
		void quickSort(T r[], int first, int end);      //快速排序
		void selectSort(T r[ ], int n);                 //简单选择排序
		
		void heapSort(T r[ ], int n);                   //堆排序
		
		void mergeSort1(T r[ ], T r1[ ], int n );      //归并排序的非递归算法
		void mergeSort2(T r[], T r1[], T r2[],int s, int t);//归并排序的递归算法
	private:
		int partition(T r[], int first, int end);       //快速排序一次划分
		void sift(T r[], int n, int hole);              //筛选法调整堆
		void merge(T r[], T r1[], int s, int m, int t);//一次归并
		void mergePass(T r[ ], T r1[ ], int n, int h); //一趟归并
};
#endif

 sort.cpp

 

#include <iostream>
#include "sort.h"
using namespace std;

//直接顺序排序
template<class T>
void Sort<T>::insertSort(T r[], int n){
	if(n <= 0) return;
	int i, j;
	for(i=2; i<n; i++){
		r[0] = r[i];
		j = i-1;
		while(r[0]<r[j]){
			r[j+1] = r[j];
			j--;
		}
		r[j+1] = r[0];
	}
}                 

//希尔排序
template<class T>
void Sort<T>::shellSort(T r[], int n){
	if(n <= 0) return;
	int i,j,d;
	//增量d不断变化
	for(int d=n/2; d>0; d = d/2){
		//对于每个增量，都是直接插入排序
		for(i = d+1; i<n; i+=d){
			r[0] = r[i];
			j = i-d;
			while(r[0]<r[j] && j>0){
				r[j+d] = r[j];
				j-=d;
			}
			r[j+d] = r[0];
		}
	}
}                   
	
//起泡排序
template<class T>
void Sort<T>::bubbleSort(T r[], int n){
	T tmp = 0;					  //用于交换
	int exchanged = 1;		//记录是否发生交换
	int bound,pos = n-1;	//最后一次的交换位置
	while(exchanged){
		bound = pos;
		exchanged = 0;
		for(int j=0; j<bound; j++){
			if(r[j]>r[j+1]){
				tmp = r[j];
				r[j] = r[j+1];
				r[j+1] = tmp;
				pos = j;
				exchanged = 1;
			}
		}
	}
}                 

//快速排序一次划分
template<class T>
int Sort<T>::partition(T r[], int first, int end){
	T tmp;
	int i=first, j=end;
	while(i<j){
		while(r[i]<r[j] && i<j) j--;
		if(i<j){
			tmp = r[i];
			r[i] = r[j];
			r[j] = tmp;
			i++;
		}
		while(r[i]<r[j] && i<j) i++;
		if(i<j){
			tmp = r[i];
			r[i] = r[j];
			r[j] = tmp;
			j--;
		}
	}
	return i;
}       

//快速排序
template<class T>
void Sort<T>::quickSort(T r[], int first, int end){
	int k;
	if(first < end){
		k = partition(r, first, end);
		//对左右递归排序
		quickSort(r, first, k-1);
		quickSort(r, k+1, end);
	}
}      

//简单选择排序
template<class T>
void Sort<T>::selectSort(T r[ ], int n){
	T tmp;
	int i, pos;
	for(i=0; i<n; i++){
		pos = i;
		for(int j=i+1; j<n; j++){
			if(r[j] < r[pos]) pos = j; 
		}
		if(pos != i){
			tmp = r[pos];
			r[pos] = r[i];
			r[i] = tmp;
		}
	}
}                 

//筛选法调整堆
template<class T>
void Sort<T>::sift(T r[], int n, int hole){
	int child;
	T tmp = r[hole];
	for(; hole*2 <= n; hole = child){
		child = hole*2;
		if(child != n && r[child+1] < r[child]){//右子树
			child++;
		}
		//如果当前比hole小，交换
		if(r[child]<tmp){
			r[hole] = r[child];
		}else{
			break;
		}
	}
	//hole是最后交换的位置
	r[hole] = tmp;
}                 

//堆排序
template<class T>
void Sort<T>::heapSort(T r[ ], int n){
	for(int i=n/2; i>0; i--){
		sift(r, n, i);
	}
	//重复移除第一个元素，并重建堆
	while(n>0){
		r[0] = r[1];
		r[1] = r[n];
		r[n] = r[0];
		n--;
		sift(r, n, 1);
	}
} 

/*
//这个写的比较容易理解，非常好！！From v_july_v
template<class T>
void Sort<T>::sift(T heap[], int i, int len)  
{  
    int min_index = -1;  
    int left = 2 * i;  
    int right = 2 * i + 1;  
    T tmp;
    
    //反正就是找其左右子树小的，然后递归
    if (left <= len && heap[left] < heap[i])  
        min_index = left;  
    else  
        min_index = i;  
      
    if (right <= len && heap[right] < heap[min_index])  
        min_index = right;  
      
    if (min_index != i)  
    {  
        // 交换结点元素  
        tmp = heap[i];
        heap[i] = heap[min_index];
        heap[min_index] = tmp;  
          
        sift(heap, min_index, len);  
    }  
}  
  
// 建立小根堆  
template<class T>
void Sort<T>::buildHeap(T heap[], int len)  
{  
    if (heap == NULL)  
        return;  
      
    int index = len / 2;  
    for (int i = index; i >= 1; i--)  
        sift(heap, i, len);  
}  
*/                              

//一次归并(有序序列r(开始位置分别为s,m的两个序列),将合并结果放入r1)
template<class T>
void Sort<T>::merge(T r[], T r1[], int s, int m, int t){
	int i=s;
	int j=m+1;
	int k=s;
	while (i<=m && j<=t)
	{   
    if (r[i]<=r[j]) 
			 r1[k++]=r[i++];            //取r[i]和r[j]中较小者放入r1[k]
    else 
			 r1[k++]=r[j++]; 
	}
      if (i<=m) 
		  while (i<=m)                  //若第一个子序列没处理完，则进行收尾处理         
			  r1[k++]=r[i++]; 
      else  
		  while (j<=t)                  //若第二个子序列没处理完，则进行收尾处理        
			r1[k++]=r[j++]; 
}

//一趟归并
template<class T>
void Sort<T>::mergePass(T r[ ], T r1[ ], int n, int h){
	int i=0;
	int k;
   while (i<=n-2*h)                     //待归并记录至少有两个长度为h的子序列
   {
     merge(r, r1, i, i+h-1, i+2*h-1);
        i+=2*h;
   }
   if (i<n-h) 
	   merge(r, r1, i, i+h-1, n);       //待归并序列中有一个长度小于h
   else for (k=i; k<=n; k++)            //待归并序列中只剩一个子序列
        r1[k]=r[k];	
}

//归并排序的非递归算法
template<class T>
void Sort<T>::mergeSort1(T r[ ], T r1[ ], int n ){
	int h=1;
  int i;

  while (h<n)
  {
    mergePass(r, r1, n-1, h);           //归并
    h=2*h;
    mergePass(r1, r, n-1, h);
    h=2*h;
  }
  for(i=0;i<n;i++)
      cout<<r[i]<<" ";
  cout<<"\n";
}      

//归并排序的递归算法
template<class T>
void Sort<T>::mergeSort2(T r[], T r1[], T r2[],int s, int t){
	int m;
	if (s==t) 
	{
		r1[s]=r[s];

	}
    else 
	{ 
            m=(s+t)/2;
            mergeSort2(r, r2, r1, s, m);        //归并排序前半个子序列		
            mergeSort2(r, r2, r1, m+1, t);      //归并排序后半个子序列
            merge(r2, r1, s, m, t);             //将两个已排序的子序列归并 		
	}	 
}

 main.cpp

 

#include <iostream>
#include "sort.cpp"
using namespace std;

int main(){
	const int numv=11;                                //赋值
  int a[]={0,3,56,32,78,5,24,9,64,34,7};						//插入排序的时候a[0]是作为了哨兵
  int b[]={0,4,6,23,45,15,10,36,25,79,21};					//希尔排序的时候a[0]是作为了哨兵
  int c[]={38,23,56,2,79,42,93,29,6,5,57};
  int d[]={50,23,45,67,87,14,29,32,44,97,89};
  int e[]={8,6,1,48,37,63,39,74,52,26,49};
  int f[]={0,12,23,45,87,2,6,15,43,26,40};					//堆的第一个位置也是暂存
  int g[]={13,10,23,45,64,34,24,7,9,3,16};
  int h[]={34,23,54,76,12,13,14,11,78,8,9};
  int g1[numv];
  int h1[numv];
  int h2[numv];  

	Sort<int> s;
	int j;
	/*
  cout << "\n直接顺序排序前：" << "\n";
  for(int j=1;j<numv;j++)
	  cout<<a[j]<<" ";
  cout << "\n直接顺序排序结果为：" << "\n";
  s.insertSort(a,numv); 
  for(int j=1;j<numv;j++)
	  cout<<a[j]<<" "; 
	
  
  cout << "\n希尔排序前：" << "\n";
  for(j=1;j<numv;j++)
	  cout<<b[j]<<" ";
  cout << "\n希尔排序结果为：" << "\n";
  s.shellSort(b, numv);
  for(j=1;j<numv;j++)
	  cout<<b[j]<<" ";
	
  
  cout << "\n起泡排序前：" << "\n";
  for(int k=0;k<numv;k++)
	  cout<<c[k]<<" ";
  cout << "\n起泡排序结果为：" << "\n";
  s.bubbleSort(c, numv);
  for(int k=0;k<numv;k++)
	  cout<<c[k]<<" ";
  
  
  cout << "\n快速排序前：" << "\n";
  for(j=0;j<numv;j++)
	  cout<<d[j]<<" ";
  cout << "\n快速排序结果为：" << "\n";
  s.quickSort(d,0,numv-1);  
  for(int i=0;i<numv;i++)
     cout<<d[i]<<" ";
  cout<<"\n";
 
  
	
  cout << "\n简单选择排序前：" << "\n";
  for(j=0;j<numv;j++)
	  cout<<e[j]<<" ";
  cout << "\n简单选择排序结果为：" << "\n";
  s.selectSort(e,numv);
	for(j=0;j<numv;j++)
	  cout<<e[j]<<" ";
 
	
  cout << "\n堆排序前：" << "\n";
  for(j=0;j<numv;j++)
	  cout<<f[j]<<" ";
  cout << "\n堆排序结果为：" << "\n";
  s.heapSort(f, numv);
   for(j=1;j<numv;j++)
	  cout<<f[j]<<" ";
  */
  
  cout << "\n归并排序非递归算法前：" << "\n";
  for(j=0;j<numv;j++)
	  cout<<g[j]<<" ";
  cout << "\n归并排序非递归算法的结果为：" << "\n";
  s.mergeSort1(g, g1,numv );

  cout << "\n归并排序递归算法前：" << "\n";
  for(j=0;j<numv;j++)
	  cout<<h[j]<<" ";
  cout << "\n归并排序递归算法的结果为：" << "\n";
  s.mergeSort2(h,h1,h2, 0, numv-1);
  for(int i=0; i < numv; i++)
       cout<<h1[i]<<" ";
  cout<<"\n";
  
  return 0;
}