题目

关于数据结构排序算法的问题
插入排序、选择排序、冒泡排序、基数排序、堆排序的算法中其比较次数与初始数据集顺序无关的是?请说明理由.

提问时间：2021-02-09

答案

选择排序.
选择排序的算法原理是：第一趟从n个待排关键字中找出最小的关键字放到第一个位置,如果要找到最小关键字则必须所有元素都进行比较,所以第一趟要比较n-1次；第二趟从剩下的n-1的元素中再通过n-2次的比较找出最小的元素…………以此类推,不管初始有没有序,它都一共要进行n-1趟排序共n(n-1)/2次比较,时间复杂度始终是O（n平方）
至于其他的,拿插入排序举例：插入排序的基本思想是每次将一个待排的记录按其关键字大小插入到前面已经排好序的子序列中.试想,如果已经排好序的子序列是123,待排记录为45,插入4时,只要和3比较一次就知道排在3后面,对5排序时只要与4比较一次就知道该排在4后面,共比较2次.如果已经排好序的子序列是234,待排记录为15,插入1时,它要从后往前依次比较3次才能找到自己的位置,同样对5排序时只要与4比较一次,共比较4次.由上例可知,插入排序会随着初始数据集的顺序不同而比较次数不同.
BTW,基数排序不是基于关键字比较的排序算法.
纯手打,望采纳,不清楚还可共同探讨.