選擇、冒泡、合并、快速、插入排序算法實現(xiàn)及性能分析

醉人說夢 2020-04-13

展開全文

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

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

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

找出待排序的數(shù)列中的最?。ɑ蜃畲螅┰?，與待排序的數(shù)列的隊首元素進(jìn)行交換，隊首元素并入已排序數(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）

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

按順序訪問待排序的數(shù)列，一次比較兩個相鄰元素，如果他們的大小關(guān)系不對就交換他們的值，遍歷一趟待排數(shù)列便會把待排數(shù)列中的最大（或最小值）移動到隊末，將該最值并入已排數(shù)列，重復(fù)訪問待排序直至待排數(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ù)進(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）

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

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

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

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時，繼續(xù)分成兩個子序列
	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;
	//將兩個有序子序列按順序合并到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ù)列重新賦值會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）

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

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

void QuickSort(int array[], int low, int high)
{
	//當(dāng)待排數(shù)組只剩一個元素時，返回空
    if(low >= high)
    {
        return;
    }
    int first = low;
    int last = high;
    int key = array[first];
    while(first < last)
    {
		//將比key小的數(shù)移動到左邊，比key大的移動到右邊
        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ù)列的第一個元素放到數(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）

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

從第二個元素開始，逆序與左邊的元素依次做比較，直到遇到不比它大的元素，便將其插入到該元素后面，再從第三個元素開始循環(huán)，直至最后一個元素完成插入。

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