Po prostu mało prawdopodobne scalić Sortuj , QuickSort to Algorytm dziel i zwyciężaj . Wybiera element jako element obrotowy i dzieli podaną tablicę wokół wybranego elementu obrotowego.

Istnieje wiele różnych wersji narzędzia QuickSort, które wybierają przestaw na różne sposoby.

1. Zawsze wybieraj pierwszy element jako oś obrotu
2. Zawsze wybieraj ostatni element jako oś obrotu
3. Wybierz losowy element jako oś obrotu
4. Wybierz medianę jako oś obrotu

Tutaj wybierzemy ostatni element jako oś obrotu. Kluczowym procesem w QuickSort jest partycja(). Celem partycji jest, mając tablicę i element „x” tablicy jako oś obrotu, umieść x we ​​właściwej pozycji w posortowanej tablicy i umieść wszystkie mniejsze elementy (mniejsze niż x) przed x i umieść wszystkie większe elementy (większe niż x) po x. Wszystko to powinno odbywać się w czasie liniowym.

Pyton Rekurencyjne szybkie sortowanie funkcjonować

// low -->Indeks początkowy, // wysoki --> Indeks końcowy QuickSort(arr[], niski, wysoki) { // Dopóki indeks początkowy nie będzie mniejszy niż indeks końcowy if (low // pi to indeks podziału, // arr[p] to teraz w odpowiednim miejscu pi = partycja(arr, niski, wysoki); // Przed pi QuickSort(arr, niski, pi - 1); // Po pi QuickSort(arr, pi + 1, wysoki); 
Python3
    
 
     
  
 
 

 
    
 
     
     
    
 
 
 

 
 
 
 
 # Python program for implementation of Quicksort Sort> # This implementation utilizes pivot as the last element in the nums list> # It has a pointer to keep track of the elements smaller than the pivot> # At the very end of partition() function, the pointer is swapped with the pivot> # to come up with a 'sorted' nums relative to the pivot> # Function to find the partition position> def> partition(array, low, high):> ># choose the rightmost element as pivot> >pivot>=> array[high]> ># pointer for greater element> >i>=> low>-> 1> ># traverse through all elements> ># compare each element with pivot> >for> j>in> range>(low, high):> >if> array[j] <>=> pivot:> ># If element smaller than pivot is found> ># swap it with the greater element pointed by i> >i>=> i>+> 1> ># Swapping element at i with element at j> >(array[i], array[j])>=> (array[j], array[i])> ># Swap the pivot element with the greater element specified by i> >(array[i>+> 1>], array[high])>=> (array[high], array[i>+> 1>])> ># Return the position from where partition is done> >return> i>+> 1> # function to perform quicksort> def> quickSort(array, low, high):> >if> low   # Find pivot element such that  # element smaller than pivot are on the left  # element greater than pivot are on the right  pi = partition(array, low, high)  # Recursive call on the left of pivot  quickSort(array, low, pi - 1)  # Recursive call on the right of pivot  quickSort(array, pi + 1, high) data = [1, 7, 4, 1, 10, 9, -2] print('Unsorted Array') print(data) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)>
 
 
 
 
    
   
 
>
 
  Wyjście  
 
Unsorted Array [1, 7, 4, 1, 10, 9, -2] Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10]>
 
    Złożoność czasowa:    W najgorszym przypadku złożoność czasowa wynosi O(N2), a średnia złożoność czasowa przypadku wynosi O(N log N)  
    Przestrzeń pomocnicza:    O(1)
 
    Używanie Pythona Quicksort         zrozumienie listy      
 
Szybkie sortowanie przy użyciu rozumienia list to rekurencyjny algorytm sortowania tablicy elementów. Działa poprzez wybranie elementu obrotowego i podzielenie tablicy wokół elementu obrotowego w taki sposób, że wszystkie elementy mniejsze niż element obrotowy zostaną przesunięte w lewo, a wszystkie elementy większe niż element obrotowy zostaną przesunięte w jego prawą stronę. Następnie rekurencyjnie stosuje ten sam proces do lewej i prawej podtablicy, dopóki cała tablica nie zostanie posortowana.
są modelowymi przykładami
 
    Algorytm:    
 
1. Jeśli tablica wejściowa ma długość 0 lub 1, zwróć tablicę, ponieważ jest już posortowana.  
2.Wybierz pierwszy element tablicy jako element obrotu.  
3. Utwórz dwie puste listy, lewą i prawą.  
4. Dla każdego elementu tablicy z wyjątkiem elementu obrotowego:  
A. Jeśli element jest mniejszy niż oś obrotu, dodaj go do lewej listy.  
B. Jeśli element jest większy lub równy osi obrotu, dodaj go do prawej listy.  
5.Rekursywnie wywołaj funkcję szybkiego sortowania na listach po lewej i prawej stronie.  
6.Połącz listę posortowaną po lewej stronie, element przestawny i listę posortowaną po prawej stronie.  
7. Zwróć połączoną listę.
 
Python3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # Approach 2: Quicksort using list comprehension> def> quicksort(arr):> >if> len>(arr) <>=> 1>:> >return> arr> >else>:> >pivot>=> arr[>0>]> >left>=> [x>for> x>in> arr[>1>:]>if> x   right = [x for x in arr[1:] if x>= obrót] return szybkie sortowanie (po lewej) + [pivot] + szybkie sortowanie (po prawej) # Przykładowe użycie arr = [1, 7, 4, 1, 10, 9, -2] sorted_arr = szybkie sortowanie (tablica) print('Sorted Array w kolejności rosnącej:') print(sorted_arr)>
 
 
 
 
    
 
>
 
    
 
>
 
  Wyjście  
 
Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10]>
 
Złożoność czasowa wynosi O(n log n)
 
Złożoność przestrzenna algorytmu wynosi O(n)