一、前言 堆排序是利用堆这种数据结构而设计的一种排序算法。时间复杂度为 O(n * lg n)。 介绍堆排序前，我们先介绍一下堆的相关概念，如果你对堆的概念还不熟悉的话可以看看。 二、堆 1. 示意图2. 性质 除最底层外，该树是完全充满的，且是从左到右填充。 树的根结点是 A[ 1 ]，若某一结点下标为 i，则很容易得到它的父节点为 i/2，左子结点为 2i，右子结点为 2i + 1。 注意： 数组的索引是 0 开始的，其左右子结点分别为 2i + ...
快速排序模版，代码如下： #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <vector> #define ll long long using namespace std ;pair<int,int>partition( vector<int> &a ,int l, int r ){int less = l-1,more = r ;while ( l < more ){if ( a[l] < a[r] ){swap(a[l++],a[++less]) ;}else if ( a[l] > a[r] ){swap(a[l],a[--more]) ;}else{l ++ ;}}swap(a[more],a[r]) ;return make_pa...
堆分为大根堆（最大堆）和小根堆（最小堆），堆排序就是二叉堆的升级版，实际上是一棵完全二叉树 不同的是这棵二叉树里每个节点保证父节点都小于孩子节点 最后进行堆排序，将堆顶最小的节点（第一个）与最后一个节点（最大的节点）进行交换，对剩下的进行调节，令其满足最小堆#include <iostream> #include <cstdlib>using namespace std;void MaxHeapIfy(int A[], int length, int i) //维护 {int left = i * 2; //节点i的左孩子...
基本步骤就是先按照weight排一次序，再按增加了额外的权值后再排一次序就好了，注意对应关系，简单的结构体排序。#include <iostream> #include <cmath> #include <stdio.h> #include <cstring> #include <algorithm> #include <cstring>using namespace std;int extra[15] ;typedef struct{int weight ;int number ; }meassage ;bool cmp( meassage a , meassage b ){if ( a.weight == b.weight ){return a.number < b.number ;}r...
第一种方法是构建一个空字符串maxx，每次和输入的字符串比较，找到最大的则更新maxx串，然后更新位置信息。 所谓最大就是 输入的字符串的长度大于maxx的长度或者在长度相等的情况下比较字典序的大小。最后输出信息即可。 详情见代码#include <iostream> #include <cstdio> #include <algorithm> #define ll long longusing namespace std ;int main(){int n ;cin >> n ;string str ;string maxx = "" ;int pos = -1 ;for ( int i =...
Shell排序 ? Shell排序是大量数据需要排序时，更为高效的插入排序。它的算法思想基于插入排序的算法思想 流程： （1）将n个元素数组分成n/2个数字序列，第一个数据和第n/2个数据为一对，等等，以此类推 （2）一次循环使每一个数对排列好顺序 （3）变成n/4个数对，再次排序。 （4）不断重复上述过程，随着序列减少直至最后变为1个，完成排序。 具体如何怎么排的可以运行代码查看每一步排序。 ? ? #include<iostream> #include<cstdl...