7种排序 C++实现

在看了morewindows的白话经典算法的排序教程后，我逐个从简单到难用C++ 来实现了一遍，增加自己的理解和记忆，以下是源代码和测试结果，代码关键部分有注释：

#include 
  
   
using namespace std;

// todo:所有排序写成一个继承模板算法类，这样就不仅仅是支持int的排序了

// 1.1原始冒泡算法，排序出一个逐渐增长的数组
class BubblingSort1  
{
public:
	BubblingSort1(int arr[], int num): //num 是待排序的数组的元素个数 
	  _arr(arr),
      _num(num)
	{
	}

	void sort()
	{
		for (int i=0;i<_num;i++)
		{
			for (int j=1;j<_num-i;j++)// 因为外循环经过一次，那么无序数组末尾就冒泡出一个数字来占用了一个位置，成为有序的一个
			{
				if (_arr[j-1]>_arr[j]) // 数组里相邻的数值进行比较
				{
					swap(_arr[j-1],_arr[j]);// C++
   系统文件自带的常用函数
				}
			}
		}

	}

	~BubblingSort1();

private:
	int* _arr;
	int _num;
};


// 1.2优化后的冒泡算法
class BubblingSort2  
{
public:
	BubblingSort2(int arr[], int num): //num 是待排序的数组的元素个数 
	  _arr(arr),
	  _num(num)
	  {
	  }
	  
	  void sort()
	  {
		  bool isSorted = false; // 假如一次外部循环无序集合相邻的一次都没交换，那说明这个无序集合已经有序了，可以不用再继续循环了。

		  for (int i=0; i < _num && isSorted==false; i++)
		  {
			  isSorted = true;
			  for (int j=1;j<_num-i;j++)// 因为外循环经过一次，那么无序数组末尾就冒泡出一个无序中最大的数字来占用了一个位置，成为有序的一个
			  {
				  if (_arr[j-1]>_arr[j]) // 数组里相邻的数值进行比较
				  {
					  swap(_arr[j-1], _arr[j]);// C++系统文件自带的常用函数
					  isSorted = false;
				  }
			  }
		  }
		  
	  }
	  
	  ~BubblingSort2();
	  
private:
	int* _arr;
	int _num;
};

// 1.3进一步优化后的冒泡算法
class BubblingSort3  
{
public:
	BubblingSort3(int arr[], int num): //num 是待排序的数组的元素个数 
	  _arr(arr),
		  _num(num)
	  {
	  }
	  
	  void sort()
	  {
		  int swapPos = _num; 
		 
		  for (int i=0; i < _num && swapPos !=0 ; i++)
		  {
			  int tmp = swapPos;
			  swapPos = 0;
			  for (int j=1; j < tmp; j++)
			  {
				  if (_arr[j-1] > _arr[j])// 数组里相邻的数值进行比较
				  {
					  swap(_arr[j-1], _arr[j]);// C++系统文件自带的常用函数
					  swapPos = j;
				  }
			  }
		  }
		  
	  }
	  
	  ~BubblingSort3();
	  
private:
	int* _arr;
	int _num;
};


// 2.插入排序使数组增序排列
class InsertionSort
{
public:
	InsertionSort(int arr[], int num): //num 是待排序的数组的元素个数 
	  _arr(arr),
	  _num(num)
	  {
	  }
	~InsertionSort();

	void sort()
	{
		int i,j;
		for (i=1;i<_num;i++)
		{
			int tmp = _arr[i];    // 待排序的值
			if (tmp >= _arr[i-1]) // 既然比有序区域的最大值都还大，那么就别循环了，什么也不要动,待排序的值就暂时放在原位置，所以说直接插入排序效率受到数组原有排序的影响大
			{
				continue;
			}
			for (j=i-1;j>=0 && tmp < _arr[j];j--) // 有时可以在for里用&&符号可以避免在循环内部用if，使之代码更加简洁
			{
				_arr[j+1] = _arr[j]; // 待排序的数字更小则往后推动
			}
			_arr[j+1] = tmp;
		}
	}
private:
	int* _arr;
	int _num;

};

// 3.希尔排序（分组的直接插入排序，即跳着插）使之增序排列
class ShellSort
{
public:
	ShellSort(int arr[], int num): //num 是待排序的数组的元素个数 
	  _arr(arr),
	  _num(num)
	  {
	  }
	~ShellSort();

	void sort()  // 不能误认为有3重for，复杂度就是o（n的三次方）
	{
		int gap;
		int i,j;

		for (gap = _num/2; gap >0; gap/=2 ) // 初始增量设置为数组长度的一半,直到为1就是插入排序了
		{		
			for (i=gap;i<_num;i+=gap)   // 在gap间断的集合里，从第二个数据开始插入，第一个数据不管间断多少都是_arr[0]
			{
				int tmp = _arr[i];      // 待排序的值
				if (tmp >= _arr[i-gap]) // 既然比有序区域的最大值都还大，那么就别循环下去了，什么也不要动,待排序的值就暂时放在原位置，所以说希尔排序效率受到数组原有排序的影响大，如果已经有序，则复杂度最好，就是0（n）的一个外部循环
				{
					continue;
				}
				for (j=i-gap; j>=0 && tmp<_arr[j]; j-=gap) // 在for里用&&符号可以避免在循环内部用if，使之代码更加简洁
				{
					_arr[j+gap]=_arr[j]; // 往后移动
				}
				_arr[j+gap] = tmp; // 插入正确位置
			}
		}

	}
private:
	int* _arr;
	int _num;
};

// 4.选择排序 （使之递增）直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接播放排序是将无序区的第一个元素直接插入
//   到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。


class SelectSort
{
public:
	SelectSort(int arr[], int num): //num 是待排序的数组的元素个数 
	  _arr(arr),
	  _num(num)
	  {
	  }
	~SelectSort();

	void sort()
	{
		int i,j;
		for (i=0; i<_num; i++)
		{	
			int minIndex = i;
			for (j=i+1;j<_num;j++)
			{
				if (_arr[minIndex] > _arr[j])
				{
					minIndex = j;
				}
			}
			swap(_arr[i], _arr[minIndex]); // 很有可能i = minIndex 的,swap 是模板函数，不止支持整数的交换
		}

	}

private:
	int* _arr;
	int _num;
};

// 5.归并排序(分治法)
class MergeSort
{
public:
	MergeSort(int arr[], int num): // num 是待排序的数组的元素个数 
	  _arr(arr),
	  _num(num)
	  {
	  }
	~MergeSort();

	void sort()
	{
	//	int tmp[_num];              // 临时数组不能通过编译，因为数组在编译时要确定大小后才能分配空间，所以用指针代替
		int* tmp = new int[_num];   //  一个外部递归处的临时大数组空间，避免在内部一直分配和释放小数组空间
		recursiveSort(0, _num-1, tmp);
		delete []tmp;   
	}

private:
	void recursiveSort(int first, int last , int tmp[])
	{
		if (first < last)
		{
			int mid = (first + last) / 2;
			recursiveSort(first, mid, tmp); // 左边有序
			recursiveSort(mid+1, last, tmp);// 右边有序,注意下mid要加1.
            mergeArray(first,mid,last,tmp); // 左右合并
		}
	}
    void mergeArray(int first, int mid, int last, int tmp[])
	{
		int i = first,j = mid + 1;
		int k=0;

		while (i<=mid && j<=last)
		{
			if (_arr[i]<=_arr[j])
			{
				tmp[k++]=_arr[i++];
			}
			else
			{
				tmp[k++]=_arr[j++];
			}
		}

		// 退出while循环了，说明要么i到达了mid，要么是j到达了last，或者同时，此时只需要将剩下的直接补到tmp数组的末尾
		while(i<=mid)
		{
			tmp[k++]=_arr[i++];
		}
		while(j<=last) 
		{
            tmp[k++]=_arr[j++];
		}

		// 很容易忽略的一步
		for (i=0; i
   
    = hole) { j--; } if (i
    
     = hole) { j--; } if (i
     
      =1; i--) { swap(_arr[i], _arr[0]); // minHeapFixDown(0,i); // 经过交换后就不符合堆的规则了，所以从根节点开始开始向下进行调准，把较为小的往上移动 } } private: void minHeapFixDown(int i, int n) // 把较小的往上移动,注意第二个参数是指这个（剩下的）堆的最大索引 { int tmp, j=2*i+1; tmp = _arr[i]; while (j
      
       =0; i-- ) { minHeapFixDown(i,_num-1); } } private: int* _arr; int _num; }; int main() { // *******************1.冒泡排序1,而2和3忽略测试了******************* cout<<"冒泡排序测试"<
       
        sort(); int i; for (i=0; i< sizeof(arr1)/sizeof(int); i++) { cout<
        
         sort(); for (i=0; i< sizeof(arr2)/sizeof(int); i++) { cout<
         
          sort(); for (i=0; i< sizeof(arr3)/sizeof(int); i++) { cout<
          
           sort(); for (i=0; i< sizeof(arr4)/sizeof(int); i++) { cout<
           
            sort(); for (i=0; i< sizeof(arr5)/sizeof(int); i++) { cout<
            
             sort(0, sizeof(arr6)/sizeof(int) - 1 ); for (i=0; i< sizeof(arr6)/sizeof(int); i++) { cout<
             
              sort(); // 外部调用递归 for (i=0; i< sizeof(arr7)/sizeof(int); i++) { cout<