寫在前邊
這篇文章呢，我們接著聊一下排序演算法，我們之前已經談到了簡單插入排序 和ta的優化版希爾排序 ，這節我們要接觸一個更“高級”的演算法了--快速排序，
在做洛谷的時候，遇到了一道卡優化的題，如果沒有去對快排進行優化的話，會有幾個點是TLE的，后邊我們可以圍繞這道題來做各種優化，先來認識一下快速排序，
思路
假如我們的計算機每秒鐘可以運行 10 億次，那么對 1 億個數進行排序，桶排序只需要 0.1 秒，而冒泡排序則需要 1 千萬秒，達到 115 天之久，是不是很嚇人？那有沒有既不浪費空間又可以快一點的排序演算法呢？那就是“快速排序”！
假設我們現在對“** 6 1 2 7 9 3 4 5 10 8”這 10 個數進行排序，首先在這個序列中隨便找一個數作為基準數（不要被這個名詞嚇到了，這就是一個用來參照的數，待會兒你就知道它用來做啥了），為了方便，就讓第一個數 6 作為基準數吧，接下來，需要將這個序列中所有比基準數大的數放在 6 的右邊，比基準數小的數放在 6 的左邊**，類似下面這種排列，
3 1 2 5 4 6 9 7 10 8
在初始狀態下，數字 6 在序列的第 1 位，我們的目標是將 6 挪到序列中間的某個位置，假設這個位置是 k，現在就需要尋找這個 k，并且以第 k 位為分界點，左邊的數都小于等于 6，右邊的數都大于等于 6，
?
方法其實很簡單：分別從初始序列“ 6 1 2 7 9 3 4 5 10 8”兩端開始“探測”，先從右往左找一個小于 6 的數，再從左往右找一個大于 6 的數，然后交換它們，這里可以用兩個變數 i 和 j，分別指向序列最左邊和最右邊，我們為這兩個變數起個好聽的名字“哨兵 i”和“哨兵 j”，剛開始的時候讓哨兵 i 指向序列的最左邊（即 i=1），指向數字 6，讓哨兵 j 指向序列的最右邊（即 j=10），指向數字 8，
圖源: 《啊哈演算法》
完整流程圖
如果mid取最左端的話，當本身有序時，會淪為冒泡排序，變成n平方
(例題)洛谷1177快速排序
https://www.luogu.com.cn/problem/P1177
錯誤版本
無優化，有序會TLE
#include <iostream>
#include<cstdio>
int a[1000001];//定義全域變數，這兩個變數需要在子函式中使用
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
//遞回方法
void quicksort(int left, int right) {
//舉例子可得出若左邊大于等于右邊就回傳?
//大于的情況是:index剛好==right,然后還要再去(index+1,right)
if (left >= right) {
return;
}
//默認基準index是最左邊那個,且i從左邊開始,j從右邊開始
int i = left, j = right, index = left;
//重構方法
//大前提,兩個沒相遇
while (i != j) {
//里邊還得判斷一下i<j,因為外邊的大前提,里邊可能會破壞掉
while (a[j] >= a[left]&&i<j) {
j--;
}
while(a[i] <= a[left]&&i<j){
i++;
}
//若i,j還未相遇
if (i < j) {
swap(&a[i], &a[j]);
}
}
//出來時i,j必然相遇
swap(&a[i],&a[index]);
//將i賦值給基準
index = i;
quicksort(left, index - 1);
quicksort(index + 1, right);
}
先取到mid，然后讓左邊跟mid交換
由于是單邊搜索，后兩個點都TLE
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <time.h>
void swap(int arr[], int i, int j)
{
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void QuickSort(int arr[], int left, int right)
{
int i, pivot;
if (left >= right)
return;
pivot = left;
swap(arr, left, (left + right) / 2);
for (i = left + 1; i <= right; i++) //單邊搜索，可以該為雙向搜索
if (arr[i] < arr[left])
swap(arr, i, ++pivot);
swap(arr, left, pivot);
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
}
int main()
{
int n;
int *arr;
int i;
scanf("%d", &n);
arr = (int*)malloc(sizeof(int) * (n + 1));
for (i = 1; i <= n; i++)
scanf("%d", arr + i);
QuickSort(arr, 1, n);
for (i = 1; i <= n; i++)
printf("%d ", arr[i]);
return 0;
}
改進成雙邊搜索
只是最后一個點TLE了，而最后一個點，剛好就是常數列的情況
#include <iostream>
#include<cstdio>
int a[100010];//定義全域變數，這兩個變數需要在子函式中使用
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
//遞回方法
void quickSort(int left, int right) {
//舉例子可得出若左邊大于等于右邊就回傳?
//大于的情況是:index剛好==right,然后還要再去(index+1,right)
if (left >= right) {
return;
}
//默認基準index是最左邊那個,且i從左邊開始,j從右邊開始
int i = left, j = right, index ;
int mid=(left+right)/2;
swap(&a[left],&a[mid]);
index=left;
//重構方法
//大前提,兩個沒相遇
while (i != j) {
//里邊還得判斷一下i<j,因為外邊的大前提,里邊可能會破壞掉
while (a[j] >= a[left]&&i<j) {
j--;
}
while(a[i] <= a[left]&&i<j){
i++;
}
//若i,j還未相遇
if (i < j) {
swap(&a[i], &a[j]);
}
}
//出來時i,j必然相遇
swap(&a[i],&a[index]);
index = i;
quickSort(left, index - 1);
quickSort(index + 1, right);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
quickSort(0, n - 1);
for (int i = 0; i < n; i++) {
i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]);
}
}
復盤mid(考慮常數列)
還沒三數取中，取到的mid是最小的話還是會退化到冒泡n平方
#include<cstdio>
#include<iostream>
using namespace std;
int a[100010];
//交換元素位置
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void quickSort(int* arr, int low, int high) {
//若長度已經不符合要求,直接回傳
if (low >= high) {
return;
}
int left = low;
int right = high;
//選取中間為基準,注意是取中間的值,而不是下標,因為下標可能在后續交換中會改變
//比如left走到了mid這里,而right停在了mid右邊,這時會去交換,arr[mid]就變了
int mid = arr[(low + high) >> 1];
while (left <= right) {
//注意是小于,如果是小于等于的話,常數列就會一直left移動,而right不移動,淪為n平方
while (arr[left] < mid) {
left++;
}
//同樣注意是大于
while (arr[right] > mid) {
right--;
}
//這里要注意是小于或等于,以便于left和right直接跳到樞紐點的左右
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--;
}
}
//遞回呼叫
//right走到了區間一的尾部
quickSort(arr,low, right);
//left走到了區間二的頭部
quickSort(arr, left, high);
}
int main()
{
int n, i;
cin >> n;
for (i = 1; i <= n; i++)
{
cin >> a[i];
}
quickSort(a,1,n);
for (i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
流程圖
此處取到的mid是60
此時left和right已經相遇了
- 然后left發現不滿足條件,86>mid(60)，left還在86
- right滿足條件,right去--，走到了15那里停下來
- 然后left不滿足<=right,直接就要開始繼續遞回了
- 遞回的區間①是: [42,15] (都小于等于60)
- 區間②是 : [86,68] (都大于等于60)
while (arr[left] < mid) {
left++;
}
//同樣注意是大于
while (arr[right] > mid) {
right--;
}
//這里要注意是小于或等于,以便于left和right直接跳到樞紐點的左右
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--;
}
//遞回呼叫
//right走到了區間一的尾部
quickSort(arr,low, right);
//left走到了區間二的頭部
quickSort(arr, left, high);
問題
因為沒有去把樞紐放到正確的位置，導致最后其實分出來的區間長度會多出一個元素:樞軸(這樣會很影響時間效率嗎)
自行用一定資料量測驗的話，時間效率上差距還算不上很大的，
**結合三數取中(暫時的神)
#include<cstdio>
#include<iostream>
#include"RcdSqList.h"
using namespace std;
//int a[100010];
//交換元素位置
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
//三數取中
int getmid(int* array, int left, int right)
{
int mid = left + ((right - left) >> 1);
if (array[left] <= array[right])
{
if (array[mid] < array[left])
return left;
else if (array[mid] > array[right])
return right;
else
return mid;
}
else
{
if (array[mid] < array[right])
return right;
else if (array[mid] > array[left])
return left;
else
return mid;
}
}
void quickSort(int* arr, int low, int high) {
//若長度已經不符合要求,直接回傳
if (low >= high) {
return;
}
int left = low;
int right = high;
//選取中間為基準,注意是取中間的值,而不是下標,因為下標可能在后續交換中會改變
//比如left走到了mid這里,而right停在了mid右邊,這時會去交換,arr[mid]就變了
//呼叫三數取中,得到中間數
int mid = arr[getmid(arr, low, high)];
while (left <= right) {
//注意是小于,如果是小于等于的話,常數列就會一直left移動,而right不移動,淪為n平方
while (arr[left] < mid) {
left++;
}
//同樣注意是大于
while (arr[right] > mid) {
right--;
}
//這里要注意是小于或等于,以便于left和right直接跳到樞紐點的左右
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--;
}
}
//遞回呼叫
//right走到了區間一的尾部
quickSort(arr, low, right);
//left走到了區間二的頭部
quickSort(arr, left, high);
}
int main()
{
int n, i;
/*cin >> n;*/
/*for (i = 1; i <= n; i++)
{
cin >> a[i];
}*/
int a[100] = { 0,42 ,90,30,86,42,15,57,20 };
quickSort(a, 1, 8);
for (i = 1; i <= 8; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
總結
最后是下載了測驗點，然后看了博客，去找超時的原因，其實是完全有序
然后拿標準答案debug一下，終于發現了區別，就是常數列的時候他兩個都移動，我只是一個移動，就退化成n平方了
注意
要<號而不是<=
**要去放大問題，比如j一直往左走，要放大到一直走走走走到i那里去了!
看黑馬視頻得出的感悟....
這個問題很嚴重，會變成n平方
如果把基準放最左邊，而本身有序的話就會超時了
xxxx樞軸要選大小為中間的值，才能解決完全有序的情況(得三數取中.)
- 注意這里的取中間值不是說取區間中間的值，而是大小在首尾和區間中間數三個值排列居中的那個
- 如果取的是區間中間的值，并不能解決完全有序的問題，比如 5 4 1 2 3 ，取mid等于1，又是取到了最小的情況，最后mid放到正確的位置(即第一個位置)，遞回他的左右，并沒有起到把原區間化成兩半的效果，只是得到了右邊那一段，相當與只是減少了一個元素(類似冒泡的把一個元素放到正確的位置而已)
讓left++的條件應該是<號! ， 交換完要順便讓left++，right--，這樣才能解決常數列的情況
如果我們不在交換完做移動的話，那>就得改成>=，這樣才會移動，但就變成單指標移動了，還是退化成n平方了
交換完移動后，left和right剛好就是兩個區間的首跟尾
**三向切割法
https://www.luogu.com.cn/problem/P1177(依舊是模板題)
先來看代碼
#include<cstdio>
#include<iostream>
using namespace std;
int a[100010];
//交換元素位置
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
//三數取中
int getmid(int* array, int left, int right)
{
int mid = left + ((right - left) >> 1);
if (array[left] <= array[right])
{
if (array[mid] < array[left])
return left;
else if (array[mid] > array[right])
return right;
else
return mid;
}
else
{
if (array[mid] < array[right])
return right;
else if (array[mid] > array[left])
return left;
else
return mid;
}
}
void quickSort_2(int rcd[], int low, int high) {
if (low >= high) {
return;
}
//呼叫三數取中,獲取樞紐位置
int pivot=getmid(rcd,low,high);
//把樞紐值放到low位置(交換)
swap(&rcd[low],&rcd[pivot]);
//樞紐值就等于rcd[low]
int pivotVal = rcd[low];
//i用來遍歷一趟區間
int left, right, i;
//直接從樞紐的下一位開始遍歷區間
left = low, right = high, i = low + 1;
//遍歷整個區間
while (i <= right) {
//若小于樞紐值
if (rcd[i] < pivotVal) {
//得放到前邊,跟left交換
swap(&rcd[i], &rcd[left]);
//交換完,i換來了一個i前邊的值,肯定比較過了,所以i++
i++;
//left換來了一個i原來位置的值,也比較過了,所以left++
left++;
}
//若大于樞紐值
else if(rcd[i]>pivotVal)
{
//得放到后邊,跟right交換
swap(&rcd[i], &rcd[right]);
//right換來了一個i原來位置的值,也比較過了,所以right++
right--;
//i不動,因為換過來一個i后邊的新的值,還沒比較過
}
//等于的情況
else
{
i++;
}
}
quickSort_2(rcd, low, left - 1);
quickSort_2(rcd, right + 1, high);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
quickSort_2(a,0, n - 1);
for (int i = 0; i < n; i++) {
i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]);
}
}
粗糙的流程圖
這里我們先默認樞軸就是最左邊的元素就好了，方便理解（實際情況再按上邊代碼取中后跟最左邊交換即可）
用一個i去遍歷這個區間，還需要一個left和一個right指標
- 當 rcd[i]大于樞紐值時，比如圖中的90
- 當rcd[i]小于樞紐值時，比如圖中的20
- 當rcd[i]等于樞紐值時，比如圖中的42
具體看圖中的文字說明
總結一下就是，如果該位置是一個已經跟樞紐值比較過了的值，或者換過來一個已經跟樞紐值比較過了的值(那就需要更新一下他的指標位置)
優勢
- 減少了對重復元素的比較操作，因為重復元素在一次排序中就已經作為單獨一部分排好了，之后只需要對不等于該重復元素的其他元素進行排序，
寫在最后
- 到了快排這里，其實已經涉及到一些遞回的知識，跟遞回相關的其實還有“折半查找”、“歸并排序”等，本專欄也還還會持續更新相關的知識，歡迎關注一起學習！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/353586.html
標籤：其他