快速选择

快速选择

快速选择其实是相当于快速排序和二分查找的结合

平均情况O(n)

static int[] array ;
        static void Main(string[] args)
        {
            array = new int[] { 21312, 43234, 5, 324, 543 } ;


            Console.WriteLine("{0}", quickselect(2, 0, 4));
            Console.ReadLine();
        }

        //  打印
        static int partition(int left_pointer,int right_pointer)
        {
            //总是取最右的值为轴
            int pivot_position = right_pointer;
            int pivot = array[pivot_position];
            right_pointer--;
            while (true)
            {
                
                while (array[left_pointer] < pivot)
                {
                    left_pointer++;
                    if (left_pointer == pivot_position)
                    {
                        break;
                    }
                }
                while (right_pointer >= 0 && array[right_pointer] > pivot)
                {
                    right_pointer--;
                    if (right_pointer == 0)
                    {
                        break;
                    }
                }
                if (left_pointer >= right_pointer)
                {
                    break;
                }
                else
                {
                    swap(left_pointer, right_pointer);
                }
            }
            swap(left_pointer, pivot_position);
            return left_pointer;
        }
        static void swap(int pointer1,int pointer2)
        {
            int temp_value = array[pointer1];
            array[pointer1] = array[pointer2];
            array[pointer2] = temp_value;
        }
        static int quickselect(int kth_lower_value,int left_index,int right_index)
        {
            if (right_index - left_index <= 0)
            {
                return array[left_index];
            }
            int pivot_position = partition(left_index, right_index);
            if (kth_lower_value < pivot_position)
            {
                return quickselect(kth_lower_value, left_index, pivot_position - 1);
            }else if (kth_lower_value > pivot_position)
            {
                return quickselect(kth_lower_value, pivot_position + 1, right_index);
            }
            else
            {
                return array[pivot_position];
            }
        }