快速排序法c語言？快速排序是基于分治技術(shù)的重要排序算法，排序算法按照元素的值對它們進行劃分。劃分是對給定數(shù)組中的元素的重新排序，使得A [ s ] A[s]A[s]左邊的元素都小于等于A [ s ]

快速排序法c語言？

快速排序是基于分治技術(shù)的重要排序算法，排序算法按照元素的值對它們進行劃分。

劃分是對給定數(shù)組中的元素的重新排序，使得A [ s ] A[s]A[s]左邊的元素都小于等于A [ s ] A[s]A[s]，而右邊A [ s ] A[s]A[s]右邊的元素都大于等于A [ s ] A[s]A[s]。

顯然，建立了一個劃分以后，A [ s ] A[s]A[s]已經(jīng)位于它在有序數(shù)組中的最終結(jié)果，接下來我們可以繼續(xù)對A [ s ] A[s]A[s]前和A [ s ]A[s]A[s]后的子數(shù)組分別進行排序(例如，使用同樣的方法)。

注意，它和合并排序不同之處在：

在合并排序算法中，將問題劃分為兩個子問題，是很快的，算法的主要工作在于合并子問題的解；

在快速排序中，算法的主要工作在于劃分階段，而不需要再去合并子問題的解了。

在快速排序、堆排序、歸并排序中，什么排序是穩(wěn)定的？

• 歸并排序是穩(wěn)定的“快速排序和堆排序都不穩(wěn)定.不穩(wěn)定：就是大小相同的兩個數(shù)，經(jīng)過排序后，最終位置與初始位置交換了。
• 快速排序：27 23 27 3以第一個27作為pivot中心點，則27與后面那個3交換，形成3 23 27 27，排序經(jīng)過一次結(jié)束，但最后那個27在排序之初先于初始位置3那個27，所以不穩(wěn)定。
• 堆排序：比如：3 27 36 27，如果堆頂3先輸出，則，第三層的27（最后一個27）跑到堆頂，然后堆穩(wěn)定，繼續(xù)輸出堆頂，是剛才那個27，這樣說明后面的27先于第二個位置的27輸出，不穩(wěn)定?！薄? 歸并排序（MergeSort）
• 歸并排序先分解要排序的序列，從1分成2，2分成4，依次分解，當分解到只有1個一組的時候，就可以排序這些分組，然后依次合并回原來的序列中，這樣就可以排序所有數(shù)據(jù)。合并排序比堆排序稍微快一點，但是需要比堆排序多一倍的內(nèi)存空間，因為它需要一個額外的數(shù)組?！?/li>

• 以Ai與Aj為例子快速排序有兩個方向，左邊的i下標一直往右走，當a[i] <= a[center_index]，其中center_index樞元素的數(shù)組下標，一般取為數(shù)組第0個元素。而右邊的j下標一直往左走，當a[j] > a[center_indexij都走不動了，i <= j， 交換a[i]和a[j]，重復上面的過程，直到i>j。
• 交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩(wěn)定性打亂，比如序列5 3 3 4 3 8 9 10 11，現(xiàn)在中樞元素5和3(第5個元素，下標從1開始計)交換就會把元素3的穩(wěn)定性打亂，所以快速排序是一個不穩(wěn)定的排序算法，不穩(wěn)定發(fā)生在中樞元素和a[j]交換的時刻。