下面的排方法中,最坏的情况下比较次数最少的是（ ） A冒泡排序 B简单选择排序 C直接插入排序 D 堆排序

下面的排方法中,最坏的情况下比较次数最少的是（ ） A冒泡排序 B简单选择排序 C直接插入排序 D 堆排序
并帮我解释一下为什么原因,分别在最坏的情况下的次数分别是多少啊?

从原理上给你推导下：
1.冒泡法：这是最原始,也是众所周知的最慢的算法了.他的名字的由来因为它的工作看来象是冒泡：#include void BubbleSort(int* pData,int Count) { int iTemp; for(int i=1;i =i;j--) { if(pData[j] 7,8,10,9(交换2次) 第一轮：7,8,10,9->7,8,9,10(交换1次) 循环次数：6次 交换次数：6次 其他：第一轮：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次) 第二轮：7,8,10,9->7,8,10,9->7,8,10,9(交换0次) 第一轮：7,8,10,9->7,8,9,10(交换1次) 循环次数：6次 交换次数：3次 上面我们给出了程序段,现在我们分析它：这里,影响我们算法性能的主要部分是循环和交换,显然,次数越多,性能就越差.从上面的程序我们可以看出循环的次数是固定的,为1+2+...+n-1.写成公式就是1/2*(n-1)*n.现在注意,我们给出O方法的定义：若存在一常量K和起点n0,使当n>=n0时,有f(n) 7,10,8,9(交换1次) 第二轮：7,10,8,9->7,8,10,9->7,8,10,9(交换1次) 第一轮：7,8,10,9->7,8,9,10(交换1次) 循环次数：6次 交换次数：3次 从运行的表格来看,交换几乎和冒泡一样糟.事实确实如此.循环次数和冒泡一样 也是1/2*(n-1)*n,所以算法的复杂度仍然是O(n*n).由于我们无法给出所有的情况,所以 只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好,在某些情况下稍差）.3.选择法：现在我们终于可以看到一点希望：选择法,这种方法提高了一点性能（某些情况下） 这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换,在从省下的部分中 选择最小的与第二个交换,这样往复下去.#include void SelectSort(int* pData,int Count) { int iTemp; int iPos; for(int i=0;i (iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次) 第二轮：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次) 第一轮：7,8,10,9->(iTemp=9)7,8,9,10(交换1次) 循环次数：6次 交换次数：3次 遗憾的是算法需要的循环次数依然是1/2*(n-1)*n.所以算法复杂度为O(n*n).我们来看他的交换.由于每次外层循环只产生一次交换（只有一个最小值）.所以f(n) 7,8,9,10(交换1次)(循环1次) 循环次数：4次 交换次数：2次 上面结尾的行为分析事实上造成了一种假象,让我们认为这种算法是简单算法中最好的,其实不是,因为其循环次数虽然并不固定,我们仍可以使用O方法.从上面的结果可以看出,循环的次数f(n)