单选题 按排序策略分类，起泡排序属于______。对n个元素的序列进行排序时，如果待排序元素序列的初始排列已经全部有序，则起泡排序过程中需进行n-1次元素值的比较，0次元素值的交换。如果待排序元素序列的初始排列完全逆序，则起泡排序过程中需进行n(n-1)/2次元素值的比较，n(n-1)/2次元素的交换。
  • A.插入排序
  • B.选择排序
  • C.交换排序
  • D.分配排序
【正确答案】 C
【答案解析】[解析] 起泡排序属于交换类排序，在排序过程中元素按排序码值两两比较，发现逆序则交换。这一类排序方法还有快速排序。当待排序元素的初始排列已经有序时，起泡排序的排序码比较次数为n-1，元素交换次数为0。当待排序元素的初始排列完全逆序时，起泡排序的排序码比较次数为(n-1)+(n-2)+…+1+0=n(n-1)/2。在排序过程中，每次比较发现逆序即交换，所以在最坏情况下，比较n(n-1)/2次需交换n(n-1)/2次。