1.简单选择排序
1.1.算法思想
遍历数组，每次找到一个最小的元素插入到表头位置
1.2代码
//交换元素 void swap(int &a, int &b){ int temp = a; a = b; b = temp; } //简单选择排序 void SelectSort(int arr[], int n){ //遍历数组 for (int i = 0; i < n; i++){ //标记当前数组中最小值元素的下标，初始为第 i 个元素 int min = i; //从i + 1开始遍历数组 for (int j = i + 1; i < n; j++){ if (arr[j] < arr[min]) min = j; } //交换第 i 个元素和最小值元素 swap(arr[i] , arr[j]); } }
1.3.时间复杂度和稳定性
1.时间复杂度：
最好情况：有序，进行0次移动
最坏情况：逆序，进行不超过3（n - 1）次移动
无论有序还是无序，都需要进行n ( n - 1) / 2次比较，区别仅在于移动次数，因此，O（n^2）
2.空间复杂度O（1）
3.稳定性：不稳定
4.适用性：顺序和链式
2.堆排序
2.1.算法思想
A.堆的本质是一棵完全二叉树
大根堆：根 >= 左右子树 L(i) >= L (2i) && L(i) >= L(2i + 1) (2i 和 2i + 1 为根节点的左右子树)
小根堆：根 <= 左右子树 L(i) <= L (2i) && L(i) <= L(2i + 1)
B.每一趟将大根堆的堆顶元素加入有序子序列（与待排序序列中的最后一个元素交换），交换后，对待排序序列重新进行大根堆的调整
1.堆顶元素为87，与9交换，且堆元素 - 1
2.9不满足大根堆的定义，开始下坠
3.9的左右孩子分别为45和78→78 > 45→78 > 9→9与78交换
4.9的左右孩子分别为65和53→65 > 53→65 > 9→9与65交换
5.堆中元素符合大根堆定义；将堆顶元素78与数组中最后一个元素53对换，堆元素 - 1
6.53的左右孩子分别为45和65→65 > 45→65 > 53→53与65交换
7.堆中元素满足大根堆定义；堆顶元素65与堆中最后一个元素9交换
8.9的左右孩子分别为45和53→53 > 45→53 > 9→09与53交换
9.堆中元素满足大根堆定义；堆顶元素53与堆中最后一个元素17交换
10.17的左右孩子分别为45和09→45 > 09→45 > 17→17与45交换
11.17只有左孩子32→32 > 17→32与17交换
12. 堆中元素满足大根堆定义；堆顶元素45与堆中最后一个元素17交换
13.17的左右孩子分别为32和09→32 > 09→32 > 17→17与45交换
14.堆中元素满足大根堆定义；堆顶元素32与堆底元素09交换，堆元素-1
15.09只有左孩子17→17 > 09→09与17交换 
16.堆顶元素17与堆底元素09交换，堆元素-1，此时堆中只有一个元素，排序结束
2.2代码
2.2.1大根堆的建立
把所有非终端结点（i <= n / 2）遍历一遍，检查是否符合大根堆 / 小根堆的特性（从后往前）：
A.不满足，左右孩子先进行一次判断，找到更大的孩子
B.判断根节点是否满足大于这个更大的孩子，即根 >= 左右孩子，不满足，则与这个孩子交换
C.若进行B的交换操作，则有可能破坏了下一级的堆的特性，则采用相同方式对下一级进行调整（递归，元素不停下坠）
注意：外层循环的 i 是 <= len，判断的是 i 该元素是否有孩子；而内层循环中的 i 是 < len，此时需要判断是否有右兄弟
//调整以k为子树的大根堆 void HeadAdjust(int arr[], int len, int k){ //数组下标0保存第k个元素 arr[0] = A[k] //找到第k个元素的左孩子 for (int i = 2 * k; i <= len; i *= 2) { //判断左右孩子谁更大 if (i < len && arr[i] < arr[i + 1]) i++; //根节点大于孩子结点中更大的结点，跳出循环 if (arr[k] > arr[i]) break; //小于，则孩子结点和根节点的值和下标都交换 else { arr[k] = arr[i]; k = i; } }//for //原根节点的值放入最终位置 arr[k] = arr[0]; } void BuildMaxHeap(int arr[], int len) { //从分支节点开始往上遍历调整 for (int i = len / 2; i > 0; i--) { HaedAdjust(arr, len, i); } }
2.2.2.大根堆排序
//交换元素 void swap(int &a, int &b){ int temp = a; a = b; b = temp; } //大根堆调整 void HeapAdjust(int arr[], int k, int len){ arr[0] = arr[k]; for (int i = 2 * k; i <= len; i *= 2) { if (i < len && arr[i] < arr[i + 1] ) i++; if (arr[k] > arr[i]) break; else { arr[k] = arr[i]; k = i; } } arr[k] = arr[0]; } //大根堆的建立 void BuildMaxHeap(int arr[], int len){ for (int i = len / 2; i > 0; i++){ HeapAdjust(arr, i, len); } } //大根堆排序 void HeapSort(int arr[], int len){ //初始化堆 BuildMaxHeap(arr, len); //循环往前遍历数组 for (int i = len; i > 1; i++) { //交换堆顶元素和堆底元素 swap(arr[i], arr[1]); //调整数组的无序部分 HeapAdjust(arr, i -1, i); } }
2.3.时间复杂度和稳定性
1.时间复杂度：O（nlog2n）
A.建堆过程比较次数不超过4n，建堆复杂度O（n）即BuildMaxHeap
B.排序总共进行n - 1趟：根节点最多下坠h - 1层，最多对比2次关键字，不超过O（h） = O（log2n）（树高）因此，每趟时间复杂度为（log2n）
2.稳定性：不稳定
2.4.小根堆的插入
A.将新元素插入表尾
B.然后与其双亲结点进行比较，若小于双亲结点，则与双亲结点进行交换
C.循环B直到该结点大于双亲结点
1.在堆底插入13
2.13 < 根节点32→13和32交换
2.13 < 根节点17→13和17交换；交换后13 > 根节点09，满足小根堆定义，停止上升
2.5.小根堆的删除
A.用堆底元素E移动被删除元素的位置
B.比较E的孩子结点，找到更小的孩子结点MIN，若MIN < E，则进行交换
C.循环进行B，直到E无法继续下坠
1.删除13
2.让堆底元素移动到原13在数组中的位置
3.46的左右孩子分别为17和45→17 < 45→17＜46→17与46交换；交换后满足小根堆定义，停止下坠
4.46的左右孩子分别为53和32→32 < 53→32＜46→32与46交换；
3.王道课后题
typedef struct LNode{ struct LNode *next; elemtype data; }LNode, *LinkList; LinkList SelectSort(LinkList &L){ LNode *p = L->next, *last = L; L->next = NULL; //循环直到p指向空 while (p) { //s用于遍历数组，min用于标记当前已遍历链表的最小值 LNode *s = p, pre = NULL, min = s, minpre = NULL; while (s) { //找到最小值，更新min和minpre if (s->data < minNode->data) { minpre = pre; min = s; } //s和pre向后移 pre = s; s = s->next; } //当前链表剩余至少两个元素，修改当前元素的前驱的next指针 if (minpre) minpre->next = min->next; //将该元素插入L后（尾插法） last->next = min; last = last->next; } //last的next置空 last->next = NULL; return L; }
bool IsMinHeap(int arr[], int len){ //从数组下标为1开始作为数组第一个元素开始向后遍历 for (int i = 1; i < n / 2; i++){ //k为左孩子，j为右孩子 int k = 2i, j = 2i + 1; //当前元素大于左孩子，返回false if (arr[i] > arr[k]) return false; //判断右孩子是否存在 else if (j <= len) { //当前元素大于右孩子，返回false if (arr[i] > arr[k) return false; } } //循环结束，返回true return true; }
