查找最小的k個數及其位置 java實作

// 用查找排序，隻找出k個從小到大排序的值的下标
public class Test {
	// 找到前k個最小值  a[]
	public static void main(String[] args) {
		int k = 5;   // 0  1  2  3  4  5 6  7 8  9  10 11
		int[] array = {12,89,64,52,98,36,2,40,1,88,32,1};
		Test sorter = new Test();
		sorter.sort(array, k);
	}
	public void sort(int[] array,int k) {
		int[] a = new int[k];
		int[] numbers = new int[array.length];
		for (int i = 0; i < numbers.length; i++) {
			numbers[i] = i;
		}
		for (int i = 0; i < k; i++) {
			// 沒有進行排序的）不斷地與第i個相比，找到剩餘中最小的，放在第i個
			int index = i;
			// find the minimum in the rest
			for (int j = i; j < array.length; j++) {
				if (array[index] > array[j]) {
					index = j;  // 不斷把找出的最小值的下标 指派給index
				}
			}
			a[i] = array[index]; // 最小值
			
			// change 得到正确下标資料的關鍵是，在交換的時候要把下标也換了
			int temp = array[i];
			array[i] = array[index];
			array[index] = temp;
			
			int temp2 = numbers[i];
			numbers[i] = numbers[index];
			numbers[index] = temp2;
		}
		int[] num_k = new int[k];
		System.arraycopy(numbers, 0, num_k, 0, k);
		
		for (int m : array) {
			System.out.print(" " + m);
		}
		System.out.println("\n輸出k個由小到大排列的值");
		for (int i : a) {
			System.out.print(" "+ i);
		}
		System.out.println("\n輸出前k個是正确排列值的下标");
		for (int ii : num_k) {
			System.out.print(" "+ ii);
		}
	}
}
           

輸出：

 1 1 2 12 32 36 64 40 52 88 98 89

輸出k個由小到大排列的值

 1 1 2 12 32

輸出前k個是正确排列值的下标

 8 11 6 0 10

這裡設定了k = 5，即在輸出的第一行中，隻有前五個是經過嚴格排序的（外層循環為5次，即隻查找了5次最大值）。