本文共 3379 字，大约阅读时间需要 11 分钟。

归并排序

class Solution {   public:	//合并两个有序子序列	void merge(vector
   
    & A,int begin,int mid,int end,vector
    
     & temp)	{   		//第一个子序列起点和第二个子序列起点，以及temp数组起点		int i = begin, j = mid + 1, k = 0;		while (i <= mid && j <= end)		{   			if (A[i] < A[j])				temp[k++] = A[i++];			else				temp[k++] = A[j++];		}		//对剩余没合并的部分进行归并		while (i <= mid)			temp[k++] = A[i++];		while (j <= end)			temp[k++] = A[j++];		//最后把temp里面存放的合并后为有序的左右序列倒回原数组a	   //注意a的起点		for (int i = 0; i < k; i++)			A[begin + i] = temp[i];	}	//归并排序	void mergeSort(vector
     
      & A,int begin,int end)	{   		static vector
      
        temp(A.size(), 0);		//拆分到只剩一个元素的极小序列,结束递归		if (begin < end)		{   			int mid = (begin + end) / 2;			//将数组左半部分合并成有序序列			mergeSort(A, begin, mid);			//将数组的右半部分合并成有序序列			mergeSort(A, mid + 1, end);			//将两个有序序列合并			merge(A, begin, mid, end, temp);		}	}    void sortIntegers2(vector
       
        & A)     {   		mergeSort(A, 0, A.size()-1);    }};
       
      
     
    
   

归并排序迭代版本

class Solution {   public:	//合并两个有序子序列	void merge(vector
   
    & A,int begin,int mid,int end,vector
    
     & temp)	{   		//第一个子序列起点和第二个子序列起点，以及temp数组起点		int i = begin, j = mid + 1, k = 0;		while (i <= mid && j <= end)		{   			if (A[i] < A[j])				temp[k++] = A[i++];			else				temp[k++] = A[j++];		}		//对剩余没合并的部分进行归并		while (i <= mid)			temp[k++] = A[i++];		while (j <= end)			temp[k++] = A[j++];		//最后把temp里面存放的合并后为有序的左右序列倒回原数组a	   //注意a的起点		for (int i = 0; i < k; i++)			A[begin + i] = temp[i];	}	//归并排序	void mergeSort(vector
     
      & A, int first, int last)	{   		 vector
      
        temp(A.size(), 0);		//迭代的实现是直接从最小子序列(含一个元素)开始往上两两合并		int k = 1;//子序列长度		int Last = 0;		int First = 0;		int mid = 0;		while (k < last)		{   			First = 0;			//3.剩余大于等于两个子序列的元素个数			while (First <= (last - 2 * k + 1))//加一的原因是因为下标从0算起			{   				mid = First + k - 1;				Last = First + 2 * k - 1;				merge(A, First, mid, Last, temp);				First += 2 * k;			}			//当剩下的没有合并处理过的元素数量不足2k，即无法构成两个子序列进行合并操作时，要分类处理		   //1.剩下小于等于一个子序列的元素个数			if (last - First <= k)			{   				mid = First + (last - First) / 2;				merge(A, First, mid, last, temp);			}			//2.剩下大于一个小于两个的子序列元素个数			else			{   				mid = First + k - 1;;				merge(A, First, mid, last, temp);			}			k *= 2;		}		//说明此时是特殊奇数情况，数组末尾还单着一个元素没有于前面一个完整的子序列合并		if (First == last)		{   			merge(A, first, last - 1, last, temp);		}	}	void sortIntegers2(vector
       
        & A) 	{   		mergeSort(A, 0, A.size() - 1);	}};
       
      
     
    
   

快速排序

class Solution {   public:    void sortIntegers2(vector
   
    & A) {           if (A.size() <= 1) return;        quick_sort(A,0,A.size() - 1);    }	//快速排序:end填入的是数组中最后一个元素的下标	void quick_sort(vector
    
     & r, int begin, int end)	{   		int pos = 0;//接收当前键值的在数组中下标的位置		if (begin < end)		{   			pos = swap_sort(r, begin, end);			quick_sort(r, begin, pos - 1);			quick_sort(r, pos + 1, end);		}	}	//交换排序---每一次返回当前键值的在数组中的下标	int swap_sort(vector
     
      & r, int begin, int end)	{   		//我们设置begin位置的元素为键值		int i = begin;		int j = end;		//当退出循环时，i==j，i和j都指向当前键值所在下标位置		while (i < j)		{   			while (i < j && r[i] <= r[j])			{   				j--;			}			if (i < j)			{   				swap(r[i], r[j]);//交换完后，r[j]的位置存储的是键值				i++;//调整i的位置			}			while (i < j && r[j] >= r[i])			{   				i++;			}			if (i < j)			{   				swap(r[i], r[j]);//交换完后，r[i]的位置存储的是键值				j--;//调整j的位置			}		}		return i;	}};
     
    
   

转载地址：http://lygqz.baihongyu.com/