文章目录
- 一、选择排序
- 二、堆排序
- 三、时间复杂度
- 四、稳定性
一、选择排序
思想：
将数组第一个元素作为min，然后进行遍历与其他元素对比，找到比min小的数就进行交换，直到最后一个元素就停止，然后再将第二个元素min，再遍历，以此下去直到最后一个数据
流程图：
代码实现：
//交换
void Swap(int* a,int* b) {
int t = *a;
*a = *b;
*b = t;
}
//打印
void Print(int* arr, int n) {
for (int i = 0;i < n; i++)
printf("%d ", arr[i]);
}
//直接选择排序
void SelectSort(int* arr, int size) {
for (int i = 0; i < size; i++)
{
int min = i;//从第一个开始
//每次从i+1的位置开始就不会影响到前面的了
for (int j = i+1; j < size; j++) {
//比较
if (arr[min] > arr[j])
min =j;//记录下标
}
Swap(&arr[i], &arr[min]);//交换
}
}
int main() {
int arr[] = { 4，3，1，5，2};
SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
Print(arr, sizeof(arr) / sizeof(arr[0]));
return 0;
}
运行结果：
选择排序优化：
我们可以设置一个min和一个max，将小的放到左边，大的放到右边，我们再设置两个控制左右两边下标的变量p，q，当它们相遇时就结束。
流程图：
特殊情况：max的位置等于p时，我们先交换arr[p]和arr[min],但是max指向p这个位置，但是p这位置的值已经改变了，这时我们就要进行纠正，将max=min，这样才能成功找到原来在p位置的值
如：
代码实现：
//交换
void Swap(int* a,int* b) {
int t = *a;
*a = *b;
*b = t;
}
//打印
void Print(int* arr, int n) {
for (int i = 0;i < n; i++)
printf("%d ", arr[i]);
}
//优化选择排序
void SelectSort1(int* arr, int size) {
int p = 0, q = size-1;//p指向数组开头，q指向数组最后一个位置
while (p < q) {//当错过或者相遇就结束
int min = p, max = p;//迭代位置
for (int i = p; i <= q; i++)
{
if (arr[min] > arr[i])//找到最小值
min = i;
if (arr[max] < arr[i])//找到最大值
max = i;
}
Swap(&arr[min], &arr[p]);//交换
if (max == p)//5 2 3 4 1//判断是否要纠正
max = min;
Swap(&arr[max], &arr[q]);//交换
p++, q--;
}
}
int main() {
int arr[] = { 4,3,1,5,2 };
SelectSort1(arr, sizeof(arr) / sizeof(arr[0]));
Print(arr, sizeof(arr) / sizeof(arr[0]));
return 0;
}
运行结果：
二、堆排序
堆：
结构性:用数组表示的完全二叉树;
有序性:任一结点的关键字是其子树所有结点的最大值(或最小值)
“最大堆(MaxHeap)”,也称“大顶堆”，即最大值所有父亲大于等于孩子
“最小堆(MinHeap)”,也称“小顶堆”，即最小值所有父亲小于等于孩子
小堆:堆顶数据是最小的，并且所有节点都小于左右子树
大堆:堆顶数据是最大的 ，并且所有节点都大于左右子树
用堆来实现排序：
（1）使用向下调整算法：
前提：左右子树必须是小堆或者大堆
作用：建堆
如：
左右子树对比选择，再与根比较
（2）建堆
当我们要实现升序时，通过向下调整法要建大堆
建的过程：因为使完全二叉树，我们可以从最后非叶点节点开始建，直到没有节点就结束。
如：
建大堆
树的左子树的下标等于根的下标*2+1，的下标等于根的下标 *2+2
建完后，我们可以将最后一个元素和第一个元素交换，然后再做向下调整即可不用重新建堆了，再让第一个元素和倒数第二个元素交换，以此类推…
为什么不建小堆呢？如果建小堆的话，用第一个根（最小值）就是数组的第一个元素了，我们不能动它，那么再让数组的第二元素重新做根，但是这样的话顺序就会被打破，又要重新建堆了，那样时间复杂度会提高（如何实现降序的话可以建小堆）
代码实现：
//交换
void Swap(int* a,int* b) {
int t = *a;
*a = *b;
*b = t;
}
//打印
void Print(int* arr, int n) {
for (int i = 0;i < n; i++)
printf("%d ", arr[i]);
}
//向下调整 大堆
void AdjustDwon(int *arr,int p,int size) {
int q = p;//节点位置
int z = q * 2 + 1;//节点左子树，z+1就是右子树的位置了
while (z<size) {//当z大于数组长度时就说明该节点不存在左右子树
//判断左右子树大小，后面是判断是否有右子树
if (arr[z] <arr[z + 1]&&z+1<size)
z += 1;
if (arr[z] > arr[q]) {//判断是否比根大
Swap(&arr[z], &arr[q]);
q = z;
z = q * 2 + 1;//迭代
}
else
break;
}
}
void HeapSort(int* arr, int size) {
//建堆，size-1-1就是除2（求子树公式反过来用，最后减一是因为我们求的是下标）
for (int i = (size - 1 - 1) / 2; i >= 0; i--) {
AdjustDwon(arr, i, size);
}
int ned = size - 1;
//最后一个下标位置开始，和下标为0的元素交换，一直交换下去，并且交换一次就调整一次
//当ned==1就证明排好了
while (ned>0) {
Swap(&arr[0], &arr[ned]);
AdjustDwon(arr, 0, ned);//重新调整
ned--;
}
}
int main() {
int arr[] = { 4,3,1,5,2 };
HeapSort(arr, sizeof(arr)/sizeof(arr[0]));
Print(arr, sizeof(arr) / sizeof(arr[0]));
return 0}
运行结果：
三、时间复杂度
选择排序：
n-1 ,n-2…2，1
是一个等差数列求前n-1项和，粗略来算就是n^2
所以时间复杂度为O（n^2）
堆排序：
建堆：O（n）
向下调整的时间复杂度为：
假设树高为 h，树的结点为n，因为n=2^h-1,那么h=log（n-1）（以2为底）
所以为O(logn-1)
我们还要进行n次这个向下调整（当然在进行的过程中n是会变化的）
那么总的次数n+nlogn
所以时间复杂度为O（nlogn）
四、稳定性
稳定性:
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[4]，且r[1]在r[4]之前，而在排序后的序列中，r[1]仍在r[4]之前，则称这种排序算法是稳定的;否则称为不稳定的。
选择排序：不稳定
如：
堆排序：不稳定
第一个9直接到最后了
以上就是我的分享了，如果有什么错误，欢迎在评论区留言。
最后，谢谢大家的观看！
文章出处登录后可见！
