选择排序（直接选择排序与堆排序的比较）

选择排序

选择排序时间复杂度

1. 直接选择排序思考⾮常好理解，但是效率不是很好。实际中很少使用，思路是先进行遍历找到元最小的元素，然后与第一个进行交换

2. 时间复杂度：O（ $n^{2}$ ）

3. 空间复杂度：O(1)

选择排序源码

void SelectSort(int* arr, int n)
{for (int i = 0; i < n; i++){int min = i;for (int j = i + 1; j < n; j++){if (arr[min] > arr[j]){min = j;}}swap(&arr[i], &arr[min]);}
}

上述代码的时间复杂度为：O（ $n^{2}$ ），但是不是最完美的所以我们进行优化一下，但是优化后时间复杂度还是O（ $n^{2}$ ）。这时就可以看出选择排序和冒泡排序的差别，冒泡排序优化后时间复杂度会进行改变但是选择排序就并不会改变。

堆排序

堆排序的分析

堆排序分为大根堆和小根堆两种方法，这两种方法主要区别的是升序还是降序。升序大根堆因为我们知道大根堆中最大位于堆顶的，经过最后一个与堆顶进行替换后最大元素会被换到后面，堆排序是基于数组的所以数值是逐渐增大的。同理分析（降序是小根堆）。

堆排序的时间复杂度

堆排序的时间复杂度要计算建堆的时间与置换的时间，以向下建堆排序为准：O(n + n ∗ log n) ，即O(n log n)。

向上建堆时间复杂度为：O(n ∗ log2 n)

向下建堆的时间复杂度为：O(n)

源代码

HeadSort.c

void swap(int* n, int* m)
{int tmp = *n;*n = *m;*m = tmp;
}
//向下调整
void HeapDown(int* arr, int parent, int n)
{//向下排序要注意是父节点与子节点两个中最小的进行比较//要限制child+1<nint child = 2 * parent + 1;//小堆排序//用child小于while (child < n){if (child + 1 < n && arr[child] > arr[child + 1]){//找到最小的节点，从而和父节点进行交换child++;}if (arr[child] < arr[parent]){swap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}

test.c

#include"HeapSort.h"
void HeapSort(int* arr, int n)
{//建堆// a数组直接建堆 O(N)for (int i = (n-1-1)/2; i >= 0; --i){HeapDown(arr, i, n);}// O(N*logN)//升序---大堆//降序----小堆//循环将堆顶数据跟最后位置（会变化，每次减少一个数据）的数据进行交换int end = n - 1;//取堆顶返回的是堆的数据结构，而不是数组，其次也是用堆顶进行覆盖原来数据//所以使用了堆顶与堆尾的向下调整，并且每次让end--while (end > 0){swap(&arr[0], &arr[end]);HeapDown(arr, 0, end);end--;}//打印for (int i = 0; i < n; i++){{printf("%d ", arr[i]);}}
}
int main()
{int arr[] = { 1,2,3,4,5,6 };HeapSort(arr, 6);
}

快速排序

快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列在相应位置上为⽌

快速排序中部分细节分析

快速排序的细节较多主要在一下两个部分。

1.left <= right？这种情况是为了预防相遇值的精度大于精准值，这样若进行替换就会造成错误的交换方式。

2.arr[right] > arr[base]？

这种情况主要是为了防止，出现相同数据造成时间复杂多过高，最好就是在递归是把一个大的队列分为大小相同的两个，然后在进行递归。

递归时的判断条件

快排特性

时间复杂度为 0(n log n)、自适应排序：在平均情况下，哨兵划分的递归层数为 log n ，每层中的总循环数为n ，总体使用0(n log n)时间。在最差情况下，每轮哨兵划分操作都将长度为n 的数组划分为长度为 0 和 n−1 的两个子数组，此时递归层数达到 n ，每层中的循环数为 n ，总体使用 0( $n^{2}$ ) 时间。

空间复杂度为 0(n )、原地排序：在输入数组完全倒序的情况下，达到最差递归深度 n，使用 0(n )栈帧空间。排序操作是在原数组上进行的，未借助额外数组。

非稳定排序：在哨兵划分的最后一步，基准数可能会被交换至相等元素的右侧。

快排的优点

从名称上就能看出，快速排序在效率方面应该具有一定的优势。尽管快速排序的平均时间复杂度与“归并排序”和“堆排序”相同，但通常快速排序的效率更高，主要有以下原因。

出现最差情况的概率很低：虽然快速排序的最差时间复杂度为 0( $n^{2}$ ) ，没有归并排序稳定，但在绝大多数情况下，快速排序能在 0(n log n) 的时间复杂度下运行。

缓存使用效率高：在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。而像“堆排序”这类算法需要跳跃式访问元素，从而缺乏这一特性。

复杂度的常数系数小：在上述三种算法中，快速排序的比较、赋值、交换等操作的总数量最少。这与 “插入排序”比“冒泡排序”更快的原因类似。

快排源码

//快速排序
void swap(int* n, int* m)
{int temp = *n;*n = *m;*m = temp;
}
int _QuickSort(int* arr, int left, int right)
{int base = left;left++;while (left<=right){while (left <= right && arr[right] > arr[base]){right--;}while (left <= right && arr[left] < arr[base]){left++;}if (left <= right){//隐藏细节swap(&arr[left++], &arr[right--]);}}//此时已经不满足，left<=right这时候把right和关键值进行置换swap(&arr[base], &arr[right]);return right;
}
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//[left,right]--->找基准值midint keyi = _QuickSort(arr, left, right);//左子序列：[left,keyi-1]QuickSort(arr, left, keyi - 1);//右子序列：[keyi+1,right]QuickSort(arr, keyi + 1, right);
}