【解析】受快速排序的启发，在快速排序中，现在数组中选择一个数字，然后调整数组中的数字的顺序，使得比选中数字小的数字都排在它的左边，比选中数字大的数字都排在它的右边。如果选中的数字的下标刚好是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选择排序在调整树的过程中改变节点的顺序导致不稳定，快排一个指针从前之后，一个从后至前，从后往前可能将多个小于基准数据的数原本先进入数组却放在了前面，归并算法采用的归并方式稳定的话就可以保证其稳定性，希尔排序是因为增量对不同组的顺序形成一种隔离，每个组内稳定，多个组在一起就不稳定。

冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止

基本排序算法：冒泡，选择，插入，希尔，归并，快排冒泡排序：functionbubbleSort(data){vartemp=0;for(vari=data.length;i>0;i--){for(varj=0;j<i-1;j++){if(data[j]>data[j+1]){temp=data[j];data[j]=data[j+1];data[j+1]=temp;}}}returndata;}选择排序：functionselectionSort(data){for(vari=0;i<data.length;i++){varmin=data[i];vartemp;varindex=1;for(varj=i+1;j<data.length;j++){if(data[j]<min){temp=data[j];data[j]=min;min=temp;}}temp=data[i];data[i]=min;data[index]=temp}}插入排序：functioninsertSort(data){varlen=data.length;for(vari=0;i<len;i++){varkey=data[i];varj=i-1;while(j>=0&&data[j]>key){data[j+1]=data[i];j--;}data[j+1]=key;}returndata;}希尔排序：functionshallSort(array){varincrement=array.length;varivartemp;//暂存do{//设置增量increment=Math.floor(increment/3)+1;for(i=increment;i<array.length;i++){if(array[i]<array[i-increment]){temp=array[i];for(varj=i-increment;j>=0&&temp<array[j];j-=increment){array[j+increment]=array[j];}array[j+increment]=temp;}}}while(increment>1)returnarray;}归并排序：functionmergeSort(array){varlen=array.length;if(len<2){returnarray;}varmiddle=Math.floor(len/2),left=array.slice(0,middle),right=array.slice(middle);returnmerge(mergeSort(left),mergeSort(right));}functionmerge(left,right){varresult=[];while(left.length&&right.length){if(left[0]<=right[0]){result.push(left.shift());}else{result.push(right.shift());}}while(left.length)result.push(left.shift());while(right.length)result.push(right.shift());returnresult;}快速排序functionquickSort(arr){if(arr.length==0)return[];varleft=[];varright=[];varpivot=arr[0];for(vari=0;i<arr.length;i++){if(arr[i]<pivot){left.push(arr[i]);}else{right.push(arr[i]);}}returnquickSort(left).concat(pivot,quickSort(right));}

冒泡排序：重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

冒泡排序的思想原理就是：交换排序。相邻的两个数字进行比较，如果反序则两两交换，直到没有要交换的，则排序结束。具体步骤：1.比较相邻的两个数据，第一个比第二个大，则相互交换2.每个相邻的两个数字都进行此操作，从左边的第一对进行到最后一对。此时最后一个元素是最大的3.所有元素重复以上两步，刚进行交换至最后的元素不用再参加比较(因为后面的已经是最大的数值了)4.持续比较，直到没有要比较的数字为止。

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