【解析】第一步:选取一个数作为基准(理论上可以随便选取)；第二步:分区,比基准值小的放左边,大的放右边,基准值放在两个分区之间；第三步:进行左边分区递归,以及右边分区递归constquicksort=arr=>{constpivotIndex=Math.floor(arr.length/2);//选取基准位置,尽量考虑随机性constpivot=arr.splice(pivotIndex,1)[0];constleft=[];constright=[];arr.forEach((item,idx)=>{if(arr[idx]<pivot){left.push(arr[idx]);}else{right.push(arr[idx]);}});returnquickSort(left).concat([pivot],quickSort(right));//连接左数组、基数组和右数组};

【解析】在快速排序中可以使用荷兰国旗问题所采用的思想,即将每次划分的中间区域用来存放当前基数。publicstaticvoidquickSort(int[]arr){if(arr==null||arr.length<2){return;}quickSort(arr,0,arr.length-1);}publicstaticvoidquickSort(int[]arr,intleft,intright){if(left<right){//下面一句话就是为了避免当前的数组已经为完全有序或者反序的状态swap(arr,left+(int)(Math.random()*(right-left+1)),right);int[]p=partition(arr,left,right);//返回等于基数的起始位置和结束位置quickSort(arr,left,p[0]-1);quickSort(arr,p[1]+1,right);}}publicstaticint[]partition(int[]arr,intleft,intright){intless=left-1;intmore=right;while(left<more){if(arr[left]<arr[right]){swap(arr,++less,left++);}elseif(arr[left]>arr[right]){swap(arr,--more,left);}else{//arr[left]==arr[right]left++;}}swap(arr,more,right);returnnewint[]{less+1,more};}publicstaticvoidswap(int[]arr,inti,intj){inttmp=arr[i];arr[i]=arr[j];arr[j]=tmp;}

【解析】基于O(n)的算法，可以用基于Partion函数解决这个问题，如果基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数组大的所有数字都位于数组的右边，这样调整之后数组左边的k个数字就是最小的k个数字，不一定有序。importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intn=in.nextInt();intk=in.nextInt();int[]num=newint[n];int[]out=newint[k];for(inti=0;i<n;i++){num[i]=in.nextInt();}booleanb=GetMinK(n,num,k,out);if(b){for(inti=0;i<k;i++){System.out.print(out[i]+"");}}}publicstaticbooleanGetMinK(intuiInputNum,int[]pInputArray,intuiK,int[]pOutputArray){if(pInputArray==null||pOutputArray==null||uiK>uiInputNum||uiInputNum<=0||uiK<=0){returnfalse;}intstart=0;intend=uiInputNum-1;intindex=partition(pInputArray,start,end);while(index!=uiK-1){if(index>uiK-1){//index在k-1的右边end=index-1;index=partition(pInputArray,start,end);}else{start=index+1;index=partition(pInputArray,start,end);}}for(inti=0;i<uiK;i++){pOutputArray[i]=pInputArray[i];}returntrue;}//partion分区函数，返回数组a的首元素快排的索引值indexpublicstaticintpartition(int[]a,intstart,intend){intprivot=a[start];inti=start;intj=end;while(i<j){while(i<j&&privot<=a[j]){j--;}swap(a,i,j);while(i<j&&privot>=a[i]){i++;}swap(a,i,j);}returni;}publicstaticvoidswap(int[]a,inti,intj){intt=a[i];a[i]=a[j];a[j]=t;}}

【解析】受快速排序的启发，在快速排序中，现在数组中选择一个数字，然后调整数组中的数字的顺序，使得比选中数字小的数字都排在它的左边，比选中数字大的数字都排在它的右边。如果选中的数字的下标刚好是n/2，那么这个数字就是数组中的中位数。importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intn=in.nextInt();int[]num=newint[n];for(inti=0;i<n;i++){num[i]=in.nextInt();}intb=GetHalfNum(n,num);if(b!=-1){System.out.println(b);}}publicstaticintGetHalfNum(intuiInputNum,int[]pInputArray){if(pInputArray==null||uiInputNum<=0){return-1;}intmiddle=uiInputNum>>1;//长度的一半intstart=0;intend=uiInputNum-1;intindex=partition(pInputArray,start,end);while(index!=middle){//如果不等于长度的一半说明就没有找到这个中位数if(index>middle){end=index-1;index=partition(pInputArray,start,end);}else{start=index+1;index=partition(pInputArray,start,end);}}returnpInputArray[index];//index=middle}publicstaticintpartition(int[]a,intstart,intend){intprivot=a[start];inti=start;intj=end;while(i<j){while(i<j&&privot<=a[j]){j--;}swap(a,i,j);while(i<j&&privot>=a[i]){i++;}swap(a,i,j);}returni;}publicstaticvoidswap(int[]a,inti,intj){intt=a[i];a[i]=a[j];a[j]=t;}}