快速排序法學習筆記

#include<stdio.h>void swap(int *a,int *b) {int t;t=*a;*a=*b;*b=t; }void quickSort(int *nums,int begin,int end) {if(begin>end)return;int tmp=nums[begin];int i,j;i=begin;j=end;while(i!=j){ while(nums[j]<=tmp&&i<j)j--;while(nums[i]>=tmp&&i<j)i++;if(j>i)swap(&nums[i],&nums[j]); }swap(&nums[begin],&nums[i]);quickSort(nums,begin,i-1);quickSort(nums,i+1,end);}int main() {int nums[10]={4,6,1,5,3,0,8,2,7,9};quickSort(nums,0,9);int i;for(i=0;i<10;i++){printf("%d ",nums[i]); }printf("\n");return 0; }

快速排序法是冒泡排序法的升級版本。
冒泡排序法是從數組的一段開始遍歷，比較相鄰兩個數的大小。
而快速排序法是，選擇任意一個數為參照，這里記為tmp，從數組的兩端開始比較，兩邊同時開始遍歷，通過將比tmp大的數放到右邊，將比tmp小的數放到左邊，結合遞歸的思想 ，不斷引用自身函數實現全體數組的排序。

寫代碼時需要注意:

讓左哨兵巡邏時，是讓左哨兵先巡邏，還是讓右哨兵先巡?

---

while(i!=j) { while(nums[j]<=tmp&&i<j)j--;while(nums[i]>=tmp&&i<j)i++;if(j>i)swap(&nums[i],&nums[j]); }

---

假設參考值選擇為數組的第一個數，即nums[0]
(哈哈一般都是這么選的)

參數i從左邊開始遍歷，找到比參考值大的數停下
參數j從右邊開始遍歷，找到比參考值小的數停下

就好像是兩個哨兵，一個從國界左邊開始巡邏，一個從國界右邊開始巡邏，當遇到不符合要求的對象時停下（即左哨兵發(fā)現對象比參考數tmp大，右哨兵發(fā)現對象沒比參考數tmp小）

這時，只需要將左右哨兵所在的位置的對象（數組值num[i],num[j]）進行交換，就能滿足，左邊的數不大于參考數tmp，右邊的數不小于參考數tmp
（一般都是這樣ha，也可以相反）

接著繼續(xù)巡邏，直到兩個哨兵相遇，該位置記為locate1，就把整個國界走過一遍（數組遍歷，與參考值tmp比較了一遍），結果是左邊的所有數都不大于參考值tmp，右邊的所有數都不小于參考值tmp，*除了數組的第一個數nums[0]，因為他被選做參考數tmp

---

while(i!=j) { while(nums[j]<=tmp&&i<j)j--;while(nums[i]>=tmp&&i<j)i++;if(j>i)swap(&nums[i],&nums[j]); }

---

這里討論一下選做參考數的數組的第一個數nums[0]應該怎么處理
首先，處理目標：讓nums[0]的數值tmp,調換到中間，使?jié)M足左邊的數都不大于tmp,右邊的數都不小于tmp
其次，處理對象：第一個數nums[0],哨兵相遇的位置上的數nums[locate1]

對于nums[locate1],c語言是面向過程的程序設計語言，代碼是依次執(zhí)行，必然存在左哨兵先巡邏至停下，或者右哨兵先巡邏至停下的情況,而這兩種情況對應的nums[locate1]與tmp的大小關系也不相同

第一種情況 左邊哨兵先巡邏，先停下
還記得左邊哨兵的終止條件么？
因為對象表示的數大于參考值時，左哨兵停下，
所以左哨兵先巡邏先停下的結果是，左右哨兵最后相遇時，

對象nums[locate1]是比參考值大的數
這時如果將 該對象的位置上的值nums[locate1]與參考值nums[0]（數組第一個數的值）進行交換，結果是，該對象的位置，locate1右邊的數都不小于參考數(滿足要求了），該位置locate1上的數nums[locate1]等于參考數(也滿足要求了），
然而locate1左邊,第一個數nums[0]大于參考數tmp

如果想實現 讓參考數左邊的數都不大于他，參考數的右邊的數都不小于他，必須進一步處理，將第一個數換成不大于參考數的數

第二種情況，右邊哨兵先巡邏，先停下
同理，這種情況，兩哨兵最終相遇時，nums[locate1]<=tmp
這時只需要將 nums[0] (之前設為參考值tmp)與nums[locate1]交換即可滿足，將參考值tmp調換到了中間位置，而且參考值tmp左邊都不大于參考值tmp,右邊都不小于參考值tmp
顯然這種思路要簡便許多
而本文最初的代碼就采用了這種思路

---

while(i!=j) { while(nums[j]<=tmp&&i<j)j--;while(nums[i]>=tmp&&i<j)i++;if(j>i)swap(&nums[i],&nums[j]); } ---

這是我在學習快速排序法中的一些心得體會，
總結了在學習中遇到的讓左哨兵先巡邏還是右哨兵先巡邏的問題，另外我在敲代碼時還犯了將哨兵巡邏 while語句中的臨界條件nums[j]<=tmp錯寫成<的錯誤
總結經驗，繼續(xù)努力嘍~

總結

以上是生活随笔為你收集整理的探索初级算法学习笔记-快速排序法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。