笔试面试最常涉及到的12种排序算法(包括插入排序、二分插入排序、希尔排序、选择排序、冒泡排序、鸡尾酒排序、快速排序、堆排序、归并排序、桶排序、计数排序和基数排序)进行了详解。每一种算法都有基本介绍、算
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）算法代码
[cpp] view plaincopy
- void insertion_sort(int array[], int first, int last)
- {
- int i,j;
- int temp;
- for (i = first+1; i<=last;i++)
- {
- temp = array[i];
- j=i-1;
- //与已排序的数逐一比较，大于temp时，该数后移
- while((j>=first) && (array[j] > temp)) //当first=0，j循环到-1时，由于[[短路求值]]，不会运算array[-1]
- {
- array[j+1] = array[j];
- j--;
- }
- array[j+1] = temp; //被排序数放到正确的位置
- }
- }
5）考察点，重点和频度分析
把插入排序放在第一个的原因是因为其出现的频度不高，尤其是这里提到的直接排序算法，基本在笔试的选择填空问时间空间复杂度的时候才可能出现。毕竟排序速度比较慢，因此算法大题中考察的次数比较比较少。
6）笔试面试例题
例题1、
请写出链表的插入排序程序
[cpp] view plaincopy
- template<typename T>
- struct list_node
- {
- struct list_node<T> *next;
- T value;
- };
- template<typename T>
- struct _list
- {
- struct list_node<T> *head;
- int size;
- };
- template<typename T>
- void SortLink(struct _list<T> * link) {
- struct list_node<T> *pHead,*pRear,*p,*tp;
- if (!link) return;
- for (pHead=link->head,pRear=0;pHead;pHead=pHead->next) {
- for (tp=pHead,p=pHead->next;p;tp=p,p=p->next)
- if (pHead->value>=p->value)
- tp->next=p->next,p->next=pHead,pHead=p,p=tp;
- if (!pRear) link->head=pHead;
- else pRear->next=pHead;
- pRear=pHead;
- }
- }
例题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演示、视频演示
图解：
视频：二分插入排序
http://v.youku.com/v_show/id_XMTA1MTkwMTEy.html
4）算法代码
[cpp] view plaincopy
- void BinInsertSort(int a[], int n)
- {
- int key, left, right, middle;
- for (int i=1; i<n; i++)
- {
- key = a[i];
- left = 0;
- right = i-1;
- while (left<=right)
- {
- middle = (left+right)/2;
- if (a[middle]>key)
- right = middle-1;
- else
- left = middle+1;
- }
- for(int j=i-1; j>=left; j--)
- {
- a[j+1] = a[j];
- }
- a[left] = key;
- }
- }
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演示、视频演示
图解：
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
- #include <stdio.h>
- int main()
- {
- const int n = 5;
- int i, j, temp;
- int gap = 0;
- int a[] = {5, 4, 3, 2, 1};
- while (gap<=n)
- {
- gap = gap * 3 + 1;
- }
- while (gap > 0)
- {
- for ( i = gap; i < n; i++ )
- {
- j = i - gap;
- temp = a[i];
- while (( j >= 0 ) && ( a[j] > temp ))
- {
- a[j + gap] = a[j];
- j = j - gap;
- }
- a[j + gap] = temp;
- }
- gap = ( gap - 1 ) / 3;
- }
- }
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 ；
快速排序一趟扫描的结果是 F, H, C, D, P, A, M, Q, R, S, Y，X ；
堆排序初始建堆的结果是 A, D, C, R, F, Q, M, S, Y，P, H, X 。
1）算法简介
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
2）算法描述和分析
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
1、初始状态：无序区为R[1..n]，有序区为空。
2、第i趟排序(i=1,2,3...n-1)
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
3、前n-1趟结束，数组有序化了
选择排序的交换操作介于0和(n-1)次之间。选择排序的比较操作为n(n-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。比较次数O(n^2),比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。 交换次数O(n),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。 交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。
|
最差时间复杂度 |
声明：该文观点仅代表作者本人，牛骨文系教育信息发布平台，牛骨文仅提供信息存储空间服务。
copyright © 2008-2019 亿联网络 版权所有 备案号：粤ICP备14031511号-2
|
