其他排序面试题

001什么是时间复杂度？

时间复杂度指执行这个算法需要消耗多少时间，也可以认为是对排序数据的总的操作次数。常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)。

//时间复杂度O(1)
sum = n*(n+1)/2; 
//时间复杂度O(n)
for(int i = 0; i < n; i++){ 
    System.out.println("%d ",i);
} 
//时间复杂度O(n^2)
for(int i = 0; i < n; i++){ 
    for(int j = 0; j < n; j++){ 
        System.out.println("%d ",i); 
    }
} 
//运行次数为(1+n)*n/2//时间复杂度O(n^2)
for(int i = 0; i < n; i++){ 
    for(int j = i; j < n; j++){ 
        System.out.println("%d ",i); 
    }
} 
//设执行次数为x. 2^x = n 即x = log2n,时间复杂度O(log2n)
int i = 1, n = 100;
while(i < n){ 
    i = i * 2;
}

002常见的时间复杂度排序?

O（1）< O（logn）<O（n）<O（nlog2n）<O（n2）<O（n3）<…<O（2n）<O（n!）

003空间复杂度是什么？

空间复杂度是指算法在计算机内执行时所需存储空间的度量，它也是问题规模n的函数

常见的空间复杂度有：常量空间复杂度O(1)、对数空间复杂度O(log2N)、线性空间复杂度O(n)。

004时间复杂度和空间复杂度关系？

对于一个算法来说，空间复杂度和时间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。有时我们可以用空间来换取时间以达到目的。

005什么是算法稳定性？

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。排序算法是否为稳定的是由算法具体实现决定的。总体上，堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法，而冒泡排序、直接插入排序、归并排序、基数排序、计数排序、桶排序是稳定的排序算法。

006比较排序和非比较排序的区别？

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。如冒泡排序、选择排序、插入排序、归并排序、堆排序、快速排序

非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 如计数排序、基数排序、桶排序

007十大排序的复杂度及稳定性？

008下列哪种排序算法不是稳定的？

A. 基数排序
B. 冒泡排序
C. 选择排序
D. 归并排序
答案：C
解析：选择排序是不稳定的，如{2*，2,1}，第一次遍历将2*与1互换，结果为{1,2,2*}，2与2*位置互换
其余排序均是稳定的

009在各自最优条件下,对N个数进行排序,哪个算法复杂度最低的是? （）

A. 插入排序
B. 快速排序
C. 堆排序
D. 归并排序
答案：A
解析：插入排序：最佳O（N）
         快速排序：最佳O（NlogN）
         堆    排序：最佳O（NlogN）
         归并排序：最佳O（NlogN），因此选择插入排序。