关于冒泡排序与快速排序.对于长度为N的线性表,在最坏的情况下,下列各排序法所对应的比较次数中正确的是（）.A冒泡排序为N/2B冒泡排序为NC快速排序为ND快速排序为N（N-1）/2

Question

关于冒泡排序与快速排序.
对于长度为N的线性表,在最坏的情况下,下列各排序法所对应的比较次数中正确的是（）.
A 冒泡排序为N/2
B 冒泡排序为N
C 快速排序为N
D 快速排序为N（N-1）/2

Answer 1

D
快速排序是拿比较向邻1个单元的大小,并按一定方向排列,大小方向不符合的就把2个单元交换,依次比较下去,12,23,34,45,56,67.这样就确定了一个最大(最小)的单元,并把它排列一端,交换次数为N-1,然后在除了最值外的N-1个单位中继续排列,出来第2个最大(最小)值,次数为N-2,以此类推.
总次数为N-1+N-2+N-3+.+1=N(N-1)/2