【解析】受快速排序的启发，在快速排序中，现在数组中选择一个数字，然后调整数组中的数字的顺序，使得比选中数字小的数字都排在它的左边，比选中数字大的数字都排在它的右边。如果选中的数字的下标刚好是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;}}

【解析】基于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;}}

【解析】在快速排序中可以使用荷兰国旗问题所采用的思想,即将每次划分的中间区域用来存放当前基数。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;}

【解析】第一步:选取一个数作为基准(理论上可以随便选取)；第二步:分区,比基准值小的放左边,大的放右边,基准值放在两个分区之间；第三步:进行左边分区递归,以及右边分区递归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));//连接左数组、基数组和右数组};

正确答案是C选择排序在调整树的过程中改变节点的顺序导致不稳定，快排一个指针从前之后，一个从后至前，从后往前可能将多个小于基准数据的数原本先进入数组却放在了前面，归并算法采用的归并方式稳定的话就可以保证其稳定性，希尔排序是因为增量对不同组的顺序形成一种隔离，每个组内稳定，多个组在一起就不稳定。

正确答案是A堆的空间复杂度为1，快速排序为log2（n），归并为n