面试/笔试数据结构之排序算法篇

2/22/2017来源:ASP.NET技巧人气:1749

面试/笔试数据结构之排序算法篇

面试时数据结构应该是面试官们一定会问到的知识块,最常见的就是对于排序、查找等算法的考察。这里先列出一些常见易考,并且比较重要的排序算法。这里都以排成增序为例,如有错误、不好之处敬请指出。

1、 直接插入排序  假设我们有一个序列{a0,a1,a2,a3……an},将a0看成是一个有序序列,a1~an看成是无序序列,插入排序就是将a1和a0比较,如果比a0小则将其插到a0前面,如果比a0大,则不做事情,这样一次之后前两个位置就是有序的,第三个到第n个仍是无序的。然后,再a2和前两个做比较,将其插入到合适的位置,这样之后,前三个元素都是有序的,第四个到第n个是无序的。如此往复,直到序列有序即可。

void InsertSort(int a[],int len) { int j,temp; for (int i=1; i<len; i++) { if (a[i]<a[i-1]) { temp=a[i]; for (j=i-1; a[j]>temp&&j>=0; j--) { a[j+1]=a[j]; } a[j+1]=temp; } } }12345678910111213141234567891011121314

2、 希尔排序  假设我们有一个序列{a0,a1,a2,a3……an},希尔排序的基本思想是会将序列分割成若干个子序列,然后再对各个子序列进行插入排序。因此希尔排序会有一个增量d,其初始值一般为序列长度的一半,即d=n/2,这样将一个序列分为两个子序列,再分别对两个子序列做插入排序。之后d取值为n/4,再对子序列做插入排序,如此往复,直到d=1,此时序列基本有序,再对其进行一次插入排序即可。

void ShellSort(int a[],int len) { int d; for (d=len/2; d>0; d/=2) {//步长 for (int i=0; i<d; i++) {//直接插入排序 for (int j=i+d; j<len; j+=d) { if (a[j]<a[j-d]) { int temp=a[j]; int k=j-d; while (k>=0&&a[k]>temp) { a[k+d]=a[k]; k-=d; } a[k+d]=temp; } } } } }1234567891011121314151617181912345678910111213141516171819

上面的代码是最能体现希尔排序思想的,下面给出两种稍加改进的代码。

void shellsort1(int a[], int n) { int j, d; for (d = n / 2; d > 0; d /= 2) for (j = d; j < n; j++)//从数组第d个元素开始 if (a[j] < a[j - d])//每个元素与自己组内的数据进行直接插入排序 { int temp = a[j]; int k = j - d; while (k >= 0 && a[k] > temp) { a[k + d] = a[k]; k -= d; } a[k + d] = temp; } } void shellsort2(int a[], int n) { int i, j, d; for (d = n / 2; d > 0; d /= 2) for (i = d; i < n; i++) for (j = i - d; j >= 0 && a[j] > a[j + d]; j -= d) swap(&a[j], &a[j + d]); }1234567891011121314151617181920212223242526272812345678910111213141516171819202122232425262728

3、 冒泡排序  两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

void swap(int *a,int *b) { int temp; temp=*a; *a=*b; *b=temp; } void BubbleSort(int a[],int len) { int i,j; for (i=0;i<len;i++) { for (j=i+1;j<len;j++) { if (a[i]>a[j]) swap(&a[i],&a[j]); } } }1234567891011121314151617181912345678910111213141516171819

下面也给出冒泡排序的另外两种实现。

void BubbleSort1(int a[],int len) { for (int i=0;i<len;i++) { for(int j=len-2;j>=i;j--) { if (a[j]>a[j+1]) //前者与后者比较,这里与前面算法的区别 swap(&a[j],&a[j+1]); } } } void BubbleSort2(int a[],int len) { int flag=1; for (int i=0;i<len &&flag;i++) { flag=0; for (int j=len-2;j>=i;j--) { if (a[j]>a[j+1]) { swap(&a[j],&a[j+1]); flag=1; } } } }123456789101112131415161718192021222324252627123456789101112131415161718192021222324252627

4、 快速排序  假设我们有一个序列{a0,a1,a2,a3……an},在快速排序算法里,我们将第一个元素用作枢轴纪录关键字key,并有一个low指针指向第一个元素,有一个high指针指向最后一个元素,当low < high时,将a[high]和key做比较,如果a[high]>=key,则high–,否则交换low和high位置的元素;当low < high时,将a[low]和key做比较,如果a[low]<=key,则low++,否则交换low和high位置的元素。直到low>=high,一次排序结束,此时key左边的值都比它小,key右边的值都比它大。

int Partiton(int a[],int low,int high) { int key; key=a[low];//枢轴的选取可以选取中间值 while (low<high) { while (low<high &&a[high]>=key) high--; swap(&a[high],&a[low]); while (low<high && a[low]<=key) low++; swap(&a[high],&a[low]); } return low; } void Qsort(int a[],int low,int high) { int pivot; if (low<high) { pivot=Partiton1(a,low,high); Qsort(a,low,pivot-1); Qsort(a,pivot+1,high); } }12345678910111213141516171819202122232425261234567891011121314151617181920212223242526

下面的代码是对快排的一种优化。

int Partiton1(int a[],int low,int high)/*y优化不需要的交换*/ { int temp,key; key=a[low]; temp=key; while (low<high) { while (low<high &&a[high]>=key) high--; a[low]=a[high]; while (low<high && a[low]<=key) low++; a[high]=a[low]; } a[low]=temp; return low; }12345678910111213141516171234567891011121314151617

5、 简单选择排序  假设我们有一个序列{a0,a1,a2,a3……an},简单选择排序就是将这n个元素遍历一遍选出最小的,再和第一个交换;再从剩下2~n个元素中选出最小的和第二个交换,重复以上步骤即可。

void SelectSort(int a[],int len) { int min; for (int i=0;i<len;i++) { min=i; for (int j=i+1;j<len;j++) { if (a[min]>a[j]) min=j; } if (i!=min) swap(&a[min],&a[i]); } }123456789101112131415123456789101112131415

6、 堆排序  输出堆顶的最小值之后,使剩下n-1个元素的序列重又建成一个堆,则得到n个元素中的次小值。如此反复执行,便能得到一个有序序列。

void HeapAdjust(int a[],int s,int m) { int temp,j=0; temp=a[s]; for (j=2*s+1;j<m;j=j*2+1) { if (j<m && a[j]<a[j+1]) ++j; if (j<m && temp>=a[j]) break; a[s]=a[j]; s=j; } a[s]=temp; } void HeapSort(int a[],int len) { int i; for (i=(len)/2-1;i>=0;i--) HeapAdjust(a,i,len); for (i=len-1;i>=1;i--) { swap(&a[0],&a[i]); HeapAdjust(a,0,i-1); } }12345678910111213141516171819202122232425261234567891011121314151617181920212223242526

下面给出上述各种算法的时间复杂度、空间复杂度、稳定性等。  这里写图片描述