---

1. 直接選擇排序

1. 思想
   以排升序?yàn)槔?。以a[i]為最大值（或最小值），從a[i+1]到a[n-1-i]比較選出最大值放在a[n-1-i]（或最小值放在a[i]）。簡(jiǎn)單講就是將以每輪排序的第一個(gè)數(shù)作為最大值或者最小值，比較剩余的元素，得到最大值或者最小值，將最大值放在剩余數(shù)據(jù)的最后一位，最小值放在剩余數(shù)據(jù)的第一位。
   升級(jí)版
   以排升序?yàn)槔?。每輪排序中選出最大值和最小值，分別放在數(shù)據(jù)的左右兩端。

2. 例子（排升序）
   

3. 代碼實(shí)現(xiàn)

//選擇排序（以排升序?yàn)槔?#xff09;
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void SelectSort(int* a, int n)
{int left = 0;int right = n - 1;while (left < right){int maxi = left, mini = left;for (int i = left + 1; i <= right; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}Swap(&a[maxi], &a[right]);//這里要考慮特殊情況：如果最小值mini==right，那么在交換maxi和right后，//最小值就發(fā)生改變，所以要最小值的下標(biāo)要改變。if (mini == right){mini == maxi;}Swap(&a[mini], &a[left]);right--;left++;}
}

4. 算法分析
   時(shí)間復(fù)雜度
   假設(shè)有n個(gè)元素，第一次排序要遍歷n-2個(gè)元素，第二次排序要遍歷n-4個(gè)元素，往后每次排序的元素個(gè)數(shù)都減2，總的遍歷次數(shù)是等差數(shù)列的前n項(xiàng)和，所以時(shí)間復(fù)雜度是O（N^2）。
   空間復(fù)雜度
   空間復(fù)雜度是O（1）。
   穩(wěn)定性
   是不穩(wěn)定的排序。如上面的例子中的12，在選出最大值和最小值時(shí)，前后順序發(fā)生改變。
   注意
   直接選擇排序的最好情況和最壞情況的時(shí)間復(fù)雜度都是O（N^2）。

---

2. 堆排序

2.1 堆

1. 概念
   堆其實(shí)是一種樹(shù)形結(jié)構(gòu)，分為大根堆和小根堆。大根堆是樹(shù)中所有父節(jié)點(diǎn)大于子節(jié)點(diǎn)，小根堆是樹(shù)中所有父節(jié)點(diǎn)小于子節(jié)點(diǎn)。但父節(jié)點(diǎn)的左右孩子誰(shuí)大誰(shuí)小沒(méi)有要求。

2. 預(yù)備知識(shí)
   （1）堆的邏輯結(jié)構(gòu)是樹(shù)，物理結(jié)構(gòu)是數(shù)組（即在內(nèi)存中以數(shù)組的形式存儲(chǔ)）。
   

（2）父節(jié)點(diǎn)和子節(jié)點(diǎn)的關(guān)系
已知子節(jié)點(diǎn)下標(biāo)，它的父節(jié)點(diǎn)下標(biāo)parent = （child - 1）/2。
已知父節(jié)點(diǎn)下標(biāo)，它的子節(jié)點(diǎn)下標(biāo)leftchild = parent * 2 + 1，rightchild = parent * 2 + 2。
（3）種存儲(chǔ)結(jié)構(gòu)只適用于滿二叉樹(shù)和完全二叉樹(shù)，否則會(huì)浪費(fèi)很多空間。

2.2 堆的實(shí)現(xiàn)（以大根堆為例）

1. 堆的定義

//堆的實(shí)現(xiàn)
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;//用來(lái)申請(qǐng)空間int size;//記錄當(dāng)前堆的元素個(gè)數(shù)int capacity;//記錄當(dāng)前堆的最大容量
};

2. 堆的初始化

//堆的初始化
void HeapInit(HP* ph)
{assert(ph);ph->a = (HPDataType*)malloc(sizeof(HPDataType)*10);//初始化容量設(shè)置為10if (ph->a == NULL){perror("malloc failed");return;}ph->capacity = 10;ph->size = 0;
}

3. 入堆

//入堆
void HeapPush(HP* ph, HPDataType x)
{assert(ph);//首先要檢查堆是否已滿if (ph->size == ph->capacity){HPDataType* tmp = (HPDataType*)realloc(ph->a, sizeof(HPDataType) * ph->capacity * 2);if (tmp == NULL){perror("realloc failed");return;}ph->a = tmp;ph->capacity *= 2;//每次容量不夠時(shí)擴(kuò)容兩倍}ph->a[ph->size++] = x;//因?yàn)橐獙?shí)現(xiàn)大根堆，如果入堆元素大于前面的元素，就要把它向上調(diào)整。AdjustUp(ph->a, ph->size - 1);//第一次參數(shù)是要調(diào)整的數(shù)據(jù)元素，第二個(gè)參數(shù)是入堆元素的下標(biāo)。
}

4. 向上調(diào)整

//向上調(diào)整
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{//得到父節(jié)點(diǎn)的下標(biāo)int parent = (child - 1) / 2;while (child > 0)//當(dāng)子節(jié)點(diǎn)爬到下標(biāo)為0的位置，就達(dá)到頂部了，此時(shí)可以停止循環(huán){//比較父節(jié)點(diǎn)和子節(jié)點(diǎn)，誰(shuí)大誰(shuí)上去//讓大的節(jié)點(diǎn)不斷往上爬if (a[chil] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

5. 出堆
   疑惑
   （1）
   出堆其實(shí)就是彈出根節(jié)點(diǎn)。但我們要考慮彈出根節(jié)點(diǎn)后，后面的數(shù)據(jù)要如何處理？將數(shù)據(jù)往前移動(dòng)？這樣數(shù)據(jù)間的關(guān)系就全亂了，且所有數(shù)據(jù)往前移效率低（O(N^2)）。
   正確的做法是交換堆頂元素和最后一個(gè)元素，然后刪除最后一個(gè)元素，然后將堆頂元素向下調(diào)整。
   （2）
   為什么要彈出根節(jié)點(diǎn)？彈出最后一個(gè)元素豈不是更簡(jiǎn)單？這就涉及到堆的應(yīng)用。我們所寫的是大根堆，根結(jié)點(diǎn)是這組數(shù)據(jù)的最大值，彈出根節(jié)點(diǎn)后，向下調(diào)整可以得到次大值，然后再?gòu)棾龈?jié)點(diǎn)。就這樣，我們就得到這組數(shù)據(jù)的前n個(gè)最大值，比如得到年紀(jì)前50名，得到產(chǎn)品銷量前100名。由此可見(jiàn)，彈出根結(jié)點(diǎn)是非常有用的。
   代碼實(shí)現(xiàn)

//堆空
bool HeapEmpty(HP* ph)
{assert(ph);return ph->size == 0;
}//出堆
void HeapPop(HP* ph)
{assert(ph);//首先判斷堆是否為空assert(!HeapEmpty(ph));//交換堆頂元素和最后一個(gè)元素Swap(&ph->a[0], &ph->a[ph->size - 1]);//刪除最后一個(gè)元素ph->size--;//向下調(diào)整AdjustDown(ph->a, ph->size, 0);//第一個(gè)參數(shù)是要調(diào)整的數(shù)據(jù)，第二個(gè)參數(shù)是數(shù)據(jù)的個(gè)數(shù)，第三個(gè)參數(shù)是要調(diào)整的位置
}

6. 向下調(diào)整

//向下調(diào)整（條件：左右子樹(shù)都是大根堆或者小根堆）
void AdjustDown(HPDataType* a, int n, int parent)
{int child = 2 * parent + 1;//先得到左孩子while (child < n)//當(dāng)子節(jié)點(diǎn)的下標(biāo)大于元素個(gè)數(shù)時(shí)停止循環(huán){//如果右孩子存在且大于左孩子，那么就換成右孩子與父節(jié)點(diǎn)比較if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}

7. 堆頂

//堆頂
HP* HeapTop(HP* ph)
{assert(ph);//首先判斷堆是否為空assert(!HeapEmpty(ph));return ph->a[ph->size - 1];
}

8. 打印前K個(gè)元素

//打印前K個(gè)元素
void PrintK(HP* ph, int k)
{while (!HeapEmpty(ph) && k--){printf("%d ", HeapTop(ph));HeapPop(ph);}printf("\n");
}

9. 銷毀

//銷毀
void HeapDestroy(HP* ph)
{assert(ph);free(ph->a);ph->a = 0;ph->capacity = 0;ph->size = 0;
}

2.3 堆排序

了解堆的基本操作后，就可以實(shí)現(xiàn)堆排序。

//法一
//堆排序（以排升序?yàn)槔?#xff09;
void HeapSort(int* a, int n)
{//建堆（大根堆或者小根堆）for (int i = 1; i < n; i++){AdjustUp(a, i);//從下標(biāo)為1的元素不斷插入，從而向上調(diào)整}//建大根堆后，就交換根結(jié)點(diǎn)和最后一個(gè)元素，每次交換都將最大值放在數(shù)據(jù)的最后面int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);//交換最大值和最后一個(gè)元素AdjustDown(a, end, 0);//交換后最后一個(gè)元素不參與調(diào)整，所有元素個(gè)數(shù)只有end個(gè)//每次調(diào)整后都會(huì)將最大值放在根節(jié)點(diǎn)的位置--end;}
}

//法二
void HeapSort(int* a, int n)
{//從最后一個(gè)元素的父節(jié)點(diǎn)開(kāi)始向下調(diào)整//目的是建成大根堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}

時(shí)間復(fù)雜度
這兩種方法唯一的不同就是法一前面是向上調(diào)整，法二前面是向下調(diào)整。要比較兩種方法的時(shí)間復(fù)雜度就得比較向下調(diào)整和向上調(diào)整的時(shí)間復(fù)雜度。

1. 向下調(diào)整的時(shí)間復(fù)雜度是O（N）
   

2. 向上調(diào)整的時(shí)間復(fù)雜度是O（NlogN）
   
   咋一看好像第二種方法時(shí)間復(fù)雜度更牛，但實(shí)際上這兩種方法的時(shí)間復(fù)雜度都是O（NlogN）。我們討論的只是向下調(diào)整和向上調(diào)整。
   
   總的來(lái)說(shuō)，堆排序的時(shí)間復(fù)雜度是O（NLogN）。兩種方法都在這個(gè)量級(jí)，但第二種方法稍微高一點(diǎn)點(diǎn)。

---

3. 堆排序（topK問(wèn)題）

找出N個(gè)數(shù)中最大的（或最小的）前K個(gè)數(shù)。
有兩種方法：
法一：建N個(gè)大根堆，然后PopK次就可以。
法二：建有K個(gè)數(shù)的小根堆，遍歷剩下的數(shù)據(jù)，如果數(shù)據(jù)比堆頂元素大，就替換它，然后向下調(diào)整，最后這個(gè)小根堆的數(shù)據(jù)就是最大的前K個(gè)。
這里主要用法二

void PrintTopK(const char* file, int k)
{//首先要建立小根堆int* topk = (int*)malloc(sizeof(int) * k);if (topk == NULL){perror("malloc failed");return;}//從文件中讀取K個(gè)數(shù)據(jù)FILE* f = fopen(file, "r");if (f == NULL){perror("fopen failed");return;}for (int i = 0; i < k; i++){fscanf(f, "%d", &topk[i]);}//建小堆（之前寫的向下調(diào)整是調(diào)整大根堆，只需修改其中一些>或者<即可）for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(topk, k, i);}//將剩下的n-k個(gè)元素依次與根節(jié)點(diǎn)比較，比它大就入堆且向下調(diào)整//這樣將大的元素往下沉，小的元素不斷換掉，最終只剩下最大的K個(gè)元素int val = 0;int ret = fscanf(f, "%d", &val);while (ret != EOF){if (val > topk[0]){topk[0] = val;AdjustDown(topk, k, 0);}ret = fscanf(f, "%d", &val);}for (int i = 0; i <k; i++){printf("%d ", topk[i]);}fclose(f);
}
void CreateData()
{int n = 1000;srand(time(0));const char* file = "TestData.txt";FILE* f = fopen("TestData.txt", "w");//以寫的形式打開(kāi)if (f == NULL){perror("fopen fail");return;}for (int i = 0; i < n; i++){int x = rand() % 1000;//獲得0~999的數(shù)字fprintf(f, "%d ", x);}fclose(f);
}