Schnellauswahl ist ein Auswahlalgorithmus, um das k-kleinste Element in einer ungeordneten Liste zu finden. Es hängt mit dem zusammen schnelle Sorte Sortieralgorithmus.
Beispiele:

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

Der Algorithmus ähnelt QuickSort. Der Unterschied besteht darin, dass es nicht für beide Seiten wiederkehrt (nachdem der Drehpunkt gefunden wurde), sondern nur für den Teil, der das k-kleinste Element enthält. Die Logik ist einfach: Wenn der Index des partitionierten Elements größer als k ist, wiederholen wir den Vorgang für den linken Teil. Wenn der Index mit k übereinstimmt, haben wir das k-kleinste Element gefunden und kehren zurück. Wenn der Index kleiner als k ist, führen wir eine Wiederholung für den rechten Teil durch. Dies reduziert die erwartete Komplexität von O(n log n) auf O(n), mit einem Worst-Case von O(n^2).

function quickSelect(list, left, right, k) if left = right return list[left] Select a pivotIndex between left and right pivotIndex := partition(list, left, right, pivotIndex) if k = pivotIndex return list[k] else if k  C++14       // CPP program for implementation of QuickSelect  #include  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);   } // Wenn k mehr als die Anzahl // Elemente im Array ist, return INT_MAX;  } // Treiberprogramm zum Testen der oben genannten Methoden 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]   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 - 1)   return arr[partition];     // if partition value is less than kth position,   // search right side of the array.   else if (partition 1)   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>Länge) { System.out.println('Index außerhalb der Grenze');   } else { // k-ten kleinsten Wert finden System.out.println( 'K-tes kleinstes Element im Array : ' + kthSmallest(arraycopy, 0, length - 1, kPosition));   } } } // Dieser Code wurde von Saiteja Pamulapati beigesteuert. Python3 # Python3-Programm von Quick Select # Standardpartitionsprozess von QuickSort().  # Es betrachtet das letzte Element als Pivot # und verschiebt alle kleineren Elemente nach links davon und alle größeren Elemente nach rechts def partition(arr, l, r): x = arr[r] i = l für j in range(l, r): wenn arr[j] <= x:   arr[i], arr[j] = arr[j], arr[i]   i += 1    arr[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 und 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) print('Index out of bound') # Treibercode arr = [ 10, 4, 5, 8, 6, 11, 26 ] n = len(arr) k = 3 print('K-tes kleinstes Element ist ', end = ' ') print(kthSmallest(arr, 0, n - 1, k)) # Dieser Code wurde von Muskan Kalra beigesteuert.   C# // C#-Programm von Quick Select using System;    Klasse GFG { // Partitionsfunktion ähnlich der Schnellsortierung // Betrachtet das letzte Element als Pivot und fügt // Elemente mit niedrigerem Wert nach links und // hohem Wert nach rechts hinzu und ändert auch // die Pivot-Position in die entsprechende Position / / im schreibgeschützten 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]   {   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   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 ofbound');   } else { // k-ten kleinsten Wert finden Console.WriteLine('K-tes kleinstes Element im Array : ' + kthSmallest(arraycopy, 0, length - 1, kPosition - 1));   } } } // Dieser Code wurde von 29AjayKumar beigesteuert. Javascript // Javascript-Programm von Quick Select // Partitionsfunktion ähnlich der Schnellsortierung // Betrachtet das letzte Element als Pivot und fügt // Elemente mit geringerem Wert links und // hohem Wert hinzu nach rechts und ändert auch // die Pivot-Position in ihre entsprechende Position // im letzten Array.  function _partition(arr, low, high) { let Pivot = arr[high], Pivotloc = Low;   für (sei i = niedrig; i <= high; i++)   {     // inserting elements of less value   // to the left of the pivot location   if (arr[i]   {   let temp = arr[i];   arr[i] = arr[pivotloc];   arr[pivotloc] = temp;   pivotloc++;   }   }     // swapping pivot to the final pivot location   let 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  function kthSmallest(arr, low, high, k)  {     // find the partition   let partition = _partition(arr, low, high);     // if partition value is equal to the kth position,   // return value at k.   if (partition == k - 1)   return arr[partition];     // if partition value is less than kth position,   // search right side of the array.   else if (partition   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  let array = [ 10, 4, 5, 8, 6, 11, 26];  let arraycopy = [10, 4, 5, 8, 6, 11, 26 ];  let kPosition = 3;  let length = array.length;    if (kPosition>length) { document.write('Index out ofbound ');  } else { // k-ten kleinsten Wert finden document.write( 'K-tes kleinstes Element im Array : ' + kthSmallest(arraycopy, 0, length - 1, kPosition)+' ');  } // Dieser Code wurde von rag2127 beigesteuert. Ausgabe: Das K-te kleinste Element ist 6. Wichtige Punkte: Wie Quicksort ist es in der Praxis schnell, weist jedoch im schlimmsten Fall eine schlechte Leistung auf. Es wird in verwendet. Der Partitionierungsprozess ist der gleiche wie bei QuickSort, nur der rekursive Code unterscheidet sich. Es gibt einen Algorithmus, der im schlimmsten Fall das k-kleinste Element in O(n) findet, aber QuickSelect schneidet im Durchschnitt besser ab.    Zugehörige C++-Funktion: std::nth_element in C++