做网站1核1g服务器够吗,外贸兼职平台,企业号码查询系统,建筑工程人才培训网选择排序 每一次从待排序的数据元素中选出最小#xff08;或最大#xff09;的一个元素#xff0c;存放在序列的起始位置#xff0c;直到全部待排序的数据元素排完 。 如果我们用扑克牌来举例#xff0c;那么选择排序就像是提前已经把所有牌都摸完了#xff0c;而再进行牌…选择排序 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 如果我们用扑克牌来举例那么选择排序就像是提前已经把所有牌都摸完了而再进行牌之间的排序而插入排序则是边摸边排。 直接选择排序 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的array[i]–array[n-2]array[i1]–array[n-1]集合中重复上述步骤直到集合剩余1个元素 直接选择排序的特性总结 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定 那么下面我先将代码展示给大家然后再为大家讲解其中奥妙
void SelectSort(int* a, int n) {int begin 0;int end n - 1;while (begin end) {int min begin;int max begin;for (int i begin 1; i end; i) {if (a[i] min) {min i;}if (a[i] max) {max i;}}Swap(a[begin], a[min]);if (max begin){max min;}Swap(a[end], a[max]);begin;end--;}
}首先呢我们先把起始位置的下标和最后位置的下标给记录下来并将最小值和最大值的下标都初始化为begin外面再套上一层循环限制条件为beginend当两个下标走到一起或者错开时就会结束循环也就排好了。
而while循环里面的才是排序的逻辑部分for循环从begin的下一个位置开始到end的位置结束并在其中进行比较改变每一次循环中最大值和最小值的下标并在循环结束后交换最小值和begin下标值的位置最大值与end下标值的位置最后begin和end都往中间走开始下一轮循环
不过需要注意的是我们加入了一个if判断语句其实这是为了防止最大值就在begin下标时原来的最大值会和最小值交换位置然后最小值会被换到end的位置上成为最大值那样子的话就会出现错误排序便失败了;但加上这个之后在第一次交换过后max的值到了min的下标这个时候只需要把max下标也改为min这个时候替换就不会再把最小值给替换到最后而是最大值了。这样讲可能也有点绕给大家画个图便于理解。 相信大家根据函数看就可以看懂啦还是很好理解的
堆排序
相比于刚才的直接选择排序想必当然还是堆排序更加吸引大家的注意那就让我们开始学习吧 堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 堆排序的特性总结 堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定 代码如下~
void HeapSort(int* a, int n) {for (int i 0; i n; i) {AdjustUp(a, i);//建大堆}int end n - 1;while (end 0) {Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}虽然堆排序的本体很小但是千万不能忽视了向上调整算法和向下调整算法所以还是把这一串代码附在下面
void AdjustUp(int* a, int child) {int parent (child - 1) / 2;while (child 0) {if (a[child] a[parent]) {Swap(a[child], a[parent]);}else {break;//这里没必要return}child parent;parent (parent - 1) / 2;}
}void AdjustDown(int* a, int size, int parent) {int child parent * 2 1;//假设左子节点小于右子节点//右子节点不一定有可能会越界while (child size) {if (child 1 size a[child 1] a[child]) {child;//其实就是左子节点转换到右子节点上}if (a[child] a[parent]) {Swap(a[child], a[parent]);parent child;//parent移动到原来child的位置上child child * 2 1;//child来寻找自己的下一个左子节点}else {break;}}
}虽然堆排序中有堆但是我们不可能真的建一个堆然后再进行排序毕竟手搓一个堆的函数还是挺麻烦的所以我们本质上是模拟堆插入的过程建堆并利用其逻辑对数组中的元素进行排序我们还是用例子说话。并且在建堆之前还有一个需要注意的因为现在给的例子是以升序排列所以我们现在建立的是大堆需要在向上调整算法和向下调整算法中改变大于小于符号
建立大堆的原因还有一个那就是如果建立小堆的话当删除堆顶元素最小值时剩下的数还看作堆的话关系就全乱了需要重新建堆浪费时间。
第一步建堆 第二步排序 其实就是将end定为数组的最后一个下标n-1然后堆顶元素和最后一个元素交换向下调整之后删除最后一个元素最后end走到0下标的时候就结束写一两步大家看看 实际上虽然在堆中删除了但我们直到此时9已经到了n-1下标的位置也就是排在了最大值的位置上。而向下调整之后我们会发现8又到了最上方并且也是目前的最大值也就是下一次8会与2交换成为次大的值2又与7交换2又与6交换那么很明显下一次循环交换的数就是7了之后就是6这样最大值就慢慢的被调节到了end的位置最后数组中的元素都正序排列。
优化
除了使用向上调整建堆其实我们还可以使用向下调整建堆进行讲解后大家甚至还会发现向下调整更加简洁方便
for (int i (n-1-1)/2; i 0; --i){AdjustDown(a, n, i);}以上便是将向上调整改为向下调整算法后的函数为什么从n-1-1/2开始呢是因为n-1是最后一个元素的下标而n-1-1/2则是找到其父节点然后从底端进行调整。
而至于为什么向下建堆更简洁呢给大家用数学写写大家就懂啦 eg.n2^h-1上面的T(n)都是T(h)到下面才是T(n)写错了QAQ 由此可以看出向下调整建堆的时间复杂度为O(n)下面我们计算向上调整建堆的时间复杂度 由此可知向上调整建堆的时间复杂度为O(nlogn)是大于向下调整建堆的这样子的话我们以后如果使用堆排序我们就可以直接忽略向上调整算法只写向下调整算法代码量可以更少时间复杂度也更精简
topK问题 TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下 用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 void PrintTopK(int* a, int n, int k) {int* heap (int*)malloc(sizeof(int) * k);if (heap NULL) {perror(malloc fail);return;}for (int i 0; i k; i) {heap[i] a[i];AdjustUp(heap, i);//先用前k个数创建一个小堆}for (int i k; i n; i) {if (a[i] heap[0]) {heap[0] a[i];//从k下标开始遍历数据如果大于heap[0]就让其成为heap[0]AdjustDown(heap, k, 0);//然后向下调整}}for (int i 0; i k; i) {printf(%d , heap[i]);//打印最大的k个数}printf(\n);free(heap);//记住释放heap开辟的内存
}我们还是照样举一个例子虽然topK是在n大于k很多的情况下才使用的但为了看上去简单我们选择两个相近的n与k 我们在插入后进行了两次向下调整由此可知当我们进行完所有的向下调整之后留在k个元素小堆中的元素一定是最大的几个
当然除了从数组中取出的方法我们还可以写出一种从文件中拿出数据并排序的topK函数大家请看
void CreateNDate()
{// 造数据int n 10000000; // 设置要生成的数据数量srand(time(0)); // 使用当前时间作为随机数种子确保每次运行生成的随机数不同const char* file data.txt; // 指定数据文件的名称FILE* fin fopen(file, w); // 以写模式打开文件if (fin NULL){perror(fopen error); // 输出文件打开错误信息return;}// 随机生成n个整数并将其写入文件for (int i 0; i n; i){int x (rand() i) % 10000000; // 生成0到9999999之间的随机整数加i是因为随机数最多只可以生成3万多个会有重复的这样能保证重复率大大降低fprintf(fin, %d\n, x); // 将随机数写入文件}fclose(fin); // 关闭文件
}void PrintTopK(const char* file, int k)
{FILE* fout fopen(file, r); // 以只读模式打开文件if (fout NULL){perror(fopen error); // 输出文件打开错误信息return;}// 建一个k个数小堆int* minheap (int*)malloc(sizeof(int) * k); // 分配大小为k的整型数组内存if (minheap NULL){perror(malloc error); // 输出内存分配错误信息return;}// 读取前k个数构建最小堆for (int i 0; i k; i){fscanf(fout, %d, minheap[i]); // 从文件中读取整数构建最小堆AdjustUp(minheap, i); // 执行向上调整维护最小堆性质}int x 0;while (fscanf(fout, %d, x) ! EOF) // 从文件中读取整数直到文件结束{if (x minheap[0]) // 如果当前数字大于堆顶元素{minheap[0] x; // 将堆顶元素替换为当前数AdjustDown(minheap, k, 0); // 执行向下调整维护最小堆性质}}for (int i 0; i k; i){printf(%d , minheap[i]); // 输出最小堆中的前k个元素}printf(\n);free(minheap); // 释放动态分配的堆内存fclose(fout); // 关闭文件
}以上就是选择排序中的几个问题下一节排序我们讲解的是交换排序欢迎大家持续收看
