您的位置: 首页  >  文章  >  找工作知识储备 3 ---从头说12种排序算法 原理 图解 动画视频演示 代码以及笔试面试题目中的应用

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

分类: 文章 • 2025-07-23 16:48:52

分享一下我老师大神的人工智能教程！零基础，通俗易懂！http://blog.****.net/jiangjunshow

也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！

               

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

分类： 笔试面试基础知识 算法那些事儿2013-09-29 16:54 199人阅读 评论(0) 收藏 举报
12种排序算法原理代码图解flash视频对应笔试面试题

目录(?)[+]

作者：寒小阳

时间：2013年9月。
出处：http://blog.****.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演示、视频演示

图解：

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

Flash：

视频：插入排序舞蹈

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

4）算法代码

[cpp] view plaincopy
  1. void insertion_sort(int array[], int first, int last)  
  2.  {  
  3.         int i,j;  
  4.         int temp;  
  5.         for (i = first+1; i<=last;i++)  
  6.         {  
  7.                 temp = array[i];  
  8.                 j=i-1;  
  9.    
  10.                 //与已排序的数逐一比较，大于temp时，该数后移  
  11.                 while((j>=first) && (array[j] > temp))  //当first=0，j循环到-1时，由于[[短路求值]]，不会运算array[-1]  
  12.                 {  
  13.                         array[j+1] = array[j];  
  14.                         j--;  
  15.                 }  
  16.                 array[j+1] = temp;      //被排序数放到正确的位置  
  17.    
  18.         }  
  19.  }  

 5）考察点，重点和频度分析

        把插入排序放在第一个的原因是因为其出现的频度不高，尤其是这里提到的直接排序算法，基本在笔试的选择填空问时间空间复杂度的时候才可能出现。毕竟排序速度比较慢，因此算法大题中考察的次数比较比较少。

6）笔试面试例题

例题1、

请写出链表的插入排序程序

[cpp] view plaincopy
  1. template<typename T>  
  2. struct list_node  
  3. {  
  4.     struct list_node<T> *next;  
  5.     T value;  
  6. };  
  7. template<typename T>  
  8. struct _list  
  9. {  
  10.     struct list_node<T> *head;  
  11.     int size;  
  12. };  
  13. template<typename T>  
  14. void SortLink(struct _list<T> * link) {  
  15.     struct list_node<T> *pHead,*pRear,*p,*tp;  
  16.     if (!link) return;  
  17.     for (pHead=link->head,pRear=0;pHead;pHead=pHead->next) {  
  18.         for (tp=pHead,p=pHead->next;p;tp=p,p=p->next)  
  19.             if (pHead->value>=p->value)  
  20.                 tp->next=p->next,p->next=pHead,pHead=p,p=tp;  
  21.         if (!pRear) link->head=pHead;  
  22.         else pRear->next=pHead;  
  23.         pRear=pHead;  
  24.     }  
  25. }  

例题2、

下列排序算法中最坏复杂度不是n(n-1)/2的是 D

A.快速排序     B.冒泡排序   C.直接插入排序   D.堆排序

二、二分插入排序

1）算法简介

       二分（折半）插入（Binary insert sort)排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接排序算法最大的区别在于查找插入位置时使用的是二分查找的方式，在速度上有一定提升。

2）算法描述和分析

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

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

    2、取出下一个元素，在已经排序的元素序列中二分查找到第一个比它大的数的位置

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

    4、重复上述两步


        1）稳定

        2）空间代价：O(1)

        3）时间代价：插入每个记录需要O(log i)比较，最多移动i+1次，最少2次。最佳情况O(n log n)，最差和平均情况O(n^2)。

        二分插入排序是一种稳定的排序。当n较大时，总排序码比较次数比直接插入排序的最差情况好得多，但比最好情况要差，所元素初始序列已经按排序码接近有序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列。

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

图解：

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

视频：二分插入排序

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

4）算法代码

[cpp] view plaincopy
  1. void BinInsertSort(int a[], int n)   
  2. {   
  3.         int key, left, right, middle;   
  4.         for (int i=1; i<n; i++)   
  5.         {   
  6.                 key = a[i];   
  7.                 left = 0;   
  8.                 right = i-1;   
  9.                 while (left<=right)   
  10.                 {   
  11.                         middle = (left+right)/2;   
  12.                         if (a[middle]>key)   
  13.                                 right = middle-1;   
  14.                         else   
  15.                                 left = middle+1;   
  16.                 }   
  17.                    
  18.                 for(int j=i-1; j>=left; j--)   
  19.                 {   
  20.                         a[j+1] = a[j];   
  21.                 }   
  22.                    
  23.                 a[left] = key;          
  24.         }   
  25. }  

 5）考察点，重点和频度分析

        这个排序算法在笔试面试中出现的频度也不高，但毕竟是直接排序算法的一个小改进算法，同时二分查找又是很好的思想，有可能会在面试的时候提到，算法不难，留心一下就会了。

6）笔试面试例题

例题1、

下面的排序算法中，初始数据集的排列顺序对算法的性能无影响的是（B）

A、二分插入排序         B、堆排序         C、冒泡排序            D、快速排序

例题2、

写出下列算法的时间复杂度。

(1)冒泡排序；(2)选择排序；(3)插入排序；(4)二分插入排序；(5)快速排序；(6)堆排序；(7)归并排序；

三、希尔排序

1）算法简介

希尔排序，也称递减增量排序算法，因DL．Shell于1959年提出而得名，是插入排序的一种高速而稳定的改进版本。

2）算法描述

    1、先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。

    2、所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序。

    3、取第二个增量d2<d1重复上述的分组和排序，

    4、直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

          希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n^2)，而Hibbard增量的希尔排序的时间复杂度为O(N^(5/4))，但是现今仍然没有人能找出希尔排序的精确下界。

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

图解：

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

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

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

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

Flash：

http://ds.fzu.edu.cn/fine/resources/FlashContent.asp?id=92

视频：希尔排序Shell Sort 舞蹈

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

4）算法代码

[cpp] view plaincopy
  1. #include <stdio.h>  
  2.    
  3. int main()  
  4. {  
  5.      const int n = 5;  
  6.      int i, j, temp;   
  7.      int gap = 0;  
  8.      int a[] = {5, 4, 3, 2, 1};   
  9.      while (gap<=n)  
  10.      {  
  11.           gap = gap * 3 + 1;  
  12.      }   
  13.      while (gap > 0)   
  14.      {  
  15.          for ( i = gap; i < n; i++ )  
  16.          {  
  17.              j = i - gap;  
  18.              temp = a[i];               
  19.              while (( j >= 0 ) && ( a[j] > temp ))  
  20.              {  
  21.                  a[j + gap] = a[j];  
  22.                  j = j - gap;  
  23.              }  
  24.              a[j + gap] = temp;  
  25.          }  
  26.          gap = ( gap - 1 ) / 3;  
  27.      }      
  28.  }  

5）考察点，重点和频度分析

        事实上希尔排序算法在笔试面试中出现的频度也不比直接插入排序高，但它的时间复杂度并不是一个定值，所以偶尔会被面试官问到选择的步长和时间复杂度的关系，要稍微有点了解吧。算法大题中使用该方法或者其思想的题也不多。

6）笔试面试例题

例题1、

写出希尔排序算法程序，并说明最坏的情况下需要进行多少次的比较和交换。

    程序略，需要O(n^2)次的比较

例题2、

设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：

冒泡排序一趟扫描的结果是       H, C, Q, P, A, M, S, R, D, F, X ,Y      ；

初始步长为4的希尔（shell）排序一趟的结果是   P, A, C, S, Q, D, F, X , R, H,M, Y     ；

二路归并排序一趟扫描的结果是   H, Q, C, Y，A, P, M, S, D, R, F, X&

给我老师的人工智能教程打call！http://blog.****.net/jiangjunshow

找工作知识储备 3 ---从头说12种排序算法 原理 图解 动画视频演示 代码以及笔试面试题目中的应用
你好！ 这是你第一次使用 **Markdown编辑器** 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。

新的改变

我们对Markdown编辑器进行了一些功能拓展与语法支持，除了标准的Markdown编辑器功能，我们增加了如下几点新功能，帮助你用它写博客：

  1. 全新的界面设计 ，将会带来全新的写作体验；
  2. 在创作中心设置你喜爱的代码高亮样式，Markdown 将代码片显示选择的高亮样式 进行展示；
  3. 增加了 图片拖拽 功能，你可以将本地的图片直接拖拽到编辑区域直接展示；
  4. 全新的 KaTeX数学公式 语法；
  5. 增加了支持甘特图的mermaid语法1 功能；
  6. 增加了 多屏幕编辑 Markdown文章功能；
  7. 增加了 焦点写作模式、预览模式、简洁写作模式、左右区域同步滚轮设置 等功能，功能按钮位于编辑区域与预览区域中间；
  8. 增加了 检查列表 功能。

功能快捷键

撤销：Ctrl/Command + Z
重做：Ctrl/Command + Y
加粗：Ctrl/Command + B
斜体：Ctrl/Command + I
标题：Ctrl/Command + Shift + H
无序列表：Ctrl/Command + Shift + U
有序列表：Ctrl/Command + Shift + O
检查列表：Ctrl/Command + Shift + C
插入代码：Ctrl/Command + Shift + K
插入链接：Ctrl/Command + Shift + L
插入图片：Ctrl/Command + Shift + G

合理的创建标题，有助于目录的生成

直接输入1次#，并按下space后，将生成1级标题。
输入2次#，并按下space后，将生成2级标题。
以此类推，我们支持6级标题。有助于使用TOC语法后生成一个完美的目录。

如何改变文本的样式

强调文本 强调文本

加粗文本 加粗文本

标记文本

删除文本

引用文本

H2O is是液体。

210 运算结果是 1024.

插入链接与图片

链接: link.

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

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

当然，我们为了让用户更加便捷，我们增加了图片拖拽功能。

如何插入一段漂亮的代码片

去博客设置页面，选择一款你喜欢的代码片高亮样式，下面展示同样高亮的 代码片.

// An highlighted block var foo = 'bar';

生成一个适合你的列表

  • 项目
    • 项目
      • 项目
  1. 项目1
  2. 项目2
  3. 项目3
  • 计划任务
  • 完成任务

创建一个表格

一个简单的表格是这么创建的：

项目 Value
电脑 $1600
手机 $12
导管 $1

设定内容居中、居左、居右

使用:---------:居中
使用:----------居左
使用----------:居右

第一列 第二列 第三列
第一列文本居中 第二列文本居右 第三列文本居左

SmartyPants

SmartyPants将ASCII标点字符转换为“智能”印刷标点HTML实体。例如：

TYPE ASCII HTML
Single backticks 'Isn't this fun?' ‘Isn’t this fun?’
Quotes "Isn't this fun?" “Isn’t this fun?”
Dashes -- is en-dash, --- is em-dash – is en-dash, — is em-dash

创建一个自定义列表

Markdown
Text-to-HTML conversion tool
Authors
John
Luke

如何创建一个注脚

一个具有注脚的文本。2

注释也是必不可少的

Markdown将文本转换为 HTML。

KaTeX数学公式

您可以使用渲染LaTeX数学表达式 KaTeX:

Gamma公式展示 Γ(n)=(n−1)!∀n∈N\Gamma(n) = (n-1)!\quad\forall n\in\mathbb N 是通过欧拉积分

Γ(z)=∫0∞tz−1e−tdt&ThinSpace;. \Gamma(z) = \int_0^\infty t^{z-1}e^{-t}dt\,.

你可以找到更多关于的信息 LaTeX 数学表达式here.

新的甘特图功能，丰富你的文章

gantt
        dateFormat  YYYY-MM-DD
        title Adding GANTT diagram functionality to mermaid
        section 现有任务
        已完成               :done,    des1, 2014-01-06,2014-01-08
        进行中               :active,  des2, 2014-01-09, 3d
        计划一               :         des3, after des2, 5d
        计划二               :         des4, after des3, 5d
  • 关于 甘特图 语法，参考 这儿,

UML 图表

可以使用UML图表进行渲染。 Mermaid. 例如下面产生的一个序列图：:

张三李四王五你好！李四, 最近怎么样?你最近怎么样，王五？我很好，谢谢!我很好，谢谢!李四想了很长时间,文字太长了不适合放在一行.打量着王五...很好... 王五, 你怎么样?张三李四王五

这将产生一个流程图。:

链接
长方形
圆
圆角长方形
菱形
  • 关于 Mermaid 语法，参考 这儿,

FLowchart流程图

我们依旧会支持flowchart的流程图：

  • 关于 Flowchart流程图 语法，参考 这儿.

导出与导入

导出

如果你想尝试使用此编辑器, 你可以在此篇文章任意编辑。当你完成了一篇文章的写作, 在上方工具栏找到 文章导出 ，生成一个.md文件或者.html文件进行本地保存。

导入

如果你想加载一篇你写过的.md文件或者.html文件，在上方工具栏可以选择导入功能进行对应扩展名的文件导入，
继续你的创作。

  1. mermaid语法说明 ↩︎

  2. 注脚的解释 ↩︎

相关推荐