快捷導(dǎo)航

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

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

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

快速排序是對(duì)冒泡法排序的一種改進(jìn)。

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

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

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

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

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

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

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

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

為了能夠加深讀者的理解，接下來通過一段代碼來了解快速排序的具體實(shí)現(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;
}

運(yùn)行結(jié)果：

排序前

32 12 7 78 23 45

排序后

7 12 23 32 45 78

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

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