快速排序

• 時間復雜度：平均、最好為O(nlogn),最壞為O(n^2)
• 空間復雜度：O(nlogn)
• 穩(wěn)定性：不穩(wěn)定

算法分析：

• 快速排序使用了分治思想來把一個數(shù)組分成兩個子數(shù)組（以數(shù)組為例）
• 快速排序從數(shù)組中選擇一個元素為基準（pivot）
• 把比基準大的元素放到基準右邊
• 把比基準小的放到基準左邊
• 這樣以基準為中心，就把原來的數(shù)組分成了兩個子序列
• 基準左邊大于基準的 和 基準右邊小于基準的交換位置（雙指針最快）
• 基準歸位
• 然后把基準分開的兩個子序列遞歸的重復上述步驟
• 最后整個數(shù)組排序完畢

動畫演示：(動畫來自五分鐘學算法，侵刪)

quickSort

C代碼

void quickSort(int arr[],int left,int right) {
    if (left > right) { return ; }
    int i,j,tmp,pivot;
    i = left;
    j = right;
    pivot = arr[left];
    while (i != j) {
        while (arr[j] >= pivot && i < j) {
            j--;
        }
        while (arr[i] <= pivot && i < j) {
            i++;
        }
        if (i < j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    //基準歸位
    arr[left] = arr[i];
    arr[i] = pivot;
    //遞歸
    quickSort(arr, left, i-1);
    quickSort(arr, i+1, right);
}

OC代碼

- (void)quickSort:(NSMutableArray *)arr left:(int)left right:(int)right {
    if (left > right) {
        return;
    }
    NSNumber *tmp = nil;
    int i = left;
    int j = right;
    NSNumber *pivot = arr[left];
    while (i != j) {
        while ([arr[j] intValue] >= pivot.intValue && i < j) {
            j--;
        }
        while ([arr[i] intValue] <= [pivot intValue] && i < j) {
            i++;
        }
        if (i < j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    arr[left] = arr[i];
    arr[i] = pivot;
    
    [self quickSort:arr left:left right:i-1];
    [self quickSort:arr left:i+1 right:right];
}

Swift代碼

func quickSort(arr: inout [Int],left:Int,right:Int) -> Void {
    if left > right { return }
    var i = left,j = right
    var pivot = arr[left],tmp = 0
    while i != j {
        while (arr[j] >= pivot && i < j) {
            j -= 1
        }
        while (arr[i] <= pivot && i < j) {
            i += 1
        }
        if i < j {
            tmp = arr[i];
            arr[i] = arr[j]
            arr[j] = tmp
        }
    }
    arr[left] = arr[i]
    arr[i] = pivot
    
    quickSort(arr: &arr, left: left, right: i-1)
    quickSort(arr: &arr, left: i+1, right: right)
}

以下代碼實現(xiàn)來源于網(wǎng)絡，未驗證

js代碼實現(xiàn)

function quick_sort(arr,from,to){
    var i = from; 
    var j = to; 
    var key = arr[from]; //標準值
    if(from >= to){ //如果數(shù)組只有一個元素
       return;
    }
    while(i < j){
        while(arr[j] > key && i < j){ //從右邊向左找第一個比key小的數(shù)，找到或者兩個哨兵相碰，跳出循環(huán)
            j--;
        }
        while(arr[i] <= key && i < j){  //從左邊向右找第一個比key大的數(shù)，找到或者兩個哨兵相碰，跳出循環(huán),這里的=號保證在本輪循環(huán)結(jié)束前，key的位置不變，否則的話跳出循環(huán)，交換i和from的位置的時候，from位置的上元素有可能不是key
            i++;
        }
        if(i < j){ //交換兩個元素的位置
            var temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    arr[from] = arr[i] //
    arr[i] = key;
    quick_sort(arr,from,i-1);
    quick_sort(arr,i+1,to);
}

Java實現(xiàn)

public static void sort(int[] a, int low, int high) {
    if(low>=high)
        return;
    int i = low;
    int j = high;
    int key = a[i];
    while (i < j) {
        while (i < j && a[j] >= key)
            j--;
        a[i++] = a[j];
    while (i < j && a[i] <= key)
            i++;
        a[j--] = a[i];
    }
    a[i] = key;
    sort(a,low,i-1);
    sort(a,i+1,high);
}

c++實現(xiàn)

 void QuickSort(int array[], int start, int last) {
    int i = start;
    int j = last;
    int temp = array[i];
    if (i < j)
    {
        while (i < j) {
            while (i < j &&  array[j]>=temp )
                j--;
            if (i < j) {
                 array[i] = array[j];
                 i++;
             }
            while (i < j && temp > array[i])
                 i++;
             if (i < j) {
                 array[j] = array[i];
                 j--;
             }
         }
         //把基準數(shù)放到i位置
         array[i] = temp;
         //遞歸方法
         QuickSort(array, start, i - 1);
         QuickSort(array, i + 1, last);
     }
 }

python實現(xiàn)

def quick_sort(array, left, right):
    if left >= right:
        return
    low = left
    high = right
    key = array[low]
    while left < right:
        while left < right and array[right] > key:
            right -= 1
        array[left] = array[right]
        while left < right and array[left] <= key:
            left += 1
        array[right] = array[left]
    array[right] = key
    quick_sort(array, low, left - 1)
    quick_sort(array, left + 1, high)

go實現(xiàn)

func quickSort(arr []int){
    arrLen := len(arr)
    if arrLen <= 1{
        return
    }

    randNum := getRandNum(arrLen -1)
    arr[randNum], arr[0] = arr[0],arr[randNum]
    mid := arr[0]//取出用于比較的元素

    head, tail := 0, arrLen -1

    for {
        for head <= tail && arr[head] < mid {
            head ++
        }
        for tail > head && arr[tail] > mid {
            tail --
        }
        if head > tail{
            break
        }
        swap(arr, head,tail)
        head++
        tail--
    }
    QSortTwoWay(arr[:head])
    QSortTwoWay(arr[head+1:])
}