排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。而一般我们所谓的算法的性能主要是指算法的复杂度，一般用O方法来表示。在后面我将给出详细的说明。既然是入门那么排序是入门必须要学的，下面总结下排序的几种常见的算法。1：冒泡法也是和基本的一个排序方法。原理：将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮2：插入法：原理：逐一取出元素，在已经排序的元素序列中从后向前扫描，放到适当的位置（起初，已经排序的元素序列为空）3：选择法：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此递归。4：堆排序利用堆（heaps）这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是小于（或者大于）它的父节点。5：箱排序设置若干个箱子，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。6：希尔排序选择一个步长(Step),然后按间隔为步长的单元进行排序.递归,步长逐渐变小,直至为1.7：桶排序桶排序的思想是把[0，1)划分为n个大小相同的子区间，每一子区间是一个桶。对于排序的算法我想先做一点简单的介绍，也是给这篇文章理一个提纲。我将按照算法的复杂度，从简单到难来分析算法。第一部分是简单排序算法，后面你将看到他们的共同点是算法复杂度为O(N*N)（因为没有使用word,所以无法打出上标和下标）。第二部分是高级排序算法，复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念，所以这里不于讨论。第三部分类似动脑筋。这里的两种算法并不是最好的（甚至有最慢的），但是算法本身比较奇特，值得参考（编程的角度）。同时也可以让我们从另外的角度来认识这个问题。第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序（抱歉，里面使用了一些论坛专家的呢称）。现在，让我们开始吧：一、简单排序算法由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLANDC++的平台上应该也不会有什么问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。1.冒泡法：这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：#include<IOSTREAM.H/>voidBubbleSort(int*pData,intCount){intiTemp;for(inti=1;i<COUNT;I++){for(intj=Count-1;j>=i;j--){if(pData[j]<PDATA[J-1]){iTemp=pData[j-1];pData[j-1]=pData[j];pData[j]=iTemp;}}}}voidmain(){intdata[]={10,9,8,7,6,5,4};BubbleSort(data,7);for(inti=0;i<7;i++)cout<<DATA[I]<<"?;<br=""/>}倒序(最糟情况)第一轮：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次)第二轮：7,10,9,8->7,10,8,9->7,8,10,9(交换2次)第一轮：7,8,10,9->7,8,9,10(交换1次)循环次数：6次交换次数：6次其他：第一轮：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次)第二轮：7,8,10,9->7,8,10,9->7,8,10,9(交换0次)第一轮：7,8,10,9->7,8,9,10(交换1次)循环次数：6次交换次数：3次上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。写成公式就是1/2*(n-1)*n。现在注意，我们给出O方法的定义：若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n)=O(g(n))。（呵呵，不要说没学好数学呀，对于编程数学是非常重要的！！！）现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。再看交换。从程序后面所跟的表可以看到