快捷導(dǎo)航

C 語言快速排序?qū)嵗a

更新時間：2016年07月18日 15:12:20 投稿：lqh

本文主要介紹了C語言的快速排序算法,這里給大家舉例說明并附代碼實例,需要的朋友可以參考下

快速排序是對冒泡法排序的一種改進。

快速排序算法的基本思想是：將所要進行排序的數(shù)分為左右兩個部分，其中一部分的所有數(shù)據(jù)都比另外一部分的數(shù)據(jù)小，然后將所分得的兩部分數(shù)據(jù)進行同樣的劃分，重復(fù)執(zhí)行以上的劃分操作，直到所有要進行排序的數(shù)據(jù)變?yōu)橛行驗橹埂?/span>

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

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

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

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

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

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

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

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

#include <stdio.h>
#include <stdlib.h>
#define N 6
int partition(int arr[], int low, int high){
  int key;
  key = arr[low];
  while(low<high){
    while(low <high && arr[high]>= 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("排序前 \n");
  for(i=0;i<N;i++)
    printf("%d\t",arr[i]);
  quick_sort(arr,0,N-1);
  printf("\n 排序后 \n");
  for(i=0; i<N; i++)
    printf("%d\t", arr[i]);
  printf ("\n");
  system("pause");
  return 0;
}

運行結(jié)果：

排序前

32 12 7 78 23 45

排序后

7 12 23 32 45 78

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

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