概念

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

首先需明确以下几个概念：

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

插入排序

直接插入排序是一种简单的插入排序法，其是基本思想：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

实际中我们玩扑克牌时，就用了插入排序的思想，在排序自己手中的扑克牌时经常会这样排。

直接插入排序

当插入第i(i >= 1)个元素时，前面的array[0], array[1], …, array[i-1]已经排好序，此时用array[i]的排序码与array[i-1], array[i-2], …的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

void insertSort(vector<int> &arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        //以end所在位置的前面所有元素已有序
        int end = i;
        //单趟排序
        int tmp = arr[end + 1]; //暂存要插入的元素
        while (end >= 0) {
            if (arr[end] > tmp)
            {
                arr[end + 1] = arr[end]; //移开，腾位置
                end--;
            }
            else break;
        }
        arr[end + 1] = tmp;
    }
}

总结：

☑ 原始集合越接近有序，直接插入排序算法的时间效率越高

☑ 时间复杂度：O(n^2)

☑ 空间复杂度：O(1)

☑ 稳定性：稳定

希尔排序 (缩小增量排序)

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成多个组，所有距离为**gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取不同的gap**，重复上述分组和排序的工作。

gap > 1时在做预排序，当到达gap = 1时相当于做直接插入排序，所有记录再统一组内排好序。

希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

在此我们选择增量 gap = length / 2，缩小增量以 gap = gap / 2 的方式，用序列 {n / 2, (n / 2) / 2，…，1} 来表示。

如图示例：

void shellSort(vector<int> &arr) {
    int n = arr.size();
    int gap = n;
    while (gap > 1) {
        // gap > 1        预排序
        //最后一次gap = 1 直接插入排序
        gap = gap / 2;
        for (int i = 0; i < n - gap; i++) {
            int end = i;
            int tmp = arr[end + gap];
            while (end >= 0) {
                if (arr[end] > tmp) {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else break;
            }
            arr[end + gap] = tmp;
        }
    }
}

总结：

☑ 希尔排序是对直接插入排序的优化。
☑ 当gap>1时都是预排序，目的是让数组更快接近于有序（跳的快）
当gap == 1时（相当于直接插入排序），数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序
的时间复杂度都不固定：
举个🌰：Knuth在所著的《计算机程序设计技巧》第三卷中，利用大量的实验统计资料得出，当n很大时，关键码平均比较次数和对象平均移动次数大概在范围n^1.25到1.6 * n^1.25范围内，这是利用直接插入排序作为子序列排序方法的情况下得到的。
因为咱们的gap是按照Knuth提出的方式取值的，而Knuth进行了大量的试验统计，我们暂时就按照：O(n^1.25)到O(1.6 * n^1.25)来算。
☑ 稳定性：不稳定(相同的数据可能被分到不同的gap组)

选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

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

总结：
☑ 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
☑ 时间复杂度：O(n^2)
☑ 空间复杂度：O(1)
☑ 稳定性：不稳定

冒泡排序

依次比较两个相邻的元素，如果顺序不符合要求，就交换位置。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。”

在这里我们加一个flag来判断待排序数列是否已经有序（不交换就是已经有序了），这样的一定程度上提高效率。

void bubbleSort(vector<int> &arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        bool flag = true;
        //单趟
        for (int j = 1; j < n - i; j++) {
            if (arr[j - 1] > arr[j]) {
                flag = false;
                swap(arr[j - 1], arr[j]);
            }
        }
        if (flag) break; //已经有序了
    }
}

总结：
☑ 冒泡排序是一种非常容易理解的排序
☑ 时间复杂度：O(n^2)
☑ 空间复杂度：O(1)
☑ 稳定性：稳定

快速排序

快速排序是由Hoare所发展的一种排序算法。快速排序使用分治法（Divide and conquer）策略。基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

在平均状况下，排序 n 个元素要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n^2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

基本实现

采用当前最左侧的元素为划分枢纽，递归法：

int partition(vector<int>& arr, int l, int r) {
    int tmp = arr[l]; //选取最左侧元素为枢纽
    while(l < r) {
        while(l < r && arr[r] >= tmp) r--;
        arr[l] = arr[r];
        while(l < r && arr[l] <= tmp) l++;
        arr[r] = arr[l];
    }
    arr[l] = tmp;
    return l;
}
void quickSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int mid = partition(arr, l, r);
        quickSort(arr, l, mid - 1);
        quickSort(arr, mid + 1, r);
    }
}

单个函数实现快排：

void quickSort(vector<int> &arr, int l, int r) {
    // 子数组长度为 1 时终止递归
    if (l >= r) return;
    // 哨兵划分操作（以 arr[l] 作为基准数）
    int i = l, j = r;
    while (i < j) {
        //顺序不能乱
        while (i < j && arr[j] >= arr[l]) j--;
        while (i < j && arr[i] <= arr[l]) i++;
        swap(arr[i], arr[j]);
    }
    swap(arr[i], arr[l]);
    // 递归左（右）子数组执行哨兵划分
    quickSort(arr, l, i - 1);
    quickSort(arr, i + 1, r);
}

总结：

☑ 可快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
☑ 时间复杂度：O(nlogn)
☑ 空间复杂度：O(logn)~O(n) (最坏情况每次key都取到最大或最小，要递归n层)
☑ 稳定性：不稳定(选key, 三数取中，很多因素使它不稳定)

快排的优化

枢纽值选取

partition如果每次选出的key都是最小或最大的会使效率大大降低。例如：1 2 3 4 5 6 这种已经顺序了的，取最左或者最右都会很慢，于是我们想到能否选出一个不是最大也不是最小的数做key。

随机选取法

int partition(vector<int>& arr, int l, int r) {
    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    ......
}

三数取中法

最左，最右，中间三个位置的数进行比较，选出中等大小的那个做key

//选出中等大小数的下标
int getMidIndex(vector<int> &arr, int left, int right) {
    int mid = left + ((right - left) >> 1);
    if (arr[left] < arr[mid]) {
        if (arr[mid] < arr[right]) return mid;
        else if (arr[left] < arr[right]) return right;
        else return left;
    }
    else {
        if (arr[right] > arr[left]) return left;
        else if (arr[mid] > arr[right]) return mid;
        else return right;
    }
}
int partition(vector<int> &arr, int l, int r) {
    // swap(arr[l], arr[rand() % (r - l + 1) + l]);
    //三数取中
    int m = getMidIndex(arr, l, r);
    swap(arr[m], arr[l]);
    ......
 }

改变小区间排序方式

快排的结构是类似于二叉树的，二叉树最后几层的数是最多的，排序难度也很低，是否能够不递归到最小区间，中途就运用另一种排序方法返回有序数组给上一层来优化呢？当然是可以的

小区间优化：递归到小的子区间时，可以考虑使用插入排序，减少递归调用

void insertSort(vector<int> &arr, int l, int r) {
    for (int i = l; i < r; ++i) {
        //以end所在位置的前面所有元素已有序
        int end = i;
        //单趟排序
        int tmp = arr[end + 1]; //暂存要插入的元素
        while (end >= 0) {
            if (arr[end] > tmp)
            {
                arr[end + 1] = arr[end]; //移开，腾位置
                end--;
            }
            else break;
        }
        arr[end + 1] = tmp;
    }
}

int partition(vector<int>& arr, int l, int r) {
    ......
}

//加小区间优化
void quickSort(vector<int>& arr, int l, int r) {
    // 子区间相等只有一个值或者不存在那么就是递归结束的子问题
    if (l >= r) return;
    if (r - l + 1 <= 3) insertSort(arr, l, r); //13为小区间门槛值
    else {
        int mid = partition(arr, l, r);
        quickSort(arr, l, mid - 1);
        quickSort(arr, mid + 1, r);
    }
}

非递归实现快排

需要用栈实现

int partition(vector<int>& arr, int l, int r) {
    ......
}

//非递归
void quickSort(vector<int>& arr, int begin, int end) {
    stack<int> stk;
    stk.emplace(begin);
    stk.emplace(end);

    //右边处理完了再处理左边
    while (!stk.empty()) {
        int right = stk.top();
        stk.pop();
        int left = stk.top();
        stk.pop();

        int key = partition(arr, left, right);
        if (left < key - 1) {
            stk.emplace(left);
            stk.emplace(key - 1);
        }
        if (key + 1 < right) {
            stk.emplace(key + 1);
            stk.emplace(right);
        }
    }
}

基于快排思想实现TopK

#include<bits/stdc++.h>
using namespace std;
//快速排序划分函数
int Partition(vector<int>& nums, int low, int high, int k){
    swap(nums[low], nums[rand() % (high - low + 1) + low]);//随机化枢纽

    int pivort = nums[low]; //取第一个元素作为枢轴元素
    int low_tmp = low; //保存low当前下标
    int high_tmp = high; //保存high当前下标
    while(low < high){
        while(low < high && nums[high] <= pivort) high--; //枢轴元素右边全放小的
        nums[low] = nums[high]; //大的放到左边
        while(low < high && nums[low] >= pivort) low++;   //枢轴元素左边全放大的
        nums[high] = nums[low]; //小的放到右边
    }
    //当low和high相等时，说明已经排好了，把枢轴元素放好
    nums[low] = pivort;
        
    //判断枢轴元素是否是第k个最大的元素
    if(low == k-1){
        return nums[low];
    }
    else if(low > k-1){ //如果当前枢轴元素索引比k-1大，说明要在左边找
        return Partition(nums, low_tmp, low-1, k);
    }
    else{ //如果当前枢轴元素索引比k-1小，说明要在右边找
        return Partition(nums, low + 1, high_tmp, k);
    }

}
int findKthLargest(vector<int>& nums, int k) {
    return Partition(nums, 0, nums.size()-1, k); //递归划分查找
}

int main() {
    vector<int> arr = {3,2,3,1,2,4,5,5,6};
    int k = 4;
    cout<<findKthLargest(arr, k);
    return 0;
}

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法，是选择排序的一种。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

步骤（以大顶堆为例）：

建堆过程：将数组看成一个假想的完全二叉树，从第一个非叶子节点开始往上操作，每次操作的内容是保证当前节点是自己和左右节点中的最大值，不是则进行交换达成这个目标，继续往下进行这个下沉操作直到叶子节点为止，这样第一次建树后肯定是根节点最大
排序过程：将根节点换到数组的最后面去，然后需要排序的数组长度-1。之后就是从根节点开始进行下沉操作让根节点最大了，建树的时间复杂度为看起来N/2 * logN，实际计算出来时O(N)

如果按照从最后一个非叶子节点开始往上操作的话复杂度就是N，每次调整堆的复杂度为logn

实现

#include<bits/stdc++.h>
using namespace std;
void heapify(vector<int>& nums, int m, int len){
        int maxIdx = m;
        int left = 2 * m + 1;
        int right = 2  * m + 2;
        if(left < len && nums[left] > nums[maxIdx]) maxIdx = left;
        if(right < len && nums[right] > nums[maxIdx]) maxIdx = right;
        if(maxIdx != m){
            swap(nums[m], nums[maxIdx]);
            heapify(nums, maxIdx, len);
        }
}
void heapSort(vector<int>& arr) {
    int len = arr.size();
    //建堆
    for(int i = len / 2; i >= 0; --i){
        heapify(arr, i, len);
    }
    //排序
    while(len > 1){
        swap(arr[0] , arr[len - 1]);
        len--;
        heapify(arr, 0, len);
    }
}
int main() {
    vector<int> arr = {8,5,4,7,6,9,3,2,1};
    heapSort(arr);
    for_each(arr.begin(), arr.end(), [](int x){cout<<x<<' ';});
    return 0;
}

总结：
☑ 堆排序使用堆来选数，效率就高了很多。
☑ 时间复杂度：O(nlogn)
☑ 空间复杂度：O(1)
☑ 稳定性：不稳定

建堆时间复杂度分析

堆排序主要分建堆和调整两个操作，我们先分别来分析两个阶段的时间复杂度

筛选法建堆

筛选法最好时间复杂度：当按顺序生成的完全二叉树就满足堆的要求的时候，那么步骤(2) 中每个节点只需要进行两次比较(一次为左右孩子比较，第二次是与最大的孩子节点进行比较),所以最好时间复杂度为 O(n)

筛选法最坏时间复杂度：当每次检查都需要交换并且一直检查到叶子节点时：第k层节点最多需要向下移动h-k次，h为堆高，由二叉树的性质可知，第k层最多有2^(k-1)个节点，

所以筛选法建堆的最坏时间复杂度至少为O(n)量级。

归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

void mergeSort(vector<int>& arr, int  l, int r) {
    if (l  >= r) return;
    int mid = l + ((r - l)>>1);
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    // 将两段排序合并
    int  k = 0, i = l, j = mid + 1;
    vector<int> tmp(r - l + 1);
    while (i <= mid && j <= r) {
        tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= r) tmp[k++] = arr[j++];
    // 复制回来原数组
    for (int i = 0; i < tmp.size(); ++i) arr[l + i] = tmp[i];
}

总结：
☑ 归并的缺点在于需要O(n)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
☑ 时间复杂度：O(nlogn)
☑ 空间复杂度：O(n)
☑ 稳定性：稳定

非递归实现归并排序

void mergeSort(vector<int>& arr, int  l, int r) {
    vector<int> tmp(r - l + 1);
    int gap = 1;
    int n = r - l + 1;
    while (gap < n) {
        //间距为gap为一组，两两归并
        for (int i = 0; i < n; i += 2 * gap) {
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            //只有end1越界，直接修正
            if (end1 >= n) end1 = n - 1;
            // begin2不存在，第二个区间不存在,修正成一个不存在的区间
            if (begin2 >= n) {
                begin2 = n;
                end2 = n - 1;
            }
            // begin2没事end2越界，修正end2
            if (end2 >= n) end2 = n - 1;
            
            // 将两段排序合并
            int index = i;
            while (begin1 <= end1 && begin2 <= end2) {
                tmp[index++] = arr[begin1] <= arr[begin2] ? arr[begin1++] : arr[begin2++];
            }
            while (begin1 <= end1) tmp[index++] = arr[begin1++];
            while (begin2 <= end2) tmp[index++] = arr[begin2++];
        }
        // 复制回来原数组
        for (int i = 0; i < tmp.size(); ++i) arr[l + i] = tmp[i];

        gap *= 2;
    }
}

以上排序算法都是基于元素比较的排序算法。接下来介绍的计数排序、基数排序、桶排序都是非比较排序算法。

计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

操作步骤：

统计相同元素出现次数
根据统计的结果将序列回收到原来的序列中

//适用于范围集中的数，排负数也行
void countSort(vector<int>& arr) {
    int n = arr.size();
    int minElem = *min_element(arr.begin(), arr.end());
    int maxElem = *max_element(arr.begin(), arr.end());
    
    int range = maxElem - minElem + 1;
    vector<int> cnt(range);

    for (int i = 0; i < n; i++) {
        cnt[arr[i] - minElem]++;
    }

    int index = 0;
    for (int i = 0; i < range; i++) {
        while (cnt[i]--) {
            arr[index++] = i + minElem;
        }
    }
}

总结：
☑ 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限，浮点数就没法排，
☑ 时间复杂度：O(max(n, range)
☑ 空间复杂度：O(range)
☑ 稳定性：稳定

桶排序（箱排序）

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

操作步骤

设置一个定量的数组当作空桶；
每个桶存放该区间的数据，由于每个桶内的数据元素个数不确定，可以使用链表表示，同时使用插入排序，让每个桶的链表有序。
这样按照次序将所有桶的元素连起来就得到完整的有序列表。

void insert(list<int>& bucket, int val) {
    auto iter = bucket.begin();
    while (iter != bucket.end() && val >= *iter)
        ++iter;
    // insert会在iter之前插入数据，这样可以稳定排序
    bucket.insert(iter, val);
}

void bucketSort(vector<int> &arr) {
    int len = arr.size();
    if (len <= 1) return;

    int minElem = *min_element(arr.begin(), arr.end());
    int maxElem = *max_element(arr.begin(), arr.end());

    int k = 10; // k为数字之间的间隔

    //向上取整，例如[0,9]有10个数，(9 - 0)/k + 1 = 1;
    int bucketsNum = (maxElem - minElem) / k + 1;

    vector<list<int>> buckets(bucketsNum);
    for (int i = 0; i < len; ++i) {
        int value = arr[i];
        //(value-min)/k就是在哪个桶里面
        insert(buckets[(value - minElem) / k], value);
    }

    int index = 0;
    for (int i = 0; i < bucketsNum; ++i) {
        if (!buckets[i].empty()) {
            for (auto &value : buckets[i])
                arr[index++] = value;
        }
    }
}

理论上来讲，桶的数量越多，时间复杂度就越低，当然空间复杂度就越高。而且和计数排序很相似，如果桶的数量是 max - min + 1，这个时候，桶排序和计数排序几乎就是一样的。

总结：
时间复杂度：O(range+n)
空间复杂度：O(range+n)
稳定性：稳定

性能分析

你可能会有一个疑问：每个桶内再用其他的排序算法进行排序（比如快排）,这样子时间复杂度不还是O(nlogn)吗？

如果要排序的数据有n个，我们把它们分在m个桶中，这样每个桶里的数据就是k = n / m。每个桶内排序的时间复杂度就为O(k*logk)。m个桶就是m * O(k * logk)=m * O((n / m)*log(n / m))=O(nlog(n / m))。当桶的个数m接近数据个数n时，log（n/m）就是一个较小的常数，所以时间复杂度接近O(n)。

应用场景：

看了上面的分析，既然桶排序时间复杂度为线性，是不是就能替代例如快排、归并这种时间复杂度为O(nlogn)的排序算法呢？

答案是否定的，桶排序的应用场景十分严苛，首先，数据应该分布比较均匀。讲一种较坏的情况，如果数据全部都被分到一个桶里，那么桶排序的时间复杂度是不是就退化到O(nlogn)了呢？其次，要排序的数据应该很容易分成m个桶，每个桶也应该有大小顺序。

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

步骤：

按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

实现

//求最大位数
int maxBit(vector<int>& arr) {
    int n = arr.size();
    int maxElem = *max_element(arr.begin(), arr.end());

    int res = 1;
    while (maxElem >= 10) {
        maxElem /= 10;
        res++;
    }
    return res;
}

void radixSort(vector<int> &arr) {
    int n = arr.size();
    int k = maxBit(arr);
    int curRadix = 1;
    vector<int> tmp(n);

    while (k--) {
        int bucket[10] = {0};

        //统计每个桶的数据个数
        for (int i = 0; i < n; i++) {
            bucket[arr[i] / curRadix % 10]++;
        }

        //累加
        for (int i = 1; i < 10; i++) {
            bucket[i] += bucket[i - 1];
        }

        //向tmp数组存入数据
        for (int i = n - 1; i >= 0; i--) {
            tmp[bucket[arr[i] / curRadix % 10] - 1] = arr[i];
            bucket[arr[i] / curRadix % 10]--;
        }

        //将tmp序列拷贝到原数组中
        copy(tmp.begin(), tmp.end(), arr.begin());

        curRadix *= 10;
    }
}

总结：
☑ 时间复杂度：O(range * n)
☑ 空间复杂度：O(range+n)
☑ 稳定性：稳定。

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；

排序算法总结

其他

swap操作–利用异或运算

void swap(int& a, int& b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

注意：a, b所处的地址不同才可以，否则会变成零！双重for循环操作数组时，i与j不能相等否则犯错！

实际应用快排与堆排选择

相同的数据规模，快速排序比堆排序的效率高很多，并且随着数据规模的扩大，二者的差距不断扩大，快速排序的优势越来越明显。快速排序的时间复杂度近似线性增长，堆排序则要大很多。究其原因，应该有以下几个方面：

在堆排序（小根堆）的时候，每次总是将最小的元素移除，然后将最后的元素放到堆顶，再让其自我调整。这样一来，有很多比较将是被浪费的，因为被拿到堆顶的那个元素几乎肯定是很大的，而靠近堆顶的元素又几乎肯定是很小的，最后一个元素能留在堆顶的可能性微乎其微，最后一个元素很有可能最终再被移动到底部。在堆排序里面有大量这种近乎无效的比较。随着数据规模的增长，比较的开销最差情况应该在（线性*对数）级别，如果数据量是原来的10倍，那么用于比较的时间开销可能是原来的10log10倍。
堆排序的过程中，需要有效的随机存取。比较父节点和字节点的值大小的时候，虽然计算下标会很快完成，但是在大规模的数据中对数组指针寻址也需要一定的时间。而快速排序只需要将数组指针移动到相邻的区域即可。在堆排序中，会大量的随机存取数据；而在快速排序中，只会大量的顺序存取数据。随着数据规模的扩大，这方面的差距会明显增大。在这方面的时间开销来说，快速排序只会线性增长，而堆排序增加幅度很大，会远远大于线性。
在快速排序中，每次数据移动都意味着该数据距离它正确的位置越来越近，而在堆排序中，类似将堆尾部的数据移到堆顶这样的操作只会使相应的数据远离它正确的位置，后续必然有一些操作再将其移动，即“做了好多无用功”。

zmqNut

经典排序算法

概念