单选题
高中信息技术
2023-02-03
对长度为n的线性表做快速排序，在最坏情况下的交换次数是（）。
A．n
B．n-1
C．n(n-1)
D．n(n-1)／2
参考答案
D
答案解析
快速排序的基本思路是：在待排序的n条记录中任选一条记录(通常取第一条记录)，以该记录的关键字值为基准，用交换的方法将所有记录分成两部分，使所有关键字值比基准小的记录均排在基准记录之前，所有关键字值比基准大的记录都排在基准记录之后，基准记录在两部分中间，其位置为该基准记录的最终位置，它不再参加以后的排序，这就完成了一趟排序。接着对所划分的前后两部分分别重复上面的操作，直到每部分内只有一条记录为止，排序结束。在最坏的情况下，每次划分选取的基准记录都是当前无序区中最小(或最大)的记录，划分的结果是基准记录左边的无序子区为空(或右边的无序子区为空)，另外一方的无序子区中记录数目仅仅比划分前的无序区中的记录个数少1个。在此情况下，快速排序必须进行n-1趟排序，每趟需比较并交换n-1次，需要交换的总次数为(n-1)+(n-2)+(n-3)+…1=n(n-1)／2。
你可能感兴趣的试题
A．in range(1，4)
B．in range(1，5)
C．in random．uniform(1，4)
D．in random．uniform(1，5)
