1. 首頁 > 生活百科 >

快速排序算法的性能取決于

百科


快速排序算法的性能取決于劃分的對稱性 。
快速排序（Quicksort）是對冒泡排序的一種改進 。快速排序由C、A、R、Hoare在1960年提出 。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序 ， 整個排序過程可以遞歸進行，以此達到整個數據變成有序序列 。

快速排序算法通過多次比較和交換來實現排序，其排序流程如下：

1、首先設定一個分界值，通過該分界值將數組分成左右兩部分 。
2、將大于或等于分界值的數據集中到數組右邊，小于分界值的數據集中到數組的左邊 。此時 ， 左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值 。

【快速排序算法的性能取決于】3、然后，左邊和右邊的數據可以獨立排序 。對于左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值 。右側的數組數據也可以做類似處理 。
4、重復上述過程，可以看出，這是一個遞歸定義 。通過遞歸將左側部分排好序后 ， 再遞歸排好右側部分的順序 。當左、右兩個部分各數據排序完成后，整個數組的排序也就完成了 。

    推薦閱讀