算法题（快速选择算法） _数据结构

本文概述

C ++
Java
Python3
C#

快速选择是一种选择算法, 用于在无序列表中找到第k个最小的元素。它与快速排序排序算法。
例子：

Input: arr[] = {7, 10, 4, 3, 20, 15} k = 3 Output: 7Input: arr[] = {7, 10, 4, 3, 20, 15} k = 4 Output: 10

【算法题（快速选择算法）】该算法类似于QuickSort。不同之处在于, 它只对包含第k个最小元素的部分重复出现, 而不是在两侧都重复出现。逻辑很简单, 如果分区元素的索引大于k, 则针对左部分递归。如果index与k相同, 则找到第k个最小元素, 然后返回。如果索引小于k, 则返回正确的部分。这将预期的复杂度从O(n log n)降低到O(n), 最坏的情况是O(n ^ 2)。

function quickSelect(list, left, right, k)if left = right return list[left]Select a pivotIndex between left and rightpivotIndex := partition(list, left, right, pivotIndex) if k = pivotIndex return list[k] else if k < pivotIndex right := pivotIndex - 1 else left := pivotIndex + 1

C ++

//CPP program for implementation of QuickSelect #include < bits/stdc++.h> using namespace std; //Standard partition process of QuickSort(). //It considers the last element as pivot //and moves all smaller element to left of //it and greater elements to right int partition( int arr[], int l, int r) { int x = arr[r], i = l; for ( int j = l; j < = r - 1; j++) { if (arr[j] < = x) { swap(arr[i], arr[j]); i++; } } swap(arr[i], arr[r]); return i; }//This function returns k'th smallest //element in arr[l..r] using QuickSort //based method.ASSUMPTION: ALL ELEMENTS //IN ARR[] ARE DISTINCT int kthSmallest( int arr[], int l, int r, int k) { //If k is smaller than number of //elements in array if (k> 0 & & k < = r - l + 1) {//Partition the array around last //element and get position of pivot //element in sorted array int index = partition(arr, l, r); //If position is same as k if (index - l == k - 1) return arr[index]; //If position is more, recur //for left subarray if (index - l> k - 1) return kthSmallest(arr, l, index - 1, k); //Else recur for right subarray return kthSmallest(arr, index + 1, r, k - index + l - 1); }//If k is more than number of //elements in array return INT_MAX; }//Driver program to test above methods int main() { int arr[] = { 10, 4, 5, 8, 6, 11, 26 }; int n = sizeof (arr) /sizeof (arr[0]); int k = 3; cout < < "K-th smallest element is " < < kthSmallest(arr, 0, n - 1, k); return 0; }

Java

//Java program of Quick Select import java.util.Arrays; class GFG {//partition function similar to quick sort //Considers last element as pivot and adds //elements with less value to the left and //high value to the right and also changes //the pivot position to its respective position //in the final array. public static int partition ( int [] arr, int low, int high) { int pivot = arr[high], pivotloc = low; for ( int i = low; i < = high; i++) { //inserting elements of less value //to the left of the pivot location if (arr[i] < pivot) { int temp = arr[i]; arr[i] = arr[pivotloc]; arr[pivotloc] = temp; pivotloc++; } }//swapping pivot to the final pivot location int temp = arr[high]; arr[high] = arr[pivotloc]; arr[pivotloc] = temp; return pivotloc; }//finds the kth position (of the sorted array) //in a given unsorted array i.e this function //can be used to find both kth largest and //kth smallest element in the array. //ASSUMPTION: all elements in arr[] are distinct public static int kthSmallest( int [] arr, int low, int high, int k) { //find the partition int partition = partition(arr, low, high); //if partition value is equal to the kth position, //return value at k. if (partition == k) return arr[partition]; //if partition value is less than kth position, //search right side of the array. else if (partition < k ) return kthSmallest(arr, partition + 1 , high, k ); //if partition value is more than kth position, //search left side of the array. else return kthSmallest(arr, low, partition- 1 , k ); }//Driver Code public static void main(String[] args) { int [] array = new int []{ 10 , 4 , 5 , 8 , 6 , 11 , 26 }; int [] arraycopy = new int []{ 10 , 4 , 5 , 8 , 6 , 11 , 26 }; int kPosition = 3 ; int length = array.length; if (kPosition> length) { System.out.println( "Index out of bound" ); } else { //find kth smallest value System.out.println( "K-th smallest element in array : " + kthSmallest(arraycopy, 0 , length - 1 , kPosition - 1 )); } } }//This code is contributed by Saiteja Pamulapati

Python3

# Python3 program of Quick Select# Standard partition process of QuickSort(). # It considers the last element as pivot # and moves all smaller element to left of # it and greater elements to right def partition(arr, l, r):x = arr[r] i = l for j in range (l, r):if arr[j] < = x: arr[i], arr[j] = arr[j], arr[i] i + = 1arr[i], arr[r] = arr[r], arr[i] return i# finds the kth position (of the sorted array) # in a given unsorted array i.e this function # can be used to find both kth largest and # kth smallest element in the array. # ASSUMPTION: all elements in arr[] are distinct def kthSmallest(arr, l, r, k):# if k is smaller than number of # elements in array if (k> 0 and k < = r - l + 1 ):# Partition the array around last # element and get position of pivot # element in sorted array index = partition(arr, l, r)# if position is same as k if (index - l = = k - 1 ): return arr[index]# If position is more, recur # for left subarray if (index - l> k - 1 ): return kthSmallest(arr, l, index - 1 , k)# Else recur for right subarray return kthSmallest(arr, index + 1 , r, k - index + l - 1 ) return INT_MAX# Driver Code arr = [ 10 , 4 , 5 , 8 , 6 , 11 , 26 ] n = len (arr) k = 3 print ( "K-th smallest element is " , end = "") print (kthSmallest(arr, 0 , n - 1 , k))# This code is contributed by Muskan Kalra.

//C# program of Quick Select using System; class GFG {//partition function similar to quick sort //Considers last element as pivot and adds //elements with less value to the left and //high value to the right and also changes //the pivot position to its respective position //in the readonly array. static int partitions( int []arr, int low, int high) { int pivot = arr[high], pivotloc = low, temp; for ( int i = low; i < = high; i++) { //inserting elements of less value //to the left of the pivot location if (arr[i] < pivot) { temp = arr[i]; arr[i] = arr[pivotloc]; arr[pivotloc] = temp; pivotloc++; } }//swapping pivot to the readonly pivot location temp = arr[high]; arr[high] = arr[pivotloc]; arr[pivotloc] = temp; return pivotloc; }//finds the kth position (of the sorted array) //in a given unsorted array i.e this function //can be used to find both kth largest and //kth smallest element in the array. //ASSUMPTION: all elements in []arr are distinct static int kthSmallest( int [] arr, int low, int high, int k) { //find the partition int partition = partitions(arr, low, high); //if partition value is equal to the kth position, //return value at k. if (partition == k) return arr[partition]; //if partition value is less than kth position, //search right side of the array. else if (partition < k ) return kthSmallest(arr, partition + 1, high, k ); //if partition value is more than kth position, //search left side of the array. else return kthSmallest(arr, low, partition - 1, k ); }//Driver Code public static void Main(String[] args) { int [] array = {10, 4, 5, 8, 6, 11, 26}; int [] arraycopy = {10, 4, 5, 8, 6, 11, 26}; int kPosition = 3; int length = array.Length; if (kPosition> length) { Console.WriteLine( "Index out of bound" ); } else { //find kth smallest value Console.WriteLine( "K-th smallest element in array : " + kthSmallest(arraycopy, 0, length - 1, kPosition - 1)); } } }//This code is contributed by 29AjayKumar

输出如下：