十大常用算法(C++版) | 您所在的位置:网站首页 › 算法包括哪些特性 › 十大常用算法(C++版) |
前言
最近在研究一些经常用到的东西想把它们做一个汇总,想了想用到最多的应该是排序算法,所以对排序算法做了个总结,并自己用C++实现了一下。 一、算法概述0.1 算法分类 十种常见排序算法可以分为两大类: 非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。 线性时间非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序。 0.2 算法复杂度 0.3 相关概念 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。 不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。 空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。 二、快速排序假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数6作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放在6的左边,类似下面这种排列: 3 1 2 5 4 6 9 7 10 8在初始状态下,数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置,假设这个位置是k。现在就需要寻找这个k,并且以第k位为分界点,左边的数都小于等于6,右边的数都大于等于6,递归对左右两个区间进行同样排序即可。想一想,你有办法可以做到这点吗?这就是快速排序所解决的问题。 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。它的平均时间复杂度为O(nlogn),最坏时间复杂度为O(n^2). 首先上图:
从图中我们可以看到: left指针,right指针,base参照数。
其实思想是蛮简单的,就是通过第一遍的遍历(让left和right指针重合)来找到数组的切割点。 第一步:首先我们从数组的left位置取出该数(20)作为基准(base)参照物。(如果是选取随机的,则找到随机的哨兵之后,将它与第一个元素交换,开始普通的快排) 第二步:从数组的right位置向前找,一直找到比(base)小的数,如果找到,将此数赋给left位置(也就是将10赋给20),此时数组为:10,40,50,10,60, left和right指针分别为前后的10。 第三步:从数组的left位置向后找,一直找到比(base)大的数,如果找到,将此数赋给right的位置(也就是40赋给10),此时数组为:10,40,50,40,60, left和right指针分别为前后的40。 第四步:重复“第二,第三“步骤,直到left和right指针重合,最后将(base)放到40的位置, 此时数组值为: 10,20,50,40,60,至此完成一次排序。 第五步:此时20已经潜入到数组的内部,20的左侧一组数都比20小,20的右侧作为一组数都比20大, 以20为切入点对左右两边数按照"第一,第二,第三,第四"步骤进行,最终快排大功告成。
快速排序动图演示: 算法分析: 最佳情况:T(n) = O(nlogn)最差情况:T(n) = O(n2)平均情况:T(n) = O(nlogn)快速排序代码: //快速排序,随机选取哨兵放前面 void QuickSort(int* h, int left, int right) { if(h==NULL) return; if(left>=right) return; //防止有序队列导致快速排序效率降低 srand((unsigned)time(NULL)); int len=right-left; int kindex=rand()%(len+1)+left; Swap(h[left],h[kindex]); int key=h[left],i=left,j=right; while(i=key && i |
CopyRight 2018-2019 实验室设备网 版权所有 |