注意一個C++的坑

sizeof()

這個函數靜態數組可以求長度，動態new出來的數組不行，因為針對的是指針……，不過既然的動態數組了，其長度本身必然是一個變量了，你沒有必要這么求長度。

下面看快速排序的代碼。

#include <iostream>
#include <algorithm>
using namespace std;// divide 比基準點小的放左邊，大的放右邊，返回基準點Index
// 對于快速排序，重點是【劃分策略】
// “=”的有無，取決于極端情況，可以使用極端序列快速判定
// 例如 5 4 3 2 1
// 需要關注幾個狀態的特征即可：初態，動態過程中的臨界，終態
int partition_array(int data[], int min,int max) {int left_pointer = min + 1; // 以data[min]為基準值int right_pointer = max;int standard_value = data[min];while (left_pointer <= right_pointer){while (data[left_pointer] <= standard_value && left_pointer <= max)	// 后面的必須是 <=，不能是 < left_pointer++;								// left = max 極端臨界狀態while (data[right_pointer] > standard_value)	// 不可能小于最小邊界，因為[min]是標準值的位置right_pointer--;if (left_pointer < right_pointer) {swap(data[left_pointer], data[right_pointer]);left_pointer++;right_pointer--;}}// 【結束狀態】// 置換結束之后，right指向的是比基準值小的，left指向的是比基準值大的，所以換rightswap(data[right_pointer], data[min]); return right_pointer;
}void quick_sort(int data[], int min, int max) {// conquerif (min >= max)return;else{// divide   [ small | standard | large ]int standard_value_index = partition_array(data, min, max);quick_sort(data, min, standard_value_index - 1);quick_sort(data, standard_value_index + 1, max);}// don't need merge
}int main() {cout << "start" << endl;int a[] = { 5,4,3,2,1 };int length = sizeof(a) / sizeof(a[0]);quick_sort(a, 0, length - 1);for (int i = 0; i < length; i++) {cout << a[i] << "  ";}return 0;
}

把握排序算法

1. 分：重點，做出簡單的排序，將基準線放中間，左邊都小，右邊都大
2. 治：一個元素或者無元素，一定有序
3. 合：不需要合，自然有序

對于分的策略，注意幾個問題

1. 幾個狀態
   1. 初態
   2. 動態
   3. 終態

在初態，選擇一個基準點，然后依次比較后面的元素。

動態過程中，注意等號問題，選取極端情況（比如完全倒序），快速判定有無等號。

終態：左指針指向大的，右指針指向小的，左指針在右指針的右邊

對于終態之后，我們將右指針的元素與基準元素換位，就可以獲取我們最初的劃分目標，之后再進行遞歸和治理。

對于之前的歸并排序，重點是合的策略，而快速排序重點則是分的策略。

但是它們都是分、治、合的分治策略，只不過側重點不同。