面试必考题目+各种排序实例及点评

1.按平均时间将排序分为4类；

A．平方阶O(n^2)排序：一般为简单的排序，例如直接插入、直接选择和冒泡排序；

B．线性对数阶O(nlgn)排序：如快速、堆和归并排序；

C．O(n^m)阶排序：m位于0和1之间的常数，即0

A．若n较小时(n<50),可采用直接插入或直接选择排序。

当记录规模较小时，直接插入排序较好。否则因为直接选择移动的记录数少于直接插入，应直接选择选择排序为宜。

B．若文件的初始状态基本有序(指正序)，则应选择直接插入排序，冒泡排序或随机的快速排序为宜。

C．若n较大时，应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。

快速排序被认为是目前基于比较的内部排序中最好的方法。当待排序的关键字随机分布时，快速排序的平均时间最短。

堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。

若要求排序稳定，则可选用归并排序。

shell排序：分组的直接插入排序，在n比较大的时候较直接插入排序有较大的改进，它是不稳定的。最好的时间复杂度是O(n)，最坏的是O(n^2)。

3.插入排序、冒泡排序、归并排序是稳定的，选择排序、希尔排序、快速排序、堆排序时不稳定的 4.各种排序算法如下：

a. shell排序：分组的直接插入排序，在n比较大的时候较直接插入排序有较大的改进，它是不稳定的。最好的时间复杂度是O(n)，最坏的是O(n^2)。 #include

void shell_sort(int a[],int len) { int h,i,j,temp; for(h=len/2;h>0;h=h/2) {

for (i=h;i=0&&temp

void print_array(int a[],int len) { for (int i=0;ivoid main() { int a[]={7,3,5,8,9,1,2,4,6}; cout<<\ print_array(a,9); shell_sort(a,9); cout<<\ print_array(a,9); }

b.直接插入排序： #include

void insert_sort(int a[],int len) { int i,j,temp; for (i=1;i=0&&temp

}

void print_array(int a[],int len) { for (int i=0;ivoid main() { int a[]={7,3,5,8,9,1,2,4,6}; cout<<\ print_array(a,9); insert_sort(a,9); cout<<\ print_array(a,9); }

c.交换排序中的冒泡排序：是就地排序，且是稳定的，由于他的记录移动次数较多，故平均时间性能比直接插入排序要差的多，最好的时间复杂度是O(n),最差是O(n^2),平均时间复杂度是O(n^2)

#include

void bubble_sort(int a[],int len) { int i,j,temp; for (i=0;ii;j--) { if (a[j]

void print_array(int a[],int len) { for (int i=0;i

} cout<

void main() { int a[]={7,3,5,8,9,1,2,4,6}; cout<<\ print_array(a,9); bubble_sort(a,9); cout<<\ print_array(a,9); }

d.交换排序中的quick_sort 是一种不稳定的排序方法，平均时间复杂度是O(n*lgn/lg2) 最差情况时间复杂度是O(n^2) #include

void quick_sort(int a[],int low,int high) { int i,j,pivot; if(low=pivot) j--; if(i

void print_array(int a[],int len) { for (int i=0;i

} cout<

void main() { int a[]={54,38,96,23,15,72,60,45,83}; cout<<\ print_array(a,9); quick_sort(a,0,8); cout<<\ print_array(a,9); }

e.直接选择排序： #include

void select_sort(int a[],int len) {

int i,j,x,l; for (i=0;i

void print_array(int a[],int len) { for (int i=0;ivoid main() { int a[]={54,38,96,23,15,72,60,45,83};