快速排序算法和归并排序算法

原理

参考链接：

https://www.cnblogs.com/seniusen/p/9810080.html

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html

源码（c++）

快速排序算法

#include<iostream>

using namespace std;

template<class T>
void QuickSort(T *a, const int left, const int right){
	if(left<right){
		
		//选枢轴划分
		int i = left;
		int j = right;	
		int pivot = a[left];
		
		while(i<j){
			//顺序很重要，要先从右边开始找(因为左边是枢纽)  后面有解释
			while(i<j && a[j]>=pivot){
				j--;
			}
			while(i<j && a[i]<=pivot){
				i++;
			}
			if(i<j){
				swap(a[i],a[j]);
			}
		}
		
		swap(a[left],a[j]);
		
		QuickSort(a,left,j-1);
		QuickSort(a,j+1,right);
	}
	
}

int main(){
	int a[]={4,5,1,9,7,6,2,3,8,0};
	//int a[]={1,3,5,0,9,4,2,8,7,6};
	QuickSort(a,0,9);
	for(int i=0; i<10; i++){
		cout<<a[i]<<endl;
	}
	return 0;
}

归并排序算法

#include<iostream>
#include<algorithm>

using namespace std;

template<class T>
void merge(T *list, T *mergeList, const int left, const int mid, const int right)
{
	int i = left;
	int j = mid+1;
	int k = 0;
	
	while(i <= mid && j <= right)
	{
		if(list[i] <= list[j])
		{
			mergeList[k] = list[i];
			i++;
			k++;
		}
		else
		{
			mergeList[k] = list[j];
			j++;
			k++;
		}
	}
	
	while(i <= mid)
	{
		mergeList[k] = list[i];
		i++;
		k++;	
	}
	
	while(j <= right)
	{
		mergeList[k] = list[j];
		j++;
		k++;
	}
	
	for(int m=0; m<k; m++)
	{
		list[left + m] = mergeList[m];
	}
}

template<class T>
void mergeSort(T *list, T *mergeList, const int left, const int right)
{
	if(left < right)
	{
		int mid = (left + right) / 2;
		
		mergeSort(list, mergeList, left, mid);
		mergeSort(list, mergeList, mid+1, right);
		merge(list, mergeList, left, mid, right);
	}
}

int main()
{
	int a[] = {23,47,81,95,7,14,39,55,62,74};
	int b[10] = {0};
	
	mergeSort(a, b, 0, 9);
	
	for(int i=0; i<10; i++)
	{
		cout<<a[i]<<" ";
	}
	return 0;
}

注意点

快速排序算法中，为什么一定要从基数（枢纽）对面先开始？

假设对如下进行排序：

如上图，6在左，9在右

假设：我们将6作为基数

从左边开始（与正确程序执行顺序正好相反）

while(i<j && a[i]<=pivot){
	i++;
}
while(i<j && a[j]>=pivot){
	j--;
}	//错误顺序

按照这个代码逻辑，走一遍，i会移动到 数字7 停下来 (此时因为 a[i]>pivot，循环退出)，而接着 j 会也会移动到 数字7 停下来 （此时因为 i==j ，循环退出），然后执行 基数6 与 a[j] 的交换

交换后数组：｛7，1，2，6，9｝

此时明显与快速排序算法的核心思想不一致

问题在于当我们先从在边开始时，那么 i 所停留的那个位置肯定是大于基数6的

而在上述例子中，为了满足 i<j 于是 j也停留在7的位置，但最后交换回去的时候，7就到了左边

所以，我们必须从基准数的对面开始