題目

排序過程中，對(duì)尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一“趟”。下列排序中，不可能是快速排序第二趟結(jié)果的是（）【2019年全國(guó)試題10（2分）】

A. 5, 2, 16, 12, 28, 60, 32, 72
B. 2, 16, 5, 28, 12, 60, 32, 72
C. 2, 12, 16, 5, 28, 32, 72, 60
D. 5, 2, 12, 28, 16, 32, 72, 60

題解

答案：D，分析如下。

每經(jīng)過一趟快排，軸點(diǎn)元素都必然就位。也就是說，一趟下來至少有1個(gè)元素在其最終位置。所以考察各個(gè)選項(xiàng)，看有幾個(gè)元素就位即可。

最終排序位置是：2, 5, 12, 16, 28, 32, 60, 72，而選項(xiàng)中正確的位置有：

A. 5, 2, 16, 12, 28, 60, 32, 72
B. 2, 16, 5, 28, 12, 60, 32, 72
C. 2, 12, 16, 5, 28, 32, 72, 60
D. 5, 2, 12, 28, 16, 32, 72, 60

• 第一趟排序，確定一個(gè)元素位置
• 第二趟排序，又確定一個(gè)或兩個(gè)元素位置
  • 當(dāng)?shù)谝惶嗽卮_認(rèn)的位置為最左或最右時(shí)，第二趟排序只能確認(rèn)一個(gè)位置（A，B選項(xiàng)情況）
  • 當(dāng)?shù)谝惶嗽卮_認(rèn)位置不是最左或最右時(shí)，第二趟能確認(rèn)2個(gè)位置（C選項(xiàng)情況）

所以，兩趟排序共確認(rèn)2或3個(gè)元素位置。

總結(jié)

以上是生活随笔為你收集整理的数据结构：下列选项中，不可能是快速排序第2趟排序结果的是（2019年全国试题10）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。