排序算法	平均时间复杂度	最坏/最好时间复杂度	空间复杂度	是否稳定
冒泡排序	$O(n^2)$	$O(n^2)$ / $O(n)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$ / $O(n^2)$	$O(1)$	不稳定
插入排序	$O(n^2)$	$O(n^2)$ / $O(n)$	$O(1)$	稳定
希尔排序	$O(nlogn)$	与步长 $d$ 有关 / $O(nlogn)$	$O(1)$	不稳定
快速排序	$O(nlogn)$	$O(n^2)$ / $O(nlogn)$	$O(logn) \sim O(n)$	不稳定
归并排序	$O(nlogn)$	$O(nlogn)$ / $O(nlogn)$	$O(n)$	稳定
堆排序	$O(nlogn)$	$O(nlogn)$ / $O(nlogn)$	$O(1)$	不稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	稳定
基数排序	$O(d\times (n+r))$	$O(d\times (n+r))$	$O(n+r)$	稳定
桶排序	$O(n+m)$	$O(n+m)$	$O(n)$	稳定

冒泡排序

从后往前, 相邻的数据两两比较, 一趟完成后, 第一个元素为最大/小值

时间复杂度: $O(n^2)$
最好情况: $O(n)$, 当某次遍历没有发生交换, 则说明已经有序
最坏情况: $O(n^2)$, 数组刚好是逆序
空间复杂度: $O(1)$
稳定性: 是稳定的, 主要就是 遇到相等的元素时不要进行交换操作 即可

void bubble_sort(vector<int> &input){
    for(int i=0; i<input.size(); i++){
        for(int bubble = input.size()-1; bubble>i; bubble--){
            if(input[bubble-1] < input[bubble] ){ //为了保证排序的稳定性, 这里不要用 <=
                int temp = input[bubble];
                input[bubble] = input[bubble-1];
                input[bubble-1] = temp;
            }
        }
    }
}

冒泡排序的改进: 鸡尾酒排序

冒泡排序是只在一个方向上进行排序, 鸡尾酒排序是从前往后和从后往前交替排序(即先找最大, 再找最小). 在面对大部分元素已经有序的数组时, 鸡尾酒排序的时间复杂度接近于 $O(n)$.

选择(交换)排序

初始时在序列中找到最小(大)元素, 放到序列的起始位置, 然后再从剩余的序列中继续寻找最小(大)元素, 并将其放到起始位置的下一个位置, 以此类推, 知道所有元素排序完毕.

时间复杂度: $O(n^2)$
最好情况: $O(n^2$, 复杂度与序列元素分布形式无关
最坏情况: $O(n^2$, 复杂度与序列元素分布形式无关
空间复杂度: $O(1)$
稳定性: 选择排序是不稳定的排序算法, 不稳定性发生在最小元素与 A[i] 交换的时刻. 因为选择排序在交换两个元素时, 是不考虑其他元素的相对位置的, 所以, 不管怎么样, 只要发生交换, 就一定会造成不稳定. 但是!!! 如果使用链表或者新开辟一个数组的话, 选择排序也是稳定的, 但实际上这种方法就没有交换的过程, 对于链表来说, 是把节点从链表中拿出来, 组成新的链表, 而不会对原来链表中的元素进行交换. 对于新开辟数组来说, 相当于是用空间换取稳定性, 同样也没有交换过程.

插入排序

将数据分为两个部分, 有序部分和无序部分, 一开始有序部分包含只包含第一个元素, 依次将无序部分的元素插入到有序部分 ( 插入的时间复杂度为 $O(n)$ ), 直到所有元素插入完毕.

插入分为数组插入和链表插入(其实堆排序也算是一种插入排序)

下面的时间和空间复杂度均指 数组直接插入, 对于链表, 时间和空间都是 $O(n)$

时间复杂度: $O(n^2)$
最好情况: $O(n)$, 对于已经有序的序列来说, 每一次插入的复杂度都是 $O(1)$, 共插入 $O(n)$ 次.
最坏情况: $O(n^2)$, 对于逆序的序列来说, 每一次插入的复杂度都是 $O(n)$, 共插入 $O(n)$ 次.
空间复杂度: $O(1)$
稳定性: 只要在插入遇到相等元素时, 将新插入的放在最后, 那么就是稳定的.

插入排序不适合对于数据量比较大的排序应用. 但是, 如果需要排序的数据量很小, 比如量级小于千, 那么插入排序还是一个不错的选择. 插入排序在工业级函数库中也有着广泛的应用, 在 STL 的 sort 算法和 stdlib 的 qsort 算法中, 都将插入排序作为快速排序的补充, 用于少量元素的排序(通常为8个或以下).

二分插入排序:
直接插入在查找插入位置时, 可以采用二分查找的方式(因为已经有序), 这样可以减少查找插入位置时花费的时间.

希尔排序

希尔排序(Shell Sort), 也叫 递减增量排序, 是插入排序中一种更高效的改进版本. 插入排序具有以下两点性质:

对于几乎已经排好序的数据操作时, 效率很高, 可以达到线性排序的效率;
插入排序在每次往前插入时只能将数据移动一位, 这使得效率较低.
因此, 希尔排序的思想是:
首先选取一个合适的步长(gap < n)作为间隔, 并将所有元素划分成 gap 个子序列, 每个子序列内部元素之间的距离都是 gap.
分别对每个子序列使用直接插入排序.
缩小步长 gap 的值, 重复上面的分组和插入排序过程, 直到 gap = 1 为止.

时间复杂度: $O(nlogn)$
最好情况: $O(n^{1.3})$, 实际中的时间复杂度与 gap 的值和序列元素的分布情况有关.
最坏情况: $O(n^2)$, 当 gap 的值为 1 时, 希尔排序就退化成了插入排序.
空间复杂度: $O(1)$
稳定性: 希尔排序是不稳定的算法, 因此对于相同的两个数, 可以由于分在不同的组中而导致它们的相对顺序发生变化. 比如序列：{ 3, 5, 10, 8, 7, 2, 8, 1, 20, 6 }, h=2时分成两个子序列 { 3, 10, 7, 8, 20 } 和 { 5, 8, 2, 1, 6 }, 未排序之前第二个子序列中的8在前面, 现在对两个子序列进行插入排序, 得到 { 3, 7, 8, 10, 20 } 和 { 1, 2, 5, 6, 8 }, 即 { 3, 1, 7, 2, 8, 5, 10, 6, 20, 8 }, 两个8的相对次序发生了改变.

快速排序

时间复杂度: $O(nlogn)$
最好情况: $O(nlogn)$, 每次选取的基准都是中位数, 这样每次都可以均匀的划分出两个分区, 只需要 $logn$ 次划分就能结束递归, 每次划分(Partition)的复杂度是 $O(n)$, 因此, 时间复杂度为 $O(nlogn)$.
最坏情况: $O(n^2)$, 每次选取的基准都是最大(小)元素, 导致只划分出了一个分区, 这样, 需要 $n-1$ 次划分才能结束递归.
空间复杂度: $O(logn)$, 主要是递归造成的栈空间的使用, 具体复杂度取决于递归的深度, 最坏情况下为 $O(n)$.
稳定性: 快速排序是不稳定的排序算法, 不稳定性发生在于基准元素交换的时刻. 快排在划分两边的元素时, 会直接交换某两个元素的位置, 并且这种交换与其他元素的值没有关系, 因此, 如果刚好有相同元素, 很容易就会破坏稳定性.

简单优化:
快排的期望时间复杂度为 $O(nlogn)$ , 最坏时间复杂度为 $O(n^2)$, 为了避免出现最坏的情况, 可进行如下改进:

哨兵元素的选择: 为了使每次划分的数不至于使两边相差过大, 我们可以选择三者取中法选择哨兵, 一般根据首尾元素和中间元素进行选择.
小数据量的改进: 递归的快排大概在n<13的时候比插入要慢, 所以我们在n<13的时候可以采用插入排序
相同数字的改进, 在存在大量相同数字的时候, 可以用两个指针保存相同数字的信息, 在划分时不用把它们算进去(这啥意思?//TODO)
递归的优化. 快排有两次递归调用, 我们可以用循环代替后面的一次递归.

空间复杂度: $logn$
对于就地快排来说, 它本身使用的空间是 $O(1)$ 的, 但是快排在 递归调用过程中, 就需要消耗一定的空间来保存哨兵及两端元素的下标, 而对于快排的非递归实现中, 需要借助两个栈来模拟系统对于数组low和high的存储情况(递归中的哨兵下标实际上会作为下一次递归的low或者high), :

最优的情况下空间复杂度为: $O(logn)$, 每一次都平分数组
最差的情况下空间复杂度为: $O(n)$, 每一次两边都极度失衡 (主要与进行迭代的次数有关, 迭代次数多了, 占用的内存就多了)

注意: 最好写出对输入的low和high进行越界检查的部分!! 这个有时候需要特别跟面试官提一声

递归实现:
要知道Partition内部使用<=的原因所在, 写成<, 会造成死循环(当遇到相等元素时, 会无限交换)

另外, 如果令 P=input[low] , 那么一定要 high--在前, 否则会造成元素覆盖

void quickSort(vector<int>& input, int low, int high){
    if(input.size()==0 || low<0 || low>=input.size() || high<0 || high>=input.size()){
        cout<<"error";
        exit(0);
    }
    int mid = Partition(input, low, high);
    if(mid<high)    quickSort(input, mid+1, high);
    if(mid>low)    quickSort(input, low, mid-1);
}

int Partition(vector<int>& input, int low, int high){
    int p = input[low];
    while(low<high){
      // 一定要high在前, 否则会造成数组元素覆盖, 回忆头条面试惨痛经历!
        while(low<high && p<=input[high]) high--; //这里注意, 如果忘了写=号, 就会陷入死循环
        input[low] = input[high];
        while(low<high && p>=input[low]) low++;
        input[high] = input[low];
    }
    input[low] = p;
    return low;
}

这里Partition用的是<=，那么在high位元素和p相等时，并不会执行交换，而是会high—, 如果忘了写等号, 就会陷入死循环。

非递归实现:

int partition(vector<int> &input, int low, int high){
    int P = input[low];
    while(low<high){
        while(low<high && P <= input[high]) high--;
        input[low] = input[high];
        while(low<high && P >= input[low]) low++;
        input[high] = input[low];
    }
    input[low] = P;
    return low;
}
void quick_sort(vector<int> &input, int low, int high){
    if(input.size()==0 || low<0 || low>=input.size() || high<0 || high>=input.size()){
        cout<<"error";
        exit(0);
    }
    stack<int> qs_stack;
    qs_stack.push(high); //入栈顺序一定要注意, 要与后面的操作对应好
    qs_stack.push(low);
    while(!qs_stack.empty()){
        low = qs_stack.top(); qs_stack.pop(); // low后入栈, 所以就应该先出栈
        high = qs_stack.top(); qs_stack.pop();
        if(low >= high) continue;
        int mid = partition(input, low, high);
        if(low<mid){
            qs_stack.push(mid-1);//入栈顺序一定要注意,
            qs_stack.push(low);
        }
        if(mid<high){
            qs_stack.push(high);//入栈顺序一定要注意,
            qs_stack.push(mid+1);
        }
    }
}

归并排序

核心思想是将两个有序数列进行合并，使其成为一个新的有序数列（时间复杂度为 $O(n)$ ）:

将序列没相邻的两个数组进行归并(merge)操作, 形成floor(n/2)个序列, 排序后每个序列包含两个元素
将上述序列在此归并, 形成floor(n/2)个序列, 每个序列包含四个元素
重复上述归并操作, 直到所有元素归并完毕

时间复杂度: $O(nlogn)$ 归并排序即使在最坏情况下, 时间复杂度也是 $O(nlogn)$, 这是它的一大优点.
最好情况: $O(nlogn)$
最好情况: $O(nlogn)$
空间复杂度: $(n)$, 需要借助临时数组(也可以不用), 同时, 递归也需要占用空间.
稳定性: 归并排序是稳定的排序算法, 在归并排序过程中, 相同元素有可能出现在同一组内或者不同组内, 如果在同一组内, 则默认就是稳定的, 如果在不同组内, 则根据组的前后位置来判断相同元素的顺序. 因此它是稳定的.

在合并时，由两种选择，一种是不使用额外空间的插入合并，这样会增加时间开销。另一种是使用额外空间的合并，这样不增加时间开销，但是需要额外空间。（当然，如果使用的是链表，则没有这种情况，可以既不增加时间，也不增加空间开销）

常规递归排序:

void mergesort(vector<int>& a,int first, int last){
  if(first<last){
    mid = (last+first)/2;
    mergesort(a, first, mid);
    mergesort(a, mid+1, last);
    mergeArray(a, first,mid,mid+1,last);
  }
}

void mergeArray(vector<int>& a, int first1,int last1,int first2,int last2){
  vector<int> temp;
  int i = first1;
  int j = first2;
  while(i<=last1 && j<=last2){
    if(a.at(i) < a.at(j)){
      temp.push_back(a.at(i));
      i++;
    }
    else{
      temp.push_back(a.at(j));
      j++;
    }      
  }
  while(i<=last1){
    temp.push_back(a.at(i));
    i++;
  }
  while(j<=last2){
    temp.push_back(a.at(j));
    j++;
  }
  for(int i = 0; i<temp.size(); i++)
    a.at(first1+i) = temp.at(i);
}

原地归并排, 不借助辅助数组

void swap_memory(vector<int> &data, int start1, int end1, int start2, int end2){
    std::reverse(data.begin()+start1, data.begin()+end1);
    std::reverse(data.begin()+start2, data.begin()+end2);
    std::reverse(data.begin()+start1, data.begin()+end2);
}

void merge_sort(vector<int> &data, int start, int end){
    int mid = (start+end)/2;
    if(start < end){
        merge_sort(data, start, mid);
        merge_sort(data, mid+1, end);
        merge_inplace(data, start, mid, mid+1, end);
    }

}

void merge_inplace(vector<int> &data, int start1, int end1, int start2, int end2){
    int i = start1;
    int j = start2;
    while(i<j && j<=end2){
        while(i<j && data[i] <= data[j]) i++;
        int index = j;
        while(i<j && data[j] <= data[i]) j++;
        swap_memory(data, i, index-1, index, j-1);

    }
}

堆排序

时间复杂度: $O(nlogn)$ 堆排序即使在最坏情况下, 时间复杂度也是 $O(nlogn)$, 这是它的一大优点. (完全二叉树)
最好情况: $O(nlogn)$
最坏情况: $O(nlogn)$
空间复杂度: $(1)$, 直接在数组上构建堆, 不需要借助临时数组
稳定性: 堆排序是不稳定的排序算法, 不稳定性发生在弹出堆顶元素, 进行对调整的时刻.

堆简介

堆排序与快速排序，归并排序一样都是时间复杂度为 $O(nlogn)$ 的几种常见排序方法

堆（二叉堆）可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。

如下图,是一个堆和数组的相互关系:

因此,对于给定的某个节点的下标i, 可以很容易计算出这个节点的父节点, 子节点的下标

Parent(i) = floor((i-1)/2)，i 的父节点下标
Left(i) = 2i + 1，i 的左子节点下标
Right(i) = 2(i + 1)，i 的右子节点下标

堆一般分为两种,大顶堆和小顶堆, 前者每个节点的值都大于它的子节点,后者反之

大顶堆:

小顶堆:

堆排序原理

堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：

最大堆调整（Max-Heapify）：将堆作调整，使得子节点永远小于父节点
创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

基于上面的三种操作,可以进行堆的插入和删除:

插入: 将新元素放置在数组末尾,然后进行堆调整
删除: 移除堆顶,然后将数组末尾元素置于堆顶,然后进行堆调整(删除主要用于排序)

最大堆调整（MAX‐HEAPIFY）的作用是保持最大堆的性质，是创建最大堆的核心子程序，作用过程如图所示：

代码实现:

// 递归实现
void max_heapify(vector<int> &vec, int index, int heap_size){
  int imax = index //mark max index
  int ileft = index*2+1; // left child
  int iright = index*2+2; // right child

  if (ileft < heap_size && vec[imax] < vec[ileft]){
    imax = ileft;
  }
  if(iright < heap_size && vec[imax] < vec[iright]){
    imax = iright;
  }
  if( imax != index){
    std::swap(vec[imax], vec[index]);
    max_heapify(vec, imax, heap_size); //由于变换了当前节点,因此子树的堆结构可能被破坏,
    //递归调整, 这里imax的坐标是左右子节点的下标之一(因为进行了交换)
  }
  // 堆是自下而上进行调整的,所以在调整当前节点符合堆要求之前,子树已经符合堆要求,
  //除非进行了节点交换,否则子树的堆结构不会被破坏, 无需进行额外处理
}

//非递归实现

void max_heapify(vector<int> &vec, int index, int heap_size){
  while(true){
    int imax = index;
    int ileft = 2*index+1;
    int iright = 2*index+2;
    if(ileft < heap_size && vec[imax] < vec[ileft]){
      imax = ileft;
    }
    if(iright < heap_size && vec[imax] < vec[iright]){
      imax = iright;
    }

    if( imax != index ){
      std::(vec[imax], vec[index]);
      index = imax; //产生了交换, 可能破坏了左右子树的堆结构, 令index为左右子树之一的下标, 继续调整
    }else{
      break; //如果没有交换，说明当前结构的堆结构已经完成，直接跳出
    }
  }
}

创建最大堆（Build-Max-Heap）的作用是将一个数组改造成一个最大堆，接受数组和堆大小两个参数，Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组，建立最大堆。因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质，所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。如果最大堆的数量元素是 n，那么 Build-Max-Heap 从 Parent(n) 开始，往上依次调用 Max-Heapify。

代码实现:

//创建堆
void build_maxheap(vector<int> &vec){
  int lasti_parent = std::floor((vec.size()-1)/2);

  for( int i = lasti_parent ; i>=0 ; i--){
    max_heapify(vec, i , vec.size()) //从下到上对每个节点进行堆调整，无需从叶子节点开始
    //堆的size需要传整个size过去,因为下标从针对整个堆而言的
  }
}

创建好堆以后,就可以通过移除堆顶来进行排序,每次将堆顶元素和数组末尾元素进行交换(这样可以不借助额外空间完成排序)，然后对数组的前n-1个元素重新进行堆调整构成新的大顶堆, 重复此过程知道堆中只剩下一个元素, 如下图所示:

//代码实现
void heap_sort(vector<int> &vec){
  build_maxheap(vec);
  for(int i = vec.size()-1 ; i > 0; i--){ //重复n-1次
    std::swap(vec[0] , vec[i]) //
    Heapify(vec, 0, i); //堆的大小变为i, 所以必须要设置一个变量来标识堆的size,而不是用vec.size()
  }
}

计数排序

计数排序是 非比较 排序算法, 适用于已知序列中的元素值在 $(0, k)$ 区间内的情况.(整数) 首先将每个元素出现的次数数出来, 然后算出该元素在最终有序序列中的绝对位置, 再依次将初始序列中元素, 根据确定的最终位置进行移动. 计算最终位置采用的思想是, 假设序列中小于元素 a 的个数为 x, 则可以直接将 a 放到第 x+1 位置上, 另外需要注意存在几个相同元素时要做适当调整, 不能将元素放在同一个位置上. 计数排序的步骤如下:

统计数组 A 中每个值 A[i] 出现的次数, 存入计数数组C[A[i]], 数组 C 的大小为 k;
从前向后, 使数组 C 中的每个值等于其和前一项的相加和, 这样, 数组 C[A[i]] 的含义就变成了代表数组 A 中 小于等于 A[i] 的元素个数.
从后往前填充排序数组 B: 将数组元素 A[i] 放在数组 B 的第 C[A[i]] 个位置(下标为 C[A[i]] - 1), 每放一个元素就将 C[A[i]] 递减(从后往前填充可保证对于相同元素的稳定性, 即位置相对靠后的元素在 B 中的位置也相对靠后).

时间复杂度: $O(n+k)$
最好情况: $O(n+k)$
最坏情况: $O(n+k)$
空间复杂度: $(n+k)$, 需要统计每个元素的个数, 同时在进行元素安放时, 也需要额外空间.
稳定性: 计数排序是稳定的排序算法, 因为在计算绝对位置的时候, 可以根据相同元素的前后关系决定绝对位置的前后.

基数排序

基数排序是 非比较 排序算法. 它首先将所有待比较正整数统一为同样的数位长度, 其中数位断的数前面补零. 然后, 从最低位开始进行基数为 10 的计数排序, 一直到最高位计数排序完后, 数列就变成了一个有序序列.

时间复杂度: $O(d\times (n+r))$, 其中, $d$ 代表位数, $r$ 代表基数, $n$ 代表是数组元素个数, 一趟分配的时间复杂度是 $O(n)$, 一趟收集的时间复杂度是 $O(r)$, 共进行 $d$ 趟分配和手机.
最好情况: $O(d\times (n+r))$
最坏情况: $O(d\times (n+r))$
空间复杂度: $(r+n)$
稳定性: 基数排序是稳定的排序算法, 因为它不需要比较数值的大小.

桶排序

桶排序是非比较排序算法. 工作原理是将数组分到有限数量的桶里, 然后每个桶的内部再分别排序(有可能使用别的排序算是或者以递归方式继续使用桶排序进行排序).

时间复杂度: $O(n+m)$, 其中 $n$ 为待排序的元素个数, $m$ 为桶的个数.
最好情况: $O(n+m)$
最坏情况: $O(n+m)$
空间复杂度: $(n)$ 所有桶内的元素个数之和为 n.
稳定性: 桶排序是稳定的排序算法, 因为它不需要比较数值的大小, 没有交换元素的相对位置.

桶排序适用于数据分布相对均匀或者数据跨度范围不大时使用, 否则, 会消耗大量的空间

应用:
(1). 一年的全国高考考生人数为500万，分数使用标准分，最低100 ，最高900 ，没有小数，要求对这500万元素的数组进行排序。
分析：对500W数据排序，如果基于比较的先进排序，平均比较次数为 $O(5000000*log5000000)≈1.112亿$。但是我们发现，这些数据都有特殊的条件： 100=<score<=900。那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。
方法：创建801(900-100)个桶。将每个考生的分数丢进 $f(score)=score-100$ 的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出，即可以得到一个有序的序列。而且可以很容易的得到100分有多少人，501分有多少人。
实际上，桶排序对数据的条件有特殊要求，如果上面的分数不是从100-900，而是从0-2亿，那么分配2亿个桶显然是不可能的。所以桶排序有其局限性，适合元素值集合并不大的情况

(2) 在一个文件中有10G个整数，乱序排列，要求找出中位数。内存限制为2G。只写出思路即可（内存限制为2G意思是可以使用2G空间来运行程序，而不考虑本机上其他软件内存占用情况。）关于中位数：数据排序后，位置在最中间的数值。即将数据分成两部分，一部分大于该数值，一部分小于该数值。中位数的位置：当样本数为奇数时，中位数=(N+1)/2 ; 当样本数为偶数时，中位数为N/2与1+N/2的均值（那么10G个数的中位数，就第5G大的数与第5G+1大的数的均值了）。
分析：既然要找中位数，很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法。
思想：将整型的每1byte作为一个关键字，也就是说一个整形可以拆成4个keys，而且最高位的keys越大，整数越大。如果高位keys相同，则比较次高位的keys。整个比较过程类似于字符串的字典序。
第一步:把10G整数每2G读入一次内存，然后一次遍历这536,870,912即（102410241024）*2 /4个数据。每个数据用位运算”>>”取出最高8位(31-24)。这8bits(0-255)最多表示256个桶，那么可以根据8bit的值来确定丢入第几个桶。最后把每个桶写入一个磁盘文件中，同时在内存中统计每个桶内数据的数量NUM[256]。
代价：(1) 10G数据依次读入内存的IO代价(这个是无法避免的，CPU不能直接在磁盘上运算)。(2)在内存中遍历536,870,912个数据，这是一个O(n)的线性时间复杂度。(3)把256个桶写回到256个磁盘文件空间中，这个代价是额外的，也就是多付出一倍的10G数据转移的时间。
第二步：根据内存中256个桶内的数量NUM[256]，计算中位数在第几个桶中。很显然，2,684,354,560个数中位数是第1,342,177,280个。假设前127个桶的数据量相加，发现少于1,342,177,280，把第128个桶数据量加上，大于1,342,177,280。说明，中位数必在磁盘的第128个桶中。而且在这个桶的第1,342,177,280-N(0-127)个数位上。N(0-127)表示前127个桶的数据量之和。然后把第128个文件中的整数读入内存。(若数据大致是均匀分布的，每个文件的大小估计在10G/256=40M左右，当然也不一定，但是超过2G的可能性很小)。注意，变态的情况下，这个需要读入的第128号文件仍然大于2G，那么整个读入仍然可以按照第一步分批来进行读取。
代价：(1)循环计算255个桶中的数据量累加，需要O(M)的代价，其中m<255。(2)读入一个大概80M左右文件大小的IO代价。
第三步：继续以内存中的某个桶内整数的次高8bit（他们的最高8bit是一样的）进行桶排序(23-16)。过程和第一步相同，也是256个桶。
第四步：一直下去，直到最低字节(7-0bit)的桶排序结束。我相信这个时候完全可以在内存中使用一次快排就可以了。
整个过程的时间复杂度在O(n)的线性级别上(没有任何循环嵌套)。但主要时间消耗在第一步的第二次内存-磁盘数据交换上，即10G数据分255个文件写回磁盘上。一般而言，如果第二步过后，内存可以容纳下存在中位数的某一个文件的话，直接快排就可以了（修改者注：我想，继续桶排序但不写回磁盘，效率会更高？）。