找工作知识储备(3)B---从头说12种排序算法：原理、图解、动画视频演示、代码以及笔试面试题目中的应用

作者：寒小阳时间：2013年9月。
出处：http://blog.csdn.net/han_xiaoyang/article/details/11596001。
声明：版权所有，转载请注明出处，谢谢。

七、快速排序

恩，重头戏开始了，快速排序是各种笔试面试最爱考的排序算法之一，且排序思想在很多算法题里面被广泛使用。是需要重点掌握的排序算法。

1）算法简介
快速排序是由东尼·霍尔所发展的一种排序算法。其基本思想是基本思想是， $\color{red}{通过一趟排序将待排记录分隔成独立的两部分}$ ， $\color{red}{其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序}$ ，以达到整个序列有序。

2）算法描述和分析
快速排序使用分治法来把一个串（list）分为两个子串行（sub-lists）。

步骤为：

$\color{blue}{1、从数列中挑出一个元素，称为 "基准"（pivot）}$ ，

$\color{blue}{2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）}$ 。 $\color{blue}{在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作}$ 。

$\color{blue}{3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序}$ 。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

算法伪代码描述：

function quicksort(q)

     var list less, pivotList, greater

     if length(q) ≤ 1 {

         return q

     } else {

         select a pivot value pivot from q

         for each x in q except the pivot element

             if x < pivot then add x to less

             if x ≥ pivot then add x to greater

         add pivot to pivotList

         return concatenate(quicksort(less), pivotList, quicksort(greater))

     }

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


最差时间复杂度	O(n^2)
最优时间复杂度	O(n log n)
平均时间复杂度	O(n log n)
最差空间复杂度	根据实现的方式不同而不同

3）算法图解、视频演示

图解：

快速排序会递归地进行很多轮，其中每一轮称之为快排的partition算法，即上述算法描述中的第2步，非常重要，且在各种笔试面试中用到该思想的算法题层出不穷，下图为第一轮的partition算法的一个示例。

视频 :舞动的排序算法

4）算法代码
事实上，这个地方需要提一下的是，快排有很多种版本。例如，我们“基准数”的选择方法不同就有不同的版本，但重要的是快排的思想，我们熟练掌握一种版本，在最后的笔试面试中也够用了，我这里罗列几种最有名的版本C代码。

1、版本一
我们选取数组的 $\color{red}{第一个元素作为主元}$ ，每一轮都是和第一个元素比较大小，通过交换，分成大于和小于它的前后两部分，再递归处理。

代码如下

/**************************************************
  函数功能：对数组快速排序                       
  函数参数：指向整型数组arr的首指针arr；          
            整型变量left和right左右边界的下标   
  函数返回值：空                                  
/**************************************************/
void QuickSort(int *arr, int left, int right)
{
  int i,j;
  if(left<right)
  {
    i=left;j=right;
    arr[0]=arr[i]; //准备以本次最左边的元素值为标准进行划分，先保存其值
    do
    {
      while(arr[j]>arr[0] && i<j) 
        j--;        //从右向左找第1个小于标准值的位置j
      if(i<j)                               //找到了，位置为j
      { 
        arr[i] = arr[j];
        i++;
      }           //将第j个元素置于左端并重置i
      while(arr[i]<arr[0] && i<j)
        i++;      //从左向右找第1个大于标准值的位置i
      if(i<j)                       //找到了，位置为i
      { 
        arr[j] = arr[i];
        j--;
      }           //将第i个元素置于右端并重置j
    }while(i!=j);
    arr[i] = arr[0];         //将标准值放入它的最终位置,本次划分结束
    quicksort(arr, left, i-1);     //对标准值左半部递归调用本函数
    quicksort(arr, i+1, right);    //对标准值右半部递归调用本函数
  }
}

2、版本二
$\color{red}{随机选基准数的快排}$

//使用引用，完成两数交换
void Swap(int& a , int& b)
{
 int temp = a;
 a = b;
 b = temp;
}
//取区间内随机数的函数
int Rand(int low, int high)
{
 int size = hgh - low + 1;
 return  low + rand()%size; 
}
    //快排的partition算法，这里的基准数是随机选取的
int RandPartition(int* data, int low , int high)
{    
 swap(data[rand(low,high)], data[low]);//
 int key = data[low];
 int i = low;
 
 for(int j=low+1; j<=high; j++)
 {
  if(data[j]<=key)
  {
   i = i+1;
   swap(data[i], data[j]);
  }            
 } 
 swap(data[i],data[low]);
 return i;
}
//递归完成快速排序
void QuickSort(int* data, int low, int high)
{
 if(low<high)
 {
  int k = RandPartition(data,low,high);
  QuickSort(data,low,k-1);
  QuickSort(data,k+1,high);
 }
}

5）考察点，重点和频度分析
完全考察快排算法本身的题目，多出现在选择填空，基本是关于时间空间复杂度的讨论，最好最坏的情形交换次数等等。倒是快排的partition算法需要特别注意！频度极高地被使用在各种算法大题中！详见下小节列举的面试小题。

6）笔试面试例题
这里要重点强调的是快排的partition算法，博主当年面试的时候就遇到过数道用该思路的算法题，举几道如下：

例题1、

$\color{red}{最小的k个数，输入n个整数，找出其中最下的k个数}$ ， $\color{red}{例如输入4、5、1、6、2、7、3、8、1、2，输出最下的4个数，则输出1、1、2、2}$ 。

当然，博主也知道这题可以建大小为k的大顶堆，然后用堆的方法解决。

但是这个题目可也以仿照快速排序，运用partition函数进行求解，不过我们完整的快速排序分割后要递归地对前后两段继续进行分割，而这里我们需要做的是 $\color{red}{判定分割的位置，然后再确定对前段还是后段进行分割，所以只对单侧分割即可}$ 。代码如下：

void GetLeastNumbers_by_partition(int* input, int n, int* output, int k)
{
    if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
        return;
    int start = 0;
    int end = n - 1;
    int index = Partition(input, n, start, end);
    while(index != k - 1)
    {
        if(index > k - 1)
        {
            end = index - 1;
            index = Partition(input, n, start, end);
        }
        else
        {
            start = index + 1;
            index = Partition(input, n, start, end);
        }
    }
    for(int i = 0; i < k; ++i)
        output[i] = input[i];
}

例题2、

$\color{red}{判断数组中出现超过一半的数字}$

当然，这道题很多人都见过，而且最通用的一种解法是数对对消的思路。这里只是再给大家提供一种思路，快排partition的方法在很多地方都能使用，比如这题。我们也可以选择合适的判定条件进行递归。代码如下：

bool g_bInputInvalid = false;
bool CheckInvalidArray(int* numbers, int length)
{
    g_bInputInvalid = false;
    if(numbers == NULL && length <= 0)
        g_bInputInvalid = true;
    return g_bInputInvalid;
}
bool CheckMoreThanHalf(int* numbers, int length, int number)
{
    int times = 0;
    for(int i = 0; i < length; ++i)
    {
        if(numbers[i] == number)
            times++;
    }
    bool isMoreThanHalf = true;
    if(times * 2 <= length)
    {
        g_bInputInvalid = true;
        isMoreThanHalf = false;
    }
    return isMoreThanHalf;
}
int MoreThanHalfNum_Solution1(int* numbers, int length)
{
    if(CheckInvalidArray(numbers, length))
        return 0;
    int middle = length >> 1;
    int start = 0;
    int end = length - 1;
    int index = Partition(numbers, length, start, end);
    while(index != middle)
    {
        if(index > middle)
        {
            end = index - 1;
            index = Partition(numbers, length, start, end);
        }
        else
        {
            start = index + 1;
            index = Partition(numbers, length, start, end);
        }
    }
    int result = numbers[middle];
    if(!CheckMoreThanHalf(numbers, length, result))
        result = 0;
    return result;
}

例题3、

$\color{red}{有一个由大小写组成的字符串，现在需要对他进行修改，将其中的所有小写字母排在大写字母的前面(不要求保持原顺序)}$

这题可能大家都能想到的方法是： $\color{blue}{设置首尾两个指针，首指针向后移动寻找大写字母，尾指针向前移动需找小写字母，找到后都停下，交换。之后继续移动，直至相遇}$ 。这种方法在这里我就不做讨论写代码了。

但是这题也可以采用类似快排的partition。这里使用从左往后扫描的方式。 $\color{blue}{字符串在调整的过程中可以分成两个部分：已排好的小写字母部分、待调整的剩余部分。用两个指针i和j}$ ， $\color{blue}{其中i指向待调整的剩余部分的第一个元素，用j指针遍历待调整的部分}$ 。 $\color{blue}{当j指向一个小写字母时，交换i和j所指的元素。向前移动i、j，直到字符串末尾}$ 。
代码如下：

#include <iostream>
using namespace std;
void Proc( char *str )
{
int i = 0;
int j = 0;
//移动指针i, 使其指向第一个大写字母
while( str[i] != '\0' && str[i] >= 'a' && str[i] <= 'z' ) i++;
if( str[i] != '\0' )
{
//指针j遍历未处理的部分，找到第一个小写字母
for( j=i; str[j] != '\0'; j++ )
{
if( str[j] >= 'a' && str[j] <= 'z' )
{
char tmp = str[i];
str[i] = str[j];
str[j] = tmp;
i++;
}
}
}
}
int main()
{
char data[] = "SONGjianGoodBest";
Proc( data );
return 0;
}

八、堆排序

不得不说，堆排序太容易出现了，选择填空问答算法大题都会出现。 $\color{blue}{建堆的过程，堆调整的过程，这些过程的时间复杂度，空间复杂度，以及如何应用在海量数据Top K问题}$ 中等等，都是需要重点掌握的。

1）算法简介
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

2）算法描述
我们这里介绍几个问题，一步步推到堆排序的算法。

$\color{red}{1、什么是堆？}$
我们这里提到的堆一般都指的是 $\color{blue}{二叉堆}$ ，它满足二个特性：

$\color{blue}{1---父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。}$

$\color{blue}{2---每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。}$

如下为一个最小堆(父结点的键值总是小于任何一个子节点的键值)

\color{red}{什么是堆调整(Heap Adjust)？}

这是为了保持堆的特性而做的一个操作。对某一个节点为根的子树做堆调整，其实就是

\color{blue}{将该根节点进行“下沉”操作(具体是通过和子节点交换完成的)，一直下沉到合适的位置，使得刚才的子树满足堆的性质。}

例如对最大堆的堆调整我们会这么做：

$\color{blue}{1、在对应的数组元素A[i], 左孩子A[LEFT(i)], 和右孩子A[RIGHT(i)]中找到最大的那一个，将其下标存储在largest中。

$\color{blue}{2、如果A[i]已经就是最大的元素，则程序直接结束。}$

$\color{blue}{3、否则，i的某个子结点为最大的元素，将A[largest]与A[i]交换。}$

$\color{blue}{4、再从交换的子节点开始，重复1,2,3步，直至叶子节点，算完成一次堆调整。}$

这里需要提一下的是， $\color{red}{一般做一次堆调整的时间复杂度为log(n)。}$

如下为我们对4为根节点的子树做一次堆调整的示意图，可帮我们理解。

\color{red}{3、如何建堆?}

\color{blue}{建堆是一个通过不断的堆调整，使得整个二叉树中的数满足堆性质的操作}

。在数组中的话，我们一般从下标为n/2的数开始做堆调整，一直到下标为0的数(因为下标大于n/2的数都是叶子节点，其子树已经满足堆的性质了)。下图为其一个图示：

很明显，对叶子结点来说，可以认为它已经是一个合法的堆了即20，60， 65， 4， 49都分别是一个合法的堆。只要从A[4]=50开始向下调整就可以了。然后再取A[3]=30，A[2] = 17，A[1] = 12，A[0] = 9分别作一次向下调整操作就可以了。

$\color{red}{4、如何进行堆排序?}$
堆排序是在上述3中对数组建堆的操作之后完成的。

$\color{blue}{数组储存成堆的形式之后，第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆}$ 。 $\color{blue}{第二次将A[0]与A[n-2]交换，再对A[0…n-3]重新恢复堆，重复这样的操作直到A[0]与A[1]交换}$ 。 $\color{blue}{由于每次都是将最小的数据并入到后面的有序区间}$ ，故操作完成后整个数组就有序了。

如下图所示：


最差时间复杂度	O(n log n)
最优时间复杂度	O(n log n)
平均时间复杂度	O(n log n)
最差空间复杂度	O(n)

3）算法图解、视频演示

图解：

略，见上一节。

视频: 堆排序

4）算法代码
直接上代码吧，重点注意HeapAdjust，BuildHeap和HeapSort的实现。

#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
 
int parent(int);
int left(int);
int right(int);
void HeapAdjust(int [], int, int);
void BuildHeap(int [], int);
void print(int [], int);
void HeapSort(int [], int);
 
/*返回父节点*/
int parent(int i)
{
    return (int)floor((i - 1) / 2);
}
 
/*返回左孩子节点*/
int left(int i)
{
    return (2 * i + 1);
}
 
/*返回右孩子节点*/
int right(int i)
{
    return (2 * i + 2);
}
 
/*对以某一节点为根的子树做堆调整(保证最大堆性质)*/
void HeapAdjust(int A[], int i, int heap_size)
{
    int l = left(i);
    int r = right(i);
    int largest;
    int temp;
    if(l < heap_size && A[l] > A[i])
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if(r < heap_size && A[r] > A[largest])
    {
        largest = r;
    }
    if(largest != i)
    {
        temp = A[i];
        A[i] = A[largest];
        A[largest] = temp;
        HeapAdjust(A, largest, heap_size);
    }
}
 
/*建立最大堆*/
void BuildHeap(int A[]，int heap_size)
{
    for(int i = (heap_size-2)/2; i >= 0; i--)
    {
        HeapAdjust(A, i, heap_size);
    }
}
 
/*输出结果*/
void print(int A[]， int heap_size)
{
    for(int i = 0; i < heap_size;i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
}
 
/*堆排序*/
void HeapSort(int A[], int heap_size)
{
    BuildHeap(A, heap_size);
    int temp;
    for(int i = heap_size - 1; i >= 0; i--)
    {
        temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        HeapAdjust(A, 0, i);
    }
    print(A, heap_size);
}
 
/*测试，对给定数组做堆排序*/
int main(int argc, char* argv[])
{
    const int heap_size = 13;
    int A[] = {19, 1, 10, 14, 16, 4, 7, 9, 3, 2, 8, 5, 11};
    HeapSort(A, heap_size);
    system("pause");
    return 0;
}

5）考察点，重点和频度分析
堆排序相关的考察太多了，选择填空问答算法大题都会出现。建堆的过程，堆调整的过程，这些过程的时间复杂度，空间复杂度，需要比较交换多少次，以及如何应用在海量数据Top K问题中等等。堆又是一种很好做调整的结构，在算法题里面使用频度很高。

6）笔试面试题

例题1、

$\color{red}{编写算法，从10亿个浮点数当中，选出其中最大的10000个}$ 。

典型的Top K问题，用堆是最典型的思路。建10000个数的小顶堆，然后将10亿个数依次读取，大于堆顶，则替换堆顶，做一次堆调整。结束之后，小顶堆中存放的数即为所求。代码如下(为了方便，这里直接使用了STL容器)：

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional> // for greater<>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
  vector<float> bigs(10000,0);
  vector<float>::iterator it;
  // Init vector data
  for (it = bigs.begin(); it != bigs.end(); it++)
  {
    *it = (float)rand()/7; // random values;
  }
  cout << bigs.size() << endl;
  make_heap(bigs.begin(),bigs.end(), greater<float>()); // The first one is the smallest one!
  float ff;
  for (int i = 0; i < 1000000000; i++)
  {
    ff = (float) rand() / 7;
    if (ff > bigs.front()) // replace the first one ?
    {
      // set the smallest one to the end!
      pop_heap(bigs.begin(), bigs.end(), greater<float>()); 
      // remove the last/smallest one
      bigs.pop_back(); 
      // add to the last one
      bigs.push_back(ff); 
      // mask heap again, the first one is still the smallest one
      push_heap(bigs.begin(),bigs.end(),greater<float>());
    }
  }
  // sort by ascent
  sort_heap(bigs.begin(), bigs.end(), greater<float>()); 
  return 0;
}

例题2、

$\color{red}{设计一个数据结构，其中包含两个函数，1.插入一个数字，2.获得中数。并估计时间复杂度}$ 。

$\color{blue}{使用大顶堆和小顶堆存储。}$

$\color{blue}{使用大顶堆存储较小的一半数字，使用小顶堆存储较大的一半数字。}$

$\color{blue}{插入数字时，在O(logn)时间内将该数字插入到对应的堆当中，并适当移动根节点以保持两个堆数字相等（或相差1）。}$

$\color{blue}{获取中数时，在O(1)时间内找到中数。}$

九、归并排序

1）算法简介
归并排序是建立在归并操作上的一种有效的排序算法。该算法是 $\color{red}{采用分治法（Divide and Conquer）的一个非常典型的应用}$ 。归并排序是一种稳定的排序方法。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

2）算法描述
归并排序具体算法描述如下(递归版本)：

$\color{blue}{1、Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。}$

$\color{blue}{2、Conquer: 对这两个子序列分别采用归并排序。}$

$\color{blue}{3、Combine: 将两个排序好的子序列合并成一个最终的排序序列。}$

归并排序的效率是比较高的，设数列长为N， $\color{red}{将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)}$ 。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。

3）算法图解、视频演示

图解：

视频：舞动的排序算法归并排序

4）算法代码

//将有二个有序数列a[first...mid]和a[mid...last]合并。
void MergeArray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid,   n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
//递归地完成归并排序
void MergeSort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp);    //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}

5）考察点、重点和频度分析
归并排序本身作为一种高效的排序算法，也是常会被问到的。尤其是归并排序体现的递归思路很重要，在递归的过程中可以完成很多事情，很多算法题也是使用的这个思路，可见下面7）部分的笔试面试算法题。

6）笔试面试题

例题1、

$\color{red}{题目输入一个数组，数组元素的大小在0->999.999.999的范围内，元素个数为0-500000范围}$ 。 $\color{red}{题目要求通过相邻的元素的交换，使得输入的数组变为有序，要求输出交换的次数}$

这题求解的其实就是一个逆序对。我们回想一下归并排序的过程：

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

$\color{blue}{分解：将n个元素分成个含n/2个元素的子序列。}$

$\color{blue}{解决：用合并排序法对两个子序列递归的排序。}$

$\color{blue}{合并：合并两个已排序的子序列已得到排序结果。}$

在归并排序算法中稍作修改，就可以在n log n的时间内求逆序对。

将数组A[1...size]，划分为A[1...mid] 和 A[mid+1...size].那么逆序对数的个数为 f(1, size) = f(1, mid) + f(mid+1, size) + s(1, mid, size)，这里s(1, mid, size)代表左值在[1---mid]中，右值在[mid+1, size]中的逆序对数。由于两个子序列本身都已经排序，所以查找起来非常方便。

代码如下：

#include<iostream>
#include<stdlib.h>
using namespace std;
void printArray(int arry[],int len)
{
    for(int i=0;i<len;i++)
        cout<<arry[i]<<" ";
    cout<<endl;
}
int MergeArray(int arry[],int start,int mid,int end,int temp[])//数组的归并操作
{
    //int leftLen=mid-start+1;//arry[start...mid]左半段长度
    //int rightLlen=end-mid;//arry[mid+1...end]右半段长度
    int i=mid;
    int j=end;
    int k=0;//临时数组末尾坐标
    int count=0;
    //设定两个指针ij分别指向两段有序数组的头元素，将小的那一个放入到临时数组中去。
    while(i>=start&&j>mid)
    {
        if(arry[i]>arry[j])
        {
            temp[k++]=arry[i--];//从临时数组的最后一个位置开始排序
            count+=j-mid;//因为arry[mid+1...j...end]是有序的，如果arry[i]>arry[j]，那么也大于arry[j]之前的元素，从a[mid+1...j]一共有j-(mid+1)+1=j-mid
            
        }
        else
        {
            temp[k++]=arry[j--];
        }
    }
    cout<<"调用MergeArray时的count："<<count<<endl;
    while(i>=start)//表示前半段数组中还有元素未放入临时数组
    {
        temp[k++]=arry[i--];
    }
    while(j>mid)
    {
        temp[k++]=arry[j--];
    }
    //将临时数组中的元素写回到原数组当中去。
    for(i=0;i<k;i++)
        arry[end-i]=temp[i];
    printArray(arry,8);//输出进过一次归并以后的数组，用于理解整体过程
    return count;
}
int InversePairsCore(int arry[],int start,int end,int temp[])
{
    int inversions = 0;  
    if(start<end)
    {
        int mid=(start+end)/2;
        inversions+=InversePairsCore(arry,start,mid,temp);//找左半段的逆序对数目
        inversions+=InversePairsCore(arry,mid+1,end,temp);//找右半段的逆序对数目
        inversions+=MergeArray(arry,start,mid,end,temp);//在找完左右半段逆序对以后两段数组有序，然后找两段之间的逆序对。最小的逆序段只有一个元素。
    }    
    return inversions;
}
int InversePairs(int arry[],int len)
{
    int *temp=new int[len];
    int count=InversePairsCore(arry,0,len-1,temp);
    delete[] temp;
    return count;
}
void main()
{
    //int arry[]={7,5,6,4};
    int arry[]={1,3,7,8,2,4,6,5};
    int len=sizeof(arry)/sizeof(int);
    //printArray(arry,len);
    int count=InversePairs(arry,len);
    //printArray(arry,len);
    //cout<<count<<endl;
    system("pause");
}

例题2、

$\color{red}{有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query}$ ， $\color{red}{每个文件的query都可能重复。要求你按照query的频度排序。}$

1、hash映射：顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为）中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。

2、hash统计：找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。注：hash_map(query,query_count)是用来统计每个query的出现次数，不是存储他们的值，出现一次，则count+1。

3、堆/快速/归并排序：利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件（记为）。对这10个文件进行归并排序（内排序与外排序相结合）。

例题3、

$\color{red}{归并一个左右两边分别排好序的数组，空间复杂度要求O(1)。}$

使用原地归并，能够让归并排序的空间复杂度降为O(1)，但是速度上会有一定程度的下降。代码如下：

#include<iostream>
#include<cmath>
#include<cstdlib>
#include<Windows.h>
using namespace std;
void insert_sort(int arr[],int n)
{
for(int i=1;i<n;++i)
{
int val=arr[i];
int j=i-1;
while(arr[j]>val&&j>=0)
{
arr[j+1]=arr[j];
--j;
}
arr[j+1]=val;
}
}
void aux_merge(int arr[],int n,int m,int aux[])
{
for(int i=0;i<m;++i)
swap(aux[i],arr[n+i]);
int p=n-1,q=m-1;
int dst=n+m-1;
for(int i=0;i<n+m;++i)
{
if(p>=0)
{
if(q>=0)
{
if(arr[p]>aux[q])
{
swap(arr[p],arr[dst]);
p--;
}
else
{
swap(aux[q],arr[dst]);
q--;
}
}
else
break;
}
else
{
swap(aux[q],arr[dst]);
q--;
}
dst--;
}
}
void local_merge(int arr[],int n)
{
int m=sqrt((float)n);
int k=n/m;
for(int i=0;i<m;++i)
swap(arr[k*m-m+i],arr[n/2/m*m+i]);
for(int i=0;i<k-2;++i)
{
int index=i;
for(int j=i+1;j<k-1;++j)
if(arr[j*m]<arr[index*m])
index=j;
if(index!=i)
for(int j=0;j<m;++j)
swap(arr[i*m+j],arr[index*m+j]);
}
for(int i=0;i<k-2;++i)
aux_merge(arr+i*m,m,m,arr+(k-1)*m);
int s=n%m+m;
insert_sort(arr+(n-2*s),2*s);
aux_merge(arr,n-2*s,s,arr+(k-1)*m);
insert_sort(arr+(k-1)*m,s);
}
void local_merge_sort(int arr[],int n)
{
if(n<=1)
return;
if(n<=10)
{
insert_sort(arr,n);
return;
}
local_merge_sort(arr,n/2);
local_merge_sort(arr+n/2,n-n/2);
local_merge(arr,n);
}
void merge_sort(int arr[],int temp[],int n)
{
if(n<=1)
return;
if(n<=10)
{
insert_sort(arr,n);
return;
}
merge_sort(arr,temp,n/2);
merge_sort(arr+n/2,temp,n-n/2);
for(int i=0;i<n/2;++i)
temp[i]=arr[i];
for(int i=n/2;i<n;++i)
temp[n+n/2-i-1]=arr[i];
int left=0,right=n-1;
for(int i=0;i<n;++i)
if(temp[left]<temp[right])
arr[i]=temp[left++];
else
arr[i]=temp[right--];
}
const int n=2000000;
int arr1[n],arr2[n];
int temp[n];
int main()
{
for(int i=0;i<n;++i)
arr1[i]=arr2[i]=rand();
int begin=GetTickCount();
merge_sort(arr1,temp,n);
cout<<GetTickCount()-begin<<endl;
begin=GetTickCount();
local_merge_sort(arr2,n);
cout<<GetTickCount()-begin<<endl;
for(int i=0;i<n;++i)
if(arr1[i]!=arr2[i])
cout<<"ERROR"<<endl;
system("pause");
}

十、桶排序

1）算法简介
桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是 $\color{red}{将数组分到有限数量的桶子里。每个桶子再个别排序}$ （有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

桶排序是稳定的，且在大多数情况下常见排序里最快的一种,比快排还要快，缺点是非常耗空间,基本上是最耗空间的一种排序算法，而且只能在某些情形下使用。

2）算法描述和分析
桶排序具体算法描述如下：

$\color{blue}{1、设置一个定量的数组当作空桶子。}$

$\color{blue}{2、寻访串行，并且把项目一个一个放到对应的桶子去。}$

$\color{blue}{3、对每个不是空的桶子进行排序。}$

$\color{blue}{4、从不是空的桶子里把项目再放回原来的串行中。}$

桶排序最好情况下使用线性时间O(n)，很显然桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n);很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

可以证明，即使选用插入排序作为桶内排序的方法，桶排序的平均时间复杂度为线性。具体证明，请参考算法导论。其空间复杂度也为线性。

3）算法图解、视频演示

图解

视频：

这里就不给出桶排序的视频了

4）算法代码

#include <time.h>
#include <iostream>
#include <iomanip>
using namespace  std;
 
/*initial arr*/
void InitialArr(double *arr,int n)
{
srand((unsigned)time(NULL));
for (int i = 0; i<n;i++)
{
arr[i] = rand()/double(RAND_MAX+1);   //(0.1)
}
}
 
/* print arr*/
void PrintArr(double *arr,int n)
{
for (int i = 0;i < n; i++)
{
cout<<setw(15)<<arr[i];
if ((i+1)%5 == 0 || i ==  n-1)
{
cout<<endl;
}
}
}
 
void BucketSort(double * arr,int n)     
{
double **bucket = new double*[10];
for (int i = 0;i<10;i++)
{
bucket[i] = new double[n];
}
int count[10] = {0};
for (int i = 0 ; i < n ; i++)
{
double temp = arr[i];
int flag = (int)(arr[i]*10); //flag标识小树的第一位 
bucket[flag][count[flag]] = temp; //用二维数组的每个向量来存放小树第一位相同的数据
int j = count[flag]++;
 
/* 利用插入排序对每一行进行排序 */
for(;j > 0 && temp < bucket[flag][j - 1]; --j)
{
bucket[flag][j] = bucket[flag][j-1];
}
bucket[flag][j] =temp;
}
 
/* 所有数据重新链接 */
int k=0;
for (int i = 0 ; i < 10 ; i++)
{
for (int j = 0 ; j< count[i];j++)
{
arr[k] = bucket[i][j];
k++;
}
}
for (int i = 0 ; i<10 ;i++)
{
delete bucket[i];
bucket[i] =NULL;
}
delete []bucket;
bucket = NULL;
}
 
void main()
{
double *arr=new double[10];
InitialArr(arr, 10);
BucketSort(arr, 10);
PrintArr(arr,10);
delete [] arr;
}

5）考察点、重点和频度分析
桶排序是一种很巧妙的排序方法，在处理密集型数排序的时候有比较好的效果(主要是这种情况下空间复杂度不高)，其思想也可用在很多算法题上，详见后续笔试面试算法例题。

6）笔试面试题

例题1、

$\color{red}{一年的全国高考考生人数为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、

$\color{red}{在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可（内存限制为 2G的意思就是}$ ， $\color{red}{可以使用2G的空间来运行程序，而不考虑这台机器上的其他软件的占用内存）}$ 。

分析：既然要找中位数，很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法。

思想：将整型的每1byte作为一个关键字，也就是说一个整形可以拆成4个keys，而且最高位的keys越大，整数越大。如果高位keys相同，则比较次高位的keys。整个比较过程类似于字符串的字典序。按以下步骤实施：

$\color{blue}{1、把10G整数每2G读入一次内存，然后一次遍历这536,870,912即（1024*1024*1024）*2 /4个数据}$ 。 $\color{blue}{每个数据用位运算">>"取出最高8位(31-24)。这8bits(0-255)最多表示255个桶}$ ， $\color{blue}{那么可以根据8bit的值来确定丢入第几个桶。最后把每个桶写入一个磁盘文件中}$ ， $\color{blue}{同时在内存中统计每个桶内数据的数量，自然这个数量只需要255个整形空间即可}$ 。

$\color{blue}{2、继续以内存中的整数的次高8bit进行桶排序(23-16)。过程和第一步相同，也是255个桶。}$

$\color{blue}{3、一直下去，直到最低字节(7-0bit)的桶排序结束。我相信这个时候完全可以在内存中使用一次快排就可以了。}$

例题3、

$\color{red}{给定n个实数x1,x2,...,xn,求这n个实数在实轴上相邻2个数之间的最大差值M,要求设计线性的时间算法}$

典型的最大间隙问题。

要求线性时间算法。需要使用桶排序。桶排序的平均时间复发度是O(N).如果桶排序的数据分布不均匀，假设都分配到同一个桶中，最坏情况下的时间复杂度将变为O(N^2).

桶排序: $\color{blue}{最关键的建桶，如果桶设计得不好的话桶排序是几乎没有作用的。通常情况下，上下界有两种取法}$ , $\color{blue}{第一种是取一个10^n或者是2^n的数，方便实现。另一种是取数列的最大值和最小值然后均分作桶}$ 。

对于这个题，最关键的一步是：由抽屉原理知：最大差值M>= (Max(V[n])-Min(V[n]))/(n-1)！所以，假如以(Max(V[n])-Min(V[n]))/(n-1)为桶宽的话，答案一定不是属于同一个桶的两元素之差。因此，这样建桶，每次只保留桶里面的最大值和最小值即可。

代码如下：

//距离平均值为offset = (arrayMax - arrayMin) / (n - 1), 则距离最大的数必然大于这个值
//每个桶只要记住桶中的最大值和最小值，依次比较上一个桶的最大值与下一个桶的最小值的差值，找最大的即可.
#include <iostream>
#define MAXSIZE 100    //实数的个数
#define MAXNUM 32767
using namespace std;
struct Barrel
{
 double min;   //桶中最小的数
 double max;   //桶中最大的数
 bool flag;   //标记桶中有数
};
int BarrelOperation(double* array, int n)
{
 Barrel barrel[MAXSIZE];  //实际使用的桶
 int nBarrel = 0;  //实际使用桶的个数
 Barrel tmp[MAXSIZE];   //临时桶，用于暂存数据
 double arrayMax = -MAXNUM, arrayMin = MAXNUM;
 for(int i = 0; i < n; i++) {
  if(array[i] > arrayMax)
   arrayMax = array[i];
  if(array[i] < arrayMin)
   arrayMin = array[i];
 }
 double offset = (arrayMax - arrayMin) / (n - 1);  //所有数的平均间隔
 //对桶进行初始化
 for(i = 0; i < n; i++) {  
  tmp[i].flag = false;
  tmp[i].max = arrayMin;
  tmp[i].min = arrayMax;
 }
 //对数据进行分桶
 for(i = 0; i < n; i++) {   
  int pos = (int)((array[i] - arrayMin) / offset);
  if(!tmp[pos].flag) {
   tmp[pos].max = tmp[pos].min = array[i];
   tmp[pos].flag = true;
  } else {
   if(array[i] > tmp[pos].max)
    tmp[pos].max = array[i];
   if(array[i] < tmp[pos].min)
    tmp[pos].min = array[i];
  } 
 }
 for(i = 0; i <= n; i++) {
  if(tmp[i].flag) 
   barrel[nBarrel++] = tmp[i];   
 }
 int maxOffset = 0.0;
 for(i = 0; i < nBarrel - 1; i++) {
  if((barrel[i+1].min - barrel[i].max) > maxOffset) 
   maxOffset = barrel[i+1].min - barrel[i].max;
 }
 return maxOffset;
}
int main()
{
 double array[MAXSIZE] = {1, 8, 6, 11, 7, 13, 16, 5};  //所需处理的数据
 int n = 8; //数的个数
 //double array[MAXSIZE] = {8, 6, 11};
 //int n = 3;
 int maxOffset = BarrelOperation(array, n);
 cout << maxOffset << endl;
 return 0;
}

十一、计数排序

1）算法简介
计数排序(Counting sort)是一种稳定的排序算法。计数排序 $\color{red}{使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数}$ 。 $\color{red}{然后根据数组C来将A中的元素排到正确的位置}$ 。它 $\color{red}{只能对整数进行排序}$ 。

2）算法描述和分析
算法的步骤如下：

$\color{blue}{1、找出待排序的数组中最大和最小的元素}$

$\color{blue}{2、统计数组中每个值为i的元素出现的次数，存入数组C的第i项}$

$\color{blue}{3、对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）}$

$\color{blue}{4、反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1}$

$\color{red}{当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)}$ 。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

3）算法图解、视频演示

图解：

我们使用计数排序对一个乱序的整数数组进行排序。

首先创建一个临时数组（长度为输入数据的最大间隔），对于每一个输入数组的整数k，我们在临时数组的第k位置"1"。如下图

上图中，第一行表示输入数据，第二行表示创建的临时数据，临时数组的下标代表输入数据的某一个值，临时数组的值表示输入数据中某一个值的数量。

如果输入数据中有重复的数值，那么我们增加临时数组相应的值（比如上图中5有3个，所以小标为5的数组的值是3）。在“初始化”临时数组以后，我们就得到了一个排序好的输入数据。

我们顺序遍历这个数组，将下标解释成数据，将该位置的值表示该数据的重复数量，记得得到一个排序好的数组。

视频：

这里就不推荐视频了

4）算法代码

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
/**************************************************************
 功能：计数排序。
 参数： data ： 要排序的数组
        size ：数组元素的个数
        k   ：数组中元素数组最大值 +1 （这个需要+1）
 返回值： 成功0；失败-1.       
 *************************************************************/
int ctsort(int *data, int size, int k)
{
    int * counts = NULL,/*计数数组*/
        * temp = NULL;/*保存排序后的数组*/
    int i = 0;
    /*申请数组空间*/
    if ((counts = (int *) malloc( k * sizeof(int))) == NULL)
        return -1;
    if ((temp = (int *) malloc( k * sizeof(int))) == NULL)
        return -1;
    /*初始化计数数组*/
    for (i = 0; i < k; i ++)
        counts[i] = 0;
    /*数组中出现的元素，及出现次数记录*/
    for(i = 0; i < size; i++)
        counts[data[i]] += 1;
    /*调整元素计数中，加上前一个数*/
    for (i = 1; i < k; i++)
        counts[i] += counts[i - 1];
    /*使用计数数组中的记录数值，来进行排序，排序后保存的temp*/
    for (i = size -1; i >= 0; i --){
        temp[counts[data[i]] - 1] = data[i];
        counts[data[i]] -= 1;
    }
    
    memcpy(data,temp,size * sizeof(int));
    free(counts);
    free(temp);
    return 0;
}
int main()
{
    int a[8] = {2,0,2,1,4,6,7,4};
    int max = a[0],
        i = 0;
    /*获得数组中中的数值*/
    for ( i = 1; i < 8; i++){
        if (a[i] > max)
            max = a[i];
    }
    ctsort(a,8,max+1);
    for (i = 0;i < 8;i ++)
        printf("%d\n",a[i]);
}

5）考察点、重点和频度分析
计数排序在处理密集整数排序的问题的时候非常有限，尤其是有时候题目对空间并不做太大限制，那使用计数排序能够达到O(n)的时间复杂度，远快于所有基于比较的其他排序方法。

6）笔试面试题

例题1、

$\color{red}{某地区年龄排序问题}$

够典型的计数排序吧，年龄的区间也就那么大，代码就不上了，请参照上述参照计数排序算法。

十二、基数排序

1）算法简介
基数排序是一种非比较型整数排序算法，其原理是 $\color{red}{将整数按位数切割成不同的数字，然后按每个位数分别比较}$ 。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机（Tabulation Machine）上的贡献。

2）算法描述和分析
整个算法过程描述如下：

$\color{blue}{1、将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。}$

$\color{blue}{2、从最低位开始，依次进行一次排序。}$

$\color{blue}{3、这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。}$

基数排序的时间复杂度是 O(k•n)，其中n是排序元素个数，k是数字位数。

注意这不是说这个时间复杂度一定优于O(n·log(n))，因为k的大小一般会受到n的影响。以排序n个不同整数来举例，假定这些整数以B为底，这样每位数都有B个不同的数字，k就一定不小于logB(n)。由于有B个不同的数字，所以就需要B个不同的桶，在每一轮比较的时候都需要平均n·log2(B) 次比较来把整数放到合适的桶中去，所以就有：

k 大于或等于 logB(n)

每一轮(平均)需要 n·log2(B) 次比较

所以，基数排序的平均时间T就是：

T ≥ logB(n)·n·log2(B) = log2(n)·logB(2)·n·log2(B) = log2(n)·n·logB(2)·log2(B) = n·log2(n)

所以和比较排序相似，基数排序需要的比较次数：T ≥ n·log2(n)。故其时间复杂度为 Ω(n·log2(n)) = Ω(n·log n) 。

3）算法图解、视频演示

图解：

视频：基数排序

4）算法代码

#include <stdio.h> 
#include <stdlib.h> 
void radixSort(int data[]) {
    int temp[10][10] = {0}; 
    int order[10] = {0}; 
    
    int n = 1; 
    while(n <= 10) { 
        
        int i;
        for(i = 0; i < 10; i++) { 
            int lsd = ((data[i] / n) % 10); 
            temp[lsd][order[lsd]] = data[i]; 
            order[lsd]++; 
        } 
        
        // 重新排列
        int k = 0;
        for(i = 0; i < 10; i++) { 
            if(order[i] != 0)  {
                int j;
                for(j = 0; j < order[i]; j++, k++) { 
                    data[k] = temp[i][j]; 
                } 
            }
            order[i] = 0; 
        } 
        n *= 10; 
    }     
}
int main(void) { 
    int data[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81}; 
      
    printf("\n排序前: "); 
    int i;
    for(i = 0; i < 10; i++) 
        printf("%d ", data[i]); 
    putchar('\n'); 
    radixSort(data);
    
    printf("\n排序後: "); 
    for(i = 0; i < 10; i++) 
        printf("%d ", data[i]); 
    return 0; 
}

总结

总结一下各种排序算法如下：


名称	时间复杂度	额外空间	稳定性	考点
插入排序	平均O(n^2), 最优O(n), 最差O(n^2)	O(1)	稳定	选择填空, 各种时间复杂度, 移动元素个数
二分插入排序	平均 O(n^2)	O(1)	稳定	同上
希尔排序	最差O(n log n), 最优 O(n)	$\color{red}{O(n)}$	不稳定	时间复杂度, 比较次数
选择排序	O(n^2)	O(1)	不稳定	同插入排序
冒泡排序	O(n^2) 最优O(n) 最差O(n^2)	O(1)	稳定	时间复杂度, 比较次数, 单轮冒泡
鸡尾酒排序	O(n^2)	O(1)	稳定	同上
快速排序	O(n log n)	O(1)	不稳定	时间复杂度, 快排partition算法
堆排序	O(n log n)	O(n)	不稳定	时间复杂度堆调整，建堆，堆排序，Top K问题
归并排序	平均O(nlogn), 最差O(nlogn), 最优O(n)	O(n)	稳定	时间复杂度, 递归思想

即

找工作知识储备(3)B---从头说12种排序算法：原理、图解、动画视频演示、代码以及笔试面试题目中的应用

七、快速排序

步骤为：

图解：

视频 :舞动的排序算法

例题1、

例题2、

例题3、

八、堆排序

图解：

视频: 堆排序

例题1、

例题2、

九、归并排序

图解：

视频：舞动的排序算法 归并排序

例题1、

例题2、

例题3、

十、桶排序

图解

视频：

例题1、

例题2、

例题3、

十一、计数排序

图解：

视频：

例题1、

十二、基数排序

图解：

视频：基数排序

总结

视频：舞动的排序算法归并排序