選擇排序、冒泡排序、合并排序、快速排序、插入排序的算法思想和實(shí)現(xiàn)，以及時(shí)間復(fù)雜度比較。

以下排序算法均沒(méi)有進(jìn)行優(yōu)化，而是采用最符合原始算法思想的方式進(jìn)行實(shí)現(xiàn)和比較。

選擇排序的思想與算法實(shí)現(xiàn)：

找出待排序的數(shù)列中的最小（或最大）元素，與待排序的數(shù)列的隊(duì)首元素進(jìn)行交換，隊(duì)首元素并入已排序數(shù)列，直至待排數(shù)列的所有元素均已排完。

void SelectSort(int array[], int length){
	int temp,key,i,j;
    for(i = 0; i< length - 1; i++){
        temp = i;
		//遍歷待排序數(shù)組，找到其中的最小值
        for(j = i + 1; j < length; j++){
            if(array[temp] > array[j])
                temp = j;
        }
		//將最小值與當(dāng)前指定元素交換
        if(i != temp){
            key = array[temp];
            array[temp] = array[i];
            array[i] = key;
		}
    }
}

T(n) = an2 + bn + c

平均情況：O（n2）
最好情況：O（n2）
最壞情況：O（n2）

冒泡排序的思想與算法實(shí)現(xiàn)：

按順序訪問(wèn)待排序的數(shù)列，一次比較兩個(gè)相鄰元素，如果他們的大小關(guān)系不對(duì)就交換他們的值，遍歷一趟待排數(shù)列便會(huì)把待排數(shù)列中的最大（或最小值）移動(dòng)到隊(duì)末，將該最值并入已排數(shù)列，重復(fù)訪問(wèn)待排序直至待排數(shù)列中的元素均已排完。

void BubbleSort(int array[],int length){
	int key,i,j;
	for(i = 0; i < length; i++){
		for(j = 0; j < length - i - 1; j++){
			//當(dāng)遍歷到左邊的數(shù)大于右邊時(shí)，相鄰兩數(shù)進(jìn)行交換
			if(array[j] > array[j+1]){
				key = array[j];
				array[j] = array[j+1];
				array[j+1] = key;
			}
		}
	}
}

T(n) = an2 + bn + c

平均情況：O（n2）
最好情況：O（n2）
最壞情況：O（n2）

合并排序的思想與算法實(shí)現(xiàn)：

將無(wú)序的數(shù)列分成兩個(gè)無(wú)序子序列，再將所有無(wú)序子序列各分成兩個(gè)無(wú)序子序列，直至所有子序列只含一個(gè)元素；將子序列合并成有序數(shù)列，相當(dāng)于先分解再求解再合并。

合并操作需要?jiǎng)?chuàng)建或傳遞一個(gè)大小等于兩個(gè)待合并序列之和的空序列，將兩個(gè)待排子序列的隊(duì)首元素進(jìn)行比較，將較小的元素按順序賦值給空序列，如果有一個(gè)子序列的元素全部賦值完，便將另一個(gè)子序列的所有值按順序賦值給空序列。

void MergeSort(int array[], int length){
	//創(chuàng)建等大數(shù)組用于合并子數(shù)列
	int *array2 = new int[length];
	if(array2 == NULL)
		return ;
	Mergesort(array, 0, length-1, array2);
	delete array2;
}
void Mergesort(int array[], int first, int last, int array2[]){
	//當(dāng)數(shù)組元素大于1時(shí)，繼續(xù)分成兩個(gè)子序列
	if(first < last){
		int middle = (first + last)/2;
		Mergesort(array, first, middle, array2);
		Mergesort(array, middle+1, last, array2);
		Merge(array, first, middle, last, array2);
	}
}
void Merge(int array[], int first, int middle, int last, int array2[]){
	int n1 = first, n2 = middle;
	int m1 = middle + 1, m2 = last;
	int i = 0,j = 0;
	//將兩個(gè)有序子序列按順序合并到array2中
	while(n1 <= n2 && m1 <= m2){
		if(array[n1] < array[m1])
			array2[i++] = array[n1++];
		else
			array2[i++] = array[m1++];
	}
	while(n1 <= n2)
		array2[i++] = array[n1++];
	while(m1 <= m2)
		array2[i++] = array[m1++];
	//將array2中的有序數(shù)列重新賦值會(huì)array
	for(j = 0; j < i; j++)
		array[first + j] = array2[j];
}

T(n) = 2T(n/2)+O(n)遞推

= nlogn

平均情況：O（nlogn）
最好情況：O（nlogn）
最壞情況：O（nlogn）

快速排序的思想與算法實(shí)現(xiàn)：

將隊(duì)首元素視為key，比key小的值移動(dòng)到左邊，比key大的值移動(dòng)到右邊，完成后以key為分界線將序列分成兩個(gè)子序列，每個(gè)子序列再重復(fù)進(jìn)行上訴操作直至排序完成，相當(dāng)于先求部分解再分解。

void QuickSort(int array[], int low, int high)
{
	//當(dāng)待排數(shù)組只剩一個(gè)元素時(shí)，返回空
    if(low >= high)
    {
        return;
    }
    int first = low;
    int last = high;
    int key = array[first];
    while(first < last)
    {
		//將比key小的數(shù)移動(dòng)到左邊，比key大的移動(dòng)到右邊
        while(first < last && array[last] >= key)
        {
            --last;
        }
		if(first<last)
			array[first] = array[last];
        while(first < last && array[first] <= key)
        {
            ++first;
        }
        if(first<last)
			array[last] = array[first];   
    }
	//將原本數(shù)列的第一個(gè)元素放到數(shù)組中正確的位置
    array[first] = key;
	//根據(jù)已排好的元素將數(shù)組分成兩部分，分別調(diào)用遞歸函數(shù)
    QuickSort(array, low, first-1);
    QuickSort(array, first+1, high);
}

T(n) = 2T(n/2)+O(n)遞推=aT(n/b)+D(n)+C(n)

= nlogn + n

平均情況：O（nlogn）
最好情況：O（nlogn）
最壞情況：O（n2）

插入排序的思想與算法實(shí)現(xiàn)：

從第二個(gè)元素開(kāi)始，逆序與左邊的元素依次做比較，直到遇到不比它大的元素，便將其插入到該元素后面，再?gòu)牡谌齻€(gè)元素開(kāi)始循環(huán)，直至最后一個(gè)元素完成插入。

void InsertSort(int array[],int length) {
	int key,i,j;
	for (i = 1; i < length; i++) {
		key = array[i];
		j = i - 1;
		//將key左邊比它大的數(shù)往右移動(dòng)，直到遇到第一個(gè)比key小的數(shù)
		while (j > 0 && array[j] > key) {
			array[j + 1] = array[j];
			j = j - 1;
		}
		//將key插入到這個(gè)比它小的數(shù)的右邊
		array[j + 1] = key;
	}
}

T(n) = an2 + bn + c

平均情況：O（n2）
最好情況：O（n）
最壞情況：O（n2）

實(shí)際測(cè)試時(shí)間復(fù)雜度：快速排序 < 合并排序 < 插入排序< 選擇排序< 冒泡排序。

win10+visual studio2015環(huán)境測(cè)試，int型數(shù)組

數(shù)組大小為10000-50000（縱坐標(biāo)為時(shí)間單位us，表示所消耗的時(shí)間）

其中快速排序比合并排序快：

合并排序和快速排序都需要進(jìn)行遞歸函數(shù)調(diào)用，但合并排序需要?jiǎng)?chuàng)建數(shù)組空間進(jìn)行合并操作，快速排序只需在初始數(shù)組中進(jìn)行交換賦值，所以合并排序的耗時(shí)比快速排序多。

數(shù)組大小為100、1000、10000、100000、100000。