插入排序，冒泡排序，快速排序，選擇排序，歸并排序等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;
}