網(wǎng)站作用微信營銷的優(yōu)勢
目錄
基數(shù)排序
快速排序?
Hoare版本（單趟）
快速排序優(yōu)化
三數(shù)取中
?小區(qū)間優(yōu)化
挖坑法（單趟）
前后指針法（單趟）
非遞歸實現(xiàn)（快排）
歸并排序
非遞歸實現(xiàn)（歸并）
計數(shù)排序
冒泡排序
插入排序
希爾排序（縮小增量排序）
選擇排序（優(yōu)化版本）
堆排序
基數(shù)排序
實現(xiàn)原理：
????????將所有待比較值統(tǒng)一為同樣的數(shù)位長度，數(shù)位端的數(shù)據(jù)前面補0，然后，從最低位開始，依次進行一次排序，這樣不斷從最低位到最高位排序完成之后，數(shù)據(jù)就有序了。
實現(xiàn)步驟：
（1）、先確實數(shù)據(jù)中最高位是幾位數(shù)（定義為 K）。
（2）、創(chuàng)建下標(biāo)為 0~9 （共10個）的隊列，因為所有的數(shù)字元素每一位都是由 0~9 這10個數(shù)組成的。
（3）、依次判斷每個數(shù)據(jù)的 個位，十位，到 K位（共K次），依次將數(shù)據(jù)進行分發(fā)到下標(biāo)對應(yīng)的隊列中，然后拿取回原數(shù)組中，最后到第K次后數(shù)據(jù)就有序了。
一組數(shù)據(jù)演示：
再將數(shù)據(jù)依次從每個隊列的隊頭中拿取出來：
?最后一次拿取分發(fā)：
代碼實現(xiàn)：
Sort.h 中函數(shù)實現(xiàn)代碼
#pragma once
#include <iostream>
#include <queue>
using namespace std;
#define K 3 //最高位次數(shù)
#define RaIndex 10std::queue<int> q[RaIndex];//用于存儲分發(fā)的數(shù)據(jù)// value: 278 k: 0 -> 8
int GetKey(int value, int k)
{int key = 0;while (k >= 0){key = value % 10;value /= 10;k--;}return key;
}//分發(fā)數(shù)據(jù)
void Distribute(int arr[], int left, int right, int k)
{for (int i = left; i < right; i++) //[left,right){//按照位數(shù)以此分發(fā)int key = GetKey(arr[i], k);//按照 key的下標(biāo)分發(fā)的對應(yīng)下標(biāo)的隊列q[key].push(arr[i]);}
}//接受數(shù)據(jù)
void Receive(int arr[])
{int index = 0;//從各個隊列中依次回收數(shù)據(jù)for (int i = 0; i < RaIndex; i++){while (!q[i].empty()){arr[index] = q[i].front();q[i].pop();index++;}}
}//基數(shù)排序
void RadixSort(int arr[], int n)
{for (int i = 0; i < K; i++){//分發(fā)數(shù)據(jù)Distribute(arr, 0, n, i);//接受數(shù)據(jù)Receive(arr);}
}
?Test.cpp 中測試代碼：
#include "Sort.h"int main()
{int arr[] = { 267,89,98,34,7,984,58,83,384,150,384,394,463 };int n = sizeof(arr) / sizeof(arr[0]);cout << "排序前：" << endl;for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;RadixSort(arr, n);cout << "排序后：" << endl;for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;return 0;
}最后進行數(shù)據(jù)測試：
快速排序?
快速排序是一種基于二叉樹結(jié)構(gòu)的交換排序算法，其基本思想：
? ? ? ? 任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該基準(zhǔn)值將待排序列分為兩個子序列，左子序列中所有的元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后左右序列遞歸實現(xiàn)該過程，直到所有元素都排序在相對應(yīng)位置上為止。
Hoare版本（單趟）
單趟動圖演示：
??單趟排序基本步驟：
（1）、選出一個key值作為基準(zhǔn)，一般是最左邊或者最右邊。
（2）、定義兩個向指針一樣的下標(biāo)（L 從左往右走 和 R 從右往左走），如果key值選的是最左邊的，就需要R先走，如果key值選的是最右邊的，就需要L先走。
（3）、若R走過程中，遇到小于key的就停下，然后L開始走，遇到大于key的就停下，隨后交換R和L位置的值，然后再次開始走，直到L撞上R，或者R撞上L，然后交換key與相撞位置的值即可。（選取左邊的值為key）
當(dāng)L撞上R時：
?當(dāng)R撞上L時：
（4）、左邊序列都是小于key的，右邊序列都是大于key的，然后再次對兩個序列進行單趟排序，直到左右序列只有一個數(shù)據(jù)或者左右序列不存在即可，此時就是數(shù)據(jù)就是有序的了。
代碼實現(xiàn)：
//快排的單趟排序 [] 左閉右閉
int SingSort(int arr[], int left, int right)
{//選取一個key值 左邊int keyi = left;while (left < right){//右邊先走，右邊找比keyi小的 相等也跳過，否則可能會死循環(huán)while (left < right && arr[right] >= arr[keyi]){right--;}//左邊找比keyi大的while (left < right && arr[left] <= arr[keyi]){left++;}if (left < right){std::swap(arr[left], arr[right]);}}int meeti = left;//此時相遇了std::swap(arr[keyi], arr[meeti]);return meeti;
}//快速排序
void QuickSort(int arr[], int begin, int end)
{if (begin >= end){return;}int keyi = SingSort(arr, begin, end);//[begin,keyi-1] keyi [keyi+1,end]QuickSort(arr, begin, keyi - 1);QuickSort(arr, keyi + 1, end);
}快速排序優(yōu)化
三數(shù)取中
? ? ? ? ?快速排序的時間復(fù)雜度為O（N * log N），是在理想的情況下計算的結(jié)果，每次進行完單趟排序之后，key的左序列與右序列的長度相同，并且所選key正好都是該序列中的 left 下標(biāo)的值與 right 下標(biāo)的值的中間值，每趟排序結(jié)束后key都位于序列的中間：
如果待排序的序列是一個有序序列，選key時依舊選最左邊或者最右邊，那么此時時間復(fù)雜度就會退化：
快速排序效率的影響最大的就是選key，key越接近中間位置，效率就越高。
三數(shù)取中邏輯：最左下標(biāo)的值，最右下標(biāo)的值，以及中間位置的值，進行大小比較，然后選大小居中位置的值作為key，當(dāng)大小居中的位置的值不在最左端或者最右端時，就需要將key值與最左端的值進行交換即可。
//三數(shù)取中邏輯
int GetMidWay(int arr[], int left, int right)
{int mid = (right + left) / 2;if (arr[right] > arr[mid]){if (arr[left] > arr[right]){return right;}else if (arr[mid] > arr[left]){return mid;}else{return right;}}else // arr[right] <= arr[mid]{if (arr[left] > arr[mid]){return mid;}else if (arr[right] > arr[left]){return right;}else{return left;}}
}//快排的單趟排序 [] 左閉右閉
int SingSort(int arr[], int left, int right)
{int mid = GetMidWay(arr, left, right);std::swap(arr[left], arr[mid]);//選取一個key值 左邊int keyi = left;while (left < right){//右邊先走，右邊找比keyi小的 相等也跳過，否則可能會死循環(huán)while (left < right && arr[right] >= arr[keyi]){right--;}//左邊找比keyi大的while (left < right && arr[left] <= arr[keyi]){left++;}if (left < right){std::swap(arr[left], arr[right]);}}int meeti = left;//此時相遇了std::swap(arr[keyi], arr[meeti]);return meeti;
}?小區(qū)間優(yōu)化
隨著遞歸的深入，每一層的遞歸次數(shù)會以2倍的形式快速增長，如果遞歸的森度過大，可能會導(dǎo)致棧溢出的情況，為了減少遞歸樹的最后幾層遞歸，可以設(shè)置一個判斷語句，當(dāng)遞歸序列的長度小于某個值時，就不再進行遞歸轉(zhuǎn)向使用其他排序方法：
//快速排序
void QuickSort(int arr[], int begin, int end)
{if (begin >= end){return;}//小區(qū)間優(yōu)化if (end - begin <= 13){//進行希爾排序InsertSort(arr + begin, end - begin + 1);//個數(shù)+1}else{int keyi = SingSort(arr, begin, end);//[begin,keyi-1] keyi [keyi+1,end]QuickSort(arr, begin, keyi - 1);QuickSort(arr, keyi + 1, end);}
}挖坑法（單趟）
單趟動圖演示：
?基本思想步驟：
（1）、選出一個數(shù)值（一般是最左邊或者最右邊的值）存儲在key變量中，在該數(shù)據(jù)位置形成了一個坑。
（2）、定義兩個像指針一樣的下表（L與R），L從左往右走，R從右往左走。（若在坑位在最左邊，需要R先走，若坑位在右邊，需要L先走）。
（3）、若R遇到小于key值的數(shù)，就將該數(shù)填入到左邊的坑位，再將這個數(shù)的位置設(shè)置為新的坑位，此時L再走，若遇到大于key值的數(shù)，就將該數(shù)填入的右邊的坑位，這個數(shù)的位置形成新的坑位，循環(huán)往下走，直到L和R的位置相遇，再將key值填入遇到位置的坑位。（最左邊的值為key）
// 挖坑法
int PartSort(int arr[], int left, int right)
{//三數(shù)取中int mid = GetMidWay(arr, left, right);std::swap(arr[left], arr[mid]);int key = arr[left];int hole = left;while (left < right){//右邊找比key小的坑，填到左邊while (left < right && arr[right] >= key){right --;}arr[hole] = arr[right];hole = right;//左邊找比key大的坑，填到右邊while (left < right && arr[left] <= key){left++;}arr[hole] = arr[left];hole = left;}arr[hole] = key;return hole;
}前后指針法（單趟）
單趟動圖演示：
?前后指針法的思想：
? cur 遇到比key小的值就停下來，是否一直++；
? prev++，交換 cur 與 prev 位置的值（也可以進行判斷 prev ++ 之后與 cur 位置是否相等，相等就不交換）
基本步驟：
（1）、選 keyi 位置的值作為基準(zhǔn)值，一般是最左邊或者最右邊。
（2）、定義兩個指針變量，開始 prev 指向序列開頭的位置，cur 指向 prev + 1 的位置。
（3）、若 cur 位置的值小于key，則 prev 位置進行 ++ ，交換 prev 位置與 cur 位置的值；
如果 cur 位置的值大于key，cur 位置一直 ++，直到 cur 指針越界，此時將 keyi 位置的值與 prev 位置的值進行交換即可。
// 前后指針法
int PartSort2(int arr[], int left, int right)
{int mid = GetMidWay(arr, left, right);std::swap(arr[mid], arr[left]);int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){//cur位置向前找小的while (arr[cur] >= arr[keyi]){cur++;}swap(arr[cur], arr[prev + 1]);}swap(arr[prev], arr[keyi]);return prev;
}非遞歸實現(xiàn)（快排）
需要借助一個數(shù)據(jù)結(jié)構(gòu)（棧）來實現(xiàn)，直接用STL中的容器（stack）即可，其中棧中存儲的是區(qū)間位置，也就是下標(biāo)。
基本思想步驟：
（1）、先將待排序序列的第一個元素的下標(biāo)與最后一個元素的下標(biāo)進行入棧。
（2）、當(dāng)棧不為空時，先讀取棧頂元素作為子區(qū)間的 right，出棧后再讀取棧頂?shù)脑刈鳛樽訁^(qū)間的 left，將這個子區(qū)間進行單趟排序，隨后將被分割的新的子區(qū)間，再進行入棧處理，直到序列中只有一個元素或者不存在即可。
//快速排序 - 非遞歸
void QuickSortNonR(int arr[], int begin, int end)
{stack<int> st;//存儲的是區(qū)間st.push(begin);st.push(end);while (!st.empty()){int right = st.top();st.pop();int left = st.top();st.pop();//區(qū)間不存在 結(jié)束/*if (left >= right){continue;}*///對區(qū)間進行單趟排序int key = PartSort(arr, left, right);// [left key-1] key [key+1 right]//對子區(qū)間進行入棧if (key + 1 < right){st.push(key + 1);st.push(right);}if (left < key - 1){st.push(left);st.push(key - 1);}}
}歸并排序
動圖演示：
?歸并排序基本思想：采用分治的方法，將已經(jīng)有序的子序列合并，從而得到一組完全有序的序列，即先使每個子序列先有序，再使子序列段間有序。
如何將兩個有序序列合并成一個有序序列？（只需要取小的尾插到新數(shù)組即可）
?如何得到有序的子序列呢？（當(dāng)序列分解到只有一個元素或者沒有元素時，就可以認為是有序的了）
歸并排序（遞歸）實現(xiàn)步驟：
（1）、需要申請一塊用于與待排序數(shù)組大小相同的用于合并兩個?子序列的臨時數(shù)組。
（2）、進行遞歸分治，直到只有一個元素或者不存在。
（3）、得到的兩個子序列，取小的尾插的臨時數(shù)組中，直到兩個子序列都尾插完全，再拷貝回原數(shù)組的相對應(yīng)位置。
代碼：
void _MergeSort(int arr[], int begin, int end, int* tmp)
{//分if (begin >= end){return;}int mid = (end + begin) / 2;//[begin mid] [mid+1 end]//遞歸劃分子區(qū)間_MergeSort(arr, begin, mid, tmp);_MergeSort(arr, mid + 1, end, tmp);//歸并int i = begin; //區(qū)間的開始int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;while (begin1 <= end1 && begin2 <= end2){//取小的尾插到臨時數(shù)組中if (arr[begin1] <= arr[begin2]){tmp[i++] = arr[begin1++];}else{tmp[i++] = arr[begin2++];}}//此時有的區(qū)間還沒有結(jié)束while (begin1 <= end1){tmp[i++] = arr[begin1++];}while (begin2 <= end2){tmp[i++] = arr[begin2++];}//拷貝子區(qū)間數(shù)組到原數(shù)組當(dāng)中memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}//歸并排序 - 遞歸
void MergeSort(int arr[], int n)
{int* tmp = new int(n);//分為子函數(shù)進行 閉區(qū)間_MergeSort(arr, 0, n - 1, tmp);
}時間復(fù)雜度（ O(N * log N) ）? ?空間復(fù)雜度（ O(N) ）?
非遞歸實現(xiàn)（歸并）
歸并排序的非遞歸實現(xiàn)，不需要借助棧等數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，只需要控制好，每次參加合并的元素個數(shù)即可，最終便能使序列變成有序：
?上面只是一個廣泛適用的樣例，其中還有很多極端場景：
場景一：
當(dāng)最后一個小組進行合并時，第二個小區(qū)間存在，但是該區(qū)間元素個數(shù)不足gap個，需要在合并序列時，對第二個小區(qū)間的邊界進行控制：
?場景二：
當(dāng)最后一個小組進行合并時，第二個小區(qū)間不存在，此時不需要對該小組進行合并：
?場景三：
當(dāng)最后一個小組進行合并時，第二個小區(qū)間不存在，并且第一個小區(qū)間元素不夠gap個時，此時也不需要對該小組進行合并：
//歸并排序 - 非遞歸
void MergeSortNonR(int arr[], int n)
{int* v = new int(n);int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int j = i;int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//場景一：第二組部分越界 直接修正邊界if (end2 >= n){end2 = n - 1;}//場景二：第二組全部越界 if (begin2>= n){break;}//場景三：第一組越界if (end1 >= n){break;}//將數(shù)組歸并while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] <= arr[begin2]){v[j++] = arr[begin1++];}else{v[j++] = arr[begin2++];}}//把剩下的數(shù)進行歸并while (begin1 <= end1){v[j++] = arr[begin1++];}while (begin2 <= end2){v[j++] = arr[begin2++];}memcpy(arr + i, v + i, sizeof(int)*(end2 - i + 1));}gap *= 2;}
}計數(shù)排序
????????計數(shù)排序，又叫非比較排序，通過統(tǒng)計數(shù)組中相同元素出現(xiàn)的次數(shù)，然后通過統(tǒng)計的結(jié)果將序列回收到原來的序列。
如例：
絕對映射：統(tǒng)計數(shù)組中的下標(biāo) i 的位置記錄的是arr數(shù)組中數(shù)字i出現(xiàn)的次數(shù)。
相對映射：統(tǒng)計中下標(biāo)為i的位置記錄的是arr數(shù)組中數(shù)字 i + min 出現(xiàn)的次數(shù)。
注意：
? ? ? ? 計數(shù)排序只適用于數(shù)據(jù)范圍較集中的序列的排序，若待排序列的數(shù)據(jù)較分散，會造成空間浪費，計數(shù)排序只適用于整型數(shù)據(jù)的排序，不適用于字符串以及浮點型數(shù)據(jù)。
代碼：
//計數(shù)排序
void CountSort(int arr[], int n)
{int a_max = arr[0], a_min = arr[0];for (int i = 1; i < n; i++){if (arr[i] > a_max){a_max = arr[i];}if (arr[i] < a_min){a_min = arr[i];}}int num = a_max - a_min + 1;//開這么大的數(shù)組vector<int> v(num);for (int i = 0; i < n; i++){v[arr[i] - a_min]++;//統(tǒng)計次數(shù)}int j = 0;for (int i = 0; i < num; i++){while (v[i]--)//次數(shù){arr[j++] = i + a_min;}}
}時間復(fù)雜度（O(N + NUM)），空間復(fù)雜度（O(NUM)）
冒泡排序
動態(tài)演示：
?冒泡排序思想：
最外層循環(huán)控制的是循環(huán)的次數(shù)，內(nèi)層循環(huán)控制的是數(shù)組中哪些元素進行交換。
代碼：
//冒泡排序
void BubbleSort(int arr[], int n)
{int flag = 0;for (int i = 0; i < n; i++){for (int j = 0; j < n - 1 - i; j++){if (arr[j] > arr[j + 1]){swap(arr[j], arr[j + 1]);//把大的換到最后面的位置flag = 1;}}if (flag == 0){break;//此時是有序的數(shù)組}}
}時間復(fù)雜度（O(N^2)）空間復(fù)雜度（O(1)）?
插入排序
動圖演示：
?????????插入排序，又名直接插入排序。在待排序的元素中，假設(shè)前 n-1 個元素已經(jīng)是有序的，現(xiàn)將第n個數(shù)插入到前面已經(jīng)排好序的序列中，使得前n個元素有序。依次對所有插入要的元素，直到整個序列有序為止。
實現(xiàn)步驟：
（1）、保存要插入的第 n 個數(shù)（要將前面的數(shù)據(jù)移動到后面所以要臨時保存）。
（2）、依次在 end >= 0的情況下，與前面的數(shù)進行對比，如果要插入的數(shù)據(jù)小于前面的數(shù)，則向?end + 1 位置進行覆蓋，大于則 break。
（3）、插入的位置有兩種情況，只需要向 end + 1位置填入即可。
?代碼：
//插入排序
void InsertSort(int arr[], int n)
{//假設(shè)[0,end]有序for (int i = 0; i < n - 1; i++){int end = i;//不能使用iint tmp = arr[end + 1];while (end >= 0){if (tmp < arr[end]){arr[end + 1] = arr[end];//繼續(xù)往前比較end--;}else{//此時 2 4 這種情況break;}}arr[end + 1] = tmp;}
}時間復(fù)雜度（O(N^2)）
希爾排序（縮小增量排序）
希爾排序?qū)ζ胀ú迦肱判虻臅r間復(fù)雜度進行分析，得出以下結(jié)論：
1、普通插入排序的時間復(fù)雜度最壞情況下為O(N^2)，此時待排序序列為逆序情況下，或者說接近逆序。
2、普通插入排序的時間復(fù)雜度最好情況下為O(N)，此時待排序序列為有序情況下，或者說接近有序。
希爾排序的思想：先將待排序序列進行一次與排序，使得待排序序列接近有序，然后再對該序列進行一次直接插入排序。
希爾排序基本步驟：
1、先選定一個小于N的整數(shù)gap作為第一增量，然后將所有距離為gap的元素分在統(tǒng)一組，并對每一組的元素進行直接插入排序，然后再取一個幣第一增量小的整數(shù)作為第二增量，重復(fù)上述步驟，直到增量為1為止。
2、當(dāng)增量大小為1時，就相當(dāng)于整個序列被分到一組，直接進行插入排序即可將排序序列成為有序序列。
問題：gap如何選擇？
gap越大，數(shù)據(jù)挪動得越快，gap越小，數(shù)據(jù)挪動得越慢，前期讓gap較大，可以讓數(shù)據(jù)更快得移動到自己對應(yīng)的位置附近（比如：大的數(shù)據(jù)到后面，小的數(shù)據(jù)到前面，對升序而言）。一般情況下，取序列的一半作為增量，也可以取 / 3 + 1，直接增量為1。
舉例說明分析：
前面兩趟都是預(yù)排序，最后一趟為直接插入排序。
//希爾排序
void ShellSort(int arr[], int n)
{控制gap的值//int gap = n;//while (gap > 1)//{// gap = gap / 3 + 1;// //按組進行// for (int j = 0; j < gap; j++)// {// for (int i = j; i < n - gap; i += gap)// {// int end = i;// int tmp = arr[end + gap];// while (end >= 0)// {// if (arr[end] > tmp)// {// arr[end + gap] = arr[end];// end -= gap;// }// else// {// break;// }// }// arr[end + gap] = tmp;// }// }//}//控制gap的值int gap = n;while (gap > 1){gap = gap / 3 + 1;//齊頭并進for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}?時間復(fù)雜度（O(N * Log N)） 平均時間復(fù)雜度（O(N^1.3)）
選擇排序（優(yōu)化版本）
動圖演示（未優(yōu)化，選擇一個數(shù)的）：
?未優(yōu)化選擇排序思想：每次從待排序中選出一個最小值，然后放在序列的起始位置，直到全部待排序序列排完即可。
void SelectSort(int arr[], int n)
{for (int i = 0; i < n; i++){int begin = i;int mini = begin;while (begin < n){if (arr[begin] < arr[mini]){mini = begin;}begin++;}swap(arr[mini], arr[i]);}
}優(yōu)化選擇排序：可以一趟選出兩個數(shù)值，一個最大值，和一個最小值，然后將它們分別放在序列的末端以及開頭，直到遍歷完整個序列。
特殊情況：
//選擇排序
void SelectSort(int arr[], int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin;int maxi = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}//進行交換swap(arr[begin], arr[mini]);//如果最大的數(shù)在begin位置，被換到mini位置了if (maxi == begin){maxi = mini;}swap(arr[end], arr[maxi]);begin++;end--;}
}時間復(fù)雜度最好與最壞（O(N^2)）?
堆排序
首先要建堆，而建堆需要執(zhí)行多次堆的向下調(diào)整算法。
堆的向下調(diào)整算法：
? ? ? ? 新插入節(jié)點，要調(diào)整為小堆，那么根節(jié)點的左右子樹必須都為小堆；調(diào)整為大堆，那么根節(jié)點的左右子樹必須都是大堆。
?向下調(diào)整算法步驟（建大堆）：
1、從根節(jié)點開始，選出左右孩子中值較大的孩子。
2、讓大的孩子與父親位置的值進行比較，若大于父親位置的值，則該孩子與父親位置進行交換，并將原來大的孩子的位置當(dāng)成父親繼續(xù)向下進行調(diào)整，直到調(diào)整到葉子節(jié)點位置；若小于父親位置的值，就不需要處理了，此時整棵數(shù)就是大堆了。
示例演示：
//堆的向下調(diào)整算法
void AdjustDown(int arr[], int n, int root)
{int parent = root;int child = parent * 2 + 1;//假設(shè)左邊孩子的值大while (child < n){if (child + 1 < n && arr[child + 1] > arr[child]) //child位置存在的情況下{child++;}if (arr[child] > arr[parent]){swap(arr[child], arr[parent]);parent = child;child = parent * 2 + 1;}else{break;//此時已經(jīng)是大堆了}}
}?堆的向下調(diào)整算法，最快情況下，一直要向下調(diào)整節(jié)點，次數(shù)為 h - 1 次（h為數(shù)的高度），而?
h = log 2 (N+1) N為結(jié)點總數(shù)，所以堆的向下調(diào)整算法的時間復(fù)雜度為 O(log N)
????????使用堆的向下調(diào)整算法需要滿足其根節(jié)點的左右子樹是大堆或者小堆才行，方法如下：
只需要從倒數(shù)第一個非葉子結(jié)點來說，從后往前，按下標(biāo)，依次作為根取向下調(diào)整即可。
建堆代碼：
//最后一個位置的下班是n-1,父親位置是 (n - 1 -1)/2
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{AdjustDown(arr, n, i);
}?建堆的時間復(fù)雜度大概是 O(N)。
如何進行堆排序？
1、將堆頂數(shù)據(jù)與堆的最后一個數(shù)據(jù)交換，然后對根位置進行一次向下調(diào)整算法，但是被交換到最后的那個最大的數(shù)不參與向下調(diào)整。
2、此時除了最后一個數(shù)之外，其余的數(shù)又成了一個大堆，然后又將堆頂數(shù)據(jù)與堆的最后一個數(shù)據(jù)進行交換，第二大的數(shù)就被放到了倒數(shù)第二位置上，反復(fù)進行運算，直到堆中只有一個數(shù)據(jù)即可。
void HeapSort(int arr[], int n)
{//最后一個位置的下班是n-1,父親位置是 (n - 1 -1)/2for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, n, i);}//此時是一個大堆，進行把大的數(shù)，放到最后即可int end = n - 1;while (end){swap(arr[0], arr[end]);//繼續(xù)向下調(diào)整，成為大堆AdjustDown(arr, end, 0);end--;}
}時間復(fù)雜度（O(N^2)）