C/C++面试经典排序算法

2016-10-10 22:59 阅读 857 次 评论 0 条

首先说下稳定排序和非稳定排序,简单地说就是所有相等的数经过某种排序方法后,仍能保持它们在排序之前的相对次序,我们就说这种排序方法是稳定的。反之,就是非稳定的。几个基本常见的排序,插入排序(包括直接插入,希尔插入,折半插入等),交换排序(包括冒泡排序,快速排序),选择排序(简单选择,堆排序,树形排序等),归并排序,基数排序(多关键字,链式基数)。

1.直接插入排序(稳定排序)

简单的说就是将序列分为有序序列和无序序列。每一趟排序都是将无序序列的第一个元素插入有序序列中。R[1… i-1]  <-  R[i…n] , 每次取R[i]插入到R[1… i-1]中。

步骤如下:1>在R[1 … i-1]中找到R[i]的插入位置k (0<k<i) 2>将R[k … i-1]均后移一位,K位置上插入R[i]

改进版:1>在R[1 … i-1]中将R[i]从右向左一一比较,R[j] >R[i],则R[j]后移一位(j = i-1开始)2>如果R[j] <=R[i],则j+1 为R[i]的插入位置

实现如下(包括测试):

2.希尔排序(不稳定排序)

希尔排序算法是先将要排序的一组数按照某个增量d分成若干组,对每组中的元素进行排序,然后在用更小的增量来进行再次分组,并给每个分组重新排序,直到增量为1时,整个要排序的数被分成一组,排序结束。

形象点说,例如[R1 ,R2 , R3, R4,R5,R6,R7,R8],先增量d =len/2 =4 ,则先分成[R1 R5] ,[R2 R6] ,[R3 R7] ,[R4 R8]四组,进行组内排序;再d=d/2 =2,分成[R1 R3 R5R7] 和 [R2 R4 R6 R8]两组,组内排序;再d=d/2=1,整个数组只剩一个大的分组[R1 , R2 , R3, R4,R5,R6,R7,R8],组内排序。全部结束。

实现如下(包括测试):

3. 冒泡排序(稳定排序)

冒泡排序也叫起泡排序,顾名思义,就是每一趟,从左到右,两两比较,大的(小的)后移,最后最轻的气泡到最后的位置R[i],为最大或最小值,然后下一趟,选出次大的到R[i-1],以此,到最后R[1],至此全部有序。(按照递增递减都可以)

实现如下:

如果中间的某一趟扫描之前,数组已经全部有序,后面的扫描则没有必要。此时可以加一个标记,来判断是否提前结束循环。改进:

4.快速排序(不稳定排序)

快速排序是一种划分交换排序,采用的是分治法的策略。该方法的基本思想是:

1.先从数列中取出一个数作为基准数。

2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。

3.再对左右区间重复第二步,直到各区间只有一个数。

以一个数组作为示例,取区间第一个数为基准数(pivot)。

0

1

2

3

4

5

6

7

8

9

72

6

57

88

60

42

83

73

48

85

初始时,i = 0;  j =9;   X = a[i] = 72

由于已经将a[0]中的数保存到X中,可以理解成在数组a[0]上挖了个坑,可以将其它数据填充到这来。从j开始向前找一个比X小或等于X的数。当j=8,符合条件,将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8];i++; 这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数,当i=3,符合条件,将a[3]挖出再填到上一个坑中a[8]=a[3];j--;

数组变为:

0

1

2

3

4

5

6

7

8

9

48

6

57

88

60

42

83

73

88

85

 i = 3;   j =7;   X=72

再重复上面的步骤,先从后向前找,再从前向后找。

从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++;

从i开始向后找,当i=5时,由于i==j退出。

此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将X填入a[5]。

数组变为:

0

1

2

3

4

5

6

7

8

9

48

6

57

42

60

72

83

73

88

85

可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。a[5]已经确定好位置。后面每一趟也是。

对挖坑填数进行总结:

1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。

3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。

4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。
具体实现如下(测试不重复,在前面的代码上加个函数,都测试过):

5.直接选择排序(不稳定排序)

选择排序的基本思想:每一次从待排序的记录中选出关键字最小的记录,顺序的放在有序的序列的最后,直至全部记录排序完毕。

而直接选择排序就是n条记录经过n-1次后,直接得到有序记录。

实现如下:

6.堆排序(不稳定排序)

堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将A[n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素。

堆的定义如下:n个关键字序列A[n]成为堆,当且仅当该序列满足:
①L(i) <= L(2i)且L(i) <= L(2i+1)  或者  ②L(i) >=L(2i)且L(i) >= L(2i+1)  其中i属于[1, n/2]。

满足第①种情况的堆称为小根堆(小顶堆),满足第②种情况的堆称为大根堆(大顶堆)。

如上的小根堆或大根堆,输出堆顶的最小(大)值之后,使得剩下的n-1个元素的序列重新建成一个新的堆,则又得到n个数中的次小(大)值,如此反复,最后得到的有序序列,这个过程就是堆排序。

代码实现:

7.归并排序(稳定排序)

归并是指将若干个已排序的子文件合并成一个有序的文件。常见的归并排序有两路归并排序。

归并操作的基本步骤如下:
1.申请两个与已经排序序列相同大小的空间,并将两个序列拷贝其中;
2.设定最初位置分别为两个已经拷贝排序序列的起始位置,比较两个序列元素的大小,依次选择相对小的元素放到原始序列;
3.重复2直到某一拷贝序列全部放入原始序列,将另一个序列剩下的所有元素直接复制到原始序列尾。

设归并排序的当前区间是R[low..high],三个步骤分别是:
1.分解:将当前区间一分为二,即求分裂点
2.求解:递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序;
3.组合:将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。
递归的终结条件:子区间长度为1(一个记录自然有序)。

代码实现:

8.基数排序(可靠排序)

转自:http://blog.csdn.NET/u012580566/article/details/47702955

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:C/C++面试经典排序算法 | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情