K路归并排序(k-way merge sort) 代码(C++)本文地址: http://blog.csdn.net/caroline_wendyK路归并排序作为经典的外部排序算法, 是程序员必须要掌握的.知识概念参考: <数据结构>主要思想: 在k个已排序的文件中, 选择第一个值, 采用败者树, 更新二叉树结构, 最终选择最优值.代码仅供参考, 如最小值用(-1)代替, 最大值用(100)代替./** main.cpp** Created on: 2014年9月11日* Author: Spike*/#include <fstream> #include <iost...
#include<iostream>using namespace std;class quicksort{public:int quicks(int *a,int low,int high){int q=a[low];//q int i=low; int j=high; while(i<j) { while(q<=a[j]&&i<j) { j--; } if(i<j) { swap(a[i++],a[j]); } while(a[i]<=q&&i<j) { i++; } if(i<j) { swap(a[i],a[j--]...
#include <iostream> usingnamespace std;//插入排序法void insertSortMethod(int intArr[],int arrLen); void printArrInfo(int intArr[],int arrLen); int main() {int arr[] = { 1,3,5,2,4,7,9,6,8 };int len = sizeof(arr) / sizeof(int);insertSortMethod(arr,len);printArrInfo(arr,len);system("pause");return0; } //插入排序法void insertSortMethod(int intArr[],int arrLen) {int start = 0;for (int i = 0; i < arrLen...
SortAlgorithm.h#include <vector> usingnamespace std;class SortAlgorithm { public:SortAlgorithm(int = 10);void displayVector();void swap(int &, int &);void insertSort(); //O(n^2)void selectSort(); //O(n^2)void mergeSort(); //O(n log n)void bubbleSort(); //O(n^2)void quickSort( int , int ); //worst: O(n^2), best: O(n l...
给定n个字符串，将这n个字符串按照字典序进行排列，此处用排列函数是C++的库函数sort，产生如下两个疑问，望大佬解答#include <iostream> #include <algorithm> #include <string> #include <vector>usingnamespace std; /* ********************************************** Q1:为什么定义类的数组，无法用sort函数排序呢？ 会出现数组越界的情况，求解答 ********************************************* int main() {string str[1...
问题：现有一整型数组int input[]={...};如果数组元素个数是奇数，则以中间一个为最大，左边第一个次之，右边第一个再次之。。。如此排序后，最左边第二小，最右边最小如果数组元素个数是偶数，则以中间两个的右边那个为最大，左边第一个次之，右边第一个再次之。。。如此排序后，最右边第二小，最左边最小举例：奇数个如：input[]={3,4,8,1,9};排序后：input[]={3,8,9,4,1};偶数个如：input[]={3,4,8,1,9,6};排序后：input[]={1,4...
1.冒泡排序冒泡排序是O（N^2）复杂度的排序算法，效率较低，需要N趟遍历，每次将候选集中最小的数通过交换浮到最上面；template <typename Type>void BubbleSort(vector<Type> &arraySort, int lowIndex, int hightIndex){ bool bChange; for (int i=lowIndex; i<hightIndex; ++i) { bChange = false; for (int j=hightIndex; j>i; --j) { if (arraySort[j-1] > arraySort[j]) ...
1.插入排序，最简单的排序，理想情况为N，一般情况为N的平方。c++: template <typename Comparable> void insertionSort(vector<Comparable> & a) {int j;for (int p=1;p<a.size();p++){Comparable temp = a[p];for(j=p;j>0 && temp<a[j-1];j--)a[j] = a[j-1];a[j] = temp;} }python: def func(a):for i in xrange(len(a)):temp = a[i]j = iwhile (j>0 and temp<a[j-1]):a[j] = a[j-1]j--a[j] = tempreturn a 原文：http://www.cnb...
# include<iostream> #include<stdio.h>usingnamespace std;void maopao(int *list){int i,j,temp;for(i=0;i<9;i++){for(j=0;j<9-i;j++){if(list[j]>list[j+1]){temp = list[j];list[j] = list[j+1];list[j+1] = temp;//用于检测每一步的输出/* cout<<"i等于"<<i<<"j等于"<<j<<endl;for(int temp=0;temp<10;temp++){cout<<list[temp]<<" ";}cout<<endl;*/}}} }int main(){int list[10];int n =9,m=0,i;cout<<"input 10 number"<<e...
经过上几篇对排序算法的了解，我们发现，所谓的排序也就是确定一个数组中每个元素的位置，然后对号入座，其过程也就是找到该元素的位置。确定位置，使用二分法可以达到很高的效率，我们将他应用到插入排序中就算是对上篇中排序的一种优化，能提高效率。基本思想： 与上篇中的插入排序类似分已排序和未排序部分，然后将未排序 部分元素逐个插入,但是插入的过程不同,需要每次求一个 中间位置,和中间位置元素比较大小,然后根据...
map是用来存放<key, value>键值对的数据结构，可以很方便快速的根据key查到相应的value。假如存储学生和其成绩（假定不存在重名，当然可以对重名加以区分），我们用map来进行存储就是个不错的选择。 我们这样定义，map<string, int>，其中学生姓名用string类型，作为Key；该学生的成绩用int类型，作为value。这样一来，我们可以根据学生姓名快速的查找到他的成绩。 但是，我们除了希望能够查询某个学生的成绩，或许还想看看...
1 #include <iostream>2 #include <vector>3usingnamespace std;4 5//交换int 6void swap(int& a, int& b){7int temp = a;8 a = b;9 b = temp; 10}11 12//冒泡 13void BulletSort(vector<int>& nums){14int n = nums.size();15for (int i = 0; i < nums.size()-1; i++){16for (int j = 0; j < nums.size() - i -1; j++){17if (nums[j] > nums[j+1]){18 swap(nums[j], nums[j+1]);19 }20 ...
void quickSort(int a[], int low, int high){ if (low <= high) return; int i = low; int j = high; int key = a[i]; while (i < j) { while (i < j && a[j] >= key) --j; a[i] = a[j]; while (i < j && a[i] <= key) ++i; a[j] = a[i]; } a[i] = key; quickSort(a, low, i - 1); quickSort(a, i + 1, high);}原文：http://sharep.blog...
继续C++11在头文件algorithm中添加的算法。至少我认为，在stl的算法中，用到最多的就是sort了，我们不去探索sort的源代码。就是介绍C++11新增的几个关于排序的函数。对于一个序列，我们怎么知道他是不是有序的呢？这就用到了：is_sorted 原型：template <class ForwardIterator>ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last);template <class ForwardIterator, class Compare>ForwardIterator ...
#include <iostream>usingnamespace std;int maxbit(int *a,int n) {int d=1;//一位int p=10;//十进制for(int i=0;i<n;i++){while(a[i]>=p){p*=10;++d;}}return d; }void Radixsort(int *a,int n) {int radix=1;int k;int d=maxbit(a,n);int *tmp=newint[n];//桶int *count=newint[10];//计数器for(int i=1;i<=d;i++){for(int j=0;j<10;j++){count[j]=0;//计数器每次都清零 }for(int j=0;j<n;j++){k=(a[j]/radix)%10;//取余...