• Quicksort is often used because it is more efficient than other sorting methods that are also O(N*logN).

  • The basic principle is that the array a = [1,3,5,7,6,4,2] 1 selects a datum A [0] 2 and places those smaller than a[0] to the left and those larger than a[0] to the right. Interrupt recursion is not performed if it is less than two digits. 3 Perform 1, 2, and 3 respectively.

  • Ideas for quicksort 1 Very fast when most of the elements to be sorted are ordered. 2 In the worst case, it’s very slow. So the optimization of fast sorting, the benchmark is very important, for example, to be sorted is ordered, the benchmark is fixed in the middle, Xiao ‘lv 4 time complexity is Nlogn, unstable sort

  • When does Swift Save time import UIKit extension Array {var Element: (head: Element, tail: [Element])? { return (count > 0) ? (self[0], Array(self[1..<count])) : nil } }

    func qsortDemo(input: [Int]) -> [Int] { if let (pivot, Decompose (rest) = input.filter {let lesser = rest.filter {$0 < pivot}// Decompose into an array less than the pivot cardinals let greater = rest.filter {$0 Return qsortDemo(lesser) + [Pivot] + qsortDemo(greater)// Recursive join array} else {return []} } var a:[Int] = [1,2,4,6,2,4,3,7,8]Copy the code

/ / / method from http://blog.csdn.net/cg1991130/article/details/48274919

  • Swift version import UIKit

    func quickSort(inout a:[Int],l:Int,r:Int){ if l < r { var i = l, j = r ,x = a[i] while i < j && a[j] >= x{ j -= 1 } if i < j { a[i] = a[j] i += 1 } while i < j && a[i] < x { i += 1 } if  i < j { a[j] = a[i] j -= 1 } a[i] = x quickSort(&a, l: l, r: i-1) quickSort(&a, l: i+1, r: R)}} var b =,7,6,5,4,3,2,1 [8] quickSort (a & b, l: 0, r: 7) print (b)Copy the code

  • C version

#include <stdio.h>

Void quickSort(int a[],int l, int r){void quickSort(int a[],int l, int r){ X int I = l, j = r, X = a[I]; While (I < j) {// start the loop with the left less than the right. while (i < j && a[j] >= x) j--; if (i < j) a[i++] = a[j]; While (I < j&&a [I] < x) I ++; if (i < j) a[j--] = a[i]; } // return a[I] = x; QuickSort (a, l, i-1); // Right quickSort(a, I +1, r); }} int main() {int a[8] = {8,7,6,5,4,3,2,1}; quickSort(a, 0, 7); for (int i = 0; i < 8; i++) { printf("%d",a[i]); } printf("\n"); return 0; }Copy the code
  • ###### Look at me so cute n(≧ del ≦)n
  • Pay attention to my meager deskmate (beam) : http://weibo.com/tongrenyinsheng
  • Personal blog: http://www.liangtongzhuo.com
  • Ios personally written app (homophone) ASMR music