O（nlogn）排序算法之快速排序

1.选择数组中的一个元素

2.进行一次Partition,将数组分为小于该元素和大于该元素的两个部分

3.分别在两个部分中选取元素递归第1-2步至有序即可

---

• 核心操作Partition:

我们通常会使用整个数组的第一个元素v作为整个数组的分界点

其中:

指向数组分界点元素v的指针记为l(小写L);

大于v和小于v的分界线上的元素给个指针记为j;

正在判断的当前元素e的指针为i;

即:

arr[l+1, j] < v

arr[j +1,i -1] > v

此时判断e与v的大小:

若e > v,则 i++即可把e放入大于v的范围中

若e < v,则交换j+1与i所指元素的位置,然后j++,即可把e放入小于v的范围中

当所有排序结束后,只需要将l与j所指元素交换位置即可让分界点位于其应该在的位置

image.png image.png

---

//返回p, 使得arr[l...p - 1] < arr[p]; arr[p + 1...r] > arr[p]
template<typename T>
int __partition(T arr[], int l, int r){

    T v = arr[l];

    //arr[l + 1...j]<v; arr[j + 1...i)>v
    int j = l;
    for (int i = l + 1; i <= r; i++){
        if (arr[i] < v){
            swap(arr[j + 1], arr[i]);
            j++;
        }
    }

    swap(arr[j], arr[l]);

    return j;
}

• 未优化quicksort

template<typename T>
void __quickSort(T arr[], int l, int r){

    if (l > r)
        return;

    int p = __partition(arr, l, r);
    __quickSort(arr, l, p - 1);
    __quickSort(arr, p + 1, r);
}

---

• 优化1：随机选中一个元素作为数组的分界点
  发现问题：对近乎有序的数组进行排序时：
  n较大，quicksort出现stackoverflow。
  n较小，快速排序的时间远大于归并排序的时间。

int __partition(T arr[], int l, int r){

    int s = rand() % (r - l + 1) + l;
    swap(arr[l], arr[s]);
    T v = arr[l];

    //arr[l + 1...j]<v; arr[j + 1...i)>v
    int j = l;
    for (int i = l + 1; i <= r; i++){
        if (arr[i] < v){
            swap(arr[j + 1], arr[i]);
            j++;
        }
    }

    swap(arr[j], arr[l]);

    return j;
}

---

• 优化2：双路快速排序法
  问题分析:由于待排数组中出现大量重复元素,导致一旦分界点选择过大或过小,就会造成大规模的不平衡。
  甚至由于有大量重复元素,就算分界点选中了正中间的5,也有大量的5聚集在大于v的节点中（因为判断条件是arr[i]<v，才进行交换，等于v时，j++）,仍会导致分配不均的问题出现。

image.png
image.png
image.png

template<typename T>
int __partition2(T arr[], int l, int r){

    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];

    //arr[l+1...i)<=v;arr(j...r]>=v
    int i = l + 1, j = r;
    while (true){
        while (i <= r&&arr[i] < v) i++;
        while (j >= l + 1 && arr[j] > v) j--;
        if (i > j) break;
        swap(arr[i], arr[j]);
        i++;
        j--;
    }
    swap(arr[l], arr[j]);
    return j;
}

---

• 优化3：三路快速排序
  e<v

  
  image.png

image.png

lt++;
i++;

---

e>v

image.png
image.png

gt--;

---

处理完后

image.png
image.png

---

• while版

template<typename T>
void __quickSort3Ways(T arr[], int l, int r){

    if (r - l <= 15){
        insertionSort2(arr, l, r);
        return;
    }

    //partition
    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];
    
    int lt = l; //arr[l+1...lt]<v
    int gt = r + 1; //arr[gt..r]>v
    int i = l + 1; //arr[lt+1...i)=v
    while (i < gt){
        if (arr[i] < v){
            swap(arr[i], arr[lt + 1]);
            lt++;
            i++;
        }
        else if (arr[i] > v){
            swap(arr[i], arr[gt - 1]);
            gt--;
        }
        else{
            i++;
        }
    }
    swap(arr[l], arr[lt]);

    __quickSort3Ways(arr, l, lt - 1);
    __quickSort3Ways(arr, gt, r);
}

---

• 自己写的for版

template<typename T>
void __quickSort3Ways(T arr[], int l, int r){

    if (r - l <= 15){
        insertionSort2(arr, l, r);
        return;
    }

    //partition
    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];
    
    int lt = l; //arr[l+1...lt]<v
    int gt = r + 1; //arr[gt..r]>v
    int i = l + 1; //arr[lt+1...i)=v
    for (int i = l + 1; i < gt; i++){
        
        if (arr[i] < v){
            swap(arr[i], arr[lt + 1]);
            lt++;
        }
        else if (arr[i] > v){
            swap(arr[i], arr[gt - 1]);
            gt--;
            --i;
        }   
    }
    swap(arr[l], arr[lt]);

    __quickSort3Ways(arr, l, lt - 1);
    __quickSort3Ways(arr, gt, r);
}