0%

时间复杂度为:O(n)

基本思想:将要排列的序列分成n组,每组分别进行排序,然后在合并到一起,这里面有分而治之的思想。

阅读全文 »

选择排序其实是冒泡法的一种改进,其基本思路也是:先确定最小元素,再找次最小元素,最后确定最大元素。

阅读全文 »

时间复杂度:O(n*n)

基本思想:从数组最后一个元素开始,依次与前一个元素比较,若比前一个元素小,则与之交换位置,然后再与当前前一个元素比较,直到遇到比它大的元素为止。例如:假设数组为:$a[5]=\{3,4,2,5,1\}$;则运算过程为:首先$1$与$5$比较,由于$1<5$,从而交换位置,数组变为$a[5]=\{3,4,2,1,5\}$;然后$1$与当前前一个元素$2$比较,一直重复上述操作,经过一次循环后,数组变为$a[5]=\{1,3,4,2,5\}$;第二次循环从倒数第二个元素开始……,总共循环$n-1$次就可以得到正确结果。总的来说,首先将最小的元素放在数组前面,然后放次最小的元素,依此类推。

阅读全文 »

时间复杂度:$O(n)$.

基本思路:两个数比较大小,我们的直观感觉是先比较高位,若相同则比较低位。但是这样做需要记录额外的数据,浪费空间。而基数排序则是先比较低位,再比较高位。通过各个位的比较进行排序,如果数组元素最大有$N$位,则总共需要$N$次排序。注意:按位排序必须是稳定排序(两个相等的数其在序列的前后位置顺序,在排序前后不改变),所以在这我选择了计数排序。

阅读全文 »

时间复杂度:$O(n)$.

基本思想:和快速排序的思想相似,也是对数组进行递归划分,但是有所差别的是,快速排序会递归处理划分的两边,而随机化的选择算法只选择一边。

阅读全文 »

时间复杂度:$O(3*floor(n/2))$

基本思想:成对地处理元素。先将一对输入元素相互比较,然后把较小的与当前最小值比较,较大的与当前最大值比较,因此每两个元素比较三次。

阅读全文 »

比较排序:通过元素间的比较对序列进行排序的算法称为比较排序。

常见的比较排序算法有:冒泡排序法、插入排序法、合并排序法、快速排序法,堆排序法等等。任何比较排序法在最坏情况下的时间复杂度为$O(nlogn)$。因此,合并排序和堆排序是渐进最优的

阅读全文 »

​ 快速排序的最坏运行时间为$O(n^2)$,虽然这最坏情况的时间复杂度比较大,但快速排序通常是用于排序的最佳实用选择,这是因为其平均性能相当好,平均时间复杂度为$O(nlogn)$,并且$O(nlogn)$中的隐含常数因子很小。另外,它能够进行就地排序,因此在虚拟内存中也能较好的运行。

阅读全文 »

​ 堆排序像合并排序一样,时间复杂度为$O(nlogn)$;像插入排序一样,是一种原地排序(在任何时候只有常数个元素存储在数组外)。

阅读全文 »

分治法:将原问题划分为n个规模较小而结构与原问题相似的子问题;递归地解决这些子问题,然后再合并其结果,就得到了原问题的解。分治法在每一个递归上都有三个步骤:分解、解决、合并。而在本文中的合并排序法正是运用了这种分而治之的策略:把一个n个元素的数组先分成两个数组,然后继续分下去,知道分成n个数组;然后将其逐一合并排序,最终得到排列好了的数组。下面我们首先看一看合并排序了原理框图:(图中黑色部分看不见不要紧,只需了解是将数组L、R中浅颜色的元素从小到大依次填入数组A中

阅读全文 »