c++怎么樣實(shí)現(xiàn)快速排序算法

這篇文章主要介紹了c++怎么樣實(shí)現(xiàn)快速排序算法，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

第一、算法描述

快速排序由C. A. R. Hoare在1962年提出，該算法是目前實(shí)踐中使用最頻繁，實(shí)用高效的最好排序算法，

快速排序算法是采用分治思想的算法，算法分三個(gè)步驟

1.從數(shù)組中抽出一個(gè)元素作為基數(shù)v（我們稱之為劃界元素）,一般是取第一個(gè)、最后一個(gè)元素或中間的元素

2.將剩余的元素中小于v的移動(dòng)到v的左邊，將大于v元素移動(dòng)到v的右邊

3.對(duì)左右兩個(gè)分區(qū)重復(fù)以上步驟直到所有元素都是有排序好。

第二、算法實(shí)現(xiàn)

/*序列劃分函數(shù)*/
int partition(int a[], int p, int r) {
  int key = a[r];//取最后一個(gè)
  int i = p - 1;
  for (int j = p; j < r; j++)
  { 
    if (a[j] <= key)
    {     
      i++;
      //i一直代表小于key元素的最后一個(gè)索引，當(dāng)發(fā)現(xiàn)有比key小的a[j]時(shí)候，i+1 后交換     
      exchange(&a[i], &a[j]);
    }   
  } 
  exchange(&a[i + 1], &a[r]);//將key切換到中間來，左邊是小于key的，右邊是大于key的值。
  return i + 1;
}
 
void quickSort(int a[], int p, int r) {
  int position = 0;
  if (p<r)
  {
    position = partition(a,p,r);//返回劃分元素的最終位置
    quickSort(a,p,position-1);//劃分左邊遞歸
    quickSort(a, position + 1,r);//劃分右邊遞歸
  } 
}
 
void main() {
  int d[] = { 6,4,1,8,7,5 };
  cout << "輸入數(shù)組 { 6,4,1,8,7,5 } " << endl; 
  quickSort(d, 0, 5);
  print_arr(d, 6);
 
}

兩個(gè)輔助函數(shù)：

void exchange(int * a, int* b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}
void print_arr(int *a, int size) //打印函數(shù) 
{
  cout << "打印數(shù)組：";
  for (int i = 0; i<size; i++)  //打印數(shù)組 
  {
    cout << a[i] << " ";
  }
  cout << endl << endl;
}

測試輸出：

第三、算法圖解分析

下面我們來具體分析下程序怎么運(yùn)行的，

quickSort(d, 0, 5);代表以靠最有一個(gè)元素5作為基數(shù)，

程序初始化時(shí)候p=0,r=5,i=-1,j=0,key=5

通過上圖我們觀察到：

1.i逐漸增加，它一直代表著小于key=5的最后一個(gè)元素，j也在主鍵增加，一直到key前面一個(gè)元素停止

2.此時(shí)循環(huán)到了最后一個(gè)元素7，以5為基數(shù)的循環(huán)已經(jīng)結(jié)束，此時(shí)i=1，a[i+1]=6,交換6和5交換，完成本輪循環(huán)

返回i+1=2，依索引2為分界線拆分2個(gè)數(shù)組，進(jìn)入遞歸循環(huán)，執(zhí)行類似上圖操作

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“c++怎么樣實(shí)現(xiàn)快速排序算法”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來學(xué)習(xí)!