日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無先后，達(dá)者為師

網(wǎng)站首頁 編程語言 正文

C語言之快速排序算法(遞歸Hoare版)介紹_C 語言

作者：紳士·永 ? 更新時(shí)間： 2022-03-06 編程語言

廢話不多說，先看代碼

#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)//分析交換找出來的值
		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) 次比較，但這種狀況并不常見。事實(shí)上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來。

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

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

簡單的說，選取一個(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、首先需要創(chuàng)建數(shù)組、數(shù)組第一個(gè)數(shù)據(jù)下標(biāo)，最后一個(gè)數(shù)據(jù)下標(biāo)三個(gè)參數(shù)，數(shù)組用于儲存數(shù)據(jù)，然后創(chuàng)建一個(gè)Compare()用于快速排序函數(shù)，最后打印出來就是我們需要的有序數(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)建

這里使用無符號返回類型，因?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、開始實(shí)現(xiàn)函數(shù)主要比較部分

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

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

4.3、此刻開始從左邊開始與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)//分析交換找出來的值
		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;
}

原文鏈接：https://blog.csdn.net/weixin_63246064/article/details/122013437

欄目分類
最近更新