C語言 八大排序算法的過程圖解及實現代碼

前言

排序是數據結構中很重要的一章,先介紹幾個基本概念。

  • 排序穩定性:多個具有相同的關鍵字的記錄,若經過排序,這些記錄的相對次
  • 序保持不變,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序後的序列中,r[i]仍在r[j]之前,則稱這種排序算法是穩定的;否則稱為不穩定的。
  • 內部排序:數據元素全部放在內存中的排序。
  • 外部排序:數據元素太多不能同時放在內存中,根據排序過程的要求不能在內外存之間移動數據的排序。

一、插入排序

時間復雜度

最壞:———–O(N^2)

最好:———–O(N)

平均:———–O(N^2)

空間復雜度

O(1)

穩定性:穩定

-『 插入排序 』:顧名思義就是把每一個數插入到有序數組中對應的位置。

就相當於你玩撲克牌的過程,抓來一張牌,就放在對應有序位置

直接插入排序:

當插入第i(i>=1)個元素時,前面的array[0],array[1],…,array[i-1]已經排好序,此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較,找到插入位置即將array[i]插入,原來位置上的元素順序後移

代碼實現(升序)

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int x = a[end+1];//x為待排序的值
		int end = i;//從end開始往前和x依次比較

		while (end >= 0)
		{
			if (a[end] > x)//隻要當前的值大於x繼續往前找
			{
				a[end+1] = a[end];
				end--;
			}
			else
			{
				break;//跳出循環說明a[end] <= x
			}
		}
		a[end + 1] = x;//跳出循環說明a[end] <= x,需要把x插入到end前邊
	}
}

那麼我們可以看到,越是接近有序的數組,插入排序的效率越高(有序時對於任何一個數隻需要和前邊的數比較一次)。

二、希爾排序

時間復雜度

O(n^(1.3—2))

空間復雜度

O(1)

穩定性:穩定

『 希爾排序 』(Shell’s Sort)是插入排序的一種又稱“縮小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因 D.L.Shell 於 1959 年提出而得名。

該方法實質上是一種『 分組插入 』方法,因為插入排序對於接近有序的數組排序效率非常高,那麼希爾提出:

算法先將要排序的一組數按某個增量d分成若幹組,每組中記錄的下標相差d.對每組中全部元素進行排序,然後再用一個較小的增量對它進行分組,在每組中再進行排序。當增量減到1時,整個要排序的數被分成一組,排序完成。

一般的初次取序列的一半為增量,以後每次減半,直到增量為1。

並且插入排序可以看成分組是1的希爾排序。動圖如下:

因為插入排序可以看做gap==1的希爾排序,因此隻需要改變插入排序中for循環的增量控制排序即可。

代碼實現

void ShellSort(int* a, int n)
{
	//按gap分組進行預排序
	int gap = n;
	while (gap>1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;//這裡分組選每次折半或者/3都可以

		for (int j = 0; j < gap; j++)//gap個組
			for (int i = j; i < n - gap; i+=gap)//每個組從j開始每個增量gap	
			{
				int end = i;
				int x = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > x)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = x;
			}
	}
}

關於希爾排序時間復雜度證明比較復雜,取決於gap怎麼取,如果按照Knuth提出的/3,來取是O(n^(1.25)- 1.6*O(n^1.25).

希爾排序的特性總結:

  1. 希爾排序是對直接插入排序的優化。
  2. 當gap > 1時都是預排序,目的是讓數組更接近於有序。當gap == 1時,數組已經接近有序的瞭,這樣就會很快。這樣整體而言,可以達到優化的效果。我們實現後可以進行性能測試的對比。
  3. 希爾排序的時間復雜度不好計算,因為gap的取值方法很多,導致很難去計算,因此在好些樹中給出的希爾排序的時間復雜度都不固定

三、選擇排序

時間復雜度

最壞:———–O(N^2)

最好:———–O(N^2)

平均:———–O(N^2)

空間復雜度

O(1)

穩定性:不穩定

『 基本思想 』:

每一次從待排序的數據元素中選出最小(或最大)的一個元素,存放在序列的起始(末尾)位置,直到全部待排序的數據元素排完 。如圖:

代碼實現

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	int mini = begin;//記錄最小值下標
	while (begin<end)
	{
		for (int i = begin; i < end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;//更新最小值下標
			}
		}
		Swap(&a[mini],&a[begin]);//把最小值放到左邊
		++begin;//左邊對應起始位置++
	}
}

直接選擇排序思考非常好理解,但是效率不是很好。實際中很少使用。

四、堆排序

時間復雜度

最壞:———–O(N * logN)

最壞:———–O(N * logN)

平均:———–O(N*logN)

空間復雜度

O(1)

堆排序(Heapsort)是指利用堆積樹(堆)這種數據結構所設計的一種排序算法,它是選擇排序的一種。它是通過堆來進行選擇數據。需要註意的是排升序要建大堆,排降序建小堆。

具體可見另一篇文章堆排序和TopK問題

動圖:

代碼實現

void Swap(int* px,int* py)
{
	int t = (*px);
	(*px) = (*py);
	 (*py)= t ;
}
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}
void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	for (int i = n - 1; i > 0; i--)
	{
		Swap(&a[0], &a[i]);
		AdjustDown(a, i, 0);
	}
}

五、冒泡排序

時間復雜度

最壞:———–O(N^2)

最好:———–O(N)

平均:———–O(N^2)

空間復雜度

O(1)

『 冒泡排序 』是大傢最熟悉的也是最容易理解的排序,如下圖:

『 冒泡排序基本思想 』就是每一次將相鄰的數據進行『 兩兩比較 』,選出最大的依次比較送到右邊,那麼最右邊就是最大值,而左邊留下的自然就是小的(排升序)

-『 冒泡排序 』需要兩層循環

『 內層循環 』表示一次冒泡,也就是兩兩比較先選出最大的放到最右邊,同時註意每一次冒泡選出最大元素,那麼兩兩比較次數-1(下一次不用比較選好的最右邊)

『 外層循環 』控制的是冒泡的次數(假設數組N 個元素)也就是N-1次冒泡選出N-1個最大的元素

代碼實現

初版代碼如下:

//初版:
void Swap(int* px, int* py)
{
	int t = (*px);
	*px = (*py);
	(*py) = t;
}
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)//外層循環
	{
		for (int j = 0; j < n-1-i; j++)
		{
			if(a[j]>a[j+1])
				Swap(&a[j],& a[j + 1]);//交換
			flag = 1;
		}	
	}
}

時間復雜度分析:每一次比較次數是N-1,N-2,N-3***1.因此是N(N-1)/2

但是這種寫法還是有缺陷,時間復雜度永遠是O(N^2) , 對於一個已經排好序的數組來說,還是需要N^2的復雜度,但對於有序的數組,每一次冒泡都不會進行交換因為有序,因此如果隻要任何一次冒泡中沒有數據交換就證明數組有序瞭。時間復雜度最好也可以達到0(N)。

代碼優化如下:

//優化:
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int flag = 0;
		for (int j = 0; j < n-1-i; j++)
		{
			if(a[j]>a[j+1])
			Swap(&a[j],& a[j + 1]);
			flag = 1;
		}
		if (flag == 0)
			break;

	}
}

六、快排排序

時間復雜度

最壞:———–O(N^2)

最好:———–O(logN)

平均:———–O(logN)

空間復雜度

O(logN)

『 快速排序 』是Hoare於1962年提出的一種二叉樹結構的交換排序方法,其『 基本思想 』為:任取待排序元素序列中的某元素作為『 基準值 』,按照該排序碼將待排序集合分割成兩子序列,左子序列中所有元素均小於基準值,右子序列中所有元素均大於基準值,然後最左右子序列重復該過程,直到所有元素都排列在相應位置上為止。如圖:

代碼實現

遞歸寫法:

// 假設按照升序對a數組中[left, right)區間中的元素進行排序
void QuickSort(int* a, int left, int right) {
	 if(right >= left )
	 	return;//遞歸截止條件
	 
	 // 按照基準值對a數組的 [left, right]區間中的元素進行劃分
	 int keyi= partion(a, left, right);
	 
	 // 劃分成功後以keyi為邊界形成瞭左右兩部分 [left, keyi-1] 和 [keyi+1, right]
	 // 遞歸排[left, keyi-1]
	 QuickSort(a, left, keyi-1);
	 
	 // 遞歸排[keyi+1, right]
	 QuickSort(a, keyi+1, right);
}

遞歸框架寫完瞭接下來就差partion函數的實現也就是快排的靈魂,去每一次找基準值。那麼一共有三種寫法如下:

hoare版本

1.首先就是要找基準值,這裡你可以選最左邊或最右邊的值(圖中是6)

2.兩個指針指向頭(這裡選左為基準值,頭指針指向第二個)和尾,基準值選左,則右指針先走,反之左指針先走。

3.左指針找到比基準值大的停下,右指針找比基準值小的停下,交換左右指針指向值

4.重復2.3動作,直到左右指針相遇,交換左指針值和基準值

左值為基準,右指針先走找比6小的:

左值為基準,右指針先走找比6小的:

交換:

最終效果:相遇交換左指針和基準值,保證瞭6的左邊都比6小,右邊比6大。

並且除此之外,由於我們看到這種算法類似於二叉樹的思想排好中間再排左右子樹,因此我要保證選取的隨機值盡量位與中位數。所以我們采取三數取中的方法。(選取最左值最右最中間的數的中位數)效率是可以提升5%到10%的。

//三數取中
int GetMidIndex(int* a, int left, int right)
{
	//int mid = (left + right) / 2;
	//int mid = left + (right - left) / 2;
	int mid = left + ((right - left)>>1);
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;

		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else 
		{
			return right;
		}
	}
	else//a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;

		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}

}
int Partion(int* a, int left,int right)
{
	int mini = GetMidIndex(a, left, right);
	Swap(&a[mini], &a[left]);
	
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}Swap(&a[left], &a[keyi]);
	return left;
}

挖坑法

挖坑法就是對hoare版本的一種變形,過程如下:

初始如下:先保存基準值,基準值形成一個坑位!

左為基準,右指針先走,找到小的送到坑位,那麼此刻右指針形成瞭新的坑位

左指針出動,找到大的繼續送到坑位,左指針形成瞭新的坑位

指針相遇,把6寫入。也保證左邊比6小,右邊比6大。代碼如下:

//挖坑法
int Partion2(int* a, int left, int right)
{
	int mini = GetMidIndex(a, left, right);
	Swap(&a[mini], &a[left]);

	int key = a[left];
	int pivot = left;
	while (left < right)
	{
		//右邊先找小
		while (left< right && a[right] >= key)
		{
			--right;
		}
		a[pivot] = a[right];
		pivot = right;
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[pivot] = a[left];
		pivot = left;
	}
	a[pivot] = key;
	return pivot;
}

前後指針版本

顧名思義,使用兩個指針,這裡選取左為基準值為例,兩個指針從左開始出發一個cur,一個prev。

要求:

cur指針先走,一旦找到比基準值小的就停下,++prev,並交換。

cur指針一直到頭為止,最後交換prev指向值和基準值

1和2都比6小cur走一步停一步,prev++並交換,指向相等。

cur越過7和9去找小的3,此時停下,prev++指向7交換。(我們註意到prev和cur不等時prev永遠是去找大的,cur是找小的,因此交換就做到把cur指向的小的往前扔,大的往後仍,)

整個過程如上,代碼:

//前後指針法
int Partion3(int* a, int left, int right)
{
	int mini = GetMidIndex(a, left, right);
	Swap(&a[mini], &a[left]);
	int prev = left, cur = left+1;
	int keyi = left;
	while (cur<=right)
	{
		if (a[cur] < a[keyi] && ++prev !=cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	return prev;
}

小結

遞歸版本三種方法如上,但是遞歸畢竟有缺陷,就是需要不斷開辟棧幀,當數據量超過10W以上時就會有棧溢出的風險。

並且遞歸類似二叉樹的結構越往下遞歸調用越多,棧幀翻倍開辟,因此我們還可以去優化一下,就是當遞歸到左右區間比較小時,我們去控制剩下的排序用別的排序來代替它。

//優化:
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	if (right - left + 1 < 10)
	{
		//小區間優化
		InsertSort(a + left , right - left + 1);
	}
	else
	{
		int keyi = Partion3(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
	
}

非遞歸:

非遞歸版本就是改變瞭快排的框架,用一個棧和循環來代替遞歸實現。依次將左右下標入棧出棧(出棧之前排序)來模擬遞歸。

void QuickSortNonR(int* a, int left, int right)
{
	Stack st;//定義一個棧
	StackInit(&st);//初始化
	StackPush(&st, left);//左下標入棧
	StackPush(&st, right);//右下標入棧
	while (StackEmpty(&st)!=0)
	{
		int end = StackTop(&st);//獲取棧頂元素即後入棧的右下標
		StackPop(&st);//出棧

		int begin = StackTop(&st);//獲取棧頂元素即先入棧的左下標
		StackPop(&st);//出棧

		int keyi = Partion3(a, begin, end);
		if (keyi + 1 < end)//相當於遞歸左半部分
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}
		if (keyi - 1 > begin)//相當於遞歸右半部分
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, begin);
		}

	}
}

七、歸並排序

時間復雜度

最壞:———–O(NlogN)

最好:———–O(NlogN)

平均:———–O(NlogN)

空間復雜度

O(N)

穩定性:穩定

基本思想:

歸並排序(MERGE-SORT)是建立在歸並操作上的一種有效的排序算法,該算法是采用分治法(Divide andConquer)的一個非常典型的應用。將已有序的子序列合並,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合並成一個有序表,稱為二路歸並。 動圖演示:

歸並的思想就是把先假設數組分成兩個有序,對其進行篩選排序,如上圖:

但是問題來瞭我們怎麼保證數組是有序的?因此就要求我們從小區間開始對數組歸並排序,對於上圖中的數據,先對開始3和3歸並,小的先進入到tmp數組,因此前兩個就是有序,再對,5和6歸並,5,6有序後,在歸並3,3,5,6……以此類推

代碼實現

遞歸寫法

框架:

void MergeSort(int* a,int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);//開辟N個大小數組
	if (tmp == NULL)
	{
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp);//進行歸並操作
	free(tmp);
	tmp = NULL;
}

歸並排序:

運用遞歸先不斷縮小偏序區間,在遞歸層層退出時一遍退出,一邊對不斷回大的區間歸並排序:

void _MergeSort(int* a, int left, int right,int* tmp)
{
	if (left >= right)
	{
		return;//遞歸截止條件left >= right區間中數的個數<=0個
	}
	int mid = left + (right - left) / 2;//取中

	_MergeSort(a, left, mid, tmp);//對左區間遞歸
	_MergeSort(a, mid+1, right, tmp);//對右區間遞歸

	int begin1 = left, end1 = mid;//左區間
	int begin2 = mid+1, end2 = right;//右區間
	int i = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1 )
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	for (size_t i = left; i <= right; i++)
	{
		a[i] = tmp[i];//把排好序[left,right]的tmp賦值給原數組
	}
}

非遞歸

非遞歸的不同就是需要手動控制區間大小,也就是不斷2倍擴大區間歸並。

但是還需要註意就是當下標是奇數,無法分成整數個組的時候,需要考慮剩餘的數,以及是否越界的問題

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		exit(-1);
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[i][i+gap-1] [i+gap][i+2*gap-1]
			int begin1 = i, end1 = i + gap-1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			int index = i;


			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}



			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++];
			}
			//控制越界問題三種情況
			if (end1 >= n)
			{
				end1 = n - 1;
			}
			if (end1 >= n)
			{
				end1 = n - 1;
			}
			if (end1 >= n)
			{
				end1 = n - 1;
			}

			for (int j = i; j <= end2; j++)
			{
				a[j] = tmp[j];
			}
		}

		
		gap *= 2;
	}
	
	free(tmp);
	tmp = NULL;

}

八、計數排序

時間復雜度

最壞:———–O(MAX(N,范圍))

最好:———–O(MAX(N,范圍))

平均:———–O(MAX(N,范圍))

空間復雜度

O(范圍)

穩定性:不穩定

思想:計數排序又稱為鴿巢原理,是對哈希直接定址法的變形應用。 操作步驟:

  1. 統計相同元素出現次數
  2. 根據統計的結果將序列回收到原來的序列中

動圖如下:

類似桶排序的思想,如上圖,先開辟數組統計數組中某一個數出現的次數,比如2出現1次,3出現兩次,那麼我們直接按順序讀入開辟的數組,在原數組寫1一個2,兩個3以此類推……

代碼實現

void CountSort(int* a, int n)
{
	int max=a[0], min= a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	memset(count, 0, sizeof(int)*range);
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
}

計數排序的特性總結:

計數排序在數據范圍集中時,效率很高,但是適用范圍及場景有限。

九、各種排序總結比較

1. 復雜度總結

2. 性質分類

 以上就是C語言 八大排序算法的過程圖解及實現代碼的詳細內容,更多關於C語言八大排序算法的資料請關註WalkonNet其它相關文章!

推薦閱讀: