前言

本帖子只是用来将看起来舒服的排序帖子整理到一起，加上自己的理解，起到加深记忆的作用

快速排序

这里给出了一种较为好理解的方法

问题

• Q：为什么要右边的指针先于左边指针移动？
  A：在while循环外会进行一次交换，以升序排序为例，如果先移动左边指针，会导致最后一次交换是将大于pivot的值放到最前面

• Q：平均复杂度？最坏情况以及复杂度？如何避免最坏复杂度？
  A：平均复杂度，这里用树给出了很好的解释，连同最坏情况一起解释了；最坏情况是已经排过序的数列，最坏复杂度为

• 讲的头头是道，能写代码吗？

#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;

void showVector(vector<int> v) {
    for (int x = 0; x < v.size(); x++)
        cout << v[x] << endl;
}

void showVector(vector<int> v, int start, int end) {
    for (int x = start; x <= end; x++)
        cout << v[x] << endl;
}

void quickSort(vector<int> &v, int start, int end) {
    if (start >= end) return;
    // O(n) get median
    // try min-max heap (https://wiki.jikexueyuan.com/project/for-offer/question-sixty-four.html)
    int s = 0;
    for (int i = start; i <= end; i++) {
        s += v[i];
    }
    s = s / (end - start + 1);
    cout << "average = " << s << endl;
    int pivot = start, d = abs(v[start] - s);
    for (int i = start + 1; i <= end; i++) {
        //cout << "d = " << abs(v[i] - s) << endl;
        if (abs(v[i] - s) < d) {
            d = abs(v[i] - s);
            pivot = i;
        }        
    }
    cout << "pivot = " << v[pivot] << endl; 
    swap(v[start], v[pivot]);
    // sort core codes
    int i = start, j = end;
    // move j first, otherwise the last swap will switch one big number to the first place
    while (i < j) {
        while(v[j] > v[start]) {
            j--;
        }
        if (i >= j) break;
        while(v[i] < v[start]) {
            i++;
        }
        if (i < j)
            swap(v[i], v[j]);
    }
    swap(v[start], v[j]);

    showVector(v, start, end);
    quickSort(v, start, j-1);
    quickSort(v, j+1, end);
}

int main(){
    //int x[] = {2,1,5,3,6,4};
    int x[] = {1,2,3,4,5,6};
    vector<int> v(x, x+6);
    quickSort(v, 0, v.size()-1);
    cout << "result" << endl;
    showVector(v);
    return 0;
}