目錄
什么是快速排序？
快速排序的使用場景：
演示快速排序的過程：
第一趟排序：
第二趟排序：
通過代碼來實現(xiàn)：
?對快速排序的總結(jié)：
什么是快速排序？
在寫快速排序的代碼之前，我們先對快速排序的排序原理以及定義進(jìn)行梳理：
快速排序（Quick_sort）是對冒泡排序的一種改進(jìn)，它也是屬于冒泡類的方法。它的基本思想是通過一趟排序?qū)⒋判蛄蟹指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，然后對這兩部分的分割后的序列再次進(jìn)行排序，直到達(dá)到整個序列有序的目的。
快速排序相當(dāng)于是冒泡排序升級版本，排序特點就是越亂越快，所以也是一種高效的算法?？焖倥判蚓褪且粋€給基準(zhǔn)數(shù)據(jù)并找到其正確索引位置的過程。
快速排序的使用場景：
對于數(shù)據(jù)量大，數(shù)據(jù)分布高度隨機的場景，使用快速排序算法的效率是非常高的，甚至高于堆排序。
演示快速排序的過程：
我在這里給出來一個隨機數(shù)組：
int ar[11] = {12,21,6,3,23,2,3,2,1,14,3};我們用一個總圖來描繪快速排序的過程：
?
在這里我重新給出一個數(shù)組我們分步來分析：
int ar[10] = {4,7,9,6,5,3,10,2,8,1};第一趟排序：
接下來我們在畫板上演示快速排序的過程：
在這里我們首先選定基準(zhǔn)元素，基準(zhǔn)元素的選擇是隨機的，我們?yōu)榱朔奖闫鹨娭苯舆x擇序列的第一個元素4作為基準(zhǔn)元素，然后我們定義兩個指針變量分別指向序列的開始和序列的末尾。我們把基準(zhǔn)元素拿出來，此時第一個元素的位置就相當(dāng)于是一個坑。?
我們從右邊的指針開始，把指針指向的元素和基準(zhǔn)元素做比較，如果指針?biāo)赶虻脑乇然鶞?zhǔn)元素大則把指針向左移動，如果指針?biāo)赶虻脑厥切∮诨鶞?zhǔn)元素的我們則把指針?biāo)赶虻脑靥钊肟又?。我們發(fā)現(xiàn)此時的1是小于4的，則把1填入至坑中。
這時1原本的位置成為了新的坑，同時p指針向后移動一位，此時我們發(fā)現(xiàn)p所指向的元素7是大于基準(zhǔn)元素4的，于是我們把7填入坑的位置。
此時7原本的位置又成為了新的坑，我們現(xiàn)在將q指針向左移動，碰到了元素8大于基準(zhǔn)元素，不動，直到碰到比基準(zhǔn)元素小的數(shù)停下，此時q停到了2的位置，2 ?< 4我們這時將2填入坑的位置。
此時2原本的位置成為了新的坑，p指針向右移動，我們碰到了元素9，元素9是大于基準(zhǔn)元素的，此時將元素9填入到坑的位置。
繼續(xù)上述操作，原本9的位置變?yōu)榱诵碌目?，q指針繼續(xù)向左移動，我們發(fā)現(xiàn)當(dāng)q指向元素3的時候，3小于基準(zhǔn)元素，于是將3填入坑的位置。
原本3的位置變?yōu)榱诵驴?，p指針向后移動我們發(fā)現(xiàn)元素6大于基準(zhǔn)元素，于是將6填入坑中。
此時原本6的位置變?yōu)榱诵驴?，q指針繼續(xù)向左移動，移動一位發(fā)現(xiàn)元素5是大于基準(zhǔn)元素的，所以5元素不動，繼續(xù)向左移動，此時p指針和q指針相撞，這時我們將基準(zhǔn)元素填回現(xiàn)在的坑中，此時第一趟排序完成。
我們更改元素的顏色，此時原基準(zhǔn)元素4 左側(cè)的藍(lán)色方框的元素代表小于基準(zhǔn)元素的區(qū)域，右側(cè)黃色方格的元素代表大于基準(zhǔn)元素的區(qū)域，
第二趟排序：
現(xiàn)在相當(dāng)于我們在基準(zhǔn)元素的兩側(cè)又重新分為了兩列，左邊的都小于基準(zhǔn)元素，右邊的都大于基準(zhǔn)元素。然后這兩列數(shù)列使用剛才的方法進(jìn)行第二趟排序，這也是分治法的思想。
此時我們先對4左側(cè)的元素進(jìn)行快速排序：
此時我們將2元素拿出來當(dāng)作基準(zhǔn)元素，從右側(cè)q指針?biāo)赶虻脑剡M(jìn)行比較，我們發(fā)現(xiàn)3大于1，繼續(xù)將q指針向左側(cè)移動，我們發(fā)現(xiàn)2大于1，q向左移動與p指針對撞，排序結(jié)束，將基準(zhǔn)元素放回坑的位置。繼續(xù)將2作為基準(zhǔn)元素，從右側(cè)指針q開始比較，我們發(fā)現(xiàn)3大于2，位置不動，q指針向左側(cè)移動與p指針相撞排序結(jié)束。
現(xiàn)在我們對4右側(cè)的元素進(jìn)行快速排序：
此時我們將5元素拿出來當(dāng)作基準(zhǔn)元素，5的位置為坑，q指針指向的元素開始和基準(zhǔn)元素做比較，q指針每一次向左移動所指向的元素均是大于5的，位置不動，直到q指針和p指針相撞，排序結(jié)束。
第二趟我們用6作為基準(zhǔn)元素，q現(xiàn)在向左邊移動我們發(fā)現(xiàn)q每一次的移動所指向的元素均是大于6的，所以他們的位置不動。p指針?biāo)赶虻?元素是小于6元素的，位置不動，現(xiàn)在重新將6元素置于坑中。
左子序列現(xiàn)在的長度僅為1，所以無需再做比較。此時我們將元素10作為基準(zhǔn)元素拿出來，10原來的位置為坑，從右側(cè)q指針?biāo)赶虻脑?開始比較，我們發(fā)現(xiàn)7是小于10元素的，所以我們將7填入坑中（原來10的位置）?，F(xiàn)在移動左側(cè)p指針，p指針向后移動的每一個元素都是小于基準(zhǔn)元素的，我們將10元素填入坑中，此時序列為：
指針對撞，第三趟排序結(jié)束?，F(xiàn)在我們開始第四趟排序，將9作為基準(zhǔn)元素拿出來，p指針指向9所在的位置：
現(xiàn)在從右側(cè)q指針開始比較，10是大于9的位置不動，q向左遷移一位，8是小于9的，我們將8填入坑中，此時指針p向后遷移一位與指針q對撞，將9置于新的坑中，第四趟排序結(jié)束。
我們現(xiàn)在進(jìn)行第五趟排序，右自序列的長度為 1，已經(jīng)不需要再比較，排序完成。?
通過代碼來實現(xiàn)：
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<assert.h>
#include<time.h>
#define MAXSIZE 11
void initar(int *ar,int len)
{
assert(ar != nullptr);
for(int i = 0;i < len;i++){
ar[i] = rand() % 30;
}
}
void showar(int *ar,int len)
{
assert(ar != nullptr);
for(int i = 0;i < len;i++){
printf("%d ",ar[i]);
}
printf("\n--------------------------\n");
}
void Quick_sort(int *ar,int left,int right)
{
assert(ar != nullptr);
if(left >= right){
return;
}
int i = left;//使用i下標(biāo)代表左邊界
int j = right;//使用j下標(biāo)代表右邊界
int pivot = ar[i];//pivot代表的就是基準(zhǔn)元素，將i下標(biāo)對應(yīng)的元素取出當(dāng)作基準(zhǔn)元素
while(i < j){//循環(huán)條件為左邊界小于右邊界
while(i < j && ar[j] >= pivot)//循環(huán)條件為當(dāng)右側(cè)j下標(biāo)對應(yīng)的元素大于基準(zhǔn)元素時
j--;//j下標(biāo)向左遷移一位
ar[i] = ar[j];//將j下標(biāo)對應(yīng)的值挪到坑的位置，這里可以理解為將值賦給i下標(biāo)對應(yīng)的元素位置，也就是大的往前挪
while(i < j && ar[i] <= pivot)//循環(huán)條件為當(dāng)右側(cè)下標(biāo)j對應(yīng)的值小于基準(zhǔn)元素時
i++;//i下標(biāo)向右側(cè)遷移一位
ar[j] = ar[i];//就是把小值往后挪，進(jìn)行賦值操作
}
ar[i] = pivot;//基準(zhǔn)元素更新
Quick_sort(ar,left,i - 1);//遞歸，基準(zhǔn)元素的左半部分
Quick_sort(ar,i + 1,right);//遞歸，基準(zhǔn)元素的右半部分
}
int main()
{
srand((unsigned int)time(NULL));
int ar[MAXSIZE];
initar(ar,MAXSIZE);
printf("原始數(shù)據(jù)為：\n");
showar(ar,MAXSIZE);
printf("\n經(jīng)過快速排序后的數(shù)據(jù)為：\n");
Quick_sort(ar,0,MAXSIZE - 1);
showar(ar,MAXSIZE);
return 0;
}運行結(jié)果：
排序完成?
?對快速排序的總結(jié)：
快速排序（Quick_sort）的特點就是：序列越亂越快，越有序越慢。
時間復(fù)雜度：
最優(yōu)情況：O（nlogn）每趟排序數(shù)據(jù)元素都能被平均分配成兩個部分，形成一個完美的二叉樹。
最壞情況：O（）也就是原序列相對最有序的情況，形成的樹只有左子樹和右子樹，比較次數(shù)為：(n - 1) + (n - 2) + (n - 3)+……+ 1 = n * (n - 1)/2
空間復(fù)雜度：
O（1）文章來源：http://www.zghlxwxcb.cn/news/detail-495940.html
和希爾排序類似，序列元素的比較與交換是跳躍進(jìn)行的，會改變元素的相對位置，所以快速排序依舊是一個不穩(wěn)定算法，但這也不妨礙它是所有排序算法中平均效率最高的算法。文章來源地址http://www.zghlxwxcb.cn/news/detail-495940.html
到了這里，關(guān)于算法 - 快速排序（Quick_sort）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
