- 浏览: 637130 次
文章分类
最新评论
-
netkongjian:
不错的报表工具知识分享![deyi]
报表漫谈 -
jiranjiran:
...
Eclipse + SVN + Google code 搭建代码仓库
几种排序算法与运用实例
我们最常见的几种排序,经常都是在迷迷糊糊中就被我们使用了,而我们很少去对我们项目中使用到的算法进行思考,是否这个算法出现在此处是合理的。虽然,一般情况下,我们使用的算法都不会造成项目的瓶颈,但那是建立在我们的项目服务的数据量不够大的基础之上的,让我们一起来看看这些算法的使用以及实际应用场合。
一、简单选择排序
从第 i 个元素开始,与接下去的 n - i 个元素比较,得出最小值或最大值,将其置换在 i 的位置,直到 i 的值为 n 为止。
#include <iostream> using namespace std; ////////////////////////////////////////////////////////////////////////////////////////// void SimpleSort(int *pArray, int nCount) // 简单选择排序 { if (!pArray) { return ; } for (int i = 0; i < nCount; i++) { int nMin = pArray[i]; int nIndex = i; for (int j = i + 1; j < nCount; j++) { if (pArray[j] < nMin) { nMin = pArray[j]; nIndex = j; } } pArray[nIndex] = pArray[i]; pArray[i] = nMin; } } ////////////////////////////////////////////////////////////////////////////////////////// int main() { int nArray[] = {4, 7, 9, 1, 8, 5, 2, 6, 3}; const int MAX_SIZE = sizeof(nArray) / sizeof(int); SimpleSort(nArray, MAX_SIZE); for (int i = 0; i < MAX_SIZE; ++i) { cout << nArray[i] << ' '; } cout << endl; return 0; }
可以看到,无论序列nArray初始状态是否有序,都需要从第1个元素开始遍历到最后一个元素,找出最小值。所以,比较的次数nSum = (n - 1) + (n - 2) + (n - 3) ... + 1 = (n - 1 + 1) * (n - 1) / 2 = n ^ 2 - n / 2,即其时间复杂度为o(n ^ 2)。对于nArray = { 2, 2, 1, 3, 4 };这样的序列,经过排序之后,两个2的相对位置会发生变化,所以简单选择排序是不稳定的排序。
举个例子,在游戏中,有一个排行需求,从上午8点到下午18点,玩家追杀敌人的数量,做一个排行,只需要取追杀数进入前3名的玩家,每半小时更新一次排行榜。
这个例子很简单,用简单选择排序就可以搞定,假如,今天参加活动的玩家数量有2000人,只需要找出最大的那三个数,半小时遍历一次,一次最多循环还不到6000次。这是完全可以接受的。拓展到找K个人,那么我们必须明白,K个人的比较次数是nK = (n - 1) + (n - 2) + (n - 3) + ... (n - k) = ((n - 1) + (n - k)) * ((n - 1) - (n - k) ) / 2 = (2n - k - 1) * (k - 1) / 2 = (2nk - 2n - k^2 + k - k + 1) / 2 = nk - n - k ^ 2 / 2 + 1 / 2 = O(n * K),而快速排序(后面会讲到)的复杂度是O(N * log2 N),所以当K <= log2N时,才推荐使用简单选择排序。
二、冒泡排序
从第一个元素开始,依次比较连续两个数值的大小,按照规则小的在前或者大的在前,交换比较的两个数的位置,直到没有需要交换的两个数为止。
#include <iostream> using namespace std; ////////////////////////////////////////////////////////////////////////////////////////// void BubbleSort(int *pArray, int nCount) // 冒泡排序 { if (!pArray) { return ; } bool bExchange = true; for (int i = 0; i < nCount - 1; i++) { if (bExchange) { bExchange = false; for (int j = 0; j < nCount - i - 1; j++) { if (pArray[j] > pArray[j+1]) { bExchange = true; int nTemp = pArray[j+1]; pArray[j+1] = pArray[j]; pArray[j] = nTemp; } } } else { break; } } } ////////////////////////////////////////////////////////////////////////////////////////// int main() { int nArray[] = {4, 7, 9, 1, 8, 5, 2, 6, 3}; const int MAX_SIZE = sizeof(nArray) / sizeof(int); BubbleSort(nArray, MAX_SIZE); for (int i = 0; i < MAX_SIZE; ++i) { cout << nArray[i] << ' '; } cout << endl; return 0; }
上面的冒泡排序比普通的冒泡排序多了一个变量bExchange。这个变量的作用是这样的,如果在某一次依次交换相邻两个数的遍历中,没有发现要交换位置的两个数,说明,这个序列已经有序了,既然已经有序了,就不需要再遍历。这样又是可以大大降低遍历的次数。
在这个算法里,我们可以看到,在最坏的情况下,需要比较的次数为nSum = (n - 1) + (n - 2) + (n - 3) ... + 1 = (n - 1 + 1) * (n - 1) / 2 = n ^ 2 - n / 2,即其时间复杂度为o(n ^ 2)。在最好的情况下,冒泡排序只要遍历一次就能排好了,复杂度为O(n)。可以看到,冒泡排序的比较总是发生在相邻两个数之间,这样的话,如果相邻两个数是相等的,我们是不会将他们交换位置的,所以,冒泡排序是一种稳定的排序算法。
举个例子,在一次班级考试中,将考生的分数录入后,需要得出每位考生的排名顺序。
这个例子可以使用冒泡排序,考生的成绩录入后,基本都是杂乱无章的,使用冒泡排序就可以很快排出名次。如果,不是班级考试,而是市级或省级考试,考生的数量很大,并且考生数量远远大于总分数时,冒泡排序当然可以解决,但不是最好的选择。总分数是固定的,我们将会在许许多多的相同成绩中做无谓的排序。这时候,我们应该使用桶排序(后面会介绍)。比如,95W的考生成绩乱序排列,冒泡一次就要95W * 95W次,但是如果用桶排序,分9个桶,算个最差的,0.5W, 2W,5W, 20W,40W,20W, 5W,2W,0.5W,用个冒泡吧,也就是0.5W * 0.5W * 2 + 2W * 2W * 2 + 5W * 5W * 2 + 20W * 20W * 2 + 40W * 40W = (0.5 + 8 + 50 + 80 + 160)W * W = 298.5W * W,比95W * 95W = 9025W * W要小多了。
三、鸡尾酒排序
鸡尾酒排序是在冒泡排序的基础上衍生出来的排序算法。从第一个元素开始,依次比较相邻的两个数,按照规则大数在前或者小数在前,交换用于比较的两个数的位置,当第一轮结束时,从后往前,按照相同的方法进行排序。
#include <iostream> using namespace std; ////////////////////////////////////////////////////////////////////////////////////////// void CocktailSort(int *pArray, int nCount) // 鸡尾酒排序 { if (!pArray) { return ; } bool bExchange = true; int nIndexFromBegin = 0; int nIndexFromEnd = nCount - 1; while(bExchange) { bExchange = false; for (int i = nIndexFromBegin; i < nCount - 1; i++) { if (pArray[i] > pArray[i + 1]) { bExchange = true; int nTemp = pArray[i + 1]; pArray[i + 1] = pArray[i]; pArray[i] = nTemp; } } nIndexFromBegin++; for (int i = nIndexFromEnd; i > 0; i--) { if (pArray[i] < pArray[i - 1]) { bExchange = true; int nTemp = pArray[i]; pArray[i] = pArray[i - 1]; pArray[i - 1] = nTemp; } } nIndexFromEnd--; } } ////////////////////////////////////////////////////////////////////////////////////////// int main() { int nArray[] = {4, 7, 9, 1, 8, 5, 2, 6, 3}; const int MAX_SIZE = sizeof(nArray) / sizeof(int); CocktailSort(nArray, MAX_SIZE); for (int i = 0; i < MAX_SIZE; ++i) { cout << nArray[i] << ' '; } cout << endl; return 0; }
看,鸡尾酒这个变相的冒泡排序,还真是有点好玩。它的时间复杂度还是O(n ^ 2),同样是稳定的排序算法。它比冒泡排序好的地方是,它可以稍微缩短排序的次数,比如这样的一个序列nArray = {2, 3, 4, 5, 6, 7, 8, 1},冒泡排序需要循环7次,而鸡尾酒排序只需要2次循环。
举个例子,某个村的所有家庭的收入已被录入,现在要对收入前10%的家庭加收富人税,收入后10%的家庭给予扶助。
这个例子就可以使用鸡尾酒排序来解决,假设有2000个家庭,那么10%也就是200,那么前后循环200次,就能找到这些富贵家庭和贫困家庭了。
四、快速排序
快速排序,听名字就很碉堡。快速排序将第一个值作为key,从右边开始找第一个比key小的数,把key对应的位置的值设置为找出来的值,再从左边开始找第一个比key大的值,将找出来的值设置为key对应位置的值,直到左右查找的索引相等时,把此索引位置的值设置为key值。如此循环,直到从左边和从右边开始查找的索引相等的为止。
#include <iostream> using namespace std; ////////////////////////////////////////////////////////////////////////////////////////// void QuickSort(int *pArray, int nMin, int nMax) // 快速排序 { if (!pArray) { return ; } int nBegin = nMin; int nEnd = nMax - 1; if (nBegin >= nEnd) { return ; } int nKey = pArray[nBegin]; while(nBegin != nEnd) { while(nEnd > nBegin && pArray[nEnd] >= nKey) nEnd--; pArray[nBegin] = pArray[nEnd]; while(nBegin < nEnd && pArray[nBegin] <= nKey) nBegin++; pArray[nEnd] = pArray[nBegin]; } pArray[nBegin] = nKey; QuickSort(pArray, nMin, nBegin - 1); QuickSort(pArray, nBegin + 1, nMax); } ////////////////////////////////////////////////////////////////////////////////////////// int main() { int nArray[] = {4, 7, 9, 1, 8, 5, 2, 6, 3}; const int MAX_SIZE = sizeof(nArray) / sizeof(int); QuickSort(nArray, 0, MAX_SIZE); for (int i = 0; i < MAX_SIZE; ++i) { cout << nArray[i] << ' '; } cout << endl; return 0; }
名字叫快速排序,有多快呢。最坏情况下,左右两边一直都是乱序,直到key值选了n-1次,这种情况下,比较次数和循环次数都是O(n ^ 2),可以想象成简单选择排序,就好懂了。在最好的情况下,也就是key值被选择的次数最少,那就是能够每次都中分,也就是最少的key选择次数为log2 n,相当于是log2 n层,每一层的循环次数是该层所有值都与key值比较的次数,也就是n,换句话说,每个数都只要被拿出来比较log2 n次。那么总共复杂度就是o(n log2 n),可以看到,快速排序可以达到比冒泡更快的速度。快速排序是不稳定的排序,比如nArray[] = {3, 5, 5, 1, 1},第一轮就造成不稳定了。
举个例子,某一个博客上面有很多博文,每篇博文上都有阅读量,现要将这些博文按照阅读量排序。
这个例子就可以使用快速排序,阅读量是个很散的数值,随机性比较大。假如有1024篇博文,排序一下,也就是1024 * log 2 1024 = 1024 * 10 = 10240次比较。
五、桶排序
上面在冒泡排序里已经有提及到桶排序了。未排序数据同在某一个范围内,将未排序数据按段划分,再对每一个数据段分别进行排序,数据段内的排序可以使用任意一种排序算法。每个桶里的数据合起来就是排序的结果。也就是说,桶排序其实是基于其他的排序算法。
#include <iostream> #include <time.h> #include <vector> using namespace std; ////////////////////////////////////////////////////////////////////////////////////////// void BubbleSort(int *pArray, int nCount) // 冒泡排序 { if (!pArray) { return ; } bool bExchange = true; for (int i = 0; i < nCount - 1; i++) { if (bExchange) { bExchange = false; for (int j = 0; j < nCount - i - 1; j++) { if (pArray[j] > pArray[j+1]) { bExchange = true; int nTemp = pArray[j+1]; pArray[j+1] = pArray[j]; pArray[j] = nTemp; } } } else { break; } } } ////////////////////////////////////////////////////////////////////////////////////////// class CBasket { public: CBasket(int nSize) : m_nSize(nSize) { m_pArray = new int[m_nSize]; memset(m_pArray, 0, m_nSize); m_nIndex = 0; } ~CBasket() { delete [] m_pArray; } public: bool PushBack(int nValue) { if (m_nIndex >= m_nSize) { return false; } *(m_pArray + m_nIndex) = nValue; ++m_nIndex; return true; } void Sort() { BubbleSort(m_pArray, m_nIndex); } void Print() { for (int i = 0; i < m_nIndex; ++i) { cout << *(m_pArray + i) << ' '; } cout << endl; } private: int *m_pArray; int m_nSize; int m_nIndex; }; ////////////////////////////////////////////////////////////////////////////////////////// int main() { // 生成100个随机数[0~20) srand((unsigned int)time(NULL)); const int MAX_SIZE = 100; const int RANGE = 20; int *pArray = new int[MAX_SIZE]; memset(pArray, 0, MAX_SIZE); for (int i = 0; i < MAX_SIZE; i++) { int nRand = rand() % RANGE; *(pArray + i) = nRand; } // 生成5个桶 const int BASKET_COUNT = 5; const int BASKET_RANGE = RANGE / BASKET_COUNT; CBasket Basket[BASKET_COUNT] = { CBasket(RANGE), CBasket(RANGE), CBasket(RANGE), CBasket(RANGE), CBasket(RANGE), }; // 将数据分别放入到5个桶内 for (int i = 0; i < MAX_SIZE; i++) { int nBasketIndex = *(pArray + i) / BASKET_RANGE; if (nBasketIndex < BASKET_COUNT) { Basket[nBasketIndex].PushBack(*(pArray + i)); } } // 对桶进行排序,并且输出 for (int i = 0; i < BASKET_COUNT; i++) { Basket[i].Sort(); Basket[i].Print(); } return 0; }
如同上面的例子所示,按照最坏的情况来算,如果直接按照冒泡直接排序,就需要O(n ^ 2)次比较,即100 * 100 = 10000,但使用桶排序后,假设每个桶的数据量一样多,就只有O(n) + O(n / 5 ^ 2) * 5 = 100 + (100 / 5 ^ 2) * 5 = 100 + 400 * 5 = 2100,看,是不是快许多了。当然,如果每个桶的数量不一样,就没有这种效果,桶排序的最坏情况是只有一个桶装下了所有数据,此时,它的复杂度就等于桶内排序的复杂度,还要加上O(n)了。所以,桶排序的时间复杂度取决于桶内排序的算法。其复杂度等于每个桶排序的复杂度相加。对于桶排序自身而言,它是稳定的。桶排序的例子参照上面冒泡排序的例子。
六、归并排序
归并排序的思路是将两个有序的数列合并成一个。首先,把数列中的元素两个两个分组并排序,接着,将排序好的分组再进行两个两个分组排序,直到不能再分组了。
#include <iostream> using namespace std; ////////////////////////////////////////////////////////////////////////////////////////// void Merge(int *pArrayLeft, int nCountLeft, int *pArrayRight, int nCountRight) { if (!pArrayLeft || !pArrayRight) { return ; } int nCount = nCountLeft + nCountRight; int *pArrayTemp = new int[nCount]; // 临时存储合并后的数组 memset(pArrayTemp, 0, nCount*sizeof(int)); int *pTemp = pArrayTemp; int i = 0; int j = 0; while(i < nCountLeft && j < nCountRight) { if (*(pArrayLeft+i) < *(pArrayRight+j)) { *pArrayTemp++ = *(pArrayLeft+i); i++; } else { *pArrayTemp++ = *(pArrayRight+j); j++; } } while(j < nCountRight) { *pArrayTemp++ = *(pArrayRight+j); j++; } while(i < nCountLeft) { *pArrayTemp++ = *(pArrayLeft+i); i++; } // 将临时存储的有序数组放回去 pArrayTemp = pTemp; for (int i = 0; i < nCountLeft + nCountRight; i++) { *pArrayLeft++ = *pArrayTemp++; } delete []pTemp; } void MergeSort(int *pArray, int nCount) { if (!pArray) { return ; } int nMid = nCount / 2; if (nMid != 0) { MergeSort(pArray, nMid); MergeSort(pArray + nMid, nCount - nMid); Merge(pArray, nMid, pArray + nMid, nCount - nMid); } } ////////////////////////////////////////////////////////////////////////////////////////// int main() { int nArray[] = {4, 7, 9, 1, 8, 5, 2, 6, 3}; const int MAX_SIZE = sizeof(nArray) / sizeof(int); MergeSort(nArray, MAX_SIZE); for (int i = 0; i < MAX_SIZE; ++i) { cout << nArray[i] << ' '; } cout << endl; return 0; }
如同上面你所看到的,归并排序需要有一个额外的存储空间来存储排序后的结果,它是一种利用空间来换取时间的算法。它的效率非常高,但它的空间消耗也非常大。如上例子,最坏情况下,它每次要中分一下原序列,并对中分后的序列进行比较排序,即上例中 i 与 j 同时达到终点值。总共log2 n层,每一层的循环比较次数是当前层所有数的个数,换个思路就是,每个数都只需要比较log2 n次,所以,它的时间复杂度是O(n log2 n)。它最快可以多快呢?可以看到,直接连接是最快的,也就是上例中,i 和 j有一个直接奔到终点值,也就是所有记录都只被扫描一次,其比较次数是O(n)。可以看到归并排序也是一种稳定的排序。
举个例子,一位运动员要参加10天的射击训练,每天训练的结果已经按照顺序排列好了,最后,需要把所有射击结果排列起来,以方便统计。
在这个例子里,每个项(天)都已经有序了,排序差不多相当于连接起来,因此使用归并排序比较快点。
相关推荐
上述资源是位与、选择、冒泡、插入、qsort算法的实例,在vc6.0下可以编译并得到预期结果。
C#中常用排序算法的一些实例代码,程序还提供了一个演示窗口,以命令提示符的方式显示算法结果,让人一目了然就能看到算法的结果,比较适合c#初学者。...通过这个小实例你会对这几种常用的排序算法有一些理解。
枚举 递归 回溯 贪心 动态规划 排序算法 LZW压缩 josephus 乘法表 积分 基数转换 矩阵问题举例 求解质数 圆周率的求法 改进的快速排序法 几种插入排序法 水仙花数 迷宫生成器 生命游戏
VC 对数组进行排序的一个算法实例,基于函数指针的数组,代码中一共包含四种排序方法:泡沫排序法(bubble)、插入排序法(insertion)、快速排序法(quick)和选择排序法(selection)。在头文件中还使用了模板技术...
介绍了C语言排序部分中几种常见的排序算法,并结合简单代码实例作了介绍。
主要介绍了java几种排序算法的实现及简单分析,实例分析了插入排序、希尔排序、选择排序等常用排序算法,并分析了各个算法的优劣,需要的朋友可以参考下
本文实例讲述了C语言基本排序算法之shell排序。分享给大家供大家参考,具体如下: shell排序是对直接插入方法的改进方法. /*-----------------------------------------------------------------------------------...
TextRank算法主要包含以下几个步骤:预处理、构建图、迭代计算节点权重、排序输出。 在预处理阶段,需要对文本进行分句和分词处理,以便于后续的图构建。在构建图的阶段,需要根据分词结果构建节点,并计算节点间的...
4.2 常用数组排序算法 117 实例099 使用选择排序法对一维数组进行排序 117 实例100 使用冒泡排序法对一维数组进行排序 118 实例101 使用快速排序法对一维数组进行排序 119 实例102 使用直接插入法对一维数组进行排序...
本文实例讲述了基于JavaScript实现的插入排序算法。分享给大家供大家参考,具体如下: 根据排序过程中使用的存储器不同,可以将排序方法分为两大类:内部排序和外部排序。 内部排序是指待排序记录存放在计算机随机...
主要介绍了C#排序算法的比较,实例分析几种比较常见的算法,并对其时间复杂度与稳定性进行了详细的分析,需要的朋友可以参考下
昨晚上开始总结了一下常见的几种排序算法,由于之前我已经写了好几篇排序的算法的相关博文了现在总结一下的话可以说是很方便的,这里的目的是为了更加完整详尽的总结一下这些排序算法,为了复习基础的东西,从冒泡...
2.1.5 数据结构的几种存储方式 2.1.6 数据类型 2.1.7 常用的数据结构 2.1.8 选择合适的数据结构解决实际问题 2.2 线性表 2.2.1 什么是线性表 2.2.2 线性表的基本运算 2.3 顺序表结构 2.3.1 准备数据 2.3.2 初始化...
2.1.5 数据结构的几种存储方式 18 2.1.6 数据类型 19 2.1.7 常用的数据结构 20 2.1.8 选择合适的数据结构解决实际问题 21 2.2 线性表 21 2.2.1 什么是线性表 21 2.2.2 线性表的基本运算 22 2.3 顺序表结构 ...
内容索引:VC/C++源码,算法相关,算法 一个基于VC的数组排序算法源码实例,程序中使用了函数指针数组,一共包含四种排序方法:泡沫排序法(bubble)、插入排序法(insertion)、快速排序法(quick)和选择排序法...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。《算法导论(原书第2版...