Понимание алгоритма QuickSelect

Важной частью быстрого выбора является раздел. Итак, позвольте мне сначала объяснить это.

Раздел при быстром выборе выбирает pivot (случайным образом или первый / последний элемент). Затем он переупорядочивает список таким образом, что все элементы меньше pivot находятся слева от точки поворота, а другие - справа. Затем он возвращает индекс элемента pivot.

Теперь мы находим k-й наименьший элемент. Случаи после разделения бывают:

1. k == pivot. Тогда вы уже нашли k-е наименьшее. Это потому, что раздел работает. Ровно k - 1 элементов меньше элемента kth.
2. k < pivot. Тогда k-й наименьший находится слева от pivot.
3. k > pivot. Тогда k-й наименьший находится справа от оси поворота. И чтобы найти его, вам нужно найти k-pivot наименьшее число справа.

кстати, в вашем коде есть несколько ошибок ..

int quickSelect(int items[], int first, int last, int k) {
    int pivot = partition(items, first, last);
    if (k < pivot-first+1) { //boundary was wrong
        return quickSelect(items, first, pivot, k);
    } else if (k > pivot-first+1) {//boundary was wrong
        return quickSelect(items, pivot+1, last, k-pivot);
    } else {
        return items[pivot];//index was wrong
    }
}

Разделение довольно простое: оно переупорядочивает элементы таким образом, что те элементы, которые меньше выбранной точки поворота, имеют более низкие индексы в массиве, чем точка поворота, а те, которые больше, чем точка поворота, имеют более высокие индексы в массиве.

Об остальном я говорил в предыдущем ответе.

int quickSelect(int A[], int l, int h,int k)
{
        int p = partition(A, l, h); 
        if(p==(k-1)) return A[p];
        else if(p>(k-1)) return quickSelect(A, l, p - 1,k);  
        else return quickSelect(A, p + 1, h,k);

}

// функция разделения такая же, как QuickSort

Я читал книгу CLRS Algorithm, чтобы узнать алгоритм быстрого выбора, мы можем легко реализовать алгоритм.

package selection;    
import java.util.Random;

/**
 * This class will calculate and print Nth ascending order element
 * from an unsorted array in expected time complexity O(N), where N is the
 * number of elements in the array.
 * 
 * The important part of this algorithm the randomizedPartition() method.
 * 
 * @author kmandal
 *
 */
public class QuickSelect {
    public static void main(String[] args) {
        int[] A = { 7, 1, 2, 6, 0, 1, 96, -1, -100, 10000 };
        for (int i = 0; i < A.length; i++) {
            System.out.println("The " + i + "th ascending order element is "
                    + quickSelect(A, 0, A.length - 1, i));
        }
    }

    /**
     * Similar to Quick sort algorithm partitioning approach works, but after
     * that instead of recursively work on both halves here will be recursing
     * into desired half. This step ensure to the expected running time to be
     * O(N).
     * 
     * @param A
     * @param p
     * @param r
     * @param i
     * @return
     */
    private static int quickSelect(int[] A, int p, int r, int i) {
        if (p == r) {
            return A[p];
        }
        int partitionIndex = randomizedPartition(A, p, r);
        if (i == partitionIndex) {
            return A[i];
        } else if (i < partitionIndex) {// element is present in left side of
                                        // partition
            return quickSelect(A, p, partitionIndex - 1, i);
        } else {
            return quickSelect(A, partitionIndex + 1, r, i);// element is
                                                            // present in right
            // side of partition
        }
    }

    /**
     * 
     * Similar to Quick sort algorithm this method is randomly select pivot
     * element index. Then it swap the random pivot element index with right
     * most element. This random selection step is expecting to make the
     * partitioning balanced. Then in-place rearranging the array to make all
     * elements in the left side of the pivot element are less than pivot
     * element and the right side elements are equals or grater than the pivot
     * element. Finally return partition index.
     * 
     * @param A
     * @param p
     * @param r
     * @return
     */
    private static int randomizedPartition(int[] A, int p, int r) {
        int partitionIndex = p;
        int random = p + new Random().nextInt(r - p + 1);// select
                                                            // pseudo random
                                                            // element
        swap(A, random, r);// swap with right most element
        int pivot = A[r];// select the pivot element
        for (int i = p; i < A.length - 1; i++) {
            if (A[i] < pivot) {
                swap(A, i, partitionIndex);
                partitionIndex++;
            }
        }
        swap(A, partitionIndex, r);
        return partitionIndex;
    }

    /**
     * Swapping 2 elements in an array.
     * 
     * @param A
     * @param i
     * @param j
     */
    private static void swap(int[] A, int i, int j) {
        if (i != j && A[i] != A[j]) {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
}


Output:
The 0th ascending order element is -100
The 1th ascending order element is -1
The 2th ascending order element is 0
The 3th ascending order element is 1
The 4th ascending order element is 1
The 5th ascending order element is 2
The 6th ascending order element is 6
The 7th ascending order element is 7
The 8th ascending order element is 96
The 9th ascending order element is 10000