插入排序，冒泡排序，快速排序，选择排序，归并排序等C++代码实现

• 最近在春招，于是整理一下常考的手写算法题，如下

#include <iostream>
using namespace std;

//直接插入排序，时间复杂度O(n*n)，空间复杂度O(1) 
void insert_sort(int a[], int n)
{
	for(int i = 1; i < n; i++)
	{
		int temp = a[i];
		int j = i-1;
		for(; a[j]> temp; j--)
			a[j+1] = a[j];
		a[j+1] = temp;
	}
}

//冒泡排序， 时间复杂度O(n*n)，空间复杂度O(1) 
void bubble_sort(int a[], int n)
{
	for(int i = 0; i < n; i++)
	{
		bool flag = true;
		for(int j = n-1; j > i; j--)
		{
			if(a[j] < a[j-1])
			{
				swap(a[j], a[j-1]);
				flag = false;   
			}	
		}
		if(flag) break;
		/*快速冒泡的操作，如果某一轮没有发生交换，
		则已经有序，直接跳出 */ 
	}
}

//选择排序，时间复杂度O(n*n)，空间复杂度O(1) 
void select_sort(int a[], int n) 
{
	for(int i = 0; i < n; i++)
	{
		int min = i;
		for(int j = i; j < n; j++)
			if(a[j] < a[min]) min = j;
		swap(a[i], a[min]); 
	}
}

//快速排序的划分操作 
int partition(int a[], int low, int high) 
{
	int pivot = a[low];
	while(low < high)
	{
		while(low < high && a[high] >= pivot) 
			high--;
		a[low] = a[high];
		while(low < high && a[low] <= pivot) 
			low++;
		a[high] = a[low];
	}
	a[low] = pivot;
	return low;
}

/*快速排序，时间复杂度平均O(n*logn)，最坏O(n*n)
空间复杂度O(1),运用递归的方法，需调用划分函数*/ 
void quick_sort(int a[], int low, int high) 
{
	if(low >= high) return;
	int pivotpos = partition(a, low, high);
	quick_sort(a, low, pivotpos-1);
	quick_sort(a, pivotpos+1, high);
}

//归并排序的归并操作 
void merge(int a[], int low, int mid, int high, int b[])
{
	for(int i = low; i <= high; i++) b[i] = a[i];
	int i = low, j = mid+1;
	int index = low;
	for(; i <= mid && j <= high; index++)
	{
		if(b[i] <= b[j]) a[index] = b[i++];
		else a[index] = b[j++];
	}
	while(i <= mid) a[index++] = b[i++];
	while(j <= high) a[index++] = b[j++];
}

//归并排序，使用递归，时间复杂度O(n*logn)，空间复杂度O(n) 
void merge_sort(int a[], int low, int high, int b[])
{
	if(low >= high) return;
	int mid = (low + high)/2;
	merge_sort(a, low, mid, b);
	merge_sort(a, mid+1, high, b);
	merge(a, low, mid, high, b);
}

//输出函数 
void print_sort(int a[], int n)
{
	for(int i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << endl;
}

int main()
{
	int n = 10000;
    int number[n+1];
    for(int i = 0; i < n; i++)
	    number[i] = rand() % 100000;
	cout << "start" << endl;
//	print_sort(number, n);
	int b[n];
	merge_sort(number, 0, n-1, b);
	print_sort(number, n);
	return 0;
}