C語(yǔ)言如何實(shí)現(xiàn)快速排序算法

這篇文章將為大家詳細(xì)講解有關(guān)C語(yǔ)言如何實(shí)現(xiàn)快速排序算法，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

代碼

#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;//最左邊數(shù)組下標(biāo)
	int last = end;//最右邊數(shù)組下標(biāo)
	int key = first;//用于比較的標(biāo)量（選取最左邊第一個(gè)元素）
	if (first >= last)
	{
		return;
	}
	while (first < last)
	{
		while (first < last && arr[last] >= arr[key])//右邊找比標(biāo)量小的數(shù)
		{
			last--;
		}
		while (first < last && arr[first] <= arr[key])//左邊找比標(biāo)量大的數(shù)
		{ 
			first++;
		}
		if(first < last)//分析交換找出來(lái)的值
		swap(&arr[first], &arr[last]);
	}
	if (first == last)
	{
		int mite = key;//交換標(biāo)量到它應(yīng)該到的位置上，重新選取標(biāo)量
		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);//傳第一個(gè)和最后一個(gè)元素的下標(biāo)
	for (i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

首先什么是快速排序算法：快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序n 個(gè)項(xiàng)目要Ο(nlogn) 次比較。在最壞狀況下則需要Ο(n2) 次比較，但這種狀況并不常見(jiàn)。事實(shí)上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來(lái)。

快速排序的最壞運(yùn)行情況是 O(n2)，比如說(shuō)順序數(shù)列的快排。但它的平攤期望時(shí)間是 O(nlogn)，且 O(nlogn) 記號(hào)中隱含的常數(shù)因子很小，比復(fù)雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以，對(duì)絕大多數(shù)順序性較弱的隨機(jī)數(shù)列而言，快速排序總是優(yōu)于歸并排序。

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

簡(jiǎn)單的說(shuō)，選取一個(gè)基準(zhǔn)（這里選取第一個(gè)數(shù)據(jù)），與其他數(shù)據(jù)進(jìn)行比較，使比它小的在它的前面，比它大的在它的后面。然后再以這個(gè)基準(zhǔn)為界限分為兩部地方（比它大的部分、比它小的部分），分別選取兩個(gè)部分的基準(zhǔn)，再進(jìn)行比較，比較完后在進(jìn)行分界，重復(fù)下去，直到最后每部分都只有一個(gè)數(shù)據(jù)時(shí)，排序結(jié)束。

圖解-->

代碼講解：<運(yùn)用遞歸>

1、首先需要?jiǎng)?chuàng)建數(shù)組、數(shù)組第一個(gè)數(shù)據(jù)下標(biāo)，最后一個(gè)數(shù)據(jù)下標(biāo)三個(gè)參數(shù)，數(shù)組用于儲(chǔ)存數(shù)據(jù)，然后創(chuàng)建一個(gè)Compare()用于快速排序函數(shù)，最后打印出來(lái)就是我們需要的有序數(shù)列。

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

2、Compare()函數(shù)創(chuàng)建

這里使用無(wú)符號(hào)返回類型，因?yàn)椴恍枰祷刂?/p>

為保證數(shù)組第一個(gè)元素和最后一個(gè)元素下標(biāo)不變，創(chuàng)建first和last兩個(gè)局部變量記錄數(shù)組第一個(gè)元素和最后一個(gè)元素的下標(biāo)

創(chuàng)建key下標(biāo)的數(shù)據(jù)作為基準(zhǔn)

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

3、首先判斷數(shù)列是否只有一個(gè)元素，如果只有一個(gè)元素，則函數(shù)結(jié)束。

4、開(kāi)始實(shí)現(xiàn)函數(shù)主要比較部分

4.1、如果選取左邊第一個(gè)數(shù)據(jù)為基準(zhǔn)，先從右邊開(kāi)始比較，

4.2、從右邊第一個(gè)數(shù)據(jù)開(kāi)始與key進(jìn)行比較，如果比它大則繼續(xù)向右比較(last--)，直到找到比key小的數(shù)據(jù)，便停下來(lái)。

4.3、此刻開(kāi)始從左邊開(kāi)始與key比較，如果比key小則繼續(xù)比較(first++)，如果比key大則與右邊找到的比key大的數(shù)進(jìn)行交換。然后右邊繼續(xù)找，重復(fù)以上步驟。

4.4、直到first>=last時(shí)，都停止尋找，并交換此時(shí)first下標(biāo)的數(shù)據(jù)與key的值

4.5、分治思想，以此時(shí)的key下標(biāo)的數(shù)組作為分界，分為比它大的、比它小的兩部分，在重復(fù)以上步驟，直至只有一個(gè)數(shù)據(jù)為止，停下排序。采用遞歸求解。

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

swap()交換函數(shù)，因?yàn)樾枰绊懙浇粨Q函數(shù)外的值，使用指針形參。

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

關(guān)于“C語(yǔ)言如何實(shí)現(xiàn)快速排序算法”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。