排序演算法:快速排序——C/C++
- 一.演算法介紹
- 二.演算法思路
- 三.動態演示
- 四.思路分析
- 五.完整代碼
一.演算法介紹
快速排序（Quicksort）是對冒泡排序演算法的一種改進，
快速排序的核心思想是分治，
快速排序幾乎是目前所有排序法中速度最快的方法（顧名思義）(￢_￢)，
STL的sort()函式就是基于快速排序的優化，
| 時間復雜度 | O |
|---|---|
| 最好 | O( n log ? 2 n n\log_2n nlog2?n) |
| 最壞（遇見概率極小） | O( n 2 n^2 n2) |
| 平均 | O( n log ? 2 n n\log_2n nlog2?n) |
| 空間復雜度 | 穩定性 |
|---|---|
| O( log ? 2 n \log_2n log2?n) | 不穩定 |
二.演算法思路
①.確定一個分界點，將序列分為左右兩區間，
②.將不大于分界點的所有數集中到左區間，其余的數集中到右區間，
③.對左右兩區間重復以上兩步進行遞回處理，直至各區間只有一個數，
三.動態演示
四.思路分析
如何將序列分成左、右兩個區間？
最樸素的方法就是創建兩個新的空間，將大于和不大于分界點的數分別放在這兩個空間，
直接在原序列上進行劃分的方法也有很多，下面就展示其中一種，
五.完整代碼
#include <iostream>
using namespace std;
const int N = 10010;
int a[N];
int partition(int l, int r) //實作演算法思路第二步
{
int mid = a[l + r >> 1]; //mid為分界點
int i = l - 1, j = r + 1; //i和j為左右指標
while (i < j) //利用左右指標完成區間劃分
{
do i++; while (a[i] < mid);
do j--; while (a[j] > mid);
if (i < j) swap(a[i], a[j]);
}
return j;
}
void quicksort(int l, int r)
{
if (l == r) return; //當區間中內只有一個數時回傳
int j = partition(l, r); //將序列劃分為左右兩區間
quicksort(l, j); //遞回處理左區間
quicksort(j + 1, r); //遞回處理右區間
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
quicksort(0, n - 1);
for (int i = 0; i < n; i++)
cout << a[i] << ' ';
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259559.html
標籤：其他
上一篇：C語言實作掃雷小游戲(上)
下一篇：【數字信號處理】正弦波傅里葉分析