排序

三种排序

以下三种排序算法复杂度O(N^2),额外空间复杂度O(1)

冒泡排序

void bubbleSort(std::vector<int> &vec){
	if(vec.empty() || vec.size()<2)
		return;
		
	bool swaped = true; //用这个变量优化排序过程,又一次没有交换则数组已经排序完成 
	for(int j=vec.size()-1; j>0; j--){
		if(!swaped)
			break;
		swaped = false;
		for(int i=0; i<j; i++){
			if(vec[i]>vec[i+1]){
				std::swap(vec[i], vec[i+1]);
				swaped = true;
			}
		}
	}
}

选择排序

void selectionSort (std::vector<int> &vec){
	if( vec.empty() || vec.size()<2)
		return;
	for(int i=0; i<vec.size()-1; i++){
		// 寻找区间最小值 
		int minIndex = i;
		for(int j=i+1; j<vec.size(); j++){
			if(vec[j]<vec[minIndex])
				minIndex = j;
		}
		std::swap(vec[i], vec[minIndex]);
	}
}

插入排序

void insertionSort(std::vector<int> &vec){
	if( vec.empty() || vec.size()<2)
		return;
	for(int i=1; i<vec.size(); i++){
		for(int j=i; vec[j]<vec[j-1] && j>0; j--){
			std::swap(vec[j], vec[j-1]);
		}
	}
}

对数器

用来验证想法的技巧。例如有个算法复杂度高，但是能得出正确结果的算法，以及新写的一个算法复杂度低的算法。要验证新算法是否正确时，就可以用对数器

步骤：

1. 随机数生成
2. 拷贝
3. 和正确算法进行比对

示例

//Step 1
srand(time(NULL));
const int maxn = 700;
const int range = 200;
std::vector<int> vec;
for(int i=0; i<maxn; i++){
	vec.push_back(rand()%range);
}
//Step 2
std::vector<int> vec_cpy(vec.begin(), vec.end());
//Step 3
bubbleSort(vec);
selectionSort(vec_cpy);
for(int i=0; i<vec.size(); i++){
	if(vec.at(i) != vec_cpy.at(i)){
		std::cout<<"compare failed!"<<std::endl;
		break;
	}
}

递归算法复杂度公式

master公式
T(N) = a*T(n/b) + O(N^d)

1. log(b,a)>d 复杂度O(N^log(b,a))
2. log(b,a)=d 复杂度O(N^d * logN)
3. log(b,a)<d 复杂度O(N^d)

归并排序

void _merge(std::vector<int> &vec, int low, int mid, int hi){
    int i=low, j=mid+1, k=0;
    std::vector<int> h(hi-low+1);
    while(i<=mid && j<=hi){
        h[k++] = vec[i]<vec[j]?vec[i++]:vec[j++];
    }
    while(i<=mid)
        h[k++] = vec[i++];
    while(j<=hi)
        h[k++] = vec[j++];
    for(int i=0; i<h.size(); i++){
        vec[i+low] = h[i];
    }
    h.clear();
}

void _mergeSort(std::vector<int> &vec, int low, int hi){
    if(low >= hi)
        return;
    int mid = low + (hi-low)/2;
    _mergeSort(vec, low, mid);
    _mergeSort(vec, mid+1, hi);
    _merge(vec, low, mid, hi);
}

void mergeSort(std::vector<int> &vec){
    _mergeSort(vec, 0, vec.size()-1);
} 

复杂度分析：
T(N) = 2T(N/2)+O(N)
用master公式可以知道，复杂度O(NlogN)
因为在merge过程中开辟了数组h， 额外空间复杂度(N)

小和问题和逆序对问题

1. 小和问题
   在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和

2. 逆序对问题
   在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所以逆序对

扩展

• master公式
  上文给出的是简化版的主方法，具体的算法导论上有详细介绍

定理4.1（主定理） 令 a≥1 和 b>1 是常数，f(n) 是一个函数，T(n) 是定义在非负整数上的递归式：
T(n) = aT(n/b) + f(n)
那么T(n)有如下渐进界：
若对某个常数 ε>0 有 f(n) = O(nlog(b,a-ε))，则 T(n) = Θ(nlog(b,a)) 。
若 f(n) = Θ(nlog(b,a))，则 T(n) = Θ(nlog(b,a)· lgn) 。
若对某个常数 ε>0 有 f(n) = Ω(nlog(b,a+ε))，且对某个常数 c<1 和所有足够大的 n 有 af(n/b) ≤ cf(n)，则 T(n) = Θ(f(n)) 。

• 泛型编程
  不局限于int,可以对double,或者自建类型排序.自建类型需要重载<操作符

• 性能测试
  写一个辅助工具，对排序时间进行测试。同时也可以把对数器放到辅助工具中

#include<cassert>
#include<ctime>
#include<iostream>
#include<vector>
using namespace std;
namespace SortTestTool{
	//生成n个范围在[rangeL, rangeR) 的数字
	vector<int> generateNArray(int n, int rangeL, int rangeR){
		assert(rangeL<=rangeR);
		

		vector<int> arr(n);
		srand(time(NULL));
		for(int i=0; i<n; i++){
			arr[i] = rangeL + rand()%(rangeR - rangeL);
		}
		return arr;
	} 
	
	//对数器
	template<typename T>
	bool comparator(const vector<T> &arr1, const vector<T> &arr2) {
		if(arr1.size() != arr2.size())
			return false;
			
		int len = arr1.size();
		for(int i=0; i<len; i++){
			if(arr1[i] != arr2[i])
				return false;
		}
		return true;
	}
	
	// 性能测试
	template<typename T>
	void performanceTest(const string& sortname, void (*sort)(vector<T>&), vector<T> &vec){
		clock_t start = clock();
		sort(vec);
		clock_t end = clock();
		
		cout << sortname << " : " << double(end - start) / CLOCKS_PER_SEC << " s" <<endl;
	} 
	
	template<typename T>
	void printElem(const vector<T> &vec){
		for(auto elem: vec){
			cout<<elem<<endl;
		}
	} 
};

• 归并+插入排序
  可以对数组切分成多个组，每个组内插入排序后，进行_merge过程来消除递归

void _merge(vector<int> &vec, int low, int mid, int hi){
	int i=low, j=mid+1, k=0;
	std::vector<int> h(hi-low+1);
	while(i<=mid && j<=hi){
		if(vec[i]<=vec[j]){
			h[k++] = vec[i++];
		}else{
			h[k++] =vec[j++];
		}
	}
	while(i<=mid)
		h[k++] = vec[i++];
	while(j<=hi)
		h[k++] = vec[j++];
	for(int i=0; i<h.size(); i++){
		vec[i+low] = h[i];
	}
	h.clear();
}

void mergeSort2(vector<int> &vec){
	int len = vec.size();
	int step = 16;
	if(len <= step){
		insertionSort(vec);
		return;
	}
	
	for(int i=0; i<len; i+=step){
		insertionSort(vec, i, min(i+step-1, len-1));
	}
	
	//每2个step合并, 每4个step合并，每8个step合并 ...
	for(int i=step; i<=len; i=i*2)
		for(int j=0; j<len-i; j+= i*2)
			if(vec[j+i-1]>vec[j+i])
				_merge(vec, j, j+i-1, min(j+2*i-1, len-1));
}