進入快序排序法之後,其實就很考驗邏輯思考,所以其實我很少用快速排序或者是合併排序法。理由很簡單,寫起來很麻煩很囉唆,一不小心就會錯很大。

不過該寫還是要寫,該複習還是要複習,所以今天來玩所謂的不穩定排序法:快速排序。

快速排序的動作如下

1. 決定一個基準點(中間、左邊、或者右邊)

2.假設你決定基準點在左邊的話,那用 i 指標從基準點後一位開始找,找到比基準值大的數值停下

3.從陣列右邊用 j 指標往回找,找到比基準值更小的值停下

4. 立刻判斷 i 是否 大於 j ,i  如果大於 j 則進入 [j] 與 基準值的 大小判斷,只要 [j] 比較小就互換

5. 承3.,如果 [i] 小於 [j],[i] 與 [j] 互換

6. recursive 呼叫,將範圍切成從兩份,第一份由0到 j,第二份由 j 到array.length-1(因為由零開始),並持續到 左邊界條件 >= 右邊界條件 為止。

 

#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;

#define SWAP(a,b){int temp = a;a=b; b=temp;}

const int size = 10;
void print_(int [], int);//ADT抽象資料型態大約這樣表示
void QS(int [],int , int );
void QS(int a[],int L, int R)
{
  int i=L+1;
  int j=R;
  while(i<j)
  {
    while(i!=R)
    {
      if(a[i]>a[L]){ break;}
      else{ i=i+1;}
    }
    while(j!=L+1)
    {
      if(a[j]<a[L])
      {
        if(i>j){break;}///////////////////////////////
        if(i<j){ SWAP(a[i],a[j]);}
        break;
      }
      else{ j=j-1;}
     }
      if(i>=j)
      {
        if(a[j]<a[L])
        {
          SWAP(a[L],a[j]);
        }
        QS(a,L,j);
        QS(a,j,R);
       }
     }
}

void main()
{
  srand(time(NULL));
  int arr[size] = {0};
  for(int i = 0; i < size; i++) {
  arr[i] = rand()%(100)+1 ;}
  cout<<"陣列內容原始狀況: "<<endl;
  print_(arr,size);

  QS(arr,0,size-1);

  cout<<"\n"<<"排序之後陣列內容:"<<endl;
  print_(arr,size);
  system("pause");
}

void print_(int a[],int size)
{
  for(int i=0; i<size;i++)
  {
    cout<<a[i]<<"\t";
  }
}

 

//更新一下
這樣應該就完全正確了ㄎㄎㄎ... 

arrow
arrow

    archerdevil 發表在 痞客邦 留言(0) 人氣()