深圳java培训机构
- 电询 人气 39
- 深圳罗湖
- 300元 立即领取
- 普通课程
- 全日制
-
该课程由猎学网审核，享受猎学网报名、支付保障
- 7天退款
- 资金担保
- 质量保障
-
深圳鲲鹏职业技术培训中心 人气 21421条评价 深圳罗湖
课程详情
完整图文>>【课程详情】
快速排序（QuickSort）：
快速排序（QuickSort）的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对着两部分记录继续进行排序，以达到整个序列有序的目的。
例题：假设现在我们要对数组{50,10,90,30,70,40,80,60,20}进行排序。算法实现如下：
#include
usingnamespacestd;
intPartion(int*array,intstart,intend)
{
/*判断参数合法性*/
if(array==NULL||start<0||end<0||start>end)
{
return-1;
}
/*取枢纽为个元素，则将array[start,end]以枢纽分成两部分，
前部分小于pivotKey,后部分大于pivotKey*/
intpivotKey=array[start];
inti=start,j=end;
while(i
{
while(i
{
j--;
}
array[i]=array[j];
while(i { i++; } array[j]=array[i]; } array[i]=pivotKey; returni; } voidQuickSort(int*array,intstart,intend) { /*判断参数合法性*/ if(array==NULL||start<0||end<0||start>end) { return; } if(start { intpivot=Partion(array,start,end); QuickSort(array,start,pivot-1); QuickSort(array,pivot+1,end); } } intmain() { intarray[]={50,10,90,30,70,40,80,60,20}; QuickSort(array,0,8); for(inti=0;i<8;i++) { cout< } cout< } #include usingnamespacestd; intPartion(int*array,intstart,intend) { /*判断参数合法性*/ if(array==NULL||start<0||end<0||start>end) { return-1; } /*取枢纽为个元素，则将array[start,end]以枢纽分成两部分， 前部分小于pivotKey,后部分大于pivotKey*/ intpivotKey=array[start]; inti=start,j=end; while(i { while(i { j--; } array[i]=array[j]; while(i { i++; } array[j]=array[i]; } array[i]=pivotKey; returni; } voidQuickSort(int*array,intstart,intend) { /*判断参数合法性*/ if(array==NULL||start<0||end<0||start>end) { return; } if(start { intpivot=Partion(array,start,end); QuickSort(array,start,pivot-1); QuickSort(array,pivot+1,end); } } intmain() { intarray[]={50,10,90,30,70,40,80,60,20}; QuickSort(array,0,8); for(inti=0;i<8;i++) { cout< } cout< } 下面我们考虑，如果使用快速排序的基本思想来解决以下问题。 例1：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。（剑指offer，面试题29，页数：163） 如果数组中有一个数字出现的次数超过数组长度的一半，则如果将该数组排序之后，那么其array[length/2]中的值必是该值。同样，该值是整个数组的中位数。即长度为n的数组的第n/2大的数字。 考虑快速排序算法，我们先在数组中选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小的数字都排在它的左边，比选中的数字大的数字都排在它的右边。如果这个被选中的数字的下标刚好是n/2，则这个数字就是数组的中位数。
猜您喜欢
更多>>
顾问将于24小时内联系您！