C語言快速排序算法及代碼

相關推薦

C語言快速排序算法及代碼

　　快速排序是對冒泡法排序的一種改進。那么有關C語言快速排序算法和代碼分別又是怎樣的呢？以下僅供參考！

　　快速排序算法的基本思想是：將所要進行排序的數分為左右兩個部分，其中一部分的所有數據都比另外一部分的數據小，然后將所分得的兩部分數據進行同樣的劃分，重復執行以上的劃分操作，直到所有要進行排序的數據變為有序為止。

　　可能僅根據基本思想對快速排序的認識并不深，接下來以對n個無序數列A[0], A[1]…, A[n-1]采用快速排序方法進行升序排列為例進行講解。

　　(1)定義兩個變量low和high，將low、high分別設置為要進行排序的序列的起始元素和最后一個元素的下標。第一次，low和high的取值分別為0和n-1，接下來的每次取值由劃分得到的序列起始元素和最后一個元素的下標來決定。

　　(2)定義一個變量key，接下來以key的取值為基準將數組A劃分為左右兩個部分，通常，key值為要進行排序序列的第一個元素值。第一次的取值為A[0]，以后毎次取值由要劃分序列的起始元素決定。

　　(3)從high所指向的數組元素開始向左掃描，掃描的同時將下標為high的數組元素依次與劃分基準值key進行比較操作，直到high不大于low或找到第一個小于基準值key的數組元素，然后將該值賦值給low所指向的數組元素，同時將low右移一個位置。

　　(4)如果low依然小于high，那么由low所指向的數組元素開始向右掃描，掃描的同時將下標為low的數組元素值依次與劃分的基準值key進行比較操作，直到low不小于high或找到第一個大于基準值key的數組元素，然后將該值賦給high所指向的數組元素，同時將high左移一個位置。

　　(5)重復步驟(3) (4)，直到low的植不小于high為止，這時成功劃分后得到的左右兩部分分別為A[low……pos-1]和A[pos+1……high]，其中，pos下標所對應的數組元素的值就是進行劃分的基準值key，所以在劃分結束時還要將下標為pos的數組元素賦值為 key。

　　(6)將劃分得到的左右兩部分A[low……pos-1]和A[pos+1……high]繼續采用以上操作步驟進行劃分，直到得到有序序列為止。

　　為了能夠加深讀者的理解，接下來通過一段代碼來了解快速排序的具體實現方法。

　　#include

　　#define N 6

　　int partition(int arr[], int low, int high){

　　int key;

　　key = arr[low];

　　while(low<high){

　　while(low= key )

　　high--;

　　if(low<high)

　　arr[low++] = arr[high];

　　while( low<high && arr[low]<=key )

　　low++;

　　if(low<high)

　　arr[high--] = arr[low];

　　}

　　arr[low] = key;

　　return low;

　　}

　　void quick_sort(int arr[], int start, int end){

　　int pos;

　　if (start<end){

　　pos = partition(arr, start, end);

　　quick_sort(arr,start,pos-1);

　　quick_sort(arr,pos+1,end);

　　}

　　return;

　　}

　　int main(void){

　　int i;

　　int arr[N]={32,12,7, 78, 23,45};

　　printf("排序前 ");

　　for(i=0;i<N;i++)

　　printf("%d ",arr[i]);

　　quick_sort(arr,0,N-1);

　　printf(" 排序后 ");

　　for(i=0; i<N; i++)

　　printf("%d ", arr[i]);

　　printf (" ");

　　system("pause");

　　return 0;

　　}

　　運行結果：

　　排序前

　　32 12 7 78 23 45

　　排序后

　　7 12 23 32 45 78

　　在上面的代碼中，根據前面介紹的步驟一步步實現了快速排序算法。接下來通過示意圖來演示第一次劃分操作。

　　在第一次劃分操作中，先進行初始設置，key的值是進行劃分的基準，其值為要劃分數組的第一個元素值，在上面的排序序列中為第一個元素值32，同時將low設置為要排序數組中第一個元素的下標，第一次排序操作時其值為0，將high設置為要排序序列最后一個元素的下標，在上面的排序序列中其第一次取值為5。先將下標為high的數組元素與key進行比較，由于該元素值大于key，因此high向左移動一個位置繼續掃描。由于接下來的值為 23，小于key的值，因此將23賦值給下標為low所指向的數組元素。接下來將low右移一個位置，將low所指向的數組元素的值與key進行比較，由干接下來的12、7都小于key，因此low繼續右移掃描，直至下標low所指向的數組元素的值為78即大于key為止，將78賦值給下標為high所指向的數組元素，同時將high左移一個位置。接下來由于low不再小于high，劃分結束。需要注意的是，在進行劃分的過程中，都是將掃描的值與key的值進行對比，如果小于key，那么將該值賦值給數組中的另外一個元素，而該元素的值并沒有改變。從圖中可以看出這一點，所以需要在劃分的最后將作為劃分基準的key值賦值給下標為 pos的數組元素，這個元素不再參與接下來的劃分操作。

【C語言快速排序算法及代碼】相關文章：

C語言快速排序實例代碼02-26

C語言選擇排序算法及實例代碼07-25

C語言插入排序算法及實例代碼07-02

C語言奇偶排序算法詳解及實例代碼04-05

桶排序算法的理解及C語言版代碼示例07-11