Selection comments updated.

liuyubobobo · liuyubobobo · commit 1cb7b390d2dc · 2018-03-08T11:43:57.000-08:00
diff --git a/03-Sorting-Advance/Course Code (C++)/Optional-05-Selection/main.cpp b/03-Sorting-Advance/Course Code (C++)/Optional-05-Selection/main.cpp
@@ -38,11 +38,15 @@ int __selection( T arr[], int l, int r, int k ){
         return arr[p];
     else if( k < p )    // 如果 k < p, 只需要在arr[l...p-1]中找第k小元素即可
         return __selection( arr, l, p-1, k);
-    else // 如果 k > p, 则需要在arr[p+1...r]中找第k小元素
+    else // 如果 k > p, 则需要在arr[p+1...r]中找第k-p-1小元素
+         // 注意: 由于我们传入__selection的依然是arr, 而不是arr[p+1...r],
+         //       所以传入的最后一个参数依然是k, 而不是k-p-1
         return __selection( arr, p+1, r, k );
 }
 
 // 寻找arr数组中第k小的元素
+// 注意: 在我们的算法中, k是从0开始索引的, 即最小的元素是第0小元素, 以此类推
+// 如果希望我们的算法中k的语意是从1开始的, 只需要在整个逻辑开始进行k--即可, 可以参考selection2
 template <typename T>
 int selection(T arr[], int n, int k) {
 
@@ -52,6 +56,14 @@ int selection(T arr[], int n, int k) {
     return __selection(arr, 0, n - 1, k);
 }
 
+// 寻找arr数组中第k小的元素, k从1开始索引, 即最小元素是第1小元素, 以此类推
+template <typename T>
+int selection2(T arr[], int n, int k) {
+
+    return selection(arr, n, k - 1);
+}
+
+
 // 测试 selection算法
 int main() {
 
@@ -69,5 +81,20 @@ int main() {
 
     delete[] arr;
 
+    cout << endl;
+
+    // 验证selection2算法
+    arr = TestHelper::generateOrderedArray(n);
+    TestHelper::shuffleArray(arr, n);
+
+    // 对arr数组求第i小元素, 应该为i - 1 (在selection2中, 第k小元素的k是从1索引的)
+    for( int i = 1 ; i <= n ; i ++ ){
+        assert( selection2(arr, n, i) == i - 1 );
+        cout<<"test "<<i<<" complete."<<endl;
+    }
+    cout<<"Test selection2 completed."<<endl;
+
+    delete[] arr;
+
     return 0;
 }
diff --git a/03-Sorting-Advance/Course Code (Java)/Optional-05-Selection/src/bobo/algo/Selection.java b/03-Sorting-Advance/Course Code (Java)/Optional-05-Selection/src/bobo/algo/Selection.java
@@ -43,15 +43,25 @@ private static Comparable solve(Comparable[] nums, int l, int r, int k){
             return nums[p];
         else if( k < p )    // 如果 k < p, 只需要在nums[l...p-1]中找第k小元素即可
             return solve( nums, l, p-1, k);
-        else // 如果 k > p, 则需要在nums[p+1...r]中找第k小元素
+        else // 如果 k > p, 则需要在nums[p+1...r]中找第k-p-1小元素
+             // 注意: 由于我们传入__selection的依然是nums, 而不是nums[p+1...r],
+             //       所以传入的最后一个参数依然是k, 而不是k-p-1
             return solve( nums, p+1, r, k );
     }
 
     // 寻找nums数组中第k小的元素
-    public static Comparable solve(Comparable nums[], int n, int k) {
+    // 注意: 在我们的算法中, k是从0开始索引的, 即最小的元素是第0小元素, 以此类推
+    // 如果希望我们的算法中k的语意是从1开始的, 只需要在整个逻辑开始进行k--即可, 可以参考solve2
+    public static Comparable solve(Comparable nums[], int k) {
 
-        assert k >= 0 && k < n;
-        return solve(nums, 0, n - 1, k);
+        assert nums != null && k >= 0 && k < nums.length;
+        return solve(nums, 0, nums.length - 1, k);
+    }
+
+    // 寻找nums数组中第k小的元素, k从1开始索引, 即最小元素是第1小元素, 以此类推
+    public static Comparable solve2(Comparable nums[], int k) {
+
+        return Selection.solve(nums, k - 1);
     }
 
     private static void swap(Object[] arr, int i, int j) {
@@ -68,11 +78,25 @@ public static void main(String[] args) {
         Integer[] arr = TestHelper.generateOrderedArray(N);
         TestHelper.shuffleArray(arr);
 
-        // 验证selection算法, 对arr数组求第i小元素, 应该为i
+        // 验证Selection.solve, 对arr数组求第i小元素, 应该为i
+        for( int i = 0 ; i < N ; i ++ ){
+            assert solve(arr, i) == i;
+            System.out.println("test " + i + " complete.");
+        }
+        System.out.println("Test Selection.solve completed.");
+        System.out.println();
+
+
+        arr = TestHelper.generateOrderedArray(N);
+        TestHelper.shuffleArray(arr);
+
+        // 验证Selection.solve2, 对arr数组求第i小元素, 应该为i-1
+        // 因为在Selection.solve2中, 第k小元素的k是从1索引的
         for( int i = 0 ; i < N ; i ++ ){
-            assert solve(arr, N, i) == i;
+            assert solve2(arr, i) == i - 1;
             System.out.println("test " + i + " complete.");
         }
+        System.out.println("Test Selection.solve2 completed.");
 
     }
 }
