快速排序圖解？

前言

此系列博客為博主在AcWing算法基礎課的學習筆記，不足之處歡迎批評指正，本文為快速排序。

一、快速排序模板

//這里為需要背誦的部分，要求：給一個相關題目，能快速寫出該模板并調試通過，后續大部分模板也一樣。
//快速排序
void quick_sort1(int q[], int l, int r) 
{//邊界不滿足左邊小，直接返回if (l >= r) return;//第一步，確定邊界//tips1：由于i和j都是先自減或自增后判斷，初始時i、j往邊界兩端擴一步int i = l - 1, j =  r + 1, x = q[l + r >> 1];//第二步，劃分區間，使得一邊小于x，一邊大于x；while (i < j){do i ++ ; while (q[i] < x);do j -- ; while (q[j] > x);if (i < j) swap(q[i], q[j]);}//第三步，遞歸處理兩邊quick_sort1(q, l, j), quick_sort1(q, j + 1, r);
}

二、快速排序模板題

1.題目要求

給定你一個長度為 n 的整數數列。

快速排序怎么排。請你使用快速排序對這個數列按照從小到大進行排序。

并將排好序的數列按順序輸出。

輸入格式
輸入共兩行，第一行包含整數 n。

第二行包含 n 個整數（所有整數均在 1～109 范圍內），表示整個數列。

輸出格式
輸出共一行，包含 n 個整數，表示排好序的數列。

數據范圍
1≤n≤100000
輸入樣例：
5
3 1 2 4 5
輸出樣例：
1 2 3 4 5

2.讀入數據

代碼如下（示例）：

#include <iostream>
//平時練習可以適當熟悉使用各種庫，實戰面試可以再用<bits/stdc++.h>
//#include <bits/stdc++.h> using namespace std;const int N = 100010;//定義const變量N，習慣性根據題目數據范圍+10int q[N];//函數體外初始化數組全為0void quick_sort(int q[], int l, int r) {if(l >= r) return;int i = l - 1, j = r + 1, x = q[l + r >> 1];while (i < j) {do i++; while (q[i] < x);do j--; while (q[j] > x);if (i < j) swap(q[i], q[j]);}quick_sort(q, l, j);quick_sort(q, j + 1, r);
}int main() {int n;cin >> n;for (int i = 0; i < n; i++) {//tips1:使用scanf而不用cin是為了在數據量較大的時候提高讀寫速度scanf("%d", &q[i]);}quick_sort(q, 0, n - 1);for (int i = 0; i < n; i++) {printf("%d ", q[i]);}return 0;
}

總結

具體內容見代碼注釋，補充內容如下：
1、C++中也可以直接用sort函數來實現排序，即sort(q, q+n)，我記得是需要引入algorithm庫，但本文意不在此；
2、若要實現從大到小排序，只需要互換模板中do…while語句中的判斷條件即可。