下面的排方法中,最坏的情况下比较次数最少的是( ) A冒泡排序 B简单选择排序 C直接插入排序 D 堆排序并帮我解释一下为什么原因,分别在最坏的情况下的次数分别是多少啊?
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/04 23:10:21
![下面的排方法中,最坏的情况下比较次数最少的是( ) A冒泡排序 B简单选择排序 C直接插入排序 D 堆排序并帮我解释一下为什么原因,分别在最坏的情况下的次数分别是多少啊?](/uploads/image/z/805045-13-5.jpg?t=%E4%B8%8B%E9%9D%A2%E7%9A%84%E6%8E%92%E6%96%B9%E6%B3%95%E4%B8%AD%2C%E6%9C%80%E5%9D%8F%E7%9A%84%E6%83%85%E5%86%B5%E4%B8%8B%E6%AF%94%E8%BE%83%E6%AC%A1%E6%95%B0%E6%9C%80%E5%B0%91%E7%9A%84%E6%98%AF%EF%BC%88+%EF%BC%89+A%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F+B%E7%AE%80%E5%8D%95%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F+C%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F+D+%E5%A0%86%E6%8E%92%E5%BA%8F%E5%B9%B6%E5%B8%AE%E6%88%91%E8%A7%A3%E9%87%8A%E4%B8%80%E4%B8%8B%E4%B8%BA%E4%BB%80%E4%B9%88%E5%8E%9F%E5%9B%A0%2C%E5%88%86%E5%88%AB%E5%9C%A8%E6%9C%80%E5%9D%8F%E7%9A%84%E6%83%85%E5%86%B5%E4%B8%8B%E7%9A%84%E6%AC%A1%E6%95%B0%E5%88%86%E5%88%AB%E6%98%AF%E5%A4%9A%E5%B0%91%E5%95%8A%3F)
下面的排方法中,最坏的情况下比较次数最少的是( ) A冒泡排序 B简单选择排序 C直接插入排序 D 堆排序并帮我解释一下为什么原因,分别在最坏的情况下的次数分别是多少啊?
下面的排方法中,最坏的情况下比较次数最少的是( ) 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)