1```2 #include<iostream>3 #include<algorithm>4 #include<vector>5 #include<map>6 #include<set>7usingnamespace std;8 9/*按key升序*/10void test01(){ 11 map<string,int,less<string> > map1; 12 map1.insert(pair<string,int>("aba",3)); 13 map1.insert(pair<string,int>("aaa",2)); 14 map1.insert(pair<string,int>("ddd",1)); 15 map1.insert(pair<string,int>("ccc",4)); 1617for(map<string,int>...
在C++中，对结构体的排序方式比C语言丰富的多。在C语言中，我们主要是通过qsort进行排序操作（抛开手写排序算法不说）。在C++<algorithm>中，有一个十分强大的排序函数sort，他的内部综合了许多种排序算法，因此非常高效。并且，用它来对结构体排序也十分方便。先贴一段示例代码： 1 #include <cstdio>2 #include <queue>3 #include <vector>4 #include <algorithm>5 #include <iostream>6usingnamespace std;7struct Mi{8int p;9i...
桶式排序 讲基数排序之前，先讲一下桶式排序，二者有较大关联。 桶式排序是一种排序方式，比如说有N个整数，这N个整数范围从1~M（0~M-1也行)，则可以创建一个数组count，大小为M，将所有元素先初始化为0，每个元素称为一个桶，这个数组有M个桶。然后将要排序的数字逐个读入，假设读到A这个数字，则数组对应的元素count[A]的值加1，即桶记录了落入该桶的数据的个数。读完后，按顺序输出非0的桶的index(count[index]为多少则...
转载自：http://blog.csdn.net/sailor_8318/article/details/30543831~n无序数组时间复杂度为O(n)排序有1,2,....一直到n的无序数组，求排序算法，并且要求时间复杂度为O(n)，空间复杂度O(1)，使用交换，而且一次只能交换两个数.（华为）分析：数组的特点是值和下标满足一定的关系，以此作为交换的终止条件。但这个算法的时间复杂度如何证明是O(n)呢？ void sortOnorder1(int array[], int len){ int temp; for(int ...
快数排序（低配算法）原理优化 （分治）将原来的N方优化为N*log（N）将逐一对比优化为分步/////////////以从大到小举例先确定分界点，将分界点的值命名为X（因为必须要在左右端点以内，所以一般取两端点之和除以2）然后以X为中心进行交换（将左边第一个比A大的数值的坐标记录，将右边第一个比A小的记录，交换两者的值）直到X的左边都比X大，X的右边都比X小，停止，向两边重复进行操作（这时以分界点为中心分为两部分，向左的部分右...
Sort a linked list using insertion sort.A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.With each iteration one element (red) is removed from the input data and inserted in-place into the sorted listAlgorithm of Insertion Sort:1Insertion sort iterates, consuming one input element each repetition, and growing a sorted outp...
我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。 排序算法大体可分为两种： 一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。 另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。下表给出了常见比较排序算法的性能： 为了便于以下描述，接下来全部算法的排序对象均为乱序数...
void ShellSort(int a[],int left,int right);//对a[left]到a[right]从小到大排序void ShellSort(int a[],int left,int right) {int len = right - left +1;int gap,i,j,temp;//Shell提出的增量选取规则n/2,n/4,...,2,1for(gap=len/2;gap>0;gap/=2)for(i=left+gap;i<=right;i++)for(j=i-gap;j>=left && a[j]>a[j+gap];j-=gap){ //a[j]和a[j+gap]为一个子序列temp = a[j]; /*当j-=gap后的子序列a[j],a[j+gap]已经处理则...
void BinaryInsertionSort(int a[],int left,int right);//对数组a[left]到a[right]段数据从小到大排序void BinaryInsertionSort(int a[],int left,int right) {int low,middle,high;int temp;int i,j;//待排元素left+1 ---> right 共right - left个，a[left]默认有序for (i=left+1;i<=right;i++){ temp = a[i];low = left; high = i - 1; //i-1为已排好序列的右边界while(low<=high){middle = (low + high) / 2;if (...
让字符串向量首先按字符串长度进行排序，长度短的在前，长的在后。如果长度相等则按字典序排序，并移除重复的字符串。去重复并按字典序排序：void elimDumps(vector<string> &words) {// 按字典序排序sort(words.begin(), words.end());// unique重排输入范围，使得每个单词只出现一次// 并排列在范围的前部，返回指向不重复区域之后一个位置的迭代器auto end_unique = unique(words.begin(), words.end());// 删除重复单词words.e...
#include <iostream>using namespace std;// 冒泡排序 (和鱼冒泡泡一样，从底部往水面冒) void BubbleSort(int A[], int n) {int i, j; // 冒泡中两层循环用到bool flag; // 判断排序是否结束for (i = 0; i < n - 1; ++i) { // 冒泡排序因为是将一个个值不停的冒到最终位置（也就是一次冒泡确定一个值的顺序），所以最多就n - 1次冒泡，其实可以试一下10,9,8,7,6,5这个逆序，当第五次冒泡结束后，5就在第一个了，不需要再继续了fla...
//合并排序 #include <iostream> #include <iomanip> using namespace std;void sort(int c[],int a[],int b[],int n) {int i=0;int j=0;//aint k=0;//bwhile(k!=5 && j!=5) { if(a[j]>b[k]){c[i++]=b[k++];}else{c[i++]=a[j++];}}while(j!=5){c[i++]=a[j++];}while(k!=5){c[i++]=b[k++];} }int main() {int a[]={2,3,4,5,8};int b[]={0,1,7,9,10};int c[10];sort(c,a,b,5);for(int i=0;i<10;i++){cout<<setw(4)<<c[i];} cout<<end...
原创文章，转载请注明出处！博客文章索引地址博客文章中代码的github地址# 预备知识 堆是一种特殊的树形数据结构，即完全二叉树。堆分为大根堆和小根堆，大根堆为根节点的值大于两个子节点的值；小根堆为根节点的值小于两个子节点的值，同时根节点的两个子树也分别是一个堆。 # 基本思路步骤一：建立大根堆--将n个元素组成的无序序列构建一个大根堆，步骤...
算法描述：从数组第二个元素开始向后扫描，将每个元素插到它前面所有元素的合适位置。下面给出整数数组的实现，对于其他复杂类型只需实现相应的自定义比较函数即可：#include <iostream> #include <math.h> using namespace std; const int Num=20; void exch(int* s,int a,int b) {int mid=s[a];for(int i=a;i>b;i--){s[i]=s[i-1];}s[b]=mid; } int main() { int array[Num]; int min=0; srand(2);//初始化随机数 for(int i=0;i<N...
#include <iostream> /* 输入一行字符串仅由小写字母所构成。 输出为一行，按 aa, bb, cc, …, zz 在字符串中的出现次数按从多到少， 将 aa, bb, cc, …, zz 排序，不同字母间以一个空格隔开，忽略行末空格。 阐述： 1.计算出现次数时是可重叠的，即在字符串 "aaaa" 中，aa 出现了三次 2.若出现次数相同，则按照字典序升序排列，比如若是ee，dd 都出现 1 次，则 dd 放在 ee 前面 3.若aa, bb, cc, …, zz 都没有出现过，则什么都不用...