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

作者：寒小阳

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

0、前言    

 从这一部分开始直接切入我们计算机互联网笔试面试中的重头戏算法了，初始的想法是找一条主线，比如数据结构或者解题思路方法，将博主见过做过整理过的算法题逐个分析一遍(博主当年自己学算法就是用这种比较笨的刷题学的，囧)，不过又想了想，算法这东西，博主自己学的过程中一直深感，基础还是非常重要的，很多难题是基础类数据结构和题目的思想综合发散而来。比如说作为最基本的排序算法就种类很多，而事实上笔试面试过程中发现掌握的程度很一般，有很多题目，包括很多算法难题，其母题或者基本思想就是基于这些经典算法的，比如说快排的partition算法，比如说归并排序中的思想，比如说桶排序中桶的思想。
        这里对笔试面试最常涉及到的12种排序算法(包括插入排序、二分插入排序、希尔排序、选择排序、冒泡排序、鸡尾酒排序、快速排序、堆排序、归并排序、桶排序、计数排序和基数排序)进行了详解。每一种算法都有基本介绍、算法原理分析、图解/flash演示/视频演示、算法代码、笔试面试重点分析、笔试面试题等板块，希望能帮助大家真正理解这些排序算法，并能使用这些算法的思想解决一些题。不多说了，下面就进入正题了。

一、插入排序1）算法简介

        插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

2）算法描述和分析

    一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

    1、从第一个元素开始，该元素可以认为已经被排序

    2、取出下一个元素，在已经排序的元素序列中从后向前扫描

    3、如果该元素（已排序）大于新元素，将该元素移到下一位置

    4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

    5、将新元素插入到该位置后

    6、重复步骤2~5

        如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说插入排序算法复杂度为O(n^2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

3）算法图解、flash演示、视频演示图解：

Flash：http://www.tjbpi.com/jpk/shujujiegou/flash/%B5%DA%CA%AE%D2%BB%D5%C2%20%C5%C5%D0%F2/%D6%B1%BD%D3%B2%E5%C8%EB%C5%C5%D0%F2.swf

视频：插入排序舞蹈

http://v.youku.com/v_show/id_XMjU4NTY5MzEy.html

4）算法代码

视频：二分插入排序
http://v.youku.com/v_show/id_XMTA1MTkwMTEy.html
4）算法代码




Flash：
http://ds.fzu.edu.cn/fine/resources/FlashContent.asp?id=92
视频：希尔排序Shell Sort 舞蹈
http://v.youku.com/v_show/id_XMjU4NTcwMDIw.html
4）算法代码
最差时间复杂度
О(n2)
最优时间复杂度
О(n2)
平均时间复杂度
О(n2)
最差空间复杂度
О(n) total, O(1)
3）算法图解、flash演示、视频演示
图解：
Flash：
http://ds.fzu.edu.cn/fine/resources/FlashContent.asp?id=85
视频：选择排序Select Sort排序舞蹈
http://v.youku.com/v_show/id_XMjU4NTY5NTcy.html
4）算法代码
最差时间复杂度
O(n^2)
最优时间复杂度
O(n)
平均时间复杂度
O(n^2)
最差空间复杂度
总共O(n)，需要辅助空间O(1)
3）算法图解、flash演示、视频演示
图解：
Flash：
http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/maopaopaixu.htm
视频：舞动的排序算法 冒泡排序
http://v.youku.com/v_show/id_XMzMyOTAyMzQ0.html
4）算法代码
#include <stdio.h>#include <string.h>//判断是不是大写字母 int isUpperAlpha(char c){if(c >= 'A' && c <= 'Z'){return 1;}return 0; }//交换两个字母 void swap(char *a, char *b){char temp = *a;*a = *b;*b = temp;} char * Reorder(char *arr, int len){if(arr == NULL || len <= 0){return NULL;}int *p1 = arr;int *p2 = arr;While(p1<arr+len && p2<arr+len){While( isUpperAlpha(*p1) ){P1++;}While( !isUpperAlpha(*p2) ){P2++;}swap(p1, p2)}//结束return arr;}int main(){char arr[] = "aaaaaaaaaaaaaaaaaaaaaaaAbcAdeBbDc";printf("%s\n", Reorder(arr, strlen(arr)));return 0;}

六、鸡尾酒排序/双向冒泡排序
1）算法简介
        鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能，原因是冒泡排序只从一个方向进行比对(由低到高)，每次循环只移动一个项目。
2）算法描述和分析
     1、依次比较相邻的两个数，将小数放在前面，大数放在后面；
     2、第一趟可得到：将最大数放到最后一位。
     3、第二趟可得到：将第二大的数放到倒数第二位。
     4、如此下去，重复以上过程，直至最终完成排序。
    鸡尾酒排序最糟或是平均所花费的次数都是O(n^2)，但如果序列在一开始已经大部分排序过的话，会接近O(n)。
    最差时间复杂度
O(n^2)
最优时间复杂度
O(n)
平均时间复杂度
O(n^2)
3）算法图解、flash演示、视频演示
图解：
Flash：
参见http://zh.wikipedia.org/zh-cn/%E9%B8%A1%E5%B0%BE%E9%85%92%E6%8E%92%E5%BA%8F右侧flash动画
4）算法代码
最差时间复杂度
O(n^2)
最优时间复杂度
O(n log n)
平均时间复杂度
O(n log n)
最差空间复杂度
根据实现的方式不同而不同
3）算法图解、flash演示、视频演示
图解：
        快速排序会递归地进行很多轮，其中每一轮称之为快排的partition算法，即上述算法描述中的第2步，非常重要，且在各种笔试面试中用到该思想的算法题层出不穷，下图为第一轮的partition算法的一个示例。
Flash：
可一步步参见http://ds.fzu.edu.cn/fine/resources/FlashContent.asp?id=86中的快排过程
视频 舞动的排序算法
http://v.youku.com/v_show/id_XMzMyODk4NTQ4.html
4）算法代码
        事实上，这个地方需要提一下的是，快排有很多种版本。例如，我们“基准数”的选择方法不同就有不同的版本，但重要的是快排的思想，我们熟练掌握一种版本，在最后的笔试面试中也够用了，我这里罗列几种最有名的版本C代码。
1、版本一
我们选取数组的第一个元素作为主元，每一轮都是和第一个元素比较大小，通过交换，分成大于和小于它的前后两部分，再递归处理。
代码如下
#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;}

八、堆排序
        不得不说，堆排序太容易出现了，选择填空问答算法大题都会出现。建堆的过程，堆调整的过程，这些过程的时间复杂度，空间复杂度，以及如何应用在海量数据Top K问题中等等，都是需要重点掌握的。
1）算法简介
        堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
2）算法描述
       我们这里介绍几个问题，一步步推到堆排序的算法。
1、什么是堆？
      我们这里提到的堆一般都指的是二叉堆，它满足二个特性：
           1---父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
           2---每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。
     如下为一个最小堆(父结点的键值总是小于任何一个子节点的键值)
2、什么是堆调整(Heap Adjust)？
        这是为了保持堆的特性而做的一个操作。对某一个节点为根的子树做堆调整，其实就是将该根节点进行“下沉”操作(具体是通过和子节点交换完成的)，一直下沉到合适的位置，使得刚才的子树满足堆的性质。
       例如对最大堆的堆调整我们会这么做：
              1、在对应的数组元素A[i], 左孩子A[LEFT(i)], 和右孩子A[RIGHT(i)]中找到最大的那一个，将其下标存储在largest中。
              2、如果A[i]已经就是最大的元素，则程序直接结束。
              3、否则，i的某个子结点为最大的元素，将A[largest]与A[i]交换。
              4、再从交换的子节点开始，重复1,2,3步，直至叶子节点，算完成一次堆调整。
       这里需要提一下的是，一般做一次堆调整的时间复杂度为log(n)。
       如下为我们对4为根节点的子树做一次堆调整的示意图，可帮我们理解。
3、如何建堆
         建堆是一个通过不断的堆调整，使得整个二叉树中的数满足堆性质的操作。在数组中的话，我们一般从下标为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分别作一次向下调整操作就可以了。
4、如何进行堆排序
        堆排序是在上述3中对数组建堆的操作之后完成的。
        数组储存成堆的形式之后，第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n-2]交换，再对A[0…n-3]重新恢复堆，重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。
如下图所示：



最差时间复杂度
O(n log n)
最优时间复杂度
O(n log n)
平均时间复杂度
O(n log n)
最差空间复杂度
 O(n)
3）算法图解、flash演示、视频演示
图解：
   略，见上一节。
Flash：
可参见http://ds.fzu.edu.cn/fine/resources/FlashContent.asp?id=88中的flash动画，帮助理解
视频 堆排序
http://v.youku.com/v_show/id_XMzQzNzAwODQ=.html
4）算法代码
   直接上代码吧，重点注意HeapAdjust，BuildHeap和HeapSort的实现。

Flash：
可以参考http://ds.fzu.edu.cn/fine/resources/FlashContent.asp?id=93中的过程
视频：舞动的排序算法 归并排序
http://video.sina.com.cn/v/b/80012415-1642346981.html
4）算法代码
#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--;}}elsebreak;}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++];elsearr[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)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。
       桶排序是稳定的，且在大多数情况下常见排序里最快的一种,比快排还要快，缺点是非常耗空间,基本上是最耗空间的一种排序算法，而且只能在某些情形下使用。
2）算法描述和分析
       桶排序具体算法描述如下：
      1、设置一个定量的数组当作空桶子。
      2、寻访串行，并且把项目一个一个放到对应的桶子去。
      3、对每个不是空的桶子进行排序。
      4、从不是空的桶子里把项目再放回原来的串行中。
       桶排序最好情况下使用线性时间O(n)，很显然桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为 其它部分的时间复杂度都为O(n);很显然，桶划分的越小，各个桶之间的数据越少，排 序所用的时间也会越少。但相应的空间消耗就会增大。
       可以证明，即使选用插入排序作为桶内排序的方法，桶排序的平均时间复杂度为线性。 具体证明，请参考算法导论。其空间复杂度也为线性。
3）算法图解、flash演示、视频演示
图解

Flash：
可以参考http://ds.fzu.edu.cn/fine/resources/FlashContent.asp?id=90中的过程
视频：
这里就不给出桶排序的视频了，见上flash吧
4）算法代码
//距离平均值为offset = (arrayMax - arrayMin) / (n - 1), 则距离最大的数必然大于这个值//每个桶只要记住桶中的最大值和最小值，依次比较上一个桶的最大值与下一个桶的最小值的差值，找最大的即可.#include <iostream>#define MAXSIZE 100    //实数的个数#define MAXNUM 32767using 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)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
2）算法描述和分析
        算法的步骤如下：
          1、找出待排序的数组中最大和最小的元素
         2、统计数组中每个值为i的元素出现的次数，存入数组C的第i项
         3、对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
         4、反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
        当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。
        由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。
3）算法图解、flash演示、视频演示
图解：
        我们使用计数排序对一个乱序的整数数组进行排序。
        首先创建一个临时数组（长度为输入数据的最大间隔），对于每一个输入数组的整数k，我们在临时数组的第k位置"1"。如下图

        上图中，第一行表示输入数据，第二行表示创建的临时数据，临时数组的下标代表输入数据的某一个值，临时数组的值表示输入数据中某一个值的数量。
         如果输入数据中有重复的数值，那么我们增加临时数组相应的值（比如上图中5有3个，所以小标为5的数组的值是3）。在“初始化”临时数组以后，我们就得到了一个排序好的输入数据。
        我们顺序遍历这个数组，将下标解释成数据， 将该位置的值表示该数据的重复数量，记得得到一个排序好的数组。
Flash：
     可参见http://ds.fzu.edu.cn/fine/resources/FlashContent.asp?id=89中的flash过程
视频：
     前面的flash已经能够清晰地表示出整个计数排序的过程了，这里就不推荐视频了
4）算法代码
Flash：
     可参见http://ds.fzu.edu.cn/fine/resources/FlashContent.asp?id=91中的flash过程
视频：
     http://www.tudou.com/programs/view/vfoUHC-tgi0
4）算法代码
插入排序
平均O(n^2)
最优O(n)
最差O(n^2)
O(1)
 稳定
选择填空
各种时间复杂度
移动元素个数
二分插入排序
平均 O(n^2)
O(1)
 稳定
同上
希尔排序
最差O(n log n)
最优 O(n)
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)
 稳定
时间复杂度
递归思想
即



 

 

查看更多 下一篇