C語言如何實現快速排序算法

蝸牛 互聯網技術資訊 2021-12-20 220 0

這篇文章將為大家詳細講解有關C語言如何實現快速排序算法,小編覺得挺實用的,因此分享給大家做個參考,希望大家閱讀完這篇文章后可以有所收獲。

代碼

#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(n2),比如說順序數列的快排。但它的平攤期望時間是 O(nlogn),且 O(nlogn) 記號中隱含的常數因子很小,比復雜度穩定等于 O(nlogn) 的歸并排序要小很多。所以,對絕大多數順序性較弱的隨機數列而言,快速排序總是優于歸并排序。

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

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

圖解-->

C語言如何實現快速排序算法  c語言 第1張

代碼講解:<運用遞歸>

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語言如何實現快速排序算法”這篇文章就分享到這里了,希望以上內容可以對大家有一定的幫助,使各位可以學到更多知識,如果覺得文章不錯,請把它分享出去讓更多的人看到。

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:niceseo99@gmail.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

評論

日本韩欧美一级A片在线观看