面试的时候总是会问到一些排序算法相关的问题，之前都只是囫囵吞枣的看了一下，被问的时候根本打不出来什么。所以还是要好好学习一下常用的几种排序算法，写一下学习笔记。

性能比较

这里参考：https://www.jianshu.com/p/334df02eb10a

首先需要一个生成随机数组的函数。

vector<int> generateRandomVector(int n, int rangeL, int rangeR)
{
    assert(rangeL <= rangeR);
    vector<int> vec(n,0);
    srand(time(NULL));

    for (int i = 0; i < n; i++)
        vec[i] = rand() % (rangeR - rangeL + 1) + rangeL;
    return vec;
}

以及一个判断数组是否排序好的函数。

bool isSorted(vector<int>& vec){
    int n = vec.size();
    for (int i = 0; i < n-1; i++)
        if (vec[i] > vec[i+1])
            return false;
    
    return true;
}

测试排序函数能否正确排序以及返回所用时间。

double testSort(const string& sortName, void(*sortFunc)(vector<int>&), vector<int> vec){
    clock_t startTime = clock();
    sortFunc(vec);
    clock_t endTime = clock();

    assert(isSorted(vec));
    cout.setf(ios_base::fixed,ios_base::floatfield);
    cout << sortName << " - using time:" << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
    return double(endTime - startTime);
}

冒泡排序

冒泡排序是最经典和简单的排序算法之一，它不断的比较两个相邻数的大小，把大的数放到后头。这样经过一次遍历之后最大的数就到了数组的最后头，下一次遍历就将第二大的数放到了倒数第二的位置。不断重复知道完成排序。冒泡排序时间复杂度为O(n^2)，并且是稳定的排序算法，可以原地进行排序（需要O(1)的额外空间）。需要比较次数为O(n^2)，需要最多进行O(n^2)次的交换。实现代码：

void bubbleSort(vector<int>& vec){
    int n = vec.size();
    for (int i = 0; i < n - 1; i++){
        for (int j = 0; j < n - i - 1; j++){
            if (vec[j] > vec[j+1]){
                swap(vec[j],vec[j+1]);
            }
        }
    }
}

插入排序

插入排序的过程就像整理扑克牌一样，可以将整个数组分为已排序和未排序，然后从未排序的部分找出一个数，将它插入到已排序数组中合适的位置。在最坏情况下需要比较次数为O(n^2)，需要最多进行O(n^2)次的赋值。插入排序是稳定的排序算法之一。

但是当排序数据量很小（小于千级）或者元素大致按照顺序排列的时候，插入排序有较好的性能。

void insertSort(vector<int>& vec){
    int j = 0, cur = 0, n = vec.size();
    for (int i = 1; i < n; i++){
        cur = vec[i];
        j = i-1;
        while(j >= 0 && cur < vec[j]){
            vec[j+1] = vec[j];
            j--;
        }
        vec[j+1] = cur;
    }
}

快速排序

快速排序是一种不稳定的排序，一般情况下时间复杂度为O(nlogn)，不过最差情况需要O(n^2)，但是这种情况很少见。快速排序使用分治策略，挑选一个基准数，然后把小于基准的数放到前面，大于基准的数放到后面，最后递归的排序子数组。

首先是快速排序函数，我们需要一个分割函数来返回基准数的位置，然后递归的排序基准两边的数组：

void quickSorter(vector<int>& vec, int left, int right){
    if (left < right){
        int mid = partition(vec, left, right);
        quickSorter(vec, left, mid - 1);
        quickSorter(vec, mid + 1, right);
    }
}

然后就是分割函数，首先选取一个基准数，然后将小于基准的放到前面，大于基准的放到后面，并且返回这个基准的位置：

int partition(vector<int>& vec, int left, int right){
    int pivot = vec[right];
    int i = left - 1;
    for (int j = left; j < right; j++){
        if (vec[j] < pivot){
            i++;
            swap(vec[i],vec[j]);
        }
    }
    swap(vec[i+1],vec[right]);
    return i+1;
}

归并排序

归并排序时间复杂度为O(nlogn)，是一种稳定的排序算法。它也采用分治策略，将当前的序列平均分成两半，然后在保持元素顺序的的同时将两个数组合并切来。

void merge(vector<int>& vec, int front, int mid, int end){
    vector<int> leftSubVec(vec.begin(), vec.begin() + mid + 1);
    vector<int> rightSubVec(vec.begin() + mid + 1, vec.begin() + end + 1);
    int leftIndex = 0, rightIndex = 0;
    leftSubVec.insert(leftSubVec.end(), INT_MAX);
    rightSubVec.insert(rightSubVec.end(), INT_MAX);
    for (int i = front; i <= end; i++){
        if (leftSubVec[leftIndex] < rightSubVec[rightIndex]){
            vec[i] = leftSubVec[leftIndex];
            leftIndex++;
        }
        else{
            vec[i] = rightSubVec[rightIndex];
            rightIndex++;
        }
    }
}

void mergeSorter(vector<int>& vec, int front, int end){
    if (front >= end)
        return;
    int mid = front + (end - front) / 2;
    mergeSorter(vec, front, mid);
    mergeSorter(vec, mid + 1, end);
    merge(vec, front, mid, end);
}

堆排序

堆排序的时间复杂度为O(nlogn)，是一种不稳定的排序算法。
首先介绍几个概念：

完全二叉树(Complete Binary Tree)：一个完全二叉树是一个二叉树除了最后一层全部都是满的，并且最后一层的节点都尽可能的在左边。这意味着一个二叉树如果有k层，那么对于第i层(1<=i<k)它的节点个数为2^(k-1)。
二叉堆(Binary Heap)：二叉堆是一种特殊的堆，它是一个完全二叉树，并且满足一个特性 - 父节点的值总是保持固定的序关系于任何一个子节点的值，且每个节点的左子树和右子树都是一个二叉堆。如果父节点的值大于任何一个子节点的值就叫”最大堆“；如果是小于就叫“最小堆”

在堆排序中，我们使用数组来表示二叉堆，因为数组可以很方便的表示一个二叉堆。如果一个父节点的index是i，那么他的左子节点是2n+1，右子节点是2n+2。

堆排序的步骤如下：

创建一个堆H[0..n-1]
把堆首（最大值）和堆尾互换
把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
重复步骤2，直到堆的尺寸为1

void heapify(vector<int>& vec, int n, int i){
    int largest = i;
    int l = i * 2 + 1;
    int r = i * 2 + 2;

    if (l < n && vec[l] > vec[largest])
        largest = l;

    if (r < n && vec[r] > vec[largest])
        largest = r;
    
    if (largest != i){
        swap(vec[i], vec[largest]);
        heapify(vec, n, largest);
    }
}

void heapSort(vector<int>& vec){
    int n = vec.size();
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(vec, n, i);
    
    for (int i = n - 1; i > 0; i--){
        swap(vec[0],vec[i]);
        heapify(vec, i, 0);
    }
}