C語言之快速排序算法（遞歸Hoare版）介紹

Posted on by

廢話不多說，先看代碼

#define  _CRT_SECURE_NO_WARNINGS 1
//快速排序算法，遞歸求解
#include <stdio.h>
void swap(int* a, int* b)
{
	int c = 0;
	c = *a;
	*a = *b;
	*b = c;
}
void Compare(int arr[], int one, int end)
{
	int first = one;//最左邊數組下標
	int last = end;//最右邊數組下標
	int key = first;//用於比較的標量（選取最左邊第一個元素）
	if (first >= last)
	{
		return;
	}
	while (first < last)
	{
		while (first < last && arr[last] >= arr[key])//右邊找比標量小的數
		{
			last--;
		}
		while (first < last && arr[first] <= arr[key])//左邊找比標量大的數
		{ 
			first++;
		}
		if(first < last)//分析交換找出來的值
		swap(&arr[first], &arr[last]);
	}
	if (first == last)
	{
		int mite = key;//交換標量到它應該到的位置上，重新選取標量
		swap(&arr[mite], &arr[last]);
	}
	Compare(arr,one,first-1);//左邊遞歸排序
	Compare(arr,first+1,end);//右邊遞歸排序
}
int main()
{
	int arr[] = { 5,4,6,5,2,1};
	int i = 0;
	int len = sizeof(arr) / 4;
	Compare(arr,i,len-1);//傳第一個和最後一個元素的下標
	for (i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

首先什麼是快速排序算法：快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序n 個項目要Ο(nlogn) 次比較。在最壞狀況下則需要Ο(n2) 次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。

快速排序的最壞運行情況是 O(n²)，比如說順序數列的快排。但它的平攤期望時間是 O(nlogn)，且 O(nlogn) 記號中隱含的常數因子很小，比復雜度穩定等於 O(nlogn) 的歸並排序要小很多。所以，對絕大多數順序性較弱的隨機數列而言，快速排序總是優於歸並排序。

快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）

簡單的說，選取一個基準（這裡選取第一個數據），與其他數據進行比較，使比它小的在它的前面，比它大的在它的後面。然後再以這個基準為界限分為兩部地方（比它大的部分、比它小的部分），分別選取兩個部分的基準，再進行比較，比較完後在進行分界，重復下去，直到最後每部分都隻有一個數據時，排序結束。

圖解–>

代碼講解：<運用遞歸>

1、首先需要創建數組、數組第一個數據下標，最後一個數據下標三個參數，數組用於儲存數據，然後創建一個Compare()用於快速排序函數，最後打印出來就是我們需要的有序數列。

int main()
{
	int arr[] = { 5,4,6,5,2,1};
	int i = 0;
	int len = sizeof(arr) / 4;
	Compare(arr,i,len-1);//傳第一個和最後一個元素的下標
	for (i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;

2、Compare()函數創建

這裡使用無符號返回類型，因為不需要返回值

為保證數組第一個元素和最後一個元素下標不變，創建first和last兩個局部變量記錄數組第一個元素和最後一個元素的下標

創建key下標的數據作為基準

void Compare(int arr[], int one, int end)
{
	int first = one;//最左邊數組下標
	int last = end;//最右邊數組下標
	int key = first;//用於比較的標量（選取最左邊第一個元素）

3、首先判斷數列是否隻有一個元素，如果隻有一個元素，則函數結束。

4、開始實現函數主要比較部分

4.1、如果選取左邊第一個數據為基準，先從右邊開始比較，

4.2、從右邊第一個數據開始與key進行比較，如果比它大則繼續向右比較(last–)，直到找到比key小的數據，便停下來。

4.3、此刻開始從左邊開始與key比較，如果比key小則繼續比較(first++)，如果比key大則與右邊找到的比key大的數進行交換。然後右邊繼續找，重復以上步驟。

4.4、直到first>=last時，都停止尋找，並交換此時first下標的數據與key的值

4.5、分治思想，以此時的key下標的數組作為分界，分為比它大的、比它小的兩部分，在重復以上步驟，直至隻有一個數據為止，停下排序。采用遞歸求解。

void Compare(int arr[], int one, int end)
{
	int first = one;//最左邊數組下標
	int last = end;//最右邊數組下標
	int key = first;//用於比較的標量（選取最左邊第一個元素）
	if (first >= last)
	{
		return;
	}
	while (first < last)
	{
		while (first < last && arr[last] >= arr[key])//右邊找比標量小的數
		{
			last--;
		}
		while (first < last && arr[first] <= arr[key])//左邊找比標量大的數
		{ 
			first++;
		}
		if(first < last)//分析交換找出來的值
		swap(&arr[first], &arr[last]);
	}
	if (first == last)
	{
		int mite = key;//交換標量到它應該到的位置上，重新選取標量
		swap(&arr[mite], &arr[last]);
	}
	Compare(arr,one,first-1);//左邊遞歸排序
	Compare(arr,first+1,end);//右邊遞歸排序
}

swap()交換函數，因為需要影響到交換函數外的值，使用指針形參。

void swap(int* a, int* b)
{
	int c = 0;
	c = *a;
	*a = *b;
	*b = c;
}

到此這篇關於C語言之快速排序算法（遞歸Hoare版）介紹的文章就介紹到這瞭,更多相關C語言快速排序算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：