此题可以用快速排序的思想来做，快速排序过程中，我们是用分治的思想，这道题我们用减治的思想，分治是将一个大问题分解成多个子问题，最后再把多个字问题合并后才能得到结果，而减治的思想就是将大问题分解城多个字问题，最后不用合并子问题就能得到结果，快速排序跟二分查找就是分治和减治的代表。此题我们用减治的思想来做。我们比较每一次枢轴跟 k-1 的值，如果枢轴大于 k-1 ，则递归对枢轴的左边进行排序，如果枢轴小于 k-1 ，则递归对枢轴的右边进行排序，一直递归到枢轴值等于 k-1 ，此时前 k-1 个值便是所求的解。
package Quick_Sort; public class test { /* * arr 为待查找的数组 * low 为数组的左边界 * high 为数组的右边界 */ public int partition(int[] arr,int low,int high ){ int i = low; int j = high; int temp = arr[i]; //第一个数作为枢轴 此处需要添加一个变量来存储枢轴值 do{ while(arr[j] > temp && i <j){ j--; } if(i < j){ arr[i] = arr[j]; i ++; } while(arr[i] < temp && i <j ){ i++; } if(i<j){ arr[j] = arr[i]; j--; } }while(i != j); //当i = j 时，i位置为枢轴的插入位置 arr[i] = temp; return i; //返回枢轴位置 } public void Sort(int[] arr,int n,int k){ if(arr == null || n ==0 || k> n){ return; } int start = 0; int end = n-1; int indx = partition(arr,start,end); while(indx != k-1){ if(indx < k-1){ start = indx + 1; indx = partition(arr,start,end); //如果枢轴位置小于 k-1 将枢轴置于枢轴右方 }else if(indx > k-1){ end = indx - 1; indx = partition(arr,start,end); //如果枢轴位置大于 k-1 将枢轴置于枢轴左方 } } // 枢轴位置就是第k小的数的位置 for(int r = 0;r <k;r++){ System.out.println(arr[r]); //打印前 k 小的数 } } public static void main(String[] args) { test test1 = new test(); int arr[] = {3,4,8,7,5,9,1,6}; test1.Sort(arr,8,3); } }