如何做一家门户网站,公司注册公司哪个好,如何注册自己的网站,聊天app推广代理前言
上一期我们已经介绍了#xff0c;排序、为什么要有排序以及排序在实际生活中的应用。并且介绍并实现了直接插入排序和它的优化即希尔排序~#xff01;本期我们再来学习一组排序 ---- 选择排序即直接选择排序和堆排序~#xff01;
本期内容介绍 直接选择排…前言
上一期我们已经介绍了排序、为什么要有排序以及排序在实际生活中的应用。并且介绍并实现了直接插入排序和它的优化即希尔排序~本期我们再来学习一组排序 ---- 选择排序即直接选择排序和堆排序~
本期内容介绍 直接选择排序 堆排序 选择排序的基本思想 每次从待排序的数据元素的序列中选出最小或最大的一个元素存放在当前序列的起始位置直到将全部待排序的数据元素排完。 直接选择排序 在元素集合a[i].....a[n-1]中选择一个最大或最小的数据如果他不是这个序列中的最后一个或第一个则与该序列中的最后一个或第一个进行交换将剩余的元素重复上述操作直到序列的元素只有一个则结束 OK举个栗子画个图这里是以升序距离的 OK直接选择排序的过程就是这样的下面我们来实现一下还是和以前一样先写单趟再来改造整体
单趟
int left begin;//当前序列的最左端
int min begin;//最小的元素的下标
for (int i begin; i n; i)
{if (a[min] a[i])min i;
}Swap(a[left], a[min]);//最左端的元素与当前序列中最小的元素交换
整体
直接选择排序改造整体也很简单只需要让每个元素都重复单趟即可~
void SelectSort(int* a, int n)
{for (int begin 0; begin n; begin){int left begin;//当前序列的最左端int min begin;//最小的元素的下标for (int i begin; i n; i){if (a[min] a[i])min i;}Swap(a[left], a[min]);//最左端的元素与当前序列中最小的元素交换}
}
OK测试一下 OK没有问题。这样写实每次找到当前序列中最小的一个然后与最左端升序交换我们其实可以对他进行一个小优化的---每次找到当前序列中的两个元素(一个最小一个最大)最小的与当前序列的最左端交换最大与当前序列的最右端交换~ OK还是先写单趟在改造多趟
单趟
int min begin, max begin;
for (int i begin 1; i right; i)
{if (a[min] a[i])min i;//选出最小if (a[max] a[i])max i;//选出最大
}Swap(a[begin], a[min]);//最小与左端交换
Swap(a[right], a[max]);//最大与右端交换
整体
void SelectSort(int* a, int n)
{int begin 0, right n - 1;while (begin right){int min begin, max begin;for (int i begin 1; i right; i){if (a[min] a[i])min i;if (a[max] a[i])max i;}Swap(a[begin], a[min]);Swap(a[right], a[max]);begin;--right;}
}
这就是一次选出两个的整体。OK我们来个栗子测试一下 怎么没有实现排序呢是我们的思想有问题OK遇事不慌调试走起 这是调试找到的第一次最大和最小的元素的下标~然后下来就是最小与左端交换最大与右端交换但此时最大恰好在最左端一执行最小与最左端交换后在在执行在最大与最右交换时发现最大的已经不在原来的位置了~这就导致了上述的乱序 解决方案在交换完最小与最左端后判断一下最大的位置如果最大的是在最左端则此时最大值应该被换到了最小值的位置因此我们只需要调整一下最大值是在最小值的位置即可即max min~ void SelectSort(int* a, int n)
{int left 0, right n - 1;while (left right){int min left, max left;for (int i left 1; i right; i){if (a[min] a[i])min i;if (a[max] a[i])max i;}Swap(a[left], a[min]);if (max left)max min;Swap(a[right], a[max]);left;--right;}
}
再来测试一下 OK没有问题了~
复杂度分析 时间复杂度O(N^2) 单趟无论选择一个还是选择两个都得遍历一遍复杂度为O(N),整体还得遍历一遍O(N) 空间复杂度O(1) 堆排序
堆排序其实在前面的二叉树堆那里已经介绍并实现过了这来就等于回顾式的再过一遍~如果想了解堆这种他是具体咋搞的请点击二叉树的实现 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据进行实现排序的。 他既然是借助堆来实现的那得有堆即要建堆。这里有两种建堆的方式向上调整建堆向下调整排序向下调整建堆向下调整排序 他排序是采用删除的思想把最大或最小的换到最后然后对前N-ii123...n)个进行向下调整注意:升序建大堆降序建小堆 OK举个排序的例子 向上调整建堆
void HeapSort(HPDataType* a, int n)
{//向上调整建堆//O(N*lgN)for (int i 1; i n; i){AdjustUp(a, i);}//向下调整排序//O(N*lgN)int end n - 1;while (end){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
} 这里的向上调整建堆和上面堆的插入是一个思路时间复杂度是O(lgN*N),向下调整排序的时间复杂度是O(N*lgN)----有n个元素每排好一个一下下标也就是上面的删除的思路 向下调整建堆
void HeapSort(HPDataType* a, int n)
{//向下调整建堆//O(N)for (int i (n - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//向下调整排序//O(N*lgN)int end n - 1;while (end){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
} 向下调整建堆就是从倒数第一个元素的父节点开始向下调整为堆这样越往上层节点的左右子树必定是堆 OK测试一下 没问题~
复杂度分析 时间复杂度O(N*logN) 向下调整和向上调整的时间复杂度都是O(logN)即最多调整高度次但向上调整建堆是O(N*log)而向下调整建堆的O(N)如下图~删除排序的时间复杂度是O(N*logN)所以综合下来就是O(N*logN) 空间复杂度O(1) 向下调整建堆时间复杂度推导 向上调整建堆时间复杂度推导 OK本期分享就到这里好兄弟下期交换排序不见不散~
