c++ 快速排序算法【過程圖解】

2020-01-26 14:08:50

字體：大中小

來源：轉載

供稿：網友

第一、算法描述

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

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

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

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

3.對左右兩個分區重復以上步驟直到所有元素都是有排序好。

第二、算法實現

/*序列劃分函數*/int partition(int a[], int p, int r) {  int key = a[r];//取最后一個  int i = p - 1;  for (int j = p; j < r; j++)  {     if (a[j] <= key)    {           i++;      //i一直代表小于key元素的最后一個索引，當發現有比key小的a[j]時候，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 << "輸入數組 { 6,4,1,8,7,5 } " << endl;   quickSort(d, 0, 5);  print_arr(d, 6); }

兩個輔助函數：

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

測試輸出：