《排序算法的学习与应用_hanker》由会员分享，可在线阅读，更多相关《排序算法的学习与应用_hanker（26页珍藏版）》请在金锄头文库上搜索。
1、排序算法的学习与应用（一）,by韩培义,阿里巴巴技术联盟技术分享,小菜一题,一道简单的算法题一个十进制数的二进制形式中1的个数,二进制数中1的个数,解法一：暴力枚举二进制数每一位进行余操作int Count(int v)int num = 0;while(v) if(v % 2 = 1)num+;v = v/ 2; return num;,二进制数中1的个数,解法二：使用位操作int Count(int v)int num = 0;While(v)num += v &0x01;v = 1;return num;前两种方法的时间复杂度均为O（log2v）,二进制数中1的个数,解法三：仅考虑二进制
2、数中的1int Count(int v)int num = 0;while(v)v &= (v-1);num+;return num;,进入今日主题,排序算法的学习与应用,说出你知道的几种排序算法,冒泡排序插入排序快速排序归并排序注意各种排序算法的特点：1.平均时间复杂度 2.最差时间复杂度 3.额外空间消耗4.稳定度,插入排序,插入排序算法类似于玩扑克时抓牌的过程，玩家每拿到一张牌都要插入到手中已有的牌里，使之从小到大排好序。,平均,最差时间复杂度：O(n2)稳定额外空间 为O(1),快速排序,快速排序算法的描述算法导论，第7章快速排序时基于分治模式处理的，对一个典型子数组Ap.r排序的分治
3、过程为三个步骤：1.分解：Ap.r被划分为俩个（可能空）的子数组Ap .q-1和Aq+1 .r，使得Ap .q-1 = Aq = Aq+1 .r2.解决：通过递归调用快速排序，对子数组Ap .q-1和Aq+1 .r排序。3.合并。,快速排序,PS.这是快速排序第一趟完成过程。这里的主元设为了最后一个数,快速排序,快速排序算法关键在于现在数组中选择一个数字，接下来把数组中的数字分为两个部分，比选择的数字小的数字移到数组的左边，比选择的数字大的数字移到数组的右边。,平均时间复杂度：O(n * logn)最差时间复杂度：O(n2)不稳定额外空间为O (n * logn),快速排序代码实现,int P
4、artition( int data, int start, int end )int i = start-1;int j;int pri = dataend;for( j = start; j end; j+)if( dataj = pri)i+;swap( &datai, dataj);swap( &datai+1, &dataend);return i+1;,快速排序代码实现,void Quicksort( int data, int start, int end )if(start end)int k = Partition( data, start, end);Quicksort(
5、data, start, k-1);Quciksort( data, k+1, end); 大家想一想？这里的函数Partition的作用！,快速排序的应用,最小的K个数输入n个整数，找出其中最小的k个数，例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。,最小的K个数,解法一O(n)的算法，完全可以基于Partition函数来解决这个问题。如果基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。解法二O(nlogk)可以利用最大堆作为仅有k个数字的容器。适用于处理海量数据。,快速排序的应用,数组
6、中出现次数超过一半的数字数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。例如输入一个长度为9的数组1,2,3,2,2,2,5,4,2。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。,数组中出现次数超过一半的数字,解法一依然是基于Partition函数的O(n)算法。若将这个数组排序，那么排序后位于数组中间的数字一定就是所求。那么这题也就转变为求长度为n的数组中第n/2大的数字。这里可以受快排的启发，如果这个选中的数字的下标刚好是n/2，那么这个数字就是数组的中位数，若大于n/2，则中位数在它的左边，则应在左边数组中查找。,数组中出现次数超过一半的数字,解法二根据数组
7、特点发现的O(n)算法要求数组中次数超过一半的数字，则说明它出现的次数比其他所有数字出现的次数的和还要多。于是我们遍历数组，记录数组中的数字和次数。若遍历到下一个数字，和之前保存的数字相同，则次数加1，反之则次数减1，若次数为0，则需要保存下一个数字，并把次数设为1。最后一次把次数设为1时对应的数字则为所求数字。,代码实现,int GetNum(int * numbers, int length)int result = numbers0;int times = 1;for( int i = 1; i length ; i+ )if(times = 0)result = numbersi;ti
8、mes=1;elseif(numbersi=result)times+;elsetimes-;if(!Check(numbers,length,result)result=0;return result;,归并排序,它采取分而治之（Divide-and-Conquer）的策略，时间复杂度是O(n * logn)，优于插入排序算法。归并排序的步骤如下：Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。Conquer: 对这两个子序列分别采用归并排序。Combine: 将两个排序好的子序列合并成一个最终的排序序列。在描述归并排序的步骤时又调用了归并排序本身，可见这是一个递归的过程。
9、平均，最差时间复杂度：O(n*logn) 稳定 额外空间:O(1),归并排序,归并排序的应用,数组中的逆序对在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。提示：归并排序的过程,归并排序的应用,统计逆序对的过程：先把数组分隔成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。这个过程实际上就是归并排序。,归并排序的应用,数组中的逆序对在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。,排序算法小练,要求对一公司上万名员工的年龄排序，要求时间效率O(n)，额外空间大小不超过O(n).,分析:员工的年龄是在一定范围的，我们用数组times来统计每个年龄出现的次数，某个年龄出现了多少次，就在数组ages里设置几次该年龄，这样就相当于给数组ages排序了。在这里我们就使用了长度为100的整数数组作为额外空间换来了O(n)的时间效率。,Thank you!,阿里巴巴技术联盟技术分享,
