分类目录归档:数据结构与算法

常见的数据结构与算法的C/C++实现

快速排序算法原理与实现

快速排序算法原理与实现
快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。一趟快速排序的算法是:

1)、设置两个变量I、J,排序开始的时候I = 1,J = N;
2)、以第一个数组元素作为关键数据,赋值给X,即X = A[1];
3)、从J开始向前搜索,即由后开始向前搜索(J = J – 1),找到第一个小于X的值,两者交换;
4)、从I开始向后搜索,即由前开始向后搜索(I = I + 1),找到第一个大于X的值,两者交换;
5)、重复第3、4步,直到I = J;

   例如:待排序的数组A的值分别是:(初始关键数据X:=49)
                   A[1]     A[2]     A[3]     A[4]     A[5]      A[6]     A[7]
                     49        38       65       97       76       13        27

进行第一次交换后:   27        38       65       97       76       13        49
                  	( 按照算法的第三步从后面开始找第一个小于X的值,此时J = 7)

进行第二次交换后:   27        38       49       97       76       13        65
                  	( 按照算法的第四步从前面开始找第一个大于X的值,65 > 49,两者交换,此时I = 3 )

进行第三次交换后:   27        38       13       97       76       49        65
			( 按照算法的第五步将又一次执行算法的第三步从后开始找,此时J = 6)

进行第四次交换后:   27        38       13       49       76       97        65
			( 按照算法的第四步从前面开始找大于X的值,97 > 49,两者交换,此时I = 4 )

此时再执行第三步的时候就发现I = J,从而结束一趟快速排序,那么经过一趟快速排序之后的结果是:27       38       13       49       76       97        65,即所有大于49的数全部在49的后面,所有小于49的数全部在49的前面。

快速排序就是递归调用此过程——以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:

初始状态 {49 38 65 97 76 13 27}
进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}
分别对前后两部分进行快速排序 {13} 27 {38} 49 {65} 76 {97}

1)、设有N(假设N=10)个数,存放在S数组中;
2)、在S[1。。N]中任取一个元素作为比较基准,例如取T=S[1],起目的就是在定出T应在排序结果中的位置K,这个K的位置在:S[1。。K-1]<=S[K]<=S[K+1..N],即在S[K]以前的数都小于S[K],在S[K]以后的数都大于S[K]; 3)、利用分治思想(即大化小的策略)可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。 如具体数据如下,那么第一趟快速排序的过程是:

数组下标: 
	1      2      3      4      5      6      7      8      9      10

	45     36     18     53     72     30     48     93     15     36

	I                                                              J

(1)      36     36     18     53     72     30     48     93     15      45
(2)      36     36     18     45     72     30     48     93     15      53
(3)      36     36     18     15     72     30     48     93     45      53
(4)      36     36     18     15     45     30     48     93     72      53
(5)      36     36     18     15     30     45     48     93     72      53

通过一趟排序将45放到应该放的位置K,这里K=6,那么再对S[1。。5]和S[6。。10]分别进行快速排序。

一般来说,冒泡法是程序员最先接触的排序方法,它的优点是原理简单,编程实现容易,但它的缺点就是–程序的大忌–速度太慢。下面我介绍一个理解上简单但编程实现上不是太容易的排序方法,我不知道它是不是现有排序方法中最快的,但它是我见过的最快的。排序同样的数组,它所需的时间只有冒泡法的 4% 左右。我暂时称它为“快速排序法”。

“快速排序法”使用的是递归原理,下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53,12,98,63,18,72,80,46, 32,21},先找到第一个数–53,把它作为中间值,也就是说,要把53放在一个位置,使得它左边的值比它小,右边的值比它大。{21,12,32, 46,18,53,80,72,63,98},这样一个数组的排序就变成了两个小数组的排序–53左边的数组和53右边的数组,而这两个数组继续用同样的方式继续下去,一直到顺序完全正确。

我这样讲你们是不是很胡涂,不要紧,我下面给出实现的两个函数:

/*
	n就是需要排序的数组,left和right是你需要排序的左界和右界,
	如果要排序上面那个数组,那么left和right分别是0和9
*/
void quicksort(int n[], int left,int right)
{
	int dp;
	if (left

我们上面提到先定位第一个数,然后整理这个数组,把比这个数小的放到它的左边,大的放右边,然后返回这中间值的位置,下面这函数就是做这个的。

int partition(int n[],int left,int right)
{
	int lo,hi,pivot,t;
	
	pivot = n[left];
	lo = left - 1;
	hi = right + 1;
	
	while(lo + 1 != hi) {
	     if(n[lo + 1] <= pivot)
	       lo++;
	     else if(n[hi - 1] > pivot)
	       hi--;
	     else {
	       t = n[lo + 1];
	       n[++lo]=n[hi - 1];
	       n[--hi]=t;
	     }
	}
	
	n[left] = n[lo];
	n[lo] = pivot;
	return lo;
}

这段程序并不难,应该很好看懂,我把过程大致讲一下,首先你的脑子里先浮现一个数组和三个指针,第一个指针称为p指针,在整个过程结束之前它牢牢的指向第一个数,第二个指针和第三个指针分别为lo指针和hi指针,分别指向最左边的值和最右边的值。lo指针和hi指针从两边同时向中间逼近,在逼近的过程中不停的与p指针的值比较,如果lo指针的值比p指针的值小,lo++,还小还++,再小再++,直到碰到一个大于p指针的值,这时视线转移到hi指针,如果 hi指针的值比p指针的值大,hi--,还大还--,再大再--,直到碰到一个小于p指针的值。这时就把lo指针的值和hi指针的值做一个调换。持续这过程直到两个指针碰面,这时把p指针的值和碰面的值做一个调换,然后返回p指针新的位置。

 
// 快速排序的递归实现 
void QuickSort(int arr[], int n)
{
     if(n <= 1)
     return;
     
     int i =0 , j = n - 1;
     int key = arr[0];
     int index = 0;
     
     while(i < j)
     {
             // 从后向前搜索 
             while(j > i && arr[j] > key)
             		j--;
             		
             if(j == i)
             		break;
             else
             {
             		//交换 a[j] a[i]
             		int tmp = arr[i];
             		arr[i] = arr[j];
             		arr[j] = tmp;
                index = j;
             }
             
             // 从前向后搜索
             while(i < j && arr[i] < key)
             		i++;
             		
             if(i == j)
             		break;
             else
             {
             		// 交换 a[i] a[j] 
             		int tmp = arr[i];
             		arr[i] = arr[j];
             		arr[j] = tmp;
                index = i;
             }             
     }    
      
     QuickSort(arr, index);
     QuickSort(arr + index + 1, n - 1 - index);
}

常见查找算法代码

常见查找算法代码

1.二分查找
原理:
二分查找的基本思想是:(设R[low..high]是当前的查找区间)
(1)首先确定该区间的中点位置:
mid = (low + high) / 2
(2)然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,具体方法如下:
  ①若R[mid].key>K,则由表的有序性可知R[mid..n].keys均大于K,因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R[1..mid-1]中,故新的查找区间是左子表R[1..mid-1]。
 ②类似地,若R[mid].keyend。
第二种方法是在[begin, end)这个半闭半开区间上进行迭代(end为begin+len),找到一个中点middle之后,将区间划分为[begin, middle)和[middle+1, end),子区间依然是半闭半开区间(且不包括middle);因为整数区间[begin, begin)是个空区间,所以迭代的终止条件是begin==end。这种实现方式和STL中容器的迭代器是很一致的

适用条件:
查找序列已经有序

// 二分查找算法
#include 

/** 非递归二分查找
 * @param array	要查找的数组
 * @param count	数组元素的个数
 * @param value	要查找的元素值
 */
int search(int array[],int count,int value)
{
	int left,right,middle;

	left = 0,right = count - 1;

	// 因为查找的区间为[left, right],左闭右闭区间,故循环的终止条件为left > right
	while(left <= right)
	{
		middle = (left + right) / 2;
		if(array[middle] > value)
			right = middle - 1;
		else if(array[middle] < value)
			left = middle + 1;
		else
			return middle;
	}

	return -1;
}

/** 递归二分查找
 * @param array	要查找的数组
 * @param low	第一个元素索引
 * @param high	最后一个元素的索引
 * @param value	要查找的元素值
 */
int search_recurse(int array[],int low,int high,int value)
{
	int middle;
	middle = (low + high) / 2;

	if(low < high)
	{
		if(array[middle] > value)
			return search_recurse(array,low,middle,value);
		else if(array[middle] < value)
			return search_recurse(array,middle + 1,high,value);
		else
			return middle;
	}
	else if(low == high)
	{
		if(array[middle] == value)
			return middle;
		else
			return -1;
	}
	else
		return -1;
}

int main()
{
	int array[] = {0,1,2,3,4,5,6,7,13,19};

	for(int i = 0; i < sizeof(array) / sizeof(array[0]); ++i)
		printf("%d ",array[i]);

	printf("\n");

	printf("count = %d\n",sizeof(array)/sizeof(array[0]));

	int index = search(array,sizeof(array)/sizeof(array[0]),13);
	printf("index = %d value = %d\n",index,array[index]);

	index = search_recurse(array,0,sizeof(array)/sizeof(array[0]),13);
	printf("index = %d value = %d\n",index,array[index]);
	
	return 0;
}

2.快速查找(找出数组中第k小元素,存入a[k - 1])

适用条件:无

#define cutoff (3)

void insertsort(int a[], int n)
{
	int i, j;
	int tmp;

	for (i = 1; i < n; i++)
	{
		tmp = a[i];
		for (j = i - 1; j >= 0 && a[j] > tmp; j--)
			a[j + 1] = a[j];
		
		a[j + 1] = tmp;
	}
}

void swap(int *a, int *b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

int median3(int a[], int left, int right)
{
	int center = (left + right) / 2;

	if (a[left] > a[center])
		swap(&a[left], &a[center]);
	
	if (a[left] > a[right])
		swap(&a[left], &a[right]);
	
	if (a[center] > a[right])
		swap(&a[center], &a[right]);

	swap(&a[center], &a[right - 1]);
	return a[right - 1];
}

void qsort(int a[], int left, int right)
{
	int i, j;
	int pivot;

	if (left + cutoff <= right)
	{
		pivot = median3(a, left, right);
		i = left;
		j = right - 1;
		for ( ; ; )
		{
			while (a[++i] < pivot) {}
			while (a[--j] > pivot) {}
			if (i < j)
				swap(&a[i], &a[j]);
			else
				break;
		}
		swap(&a[i], &a[right - 1]);

		qsort(a, left, i - 1);
		qsort(a, i + 1, right);
	}
	else
	insertsort(a + left, right - left + 1);
}

void qsearch(int a[], int k, int left, int right)
{
	int i, j;
	int pivot;

	if (left + cutoff <= right)
	{
		pivot = median3(a, left, right);
		i = left;
		j = right - 1;
		for ( ; ; )
		{
			while (a[++i] < pivot) {}
			while (a[--j] > pivot) {}
			if (i < j)
				swap(&a[i], &a[j]);
			else
				break;
		}
		swap(&a[i], &a[right - 1]);

		if (k <= i)
			qsort(a, left, i - 1);
		else
			qsort(a, i + 1, right);
	}
	else
		insertsort(a + left, right - left + 1);
}

常见排序算法代码

常见排序算法代码

1.插入排序

稳定
空间复杂度O(1)
时间复杂度O(n^2)
最差情况:反序,需要移动n*(n-1)/2个元素(1、2、3、4、5、6)
最好情况:正序,不需要移动元素(6、5、4、3、2、1)

void insertsort(int a[], int n)
{
	int i, j;
	int tmp;

	for (i = 1; i < n; i++)
	{
		tmp = a[i];
		// 从第一次循环开始,a[i]的左侧元素始终处于正序状态,则tmp小于a[i]左侧的第一元素时,a[i]就应该在当前位置,不会移动;
		// tmp大于a[i]左侧的第一元素时,需要将a[i]左侧的第一个元素的位置与a[i]的当前位置进行交换(一直递归到tmp小于时为止)
		for (j = i - 1; j >= 0 && a[j] < tmp; j--)
		      a[j + 1] = a[j];

		// j + 1为交换后,当前a[i]所在的位置;若传入进来的a[i]数组为正序,则只是将原值赋给原值。
		a[j + 1] = tmp;
	}
}

2.冒泡排序

 冒泡排序(BubbleSort)的基本概念是:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。如此下去,重复以上过程,直至最终完成排序。
  由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。

稳定
空间复杂度O(1)
时间复杂度O(n^2)
最差情况:反序,需要交换n*(n-1)/2个元素
最好情况:正序,不需要交换元素

void bubblesort(int a[], int n)
{
	int i, j;
	int tmp;

	for (i = n - 1; i > 0; i--)
	for (j = 0; j < i; j++)
	{
		if (a[j] > a[j + 1])
		{
			tmp = a[j];
			a[j] = a[j + 1];
			a[j + 1] = tmp;
		}
	}
}

3.选择排序
不稳定
空间复杂度O(1)
时间复杂度O(n^2)
最差情况:第一个元素为最大元素,其余元素正序,需要交换n-1个元素(例如:4 3 2 1)
最好情况:正序,不需要交换元素

void selectsort(int a[], int n)
{
	int i, j, k;
	int tmp;

	for (i = 0; i < n - 1; i++)
	{
		k = i;
		for (j = i + 1; j < n; j++)
		{
			if (a[j] < a[k])
			        k = j;
		}

		if (k != i)
		{
			tmp = a[i];
			a[i] = a[k];
			a[k] = tmp;
		}
	}
}

4.希尔排序(缩小增量排序)

不稳定
空间复杂度O(1)
时间复杂度优于插入排序,最坏情况下O(n^2)
最差情况:有n=2^k个元素,偶数位置上有n/2个同为最大的元素,奇数位置上有n/2个同为最小的元素,此时最优最后一趟进行插入排序(例如:1 5 2 6 3 7 4 8)
最好情况:正序,不需要移动元素

void shellsort(int a[], int n)
{
	int i, j, increment;
	int tmp;
	for (increment = n / 2; increment > 0; increment /= 2)
	{
		for (i = increment; i < n; i++)
		{
			tmp = a[i];
			for (j = i - increment; j >= 0 && tmp < a[j]; j -= increment)
			{
				a[j + increment] = a[j];
			}

			a[j + increment] = tmp;
		}
	}
}

5.堆排序

不稳定
空间复杂度O(1)
时间复杂度O(nlogn)

#define leftchild(i) (2 * (i) + 1)

void percdown(int a[], int i, int n)
{
	int child;
	int tmp;

	for (tmp = a[i]; leftchild(i) < n; i = child)
	{
		child = leftchild(i);
		if (child != n - 1 && a[child + 1] > a[child])
			child++;

		if (tmp < a[child])
			a[i] = a[child];
		else
			break;
	}

	a[i] = tmp;
}

void heapsort(int a[], int n)
{
	int i;
	int tmp;

	for (i = n / 2; i >= 0; i--)
	{
		percdown(a, i, n);
	}
	for (i = n - 1; i > 0; i--)
	{
		tmp = a[0];
		a[0] = a[i];
		a[i] = tmp;
		percdown(a, 0, i);
	}
}

6.归并排序

稳定
空间复杂度O(n)
时间复杂度O(nlogn)

void merge(int a[], int tmparray[], int lpos, int rpos, int rightend)
{
	int i, leftend, numelements, tmppos;

	leftend = rpos - 1;
	tmppos = lpos;
	numelements = rightend - lpos + 1;

	while (lpos <= leftend && rpos <= rightend)
	{
		if (a[lpos] <= a[rpos])
			tmparray[tmppos++] = a[lpos++];
		else
			tmparray[tmppos++] = a[rpos++];
	}

	while (lpos <= leftend)
		tmparray[tmppos++] = a[lpos++];

	while (rpos <= rightend)
		tmparray[tmppos++] = a[rpos++];

	for (i = 0; i < numelements; i++, rightend--)
		a[rightend] = tmparray[rightend];
}

void msort(int a[], int tmparray[], int left, int right)
{
	int center;

	if (left < right)
	{
		center = (left + right) / 2;
		msort(a, tmparray, left, center);
		msort(a, tmparray, center + 1, right);
		merge(a, tmparray, left, center + 1, right);
	}
}

void mergesort(int a[], int n)
{
	int *tmparray;

	tmparray = (int*)malloc(n * sizeof(int));
	if (tmparray != NULL)
	{
		msort(a, tmparray, 0, n - 1);
		free(tmparray);
	}
	else
		printf("No space for tmp array!!!\n");
}

7.快速排序(当小于4个元素时,用到插入排序)

不稳定
空间复杂度O(1)
时间复杂度O(nlogn)
最差情况:要排序的数组基本有序,枢纽每次取最大(小)元素,退化为冒泡算法
最好情况:枢纽两边元素个数基本相同

#define cutoff (3)

void swap(int *a, int *b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

int median3(int a[], int left, int right)
{
	int center = (left + right) / 2;

	if (a[left] > a[center])
		swap(&a[left], &a[center]);

	if (a[left] > a[right])
		swap(&a[left], &a[right]);

	if (a[center] > a[right])
		swap(&a[center], &a[right]);

	swap(&a[center], &a[right - 1]);
	return a[right - 1];
}

void qsort(int a[], int left, int right)
{
	int i, j;
	int pivot;

	if (left + cutoff <= right)
	{
		pivot = median3(a, left, right);
		i = left;
		j = right - 1;
		for ( ; ; )
		{
			while (a[++i] < pivot) {}
			while (a[--j] > pivot) {}
			if (i < j)
				swap(&a[i], &a[j]);
			else
				break;
		}
		swap(&a[i], &a[right - 1]);

		qsort(a, left, i - 1);
		qsort(a, i + 1, right);
	}
	else
		insertsort(a + left, right - left + 1);
}

void quicksort(int a[], int n)
{
	qsort(a, 0, n - 1);
}

参考资料:

关于常见排序算法的稳定性分析和结论

排序算法归总

《数据结构与算法分析—C语言描述》

详细解说 STL 排序(Sort)

http://www.cppblog.com/mzty/archive/2009/11/17/1770.html

作者Winter

一切复杂的排序操作,都可以通过STL方便实现 !

0 前言: STL,为什么你必须掌握


对 于程序员来说,数据结构是必修的一门课。从查找到排序,从链表到二叉树,几乎所有的算法和原理都需要理解,理解不了也要死记硬背下来。幸运的是这些理论都 已经比较成熟,算法也基本固定下来,不需要你再去花费心思去考虑其算法原理,也不用再去验证其准确性。不过,等你开始应用计算机语言来工作的时候,你会发 现,面对不同的需求你需要一次又一次去用代码重复实现这些已经成熟的算法,而且会一次又一次陷入一些由于自己疏忽而产生的bug中。这时,你想找一种工 具,已经帮你实现这些功能,你想怎么用就怎么用,同时不影响性能。你需要的就是STL, 标准模板库!

西方有句谚语:不要重复发明轮子!

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除……可以说,如果你理解了STL,你会发现你已不用拘泥于算法本身,从而站在巨人的肩膀上去考虑更高级的应用。

排序是最广泛的算法之一,本文详细介绍了STL中不同排序算法的用法和区别。

1 STL提供的Sort 算法


C++之所以得到这么多人的喜欢,是因为它既具有面向对象的概念,又保持了C语言高效的特点。STL 排序算法同样需要保持高效。因此,对于不同的需求,STL提供的不同的函数,不同的函数,实现的算法又不尽相同。

1.1 所有sort算法介绍

所 有的sort算法的参数都需要输入一个范围,[begin, end)。这里使用的迭代器(iterator)都需是随机迭代器(RadomAccessIterator), 也就是说可以随机访问的迭代器,如:it+n什么的。(partition 和stable_partition 除外)

如果你需要自己定义比较函数,你可以把你定义好的仿函数(functor)作为参数传入。每种算法都支持传入比较函数。以下是所有STL sort算法函数的名字列表:

函数名 功能描述
sort 对给定区间所有元素进行排序
stable_sort 对给定区间所有元素进行稳定排序
partial_sort 对给定区间所有元素部分排序
partial_sort_copy 对给定区间复制并排序
nth_element 找出给定区间的某个位置对应的元素
is_sorted 判断一个区间是否已经排好序
partition 使得符合某个条件的元素放在前面
stable_partition 相对稳定的使得符合某个条件的元素放在前面

其中nth_element 是最不易理解的,实际上,这个函数是用来找出第几个。例如:找出包含7个元素的数组中排在中间那个数的值,此时,我可能不关心前面,也不关心后面,我只关心排在第四位的元素值是多少。

1.2 sort 中的比较函数

当你需要按照某种特定方式进行排序时,你需要给sort指定比较函数,否则程序会自动提供给你一个比较函数。

vector < int > vect;
//...
sort(vect.begin(), vect.end());
//此时相当于调用
sort(vect.begin(), vect.end(), less<int>() );

上述例子中系统自己为sort提供了less仿函数。在STL中还提供了其他仿函数,以下是仿函数列表:

名称 功能描述
equal_to 相等
not_equal_to 不相等
less 小于
greater 大于
less_equal 小于等于
greater_equal 大于等于

需要注意的是,这些函数不是都能适用于你的sort算法,如何选择,决定于你的应用。另外,不能直接写入仿函数的名字,而是要写其重载的()函数:

less<int>()
greater<int>()

当你的容器中元素时一些标准类型(int float char)或者string时,你可以直接使用这些函数模板。但如果你时自己定义的类型或者你需要按照其他方式排序,你可以有两种方法来达到效果:一种是自己写比较函数。另一种是重载类型的'<‘操作赋。

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;

class myclass {
        public:
        myclass(int a, int b):first(a), second(b){}
        int first;
        int second;
        bool operator < (const myclass &m)const {
                return first < m.first;
        }
};

bool less_second(const myclass & m1, const myclass & m2) {
        return m1.second < m2.second;
}

int main() {

        vector< myclass > vect;
        for(int i = 0 ; i < 10 ; i ++){
                myclass my(10-i, i*3);
                vect.push_back(my);
        }
        for(int i = 0 ; i < vect.size(); i ++) 
        cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
        sort(vect.begin(), vect.end());
        cout<<"after sorted by first:"<<endl;
        for(int i = 0 ; i < vect.size(); i ++) 
        cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
        cout<<"after sorted by second:"<<endl;
        sort(vect.begin(), vect.end(), less_second);
        for(int i = 0 ; i < vect.size(); i ++) 
        cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";

        return 0 ;
}

知道其输出结果是什么了吧:

(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)
after sorted by first:
(1,27)
(2,24)
(3,21)
(4,18)
(5,15)
(6,12)
(7,9)
(8,6)
(9,3)
(10,0)
after sorted by second:
(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)

1.3 sort 的稳定性

你 发现有sort和stable_sort,还有 partition 和stable_partition, 感到奇怪吧。其中的区别是,带有stable的函数可保证相等元素的原本相对次序在排序后保持不变。或许你会问,既然相等,你还管他相对位置呢,也分不清 楚谁是谁了?这里需要弄清楚一个问题,这里的相等,是指你提供的函数表示两个元素相等,并不一定是一摸一样的元素。

例如,如果你写一个比较函数:

bool less_len(const string &str1, const string &str2)
{
        return str1.length() < str2.length();
}

此 时,”apple” 和 “winter” 就是相等的,如果在”apple” 出现在”winter”前面,用带stable的函数排序后,他们的次序一定不变,如果你使用的是不带”stable”的函数排序,那么排序完 后,”Winter”有可能在”apple”的前面。

1.4 全排序

全排序即把所给定范围所有的元素按照大小关系顺序排列。用于全排序的函数有

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);

template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, 
StrictWeakOrdering comp);

在 第1,3种形式中,sort 和 stable_sort都没有指定比较函数,系统会默认使用operator< 对区间[first,last)内的所有元素进行排序, 因此,如果你使用的类型义军已经重载了operator<函数,那么你可以省心了。第2, 4种形式,你可以随意指定比较函数,应用更为灵活一些。来看看实际应用:

班上有10个学生,我想知道他们的成绩排名。

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
using namespace std;

class student{
        public:
        student(const string &a, int b):name(a), score(b){}
        string name;
        int score;
        bool operator < (const student &m)const {
                return score< m.score;
        }
};

int main() {
        vector< student> vect;
        student st1("Tom", 74);
        vect.push_back(st1);
        st1.name="Jimy";
        st1.score=56;
        vect.push_back(st1);
        st1.name="Mary";
        st1.score=92;
        vect.push_back(st1);
        st1.name="Jessy";
        st1.score=85;
        vect.push_back(st1);
        st1.name="Jone";
        st1.score=56;
        vect.push_back(st1);
        st1.name="Bush";
        st1.score=52;
        vect.push_back(st1);
        st1.name="Winter";
        st1.score=77;
        vect.push_back(st1);
        st1.name="Andyer";
        st1.score=63;
        vect.push_back(st1);
        st1.name="Lily";
        st1.score=76;
        vect.push_back(st1);
        st1.name="Maryia";
        st1.score=89;
        vect.push_back(st1);
        cout<<"------before sort..."<<endl;
        for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
        stable_sort(vect.begin(), vect.end(),less<student>());
        cout <<"-----after sort ...."<<endl;
        for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
        return 0 ;
}

其输出是:

------before sort...
Tom:    74
Jimy:   56
Mary:   92
Jessy:  85
Jone:   56
Bush:   52
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89
-----after sort ....
Bush:   52
Jimy:   56
Jone:   56
Andyer: 63
Tom:    74
Lily:   76
Winter: 77
Jessy:  85
Maryia: 89
Mary:   92

sort采用的是成熟的”快速排序算法”(目前大部分STL版本已经不是采用简单的快速排序,而是结合内插排序算法)。注1, 可以保证很好的平均性能、复杂度为n*log(n),由于单纯的快速排序在理论上有最差的情况,性能很低,其算法复杂度为n*n,但目前大部分的STL版 本都已经在这方面做了优化,因此你可以放心使用。stable_sort采用的是”归并排序”,分派足够内存是,其算法复杂度为n*log(n), 否则其复杂度为n*log(n)*log(n),其优点是会保持相等元素之间的相对位置在排序前后保持一致。

1.5 局部排序

局部排序其实是为了减少不必要的操作而提供的排序方式。其函数原型为:

template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, 
RandomAccessIterator middle,
RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last, 
StrictWeakOrdering comp);

template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);

template <class InputIterator, class RandomAccessIterator, 
class StrictWeakOrdering>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last, Compare comp);

理 解了sort 和stable_sort后,再来理解partial_sort 就比较容易了。先看看其用途: 班上有10个学生,我想知道分数最低的5名是哪些人。如果没有partial_sort,你就需要用sort把所有人排好序,然后再取前5个。现在你只需 要对分数最低5名排序,把上面的程序做如下修改:

stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());

输出结果为:

------before sort...
Tom:    74
Jimy:   56
Mary:   92
Jessy:  85
Jone:   56
Bush:   52
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89
-----after sort ....
Bush:   52
Jimy:   56
Jone:   56
Andyer: 63
Tom:    74
Mary:   92
Jessy:  85
Winter: 77
Lily:   76
Maryia: 89

这样的好处知道了吗?当数据量小的时候可能看不出优势,如果是100万学生,我想找分数最少的5个人……

partial_sort采用的堆排序(heapsort),它在任何情况下的复杂度都是n*log(n). 如果你希望用partial_sort来实现全排序,你只要让middle=last就可以了。

partial_sort_copy 其实是copy和partial_sort的组合。被排序(被复制)的数量是[first, last)和[result_first, result_last)中区间较小的那个。如果[result_first, result_last)区间大于[first, last)区间,那么partial_sort相当于copy和sort的组合。

1.6 nth_element 指定元素排序

nth_element一个容易看懂但解释比较麻烦的排序。用例子说会更方便:
班上有10个学生,我想知道分数排在倒数第4名的学生。
如果要满足上述需求,可以用sort排好序,然后取第4位(因为是由小到大排), 更聪明的朋友会用partial_sort, 只排前4位,然后得到第4位。其实这是你还是浪费,因为前两位你根本没有必要排序,此时,你就需要nth_element:

template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, StrictWeakOrdering comp);

对于上述实例需求,你只需要按下面要求修改1.4中的程序:

stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());

运行结果为:

------before sort...
Tom:    74
Jimy:   56
Mary:   92
Jessy:  85
Jone:   56
Bush:   52
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89
-----after sort ....
Jone:   56
Bush:   52
Jimy:   56
Andyer: 63
Jessy:  85
Mary:   92
Winter: 77
Tom:    74
Lily:   76
Maryia: 89

第四个是谁?Andyer,这个倒霉的家伙。为什么是begin()+3而不是+4? 我开始写这篇文章的时候也没有在意,后来在ilovevc 的提醒下,发现了这个问题。begin()是第一个,begin()+1是第二个,… begin()+3当然就是第四个了。

1.7 partition 和stable_partition

好像这两个函数并不是用来排序的,’分类’算法,会更加贴切一些。partition就是把一个区间中的元素按照某个条件分成两类。其函数原型为:

template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first,
ForwardIterator last, Predicate pred)
template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, 
Predicate pred);

看看应用吧:班上10个学生,计算所有没有及格(低于60分)的学生。你只需要按照下面格式替换1.4中的程序:

stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
student exam("pass", 60);
stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));

其输出结果为:

------before sort...
Tom:    74
Jimy:   56
Mary:   92
Jessy:  85
Jone:   56
Bush:   52
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89
-----after sort ....
Jimy:   56
Jone:   56
Bush:   52
Tom:    74
Mary:   92
Jessy:  85
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89

看见了吗,Jimy,Jone, Bush(难怪说美国总统比较笨 smile )都没有及格。而且使用的是stable_partition, 元素之间的相对次序是没有变.

2 Sort 和容器


STL中标准容器主要vector, list, deque, string, set, multiset, map, multimay, 其中set, multiset, map, multimap都是以树结构的方式存储其元素详细内容请参看:学习STL map, STL set之数据结构基础. 因此在这些容器中,元素一直是有序的。

这些容器的迭代器类型并不是随机型迭代器,因此,上述的那些排序函数,对于这些容器是不可用的。上述sort函数对于下列容器是可用的:

  • vector
  • string
  • deque

如果你自己定义的容器也支持随机型迭代器,那么使用排序算法是没有任何问题的。

对 于list容器,list自带一个sort成员函数list::sort(). 它和算法函数中的sort差不多,但是list::sort是基于指针的方式排序,也就是说,所有的数据移动和比较都是此用指针的方式实现,因此排序后的 迭代器一直保持有效(vector中sort后的迭代器会失效).

3 选择合适的排序函数


为什么要选择合适的排序函数?可能你并不关心效率(这里的效率指的是程序运行时间), 或者说你的数据量很小, 因此你觉得随便用哪个函数都无关紧要。

其实不然,即使你不关心效率,如果你选择合适的排序函数,你会让你的代码更容易让人明白,你会让你的代码更有扩充性,逐渐养成一个良好的习惯,很重要吧 smile

如果你以前有用过C语言中的qsort, 想知道qsort和他们的比较,那我告诉你,qsort和sort是一样的,因为他们采用的都是快速排序。从效率上看,以下几种sort算法的是一个排序,效率由高到低(耗时由小变大):

  1. partion
  2. stable_partition
  3. nth_element
  4. partial_sort
  5. sort
  6. stable_sort

记得,以前翻译过Effective STL的文章,其中对如何选择排序函数总结的很好:

  • 若需对vector, string, deque, 或 array容器进行全排序,你可选择sort或stable_sort;
  • 若只需对vector, string, deque, 或 array容器中取得top n的元素,部分排序partial_sort是首选.
  • 若对于vector, string, deque, 或array容器,你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部顺序,nth_element是最理想的;
  • 若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开,你最好使用partition或stable_partition;
  • 若使用的list容器,你可以直接使用partition和stable_partition算法,你可以使用list::sort代 替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果,你必须间接使用。正如上面介绍的有 几种方式可以选择。

总之记住一句话: 如果你想节约时间,不要走弯路, 也不要走多余的路!

4 小结


讨 论技术就像个无底洞,经常容易由一点可以引申另外无数个技术点。因此需要从全局的角度来观察问题,就像观察STL中的sort算法一样。其实在STL还有 make_heap, sort_heap等排序算法。本文章没有提到。本文以实例的方式,解释了STL中排序算法的特性,并总结了在实际情况下应如何选择合适的算法。

5 参考文档

条款31:如何选择排序函数
The Standard Librarian: Sorting in the Standard Library
Effective STL中文版
Standard Template Library Programmer’s Guide vvvv

c++中sort用法 algorithm

http://hi.baidu.com/hxk622/blog/item/eb9301c1be617858b219a862.html

学习网站:http://www.stlchina.org/twiki/bin/view.pl/Main/STLTechArticles

http://www.stlchina.org/twiki/bin/view.pl/Main/STLSortAlgorithms

排序(sort):所有sort算法介绍:使用的迭代器(iterator)都需是随机迭代器(RadomAccessIterator)

1.      所有STL sort算法函数的名字列表:

函数名 功能描述
sort 对给定区间所有 元素进行排序
stable_sort 对给定区间所有 元素进行稳定排序
partial_sort 对给定区间所有 元素部分排序
partial_sort_copy 对给定区间复制 并排序
nth_element 找出给定区间的 某个位置对应的元素
is_sorted 判断一个区间是 否已经排好序
partition 使得符合某个条 件的元素放在前面
stable_partition 相对稳定的使得 符合某个条件的元素放在前面

2.      比较函数:当你需要按照某种特定方式进行排序时,你需要给sort指定比较函数,否则程序会自动提供给你一个比较函数。

vector < int > vect;

//…

sort(vect.begin(), vect.end());

//此时相当于调用

sort(vect.begin(), vect.end(), less<int>() );

sort 中的其他比较函 数

equal_to 相等
not_equal_to 不相等
less 小于
greater 大于
less_equal 小于等于
greater_equal 大于等于

上述例子中系统 自己为sort提供了less仿函数。在STL中还提供了其他仿函 数,以下是仿函数列表:

不能直接写入仿 函数的名字,而是要写其重载的()函数: less<int>();

当你的容器中元 素时一些标准类型(int float char)或者string时,你可以直 接使用这些函数模板。但如果你

时自己定义的类 型或者你需要按照其他方式排序,你可以有两种方法来达到效果:一种是自己写比较函数。另一种是重载类型的'<‘操作赋。如:

bool less_second(const myclass & m1, const myclass & m2) {

return m1.second < m2.second;

}

3.      全排序:全排序即把所给定范围所有的元素按照大小关系顺序排列。sort采用的是成熟的”快速排序算法”(目前大部分STL版本已经不是采用简单 的快速排序,而是结合内插排序算法)。复杂度为n*log(n).stable_sort采用的是”归并排序”,分派足够内存是,其算法复杂度为n*log(n), 否则 其复杂度为n*log(n)*log(n),其优点是会保持相等元素之间的相对位置在排序前后保持一致。

用于全排序的函 数有:

void sort(RandomAccessIterator first, RandomAccessIterator last);

void sort(RandomAccessIterator first, RandomAccessIterator last,StrictWeakOrdering comp);

void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);

4.      局部排序:partial_sort采 用的堆排序(heapsort),它在任 何情况下的复杂度都是n*log(n).

局部排序其实是 为了减少不必要的操作而提供的排序方式。

其函数原型为:

1)      void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);

2)      void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,
RandomAccessIterator last, StrictWeakOrdering comp);

3)      RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,RandomAccessIterator result_last);

4)      RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,RandomAccessIterator result_last, Compare comp);

用法使用情况: 班上有1000个学生,我想知道分数最低的5名是哪些人。

partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());

5.      nth_element 指定元素排序

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

void nth_element(RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last,

StrictWeakOrdering comp);

使用情况:班上 有1000个学生,我想知道分数排在倒数第4名的学生。

nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());

6.          partition 和stable_partition :partition就是把一个区间中的元素按照某个条件分成两类,并没有排序。

其函数原型为:

ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)

ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);

用法如:班上10个学生,计算所有没有及格(低于60分)的学生:

student exam(“pass”, 60);

stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));

7.      效率由高到低(耗时由小变大):

partion

stable_partition

nth_element

partial_sort

sort

stable_sort

8.      Effective STL对如何选择排序函数总结的很好:

1)      若需对vector, string, deque, 或 array容器进行全排 序,你可选择sort或stable_sort;

若只需对vector, string, deque, 或 array容器中取得top n的元素,部分排序partial_sort是首选.

若对于vector, string, deque, 或array容器,你需要找到第n个位置的元素或者你需要得 到top n且不关系top

2)      n中的内部 顺序,nth_element是最 理想的;

3)      若你需要从 标准序列容器或者array中把满足某个条件 或者不满足某个条件的元素分开,你最好使用partition或stable_partition;

4)      若使用的list容器,你可以直接使用partition和stable_partition算法,你可以使用list::sort代替sort和stable_sort排 序。若你需要得到partial_sort或nth_element的排序效果,你必须间接使用。

STL通用算法

STL通用算法

http://blog.csdn.net/capter/archive/2005/12/26/562328.aspx

STL算法.cpp : 定义控制台应用程序的入口点。

/*******************************************************************************
STL 通用算法:                   Description:
1、非修正序列算法           不对其所作用的容器进行修改
2、修正序列算法             对其所作用的容器进行修改
3、排序算 法                 对容器的内容进行不同方式的排序
4、数值算法                 对容器的内容进行数值计算
*******************************************************************************/

#include “stdafx.h”
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
using namespace std;
////////////////////////////////////////////////////////////////////////////////////////////////////////////
第 一类通用算法—非修正序列算法
////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*******************************************************
Function:  adjacent_find(first,last)
Description: 搜索重复对
Parameter:     搜索时的起始位置
Return:      返回在该区间第一个重复的对.
By:       capter
Date:   2005-12-23
*******************************************************/

int _tmain(int argc, _TCHAR* argv[])
{
multiset<int> intset;
intset.insert(10);
intset.insert(3);
intset.insert(1);
intset.insert(3);
intset.insert(8);
intset.insert(8);
intset.insert(5);
// 显示该多重集合
multiset<int>::iterator iter;
for(iter=intset.begin(); iter!=intset.end(); iter++)
cout<<*iter<<” “;
cout<<endl;

// 查找第一个相等的值
iter = adjacent_find(intset.begin(),intset.end());
cout<<*iter<<endl;
iter++;
cout<<*iter<<endl;
return 0;
}

/*******************************************************
Function:      count(first,last,val)
Description:     计算val出现的次数
Parameter:     搜索时的起始位置和要计算的值
Return:      返回出现的次数
By:       capter
Date:       2005-12-23
*******************************************************/
int main()
{
multiset<int> intset;
intset.insert(10);
intset.insert(6);
intset.insert(1);
intset.insert(3);
intset.insert(6);
intset.insert(2);
intset.insert(3);
// 显示该多重集合的值
multiset<int>::iterator iter;
for(iter=intset.begin(); iter!=intset.end(); iter++)
cout<<*iter<<” “;
cout<<endl;
// 搜索数字3出现的次数
int n = count(intset.begin(),intset.end(),3);
cout<<” 数字3在该多重集合中共出现了:”<<n<<“次”<<endl;
return 0;
}

/*******************************************************
Function:      for_each(first,last,func)
Description:     对first,last范围内每个元素执行func定义的函数
Parameter:     first,last要执行元素的范围,func自己定义的函数
By:       capter
Date:       2005-12-23
*******************************************************/
void showvalue(int x)
{
cout<<x<<” “;
}

int main()
{
multiset<int> intset;
intset.insert(10);
intset.insert(6);
intset.insert(1);
intset.insert(3);
intset.insert(6);
intset.insert(2);
intset.insert(3);
// 显示该多重集合的值
for_each(intset.begin(),intset.end(),showvalue);
cout<<endl;
return 0;
}
//////////////////////////////////////////////////
第一类–非 修正序列算法还有其他函数
equal(first,last,first2)
find(first,last,val)
find_end(first,last,first2,last2)
find_first(first,last,first2,last2)
mismatch(first,last,first2)
search(first,last,first2,last2)
//////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
第 二类通用算法—修正序列算法
////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*******************************************************
Function:      fill(first,last,val)
Description:     把val的值赋给first,last中所有的元素
Parameter:     起始位置和要赋的值
By:       capter
Date:       2005-12-23
*******************************************************/
void showvalue(int x)
{
cout<<x<<” “;
}
int main()
{
vector<int> intvector;
for(int x=0;x<10;x++)
intvector.push_back(x);
//显示该向量的内容
for_each(intvector.begin(),intvector.end(),showvalue);
cout<<endl;
// 填充该值
fill(intvector.begin(),intvector.begin()+5,0);
//显示填充后的值
for_each(intvector.begin(),intvector.end(),showvalue);
cout<<endl;
return 0;
}

/*******************************************************
Function:      random_shuffle(first,last)
Description:     在指示器first,last中随机排列元素
Parameter:     起始位置
By:       capter
Date:       2005-12-23
*******************************************************/
void showvalue(int x)
{
cout<<x<<” “;
}

int main()
{
vector<int> intvector;
for(int x=0;x<10;x++)
intvector.push_back(x);
//显示该向量的值
for_each(intvector.begin(),intvector.end(),showvalue);
cout<<endl;
// 对该向量进行随机排序
random_shuffle(intvector.begin(),intvector.end());
// 显示随机排序后的值
for_each(intvector.begin(),intvector.end(),showvalue);
cout<<endl;
return 0;
}

/*******************************************************
Function:      partition(first,last,pred)
Description:     在指示器first,last中经过谓词的判断后一分为二
Parameter:     起始位置和谓词
By:       capter
Date:       2005-12-23
*******************************************************/
void showvalue(int x)
{
cout<<x<<” “;
}
//谓词函数
bool equals5(int val)
{
return (val == 5);
}
int main()
{
vector<int> intvector;
intvector.push_back(8);
intvector.push_back(5);
intvector.push_back(7);
intvector.push_back(5);
intvector.push_back(2);
intvector.push_back(5);

// 显示该向量的内容
for_each(intvector.begin(),intvector.end(),showvalue);
cout<<endl;
// 对该向量进行分段
partition(intvector.begin(),intvector.end(),equals5);

// 显示新内容
for_each(intvector.begin(),intvector.end(),showvalue);
cout<<endl;
return 0;
}

/*******************************************************
Function:      rotate(first,middle,last)
Description:     把从middle到last的元素旋转到first范围处
Parameter:     起始位置和开始旋转位置
By:       capter
Date:       2005-12-23
*******************************************************/
void showvalue(char x)
{
cout<<x<<” “;
}

int main()
{
vector<char> charvector;
for(int i=0;i<10;i++)
charvector.push_back(65+i);

//显示向量内容
for_each(charvector.begin(),charvector.end(),showvalue);
cout<<endl;
// 旋转
rotate(charvector.begin(),charvector.begin()+6,charvector.end());
// 显示旋转后的内容
for_each(charvector.begin(),charvector.end(),showvalue);
cout<<endl;
return 0;
}
//////////////////////////////////////////////////
copy(first,last,first2)
copy_backward(first,last,first2)
generate(first,last,func)
remove(first,last,val)
replace(first,last,val1,val2)
reverse(first,last)
swap(it1,it2)
swap_ranges(first,last,first2)
transform(first,last,first2,func)
unique(first,last)
//////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////////////////////////////
第 三类通用算法—排序算法
/////////////////////////////////////////////////////////////////////////////////////////////////////

/*******************************************************
Function:      sort(first,last)
Description:     排序
Parameter:     起始位置
By:       capter
Date:       2005-12-23
*******************************************************/
void show(char val)
{
cout<<val<<” “;
}
int main()
{
vector<char> charvector;
charvector.push_back(‘Z’);
charvector.push_back(‘D’);
charvector.push_back(‘F’);
charvector.push_back(‘S’);
charvector.push_back(‘A’);
charvector.push_back(‘Q’);
charvector.push_back(‘C’);
charvector.push_back(‘G’);
charvector.push_back(‘M’);
charvector.push_back(‘Y’);
// 显示向量
for_each(charvector.begin(),charvector.end(),show);
cout<<endl;
// 排序
sort(charvector.begin(),charvector.end());
//显示排序后的向量
for_each(charvector.begin(),charvector.end(),show);
cout<<endl;
return 0;
}

/*******************************************************
Function:  partial_sort(first,middle,last)
Description: 进 行偏序排序
Parameter:     起始位置
By:       capter
Date:   2005-12-23
*******************************************************/
void show(string val)
{
cout<<val<<endl;
}
int main()
{
vector<string> strvector;
strvector.push_back(“zebra”);
strvector.push_back(“deer”);
strvector.push_back(“fish”);
strvector.push_back(“snake”);
strvector.push_back(“bat”);
strvector.push_back(“cat”);
strvector.push_back(“bird”);
strvector.push_back(“turtle”);
strvector.push_back(“horse”);
strvector.push_back(“cow”);
// 显示向量内容
for_each(strvector.begin(),strvector.end(),show);
cout<<endl;
// 进行偏序排序
partial_sort(strvector.begin(),strvector.begin()+5,strvector.end());
// 显示排序后的内容
for_each(strvector.begin(),strvector.end(),show);
cout<<endl;
return 0;
}

/*******************************************************
Function:      nth_element(first,nth,last)
Description:     排序
Parameter:     起始位置
By:       capter
Date:       2005-12-23
*******************************************************/
void show(string val)
{
cout<<val<<endl;
}
int main()
{
vector<string> strvector;
strvector.push_back(“zebra”);
strvector.push_back(“deer”);
strvector.push_back(“fish”);
strvector.push_back(“snake”);
strvector.push_back(“bat”);
strvector.push_back(“cat”);
strvector.push_back(“bird”);
strvector.push_back(“turtle”);
strvector.push_back(“horse”);
strvector.push_back(“cow”);
// 显示向量内容
for_each(strvector.begin(),strvector.end(),show);
cout<<endl;
// 进行偏序排序
nth_element(strvector.begin(),strvector.begin()+5,strvector.end());
// 显示排序后的内容
for_each(strvector.begin(),strvector.end(),show);
cout<<endl;
return 0;
}

/*******************************************************
Function:      merge(first,last,first2,last2,result)
Description:     合并排序
Parameter:     起始位置和结果集
By:       capter
Date:       2005-12-23
*******************************************************/
void show(string val)
{
cout<<val<<endl;
}
int main()
{
vector<string>  strvector1,strvector2;
vector<string>  strvector3(10);
strvector1.push_back(“zebra”);
strvector1.push_back(“deer”);
strvector1.push_back(“fish”);
strvector1.push_back(“snake”);
strvector1.push_back(“bat”);

strvector2.push_back(“cat”);
strvector2.push_back(“bird”);
strvector2.push_back(“turtle”);
strvector2.push_back(“horse”);
strvector2.push_back(“cow”);
// 显示向量内容
for_each(strvector1.begin(),strvector1.end(),show);
cout<<endl;
// 显示排序后的内容
for_each(strvector2.begin(),strvector2.end(),show);
cout<<endl;
sort(strvector1.begin(),strvector1.end());
sort(strvector2.begin(),strvector2.end());
merge(strvector1.begin(),strvector1.end(),strvector2.begin(),strvector2.end(),strvector3.begin());
// 显示排序后的结果
for_each(strvector3.begin(),strvector3.end(),show);
cout<<endl;
return 0;
}
/////////////////////////////////////////////////////////////////////
第 二种通用算法还有以下几种
binary_search(first,last,val)
equal_range(first,last,val)
includes(first,last,first2,last2)
lexicographical_compare(first,last,first2,last2)
lower_bound(first,last,val)
make_heap(first,last)
max(val1,val2)
max_element(first,last)
min(val1,val2)
next_permutation(first,last)
partial_sort_copy(first,last,first2,last2);
pop_heap(first,last)
prev_permutation(first,last)
push_heap(first,last)
set_difference(first,last,first2,last2,result)
set_intersection(first,last,first2,last2,result)
set_symmetric_difference(first,last,first2,last2,result)
set_union(first,last,first2,last2,result)
sort(first,last)
sort_heap(first,last)
stable_sort(first,last)
upper_bound(first,last,val)
////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
第 四种算法—数值算法
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*******************************************************
Function:      accumulate(first,last,init)
Description:     求和
Parameter:     起始位置和初始参数
Return:           结果
By:       capter
Date:       2005-12-23
*******************************************************/
void show(int x)
{
cout<<x<<” “;
}

int main()
{
vector<int> intvector;
for(int x=0; x<5; ++x)
intvector.push_back(x);
// 显示内容
for_each(intvector.begin(),intvector.end(),show);
//求和
int result = accumulate(intvector.begin(),intvector.end(),5);
cout<<result<<endl;
return 0;
}

/*******************************************************
Function:      inner_product(first,last,first2,init)
Description:     两向量对应的值相加,然后再求和
Parameter:     起始位置和初始参数
Return:           结果
By:       capter
Date:       2005-12-23
*******************************************************/
void show(int x)
{
cout<<x<<” “;
}

int main()
{
vector<int> vector1,vector2;
for(int i=0;i<5;i++)
vector1.push_back(i);
for(int i=2;i<7;i++)
vector2.push_back(i);
for_each(vector1.begin(),vector1.end(),show);
cout<<endl;
for_each(vector2.begin(),vector2.end(),show);
cout<<endl;

int result = inner_product(vector1.begin(),vector1.end(),vector2.begin(),0);
cout<<result<<endl;

return 0;
}

/*******************************************************
Function:      partial_sum(first,last,first2,init)
Description:     求部分和
Parameter:     起始位置和初始参数
Return:           结果
By:       capter
Date:       2005-12-23
*******************************************************/
void show(int x)
{
cout<<x<<” “;
}

int main()
{
vector<int> vector1;
vector<int> vector2(5);
for(int i=2;i<7;++i)
vector1.push_back(i);
// 显示向量内容
for_each(vector1.begin(),vector1.end(),show);
cout<<endl;
// 求部分和
partial_sum(vector1.begin(),vector1.end(),vector2.begin());
// 显示求和后的结果
for_each(vector2.begin(),vector2.end(),show);
cout<<endl;

return 0;
}

/*******************************************************
Function:      adjacent_difference(first,last,first2,result)
Description:     两向量对应的值相加,然后再求和
Parameter:     起始位置和初始参数
Return:           结果
By:       capter
Date:       2005-12-23
*******************************************************/
void show(int x)
{
cout<<x<<” “;
}

int main()
{
vector<int> vector1;
vector<int> vector2(5);
vector1.push_back(3);
vector1.push_back(4);
vector1.push_back(12);
vector1.push_back(6);
vector1.push_back(10);

显示向量内容
for_each(vector1.begin(),vector1.end(),show);
cout<<endl;
求 部分差
adjacent_difference(vector1.begin(),vector1.end(),vector2.begin());
显 示求和后的结果
for_each(vector2.begin(),vector2.end(),show);
cout<<endl;

return 0;
}