C/C 十大經典演算法之快速排序

NO IMAGE

一、該方法的基本思想是:

1.先從數列中取出一個數作為基準數。

2.分割槽過程,將比這個數大的數全放到它的右邊,小於或等於它的數全放到它的左邊。

3.再對左右區間重複第二步,直到各區間只有一個數。

二、圖說:

三、為什麼採用快速排序?

首先快速排序的穩定度並不高,快速排序之所比較快,因為相比氣泡排序,每次交換是跳躍式的。每次排序的時候設定一個基準點,將小於等於基準點的數全部放到基準點的左邊,將大於等於基準點的數全部放到基準點的右邊。這樣在每次交換的時候就不會像氣泡排序一樣每次只能在相鄰的數之間進行交換,交換的距離就大的多了。因此總的比較和交換次數就少了,速度自然就提高了。當然在最壞的情況下,仍可能是相鄰的兩個數進行了交換。因此快速排序的最差時間複雜度和氣泡排序是一樣的都是O(N2),它的平均時間複雜度為O(NlogN)。其實快速排序是基於一種叫做“二分”的思想。

程式碼實現:

//快速排序.cpp:定義控制檯應用程式的入口點。

//作者:Hacker.ST.Tan

 

#include”stdafx.h”

#include<iostream>

#include<time.h>

#include<windows.h>

#defineMAX10

 

void QuickSort(intArray[],int left,intright);

void Output(intArray[],int Length);

void Ran_Array(intArray[],int Length);

 

int main(){

   intArray[MAX];

   intLength =sizeof(Array) /sizeof(int);

   printf(“產生的隨機陣列為:\n”);

   Ran_Array(Array,Length);

   Output(Array,Length);

   printf(“排序後為:\n”);

   QuickSort(Array,0,Length-1);

   Output(Array,Length);

   system(“pause”);

   return0;

}

 

/*基於分治法,快速排序*/

void QuickSort(intArray[],intleft,intright){

   if(left>right)

        return;

   inti, j, temp, t;

   temp = Array[left];//基準數獲取

   i = left;j =right;//偵察兵

 

   //當i=j時,Array[i]、Array[i]指向同一個位置,本趟排序結束

   while(i!=j){

        //從右邊開始找,注意:“偵察兵”j先動,如果j找到比基數大的值,停下,等待i找到比基數小的值

        while(Array[j]>= temp&&i < j)

            –j;

        //再從左邊開始找,如果i找到比基數大的值,停下

        while(Array[i]<= temp&&i < j)

             i;

        //然後交換找到的兩個數的位置

        if(i<j){

            t= Array[i];

            Array[i]=Array[j];

            Array[j]= t;

        }       

   }

   //最終將基數歸位,基數位於中間

   Array[left]=Array[i];

   Array[i]= temp;

 

   /*再分治*/

   QuickSort(Array,left,i – 1);//左側遞迴

   QuickSort(Array,i 1,right);//右側遞迴

}

 

//隨機陣列

void Ran_Array(intArray[],intLength){

   srand((unsigned)time(NULL));

   for(inti = 0; i < Length; i){

        intj ;

         int temp =rand() % 100;

         for (j = 0;j < i; j){

             if (Array[j]==temp){

                  –i;

                  break;

             }

         }

         if (j>= i)

             Array[i] =temp;

   }

}

 

//輸出

void Output(intArray[],intLength){

   for(inti = 0; i < Length; i)

        printf(“%d “,Array[i]);

   printf(“\n”);

}