c排序算法大全

排序算法是一種基本并且常用的算法。由于實際工作中處理的數量巨大，是以排序算法 對算法本身的速度要求很高。

而一般我們所謂的算法的性能主要是指算法的複雜度，一般用O方法來表示。在後面将給出詳細的說明。《計算機程式設計技巧》（第三卷，排序和查找）

     對于排序的算法我想先做一點簡單的介紹，也是給這篇文章理一個提綱。

我将按照算法的複雜度，從簡單到難來分析算法。第一部分是簡單排序算法，後面你将看到他們的共同點是算法複雜度為O(N*N)（因為沒有使用word,是以無法打出上标和下标）。第二部分是進階排序算法，複雜度為O(Log2(N))。這裡我們隻介紹一種算法。另外還有幾種

算法因為涉及樹與堆的概念，是以這裡不于讨論。第三部分類似動腦筋。這裡的兩種算法并不是最好的（甚至有最慢的），但是算法本身比較奇特，值得參考（程式設計的角度）。同時也可以讓我們從另外的角度來認識這個問題。現在，讓我們開始吧：

一、簡單排序算法

由于程式比較簡單，是以沒有加什麼注釋。所有的程式都給出了完整的運作代碼，并在我的VC環境

下運作通過。因為沒有涉及MFC和WINDOWS的内容，是以在BORLAND

C++的平台上應該也不會有什麼

問題的。在代碼的後面給出了運作過程示意，希望對了解有幫助。

1.冒泡法：(從後向前倒)

這是最原始，也是衆所周知的最慢的算法了。他的名字的由來因為它的工作看來象是冒泡：

#include

<iostream.h>

void BubbleSort(int* pData,int

Count)

{

int iTemp;

for(int

i=1;i<Count;i++)

        {

          for(int

j=Count-1;j>=i;j--)

                 {

                   if(pData[j]<pData[j-1])

                             {

                               iTemp

=

pData[j-1];

                               pData[j-1]

pData[j];

                               pData[j]

iTemp;

                             }

                 }

        }

}

void

main()

int data[] =

{10,9,8,7,6,5,4};

BubbleSort(data,7);

for (int

i=0;i<7;i++)

             cout<<data[i]<<"

";

cout<<"\n";

倒序(最糟情況)

第一輪：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交換3次)

第二輪：7,10,9,8->7,10,8,9->7,8,10,9(交換2次)

第一輪：7,8,10,9->7,8,9,10(交換1次)

循環次數：6次

交換次數：6次

其他：

第一輪：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交換2次)

第二輪：7,8,10,9->7,8,10,9->7,8,10,9(交換0次)

交換次數：3次

上面我們給出了程式段，現在我們分析它：這裡，影響我們算法性能的主要部分是循環和交換，顯然，次數越多，性能就越差。從上面的程式我們可以看出循環的次數是固定的，為1+2+...+n-1。

寫成公式就是1/2*(n-1)*n。現在注意，我們給出O方法的定義：

若存在一常量K和起點n0，使當n>=n0時，有f(n)<=K*g(n),則f(n)

= O(g(n))。（呵呵，不要說沒

學好數學呀，對于程式設計數學是非常重要的！！！）

現在我們來看1/2*(n-1)*n，當K=1/2，n0=1，g(n)=n*n時，1/2*

(n-1)*n<=1/2*n*n=K*g(n)。是以f(n)

=O(g(n))=O(n*n)。是以我們程式循環的複雜度為O(n*n)。再看交換。從程式後面所跟的表可以看到，兩種情況的循環相同，交換不同。其實交換本身同資料源的有序程度有極大的關系，當資料處于倒序的情況時，交換次數同循環一樣（每次循環判斷都會交換），複雜度為O(n*n)。當資料為正序，将不會有交換。複雜度為O(0)。亂序時處于中間狀态。正是由于這樣的原因，我們通常都是通過循環次數來對比算法。

2.交換法：

    交換法的程式最清晰簡單，每次用目前的元素一一的同其後的元素比較并交換。

void ExchangeSort(int* pData,int

i=0;i<Count-1;i++)

           {

             for(int

j=i+1;j<Count;j++)

                      {

                        if(pData[j]<pData[i])

                                  {

                                    iTemp

pData[i];

                                    pData[i]

                                    pData[j]

                                  }

                      }

          }

ExchangeSort(data,7);

               cout<<data[i]<<"

第一輪：10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交換3次)

第二輪：7,10,9,8->7,9,10,8->7,8,10,9(交換2次)

第一輪：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交換1次)

第二輪：7,10,8,9->7,8,10,9->7,8,10,9(交換1次)

從運作的表格來看，交換幾乎和冒泡一樣糟。事實确實如此。循環次數和冒泡一樣也是1/2*

(n-1)*n，是以算法的複雜度仍然是O(n*n)。由于我們無法給出所有的情況，是以隻能直接告訴大家他們在交換上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。

3.選擇法：：(從第一個開始和後面的最大的進行比較)

現在我們終于可以看到一點希望：選擇法，這種方法提高了一點性能（某些情況下）

這種方法類似我們人為的排序習慣：從資料中選擇最小的同第一個值交換，在從省下的部分中

選擇最小的與第二個交換，這樣往複下去。

void SelectSort(int* pData,int

int

iPos;

             {

               iTemp

               iPos

i;

               for(int

                            {

                              if(pData[j]<iTemp)

                                         {

                                           iTemp

                                           iPos

j;

                                          }

                            }

               pData[iPos]

               pData[i]

              }

SelectSort(data,7);

第一輪：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7-&

gt;(iTemp=7)7,9,8,10(交換1次)

第二輪：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交換1次)

第一輪：7,8,9,10->(iTemp=9)7,8,9,10(交換0次)

交換次數：2次

第一輪：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9-&

gt;(iTemp=7)7,10,8,9(交換1次)

第二輪：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交換1次)

第一輪：7,8,10,9->(iTemp=9)7,8,9,10(交換1次)

遺憾的是算法需要的循環次數依然是1/2*(n-1)*n。是以算法複雜度為O(n*n)。我們來看他的交換。由于每次外層循環隻産生一次交換（隻有一個最小值）。是以f(n)<=n

是以我們有f(n)=O(n)。是以，在資料較亂的時候，可以減少一定的交換次數。

4.插入法：

插入法較為複雜，它的基本工作原理是抽出牌，在前面的牌中尋找相應的位置插入，然後繼續下一張

void InsertSort(int* pData,int

              {

i-1;

               while((iPos>=0)

&&

(iTemp<pData[iPos]))

                               {

                                 pData[iPos+1]

pData[iPos];

                                 iPos--;

                               }

               pData[iPos+1]

             }

InsertSort(data,7);

第一輪：10,9,8,7->9,10,8,7(交換1次)(循環1次)

第二輪：9,10,8,7->8,9,10,7(交換1次)(循環2次)

第一輪：8,9,10,7->7,8,9,10(交換1次)(循環3次)

第一輪：8,10,7,9->8,10,7,9(交換0次)(循環1次)

第二輪：8,10,7,9->7,8,10,9(交換1次)(循環2次)

第一輪：7,8,10,9->7,8,9,10(交換1次)(循環1次)

循環次數：4次

上面結尾的行為分析事實上造成了一種假象，讓我們認為這種算法是簡單算法中最好的，其實不是，因為其循環次數雖然并不固定，我們仍可以使用O方法。從上面的結果可以看出，循環的次數f(n)<=

1/2*n*(n-1)<=1/2*n*n。是以其複雜度仍為O(n*n)（這裡說明一下，其實如果不是為了展示這些簡單排序的不同，交換次數仍然可以這樣推導）。現在看交換，從外觀上看，交換次數是O(n)（推導類似選擇法），但我們每次要進行與内層循環相同次數的‘=’操作。正常的一次交換我們需要三次‘=’

而這裡顯然多了一些，是以我們浪費了時間。

最終，我個人認為，在簡單排序算法中，選擇法是最好的。

二、進階排序算法：

進階排序算法中我們将隻介紹這一種，同時也是目前我所知道（我看過的資料中）的最快的。它的工作看起來仍然象一個二叉樹。首先我們選擇一個中間值

middle程式中我們使用數組中間值，然後把比它小的放在左邊，大的放在右邊（具體的實作是從兩邊找，找到一對後交換）。然後對兩邊分别使

用這個過程（最容易的方法——遞歸）。

1.快速排序：(二分法)

void run(int* pData,int left,int

right)

int i,j;

middle,iTemp;

i = left;

j =

right;

middle = pData[(left+right)/2];

//求中間值

   do{

         while((pData[i]<middle)

(i<right))//從左掃描大于中值的數

                        i++;

         while((pData[j]>middle)

(j>left))//從右掃描大于中值的數

                        j--;

         if(i<=j)//找到了一對值

                       {

                        //交換

                         iTemp =

                         pData[i]

                         pData[j]

                         i++;

                         j--;

                       }

}while(i<=j);//如果兩邊掃描的下标交錯，就停止（完成一次）

//當左邊部分有值(left<j)，遞歸左半邊

if(left<j)

           run(pData,left,j);

//當右邊部分有值(right>i)，遞歸右半邊

if(right>i)

           run(pData,i,right);

QuickSort(int* pData,int

run(pData,0,Count-1);

QuickSort(data,7);

            cout<<data[i]<<"

這裡我沒有給出行為的分析，因為這個很簡單，我們直接來分析算法：首先我們考慮最理想的情況

1.數組的大小是2的幂，這樣分下去始終可以被2整除。假設為2的k次方，即k=log2(n)。

2.每次我們選擇的值剛好是中間值，這樣，數組才可以被等分。

第一層遞歸，循環n次，第二層循環2*(n/2)......

是以共有n+2(n/2)+4(n/4)+...+n*(n/n)

n+n+n+...+n=k*n=log2(n)*n

是以算法複雜度為O(log2(n)*n)

其他的情況隻會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那麼他将變成交換法（由于使用了遞歸，情況更糟）。但是你認為這種情況發生的幾率有多大？？呵呵，你完全不必擔心這個問題。實踐證明，大多數的情況，快速排序總是最好的。如果你擔心這個問題，你可以使用堆排序，這是一種穩定的O(log2(n)*n)算法，但是通常情況下速度要慢

于快速排序（因為要重組堆）。