作者主頁(yè)：paper jie的博客_CSDN博客-C語(yǔ)言,算法詳解領(lǐng)域博主

本文作者：大家好，我是paper jie，感謝你閱讀本文，歡迎一建三連哦。

本文錄入于《算法詳解》專欄，本專欄是針對(duì)于大學(xué)生，編程小白精心打造的。筆者用重金(時(shí)間和精力)打造，將算法基礎(chǔ)知識(shí)一網(wǎng)打盡，希望可以幫到讀者們哦。

其他專欄：《系統(tǒng)解析C語(yǔ)言》《C語(yǔ)言》《C語(yǔ)言-語(yǔ)法篇》

內(nèi)容分享：本期將對(duì)八大排序中的快速排序進(jìn)行詳細(xì)的講解，各位看官姥爺快搬好小板凳坐好叭。

? ? -------- 不要998，不要98，只要一鍵三連，三連買不了吃虧，買不了上當(dāng)

前言

在之前的排序中，我們對(duì)交換排序中的冒泡排序進(jìn)行了講解，帶學(xué)習(xí)的過(guò)程中，我們發(fā)現(xiàn)一個(gè)問(wèn)題，冒泡排序的速度實(shí)在是太慢了，它是兩個(gè)兩個(gè)元素進(jìn)行比較。那有沒有比這種排序更快的算法呢？當(dāng)然是有的，就是今天我們講的快速排序。

什么是快速排序

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列?？焖倥判蚴菍?duì)冒泡排序的一種改進(jìn)，大大的提升了排序的速度。

快速排序的實(shí)現(xiàn)

基本思想

定義一個(gè)中心軸pivot

將小于pivot的元素放在左邊

將大于pivot的元素放在右邊

將子數(shù)組用遞歸重復(fù)上面三步驟

具體代碼

#include <stdio.h>

void Quick_Sort(int arr[], int l, int r)
{
	//如果就子數(shù)組就一個(gè)元素了，那它本身就是有序的
	//直接返回
	if (l >= r)
		return;
	int left = l;
	int right = r;
	//設(shè)置最左邊的為基準(zhǔn)軸
	int pivot = arr[left];

	while (left < right)
	{
		//從右邊開始比較
		//大于pivot，right就--再比較前一個(gè)元素
		while (left < right && arr[right] > pivot)
		{
			right--;
		}
		//要是小于基準(zhǔn)軸就將它放到left指向的元素
		//因?yàn)檫@個(gè)元素已經(jīng)比pivot小了，left++跳過(guò)它
		if (left < right)
		{
			arr[left] = arr[right];
			left++;
		}
		//再?gòu)淖筮呴_始比較
		//小于pivot，left就++
		while (left < right && arr[left] < pivot)
		{
			left++;
		}
		//要是大于pivot，就將它放到right指向的元素
		//再right--，因?yàn)檫@個(gè)元素已經(jīng)知道大于pivot了
		if (left < right)
		{
			arr[right] = arr[left];
			right--;
		}
		//當(dāng)兩個(gè)指針重合時(shí)，將pivot放入其中
		//這時(shí)比它小的都在左邊，比他大的都在右邊
		if (left >= right)
		{
			arr[left] = pivot;
		}
	}
	//遞歸處理左邊的子數(shù)組
	Quick_Sort(arr, l, right - 1);
	//遞歸處理右邊的子數(shù)組
	Quick_Sort(arr, right + 1, r);

}
int main()
{
	int arr[] = { 3,2,5,8,7,1,4,6,0,9 };
	int l = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	int r = sz - 1;
	//快速排序
	Quick_Sort(arr, l, r);
	//打印
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

快速排序?qū)崿F(xiàn)的原理

排序算法的思想非常簡(jiǎn)單，在排序的數(shù)列中，我們首先要找一個(gè)數(shù)字作為基準(zhǔn)數(shù)為了方便，我們一般選擇第 1 個(gè)數(shù)字作為基準(zhǔn)數(shù)。接下來(lái)我們需要把這個(gè)待排序的數(shù)列中小于基準(zhǔn)數(shù)的元素移動(dòng)到待排序的數(shù)列的左邊，把大于基準(zhǔn)數(shù)的元素移動(dòng)到待排序的數(shù)列的右邊。這時(shí)，左右兩個(gè)分區(qū)的元素就相對(duì)有序了；接著把兩個(gè)分區(qū)的元素分別按照上面兩種方法繼續(xù)對(duì)每個(gè)分區(qū)找出基準(zhǔn)數(shù)，然后移動(dòng)，直到各個(gè)分區(qū)只有一個(gè)數(shù)時(shí)為止。

這是典型的分治思想，即分治法。下面我們代碼中的例子進(jìn)行算法描述，講解快速排序的排序步驟。

以 3 2?5 8 7 1 4 6 0 9的待排序的數(shù)列為例進(jìn)行排序。首先我們需要在數(shù)列中選擇一個(gè)基準(zhǔn)數(shù)，我們一般會(huì)選擇中間的一個(gè)數(shù)或者頭尾的數(shù)，這里直接選擇第 1 個(gè)數(shù) 3作為基準(zhǔn)數(shù)，接著把比 3小的數(shù)字移動(dòng)到左邊，把比 3大的數(shù)字移動(dòng)到右邊，對(duì)于相等的數(shù)字不做移動(dòng)。所以實(shí)際上我們需要找到中間的某個(gè)位置 k，這樣 k 左邊的值全部比 k 上的值小，k 右邊的值全部比 k 上的值大。

接下來(lái)開始移動(dòng)元素。怎么移動(dòng)呢？其實(shí)冒泡排序也涉及對(duì)元素的移動(dòng)，但是那樣移動(dòng)起來(lái)很累，比如把最后一個(gè)元素移動(dòng)到第 1 個(gè)，就需要比較 n-1 次，同時(shí)交換 n-1 次，效率很低。其實(shí)，只需把第 1 個(gè)元素和最后一個(gè)元素交換就好了，這種思想是不是在排序時(shí)可以借鑒呢？之前說(shuō)快速排序就是對(duì)冒泡排序的一個(gè)改進(jìn)，就是這個(gè)原因。

快速排序的操作是這樣的：首先從數(shù)列的右邊開始往左邊找，我們?cè)O(shè)這個(gè)下標(biāo)為 i，也就是進(jìn)行減減操作（i--），找到第 1 個(gè)比基準(zhǔn)數(shù)小的值，讓它與基準(zhǔn)值交換；接著從左邊開始往右邊找，設(shè)這個(gè)下標(biāo)為 j，然后執(zhí)行加加操作（j++），找到第 1 個(gè)比基準(zhǔn)數(shù)大的值，讓它與基準(zhǔn)值交換；然后繼續(xù)尋找，直到 i 與 j 相遇時(shí)結(jié)束，最后基準(zhǔn)值所在的位置即 k 的位置，也就是說(shuō) k 左邊的值均比 k 上的值小，而 k 右邊的值都比 k 上的值大。

這樣就是一次比較，后面的子數(shù)組重復(fù)以上操作，到數(shù)組只有一個(gè)元素的時(shí)候就結(jié)束了，因?yàn)橐粋€(gè)數(shù)組它就是有序的。

畫圖理解：

?

快速排序的特點(diǎn)與性能

快速排序是在冒泡排序的基礎(chǔ)上改進(jìn)而來(lái)的，冒泡排序每次只能交換相鄰的兩個(gè)元素，而快速排序是跳躍式的交換，交換的距離很大，因此總的比較和交換次數(shù)少了很多，速度也快了不少。
但是快速排序在最壞情況下的時(shí)間復(fù)雜度和冒泡排序一樣，是?O(n2)，實(shí)際上每次比較都需要交換，但是這種情況并不常見。我們可以思考一下如果每次比較都需要交換，那么數(shù)列的平均時(shí)間復(fù)雜度是?O(nlogn)，事實(shí)上在大多數(shù)時(shí)候，排序的速度要快于這個(gè)平均時(shí)間復(fù)雜度。這種算法實(shí)際上是一種分治法思想，也就是分而治之，把問(wèn)題分為一個(gè)個(gè)的小部分來(lái)分別解決，再把結(jié)果組合起來(lái)。
快速排序只是使用數(shù)組原本的空間進(jìn)行排序，所以所占用的空間應(yīng)該是常量級(jí)的，但是由于每次劃分之后是遞歸調(diào)用，所以遞歸調(diào)用在運(yùn)行的過(guò)程中會(huì)消耗一定的空間，在一般情況下的空間復(fù)雜度為?O(logn)，在最差的情況下，若每次只完成了一個(gè)元素，那么空間復(fù)雜度為?O(n)。所以我們一般認(rèn)為快速排序的空間復(fù)雜度為?O(logn)。
快速排序是一個(gè)不穩(wěn)定的算法，在經(jīng)過(guò)排序之后，可能會(huì)對(duì)相同值的元素的相對(duì)位置造成改變。
快速排序基本上被認(rèn)為是相同數(shù)量級(jí)的所有排序算法中，平均性能最好的。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-498801.html

到了這里，關(guān)于快速排序到底有多快的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！