C語言超詳細講解排序算法下篇

更新時間：2022年04月06日 08:36:05 作者：程序猿教你打籃球

今天我們主要難點有快速排序和歸并排序，會簡單涉及到二叉樹相關(guān)知識，相對來說比較抽象！所以如果有看不懂或者不明白的地方可以看看我之前的詳解二叉樹

1、冒泡排序

冒泡排序是我們相對最好理解的個排序，但是有些小優(yōu)化的地方我會指出來，我們先看圖解：

void BubbleSort(int* a, int n)//升序
{
	//時間復雜度O(N^2)
	while (n > 0)
	{
		int exchange = 0;
		for (int i = 1; i < n; ++i)//防止越界訪問
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);//交換
				exchange = 1;
			}
		}
		if (exchange == 0)
		{
			break;
		}
		--n;
	}
}

代碼分析：我們每排完一趟，就可以確定最后一個位置的數(shù)，再者我們定義了一個exchange來判斷在排序過程中是否發(fā)生了交換，如果沒有發(fā)生交換，證明此數(shù)組已經(jīng)有序，我們可以直接跳出循環(huán)，避免不必要的循環(huán)！

冒泡排序的特性總結(jié)：

1. 冒泡排序是一種非常容易理解的排序

2. 時間復雜度：O(N^2) 、空間復雜度：O(1)

3. 穩(wěn)定性：穩(wěn)定

2、快速排序 ( 三種方法 )

快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法。

基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。

第一種方法是我們最常見的挖坑法：

代碼實現(xiàn)如下：

void QuickSort(int* a, int left, int right)//升序
{
	if (left >= right)
	{
		return;
	}
 
	int begin = left;
	int end = right;
	int pivot = begin;
	int key = a[begin];
 
	while (begin < end)
	{
		//右邊找小
		while (begin < end && a[end] >= key) //這里如果不寫begin<end的話可能會出現(xiàn)越界訪問
		{
			--end;
		}
		//小的放到左邊的坑里，自己形成了新的坑位
		a[pivot] = a[end];
		pivot = end;
        
        //左邊找大
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		//大的放到左邊的坑里，自己形成了新的坑位
		a[pivot] = a[begin];
		pivot = begin;
	}
 
	//當begin和end相遇，證明他們兩都到了坑的位置
	pivot = begin;//隨便給一個
	a[pivot] = key;
 
	//[left, pivot - 1] pivot [pivot+ 1, right]
	//左子區(qū)間和右子區(qū)間有序，我們就有序了，如何讓他們有序呢？分治遞歸
	QuickSort(a, left, key - 1);
	QuickSort(a, key + 1, right);
}
 
//函數(shù)傳參：QuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);

第二種方法左右指針法：

代碼實現(xiàn)如下：

void QuickSort(int* a, int left, int right)//升序
{
	if (left >= right)
	{
		return;
	}
 
	int begin = left;
	int end = right;
	int keyi = begin;
 
	while (begin < end)
	{
		//找小
		while (begin < end && a[end] >= a[keyi])
		{
			--end;
		}
		//找大
		while (begin < end && a[begin] <= a[keyi])
		{
			++begin;
		}
		Swap(&a[begin], &a[end]);
	}
 
	Swap(&a[begin], &a[keyi]);
	keyi = begin;
 
	//[left, keyi - 1] keyIndex [keyi + 1, right]
	//左子區(qū)間和右子區(qū)間有序，我們就有序了，如何讓他們有序呢？分治遞歸
 
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

第三種方法前后指針法：

代碼實現(xiàn)如下：

void QuickSort(int* a, int left, int right)//升序
{
	if (left >= right)
	{
		return;
	}
 
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
        //++prev != cur為了防止自己跟自己交換造成不必要的消耗
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[keyi], &a[prev]);
	keyi = prev;
	
	//[left, keyi - 1] keyi [keyi + 1, right]
	//左子區(qū)間和右子區(qū)間有序，我們就有序了，如何讓他們有序呢？分治遞歸
 
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

3、歸并排序

基本思想：歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

歸并排序我們思想還是和快排思想差不多采用分治算法，當數(shù)組被分為單獨一個元素就是有序的了(見上圖)，在接著歸并到一個數(shù)組中，即可實現(xiàn)排序！

代碼實現(xiàn)如下：

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;
 
	int mid = (left + right) >> 1;
	// 假設[left, mid] [mid + 1, right] 有序，那么我們就可以歸并了
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);
 
	//歸并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
 
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
 
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
 
	//拷貝回去
	for (int i = left; i <= right; ++i)
	{
		a[i] = tmp[i];
	}
}
 
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);
 
	free(tmp);
}

4、排序算法復雜度及穩(wěn)定性分析

穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

gitee(碼云)：Mercury. (zzwlwp) - Gitee.com

到此這篇關(guān)于C語言超詳細講解排序算法下篇的文章就介紹到這了,更多相關(guān)C語言排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: