快速排序 算法

算法思路

1. 序列終任意選擇一個數，把序列分為比這個數大和比這個數小的兩個子序列
2. 不斷重複以上步驟(遞歸)

代碼實作

int partition1(vector<int> &arr, int begin , int end) {
  int ret = arr[begin];
  int index = begin + 1;
  for (int i = index;i <= end; ++i) {
    if (arr[i] < ret) {
      swap(arr[i],arr[index]);
      index ++;
    }
  }
  swap(arr[begin],arr[index - 1]);
  return index - 1;
}

int partition2(vector<int> &arr,int beg, int end) {
  int ret = arr[beg];
  int l = beg + 1;
  int r = end;
  while(l<=r){//一次周遊，并找到放置arr[beg]的位置
    if(arr[l] < ret) l++;//将小于arr[beg]的放在其左側
    else if(arr[r] > ret) r--;//大于arr[beg]的放在其右側
    else if(arr[l] >= ret && arr[r] <= ret) {
      swap(arr[l++],arr[r--]);
    }
  }
  swap(arr[r],arr[beg]);
  return r;
}

void quick(vector<int> &arr,int beg, int end) {
  if (beg < end) {
    //int ret = partition1(arr,beg,end);
    int ret = partition2(arr,beg,end);
    
    quick(arr,beg,ret - 1);
    quick(arr,ret + 1, end);
  }
}      

算法分析