时间复杂度：O(N^2) 空间复杂度：O(1) 稳定性：不稳定 这里需要格外注意，很多人认为选择排序选最值的方法是稳定的，但是当面对特殊情况下会不稳定，例如：【2，2，1，1】，当选择出最小值时与最左边的值交换，这样就破坏了数据2内的稳定性

希尔排序

希尔排序的核心思想与插入排序一致，但是希尔排序会先对数组进行预排序，使之基本有序，当进行最后一趟排序（也就是插入排序时）会变得很快。 预排序时，先每个几个元素进行预插入排序，这样可以使大数很快的跳到后部，小数很快的跳的前部，提高了效率。 算法实现；

void ShellSort(vector&v){
	int gap=v.size();
	while(gap>1){
		gap=gap/3+1;//也可以选择/2，只要最后一趟是1即可
		for(int i=gap;i=0&&v[tmp-gap]>v[tmp]){
				swap(v[tmp-gap],v[tmp]);
				tmp-=gap;
			}
		}
	}
}

时间复杂度：希尔排序的时间复杂度很难进行分析，目前一般认为是O(N^(1.3))左右 空间复杂度：O(1) 稳定性：不稳定 虽然插入排序是稳定的，但是希尔排序因为进行了分组，使得同一个数在一组里面可能跳到前面也可能跳到后面，破坏了稳定性

堆排序

堆排序利用了二叉堆这种数据结构的性质，它可以轻松的选出一组数里权最大的元素，我们只需要建堆，然后不断将堆顶元素放到数据末端即可。 算法实现：

void HeapSort(vector& v){
	int sz=v.size();
//向下调整建堆
	for(int i=(sz-1-1)/2;i>=0;--i){
		int father=i,child=(i*2)+1;
		while(childv[child]){
				++child;
			}
			if(v[child]>v[father]){
				swap(v[child],v[father]);
			}else break;
			father=child;
			child=(child*2)+1;
		}
	}
//将堆顶元素与末尾元素交换，然后将堆顶元素向下调整即可
	while(sz--){
		swap(v[0],v[sz]);
		int father=0,child=1;
		while(childv[child]){
				++child;
			}
			if(v[child]>v[father]){
				swap(v[child],v[father]);
			}else break;
			father=child;
			child=(child*2)+1;
		}
	}
}

时间复杂度：O(NlogN) 空间复杂度：O(1) 稳定性：不稳定

快速排序

快速排序的思想就是每一趟选定一个数作为key，在一趟排序中将所有比key小的数放到k前面，比k大的数放到k后面，经过一趟这样的排序key就能在最终应该在的位置。 算法实现：

//非递归+双指针法+三数取中
void QuickSort(vector&v){
	queue>q;
	q.push ({0,v.size()-1});
	while(!q.empty()){
		int left=q.front().first,right=q.front().second;
		q.pop();
		int k= find_mid (left,right,(left+right)/2,v);
		swap(v[k],v[left]);
		k=left;
		int less,cur;
		less=cur=left;
		++cur;
		while(cur<=right){
			if(v[cur]less+1)q.push ({less+1,right});
	}
}

选key可以使用随机k法和三数取中法，可以使快排的最坏情况更难出现。 时间复杂度：O(NlogN) 空间复杂度：O(logN) 需要进行递归或者使用数据记录开始和结束位点 稳定性：不稳定

归并排序

归并排序与快速排序同样采用分治法对数据进行排序，将两组有序的数组进行归并，变成一个有序的更大的数组

//递归版本
void MergeSortRec(vector&v,int begin,int end,vector&tmp){
	if(begin>=end)return;
	int mid=(begin+end)/2;
	MergeSortRec (v,begin,mid,tmp);
	MergeSortRec (v,mid+1,end,tmp);
	int begin1=begin,end1=mid;
	int begin2=mid+1,end2=end;
	int m=begin;
	while(begin1<=end1&&begin2<=end2){
		if(v[begin1]

//非递归
void MergeSort(vector&v){
	auto tmp=v;
	int gap=1;
	while( gap < v.size()){
		int i=0;
		while( i < v.size() / gap / 2 + 1){
			int left_begin = i * 2 * gap, left_end = left_begin + gap - 1;
			int right_begin = left_end + 1, right_end = right_begin + gap - 1;
			int m = left_begin;
			//进行边界划分
			//如果rb越界，直接跳出循环，只有一组的不需要归并和拷贝
			if( right_begin >= v.size()){
				break;
			}
			else if( right_end >= v.size()){
				right_end= v.size() - 1;
			}
			printf("[%d,%d][%d,%d] ",left_begin,left_end,right_begin,right_end);
			while ( left_begin <= left_end && right_begin <= right_end ) {
				if ( v[ left_begin ] < v[ right_begin ] ) {
					tmp[ m++ ] = v[ left_begin++ ];
				} else {
					tmp[ m++ ] = v[ right_begin++ ];
				}
			}
			while ( left_begin <= left_end ) {
				tmp[ m++ ] = v[ left_begin++ ];
			}
			while ( right_begin <= right_end ) {
				tmp[ m++ ] = v[ right_begin++ ];
			}
			for(int t=i*2*gap;t<=right_end;++t){
				v[t]=tmp[t];
			}
			++i;
		}
		gap*=2;
		cout<