package sort;

/**
 * @author wangjunwei87
 * @since 2019-03-10
 */
public class KthSmallest {

    public static int kthSmallest(int[] arr, int k) {
        if (arr == null || arr.length < k) {
            return -1;
        }

        int partition = partition(arr, 0, arr.length - 1);
        while (partition + 1 != k) {
            if (partition + 1 < k) {
                partition = partition(arr, partition + 1, arr.length - 1);
            } else {
                partition = partition(arr, 0, partition - 1);
            }
        }

        return arr[partition];
    }

    private static int partition(int[] arr, int p, int r) {
        int pivot = arr[r];

        int i = p;
        for (int j = p; j <= r - 1; j++) {
            if (arr[j] < pivot) {
                swap(arr, i, j);
                i++;
            }
        }

        swap(arr, i, r);

        return i;
    }

    private static void swap(int[] arr, int i, int j) {
        if (i == j) {
            return;
        }

        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

@@ -715,15 +715,10 @@
  j %3C
-=
  r
- - 1
 ; j+
@@ -718,24 +718,80 @@
 %3C r; j++) %7B%0A
+            // %E8%BF%99%E9%87%8C%E8%A6%81%E6%98%AF %3C= %EF%BC%8C%E4%B8%8D%E7%84%B6%E4%BC%9A%E5%87%BA%E7%8E%B0%E6%AD%BB%E5%BE%AA%E7%8E%AF%EF%BC%8C%E6%AF%94%E5%A6%82%E6%9F%A5%E6%89%BE%E6%95%B0%E7%BB%84 %5B1,1,2%5D %E7%9A%84%E7%AC%AC%E4%BA%8C%E5%B0%8F%E7%9A%84%E5%85%83%E7%B4%A0%0A
             
@@ -802,16 +802,17 @@
 arr%5Bj%5D %3C
+=
  pivot) 

fix bug 12_sorts.KthSmallest