c++ 快速排序算法【过程图解】

时间：2021-05-14 10:37:21|栏目：C代码|点击：次

第一、算法描述

快速排序由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;
}

测试输出：