如何通过过程图解快速掌握快速排序算法？

本文共计977个文字，预计阅读时间需要4分钟。

快速排序算法是由C.A.R. Hoare在1962年提出的，是目前实践中使用最频繁、效率最高的排序算法之一。它是一种分治思想的算法，将问题分解为三个步骤：

1. 从数组中抽取一个元素作为基准（pivot）。

2.将数组分为两部分，一部分包含小于基准的元素，另一部分包含大于基准的元素。

3.递归地对这两部分进行快速排序。

快速排序的核心在于基准元素的选取和数组的划分。

第一、算法描述

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

测试输出：

第三、算法图解分析

下面我们来具体分析下程序怎么运行的，

quickSort(d, 0, 5);代表以靠最有一个元素5作为基数，

程序初始化时候p=0,r=5,i=-1,j=0,key=5

通过上图我们观察到：

1.i逐渐增加，它一直代表着小于key=5的最后一个元素，j也在主键增加，一直到key前面一个元素停止

2.此时循环到了最后一个元素7，以5为基数的循环已经结束，此时i=1，a[i+1]=6,交换6和5交换，完成本轮循环

返回i+1=2，依索引2为分界线拆分2个数组，进入递归循环，执行类似上图操作

第四、总结

快速排序之所以快，相比冒泡排序他的交换是跳跃式的，它的最差时间复杂度是O(N2) 和冒泡一样，但是它的平均时间复杂度是O(nlog2N),是一种就地排序算法，

看了很多别人写的算法介绍，还是觉的不够清晰，于是决定自己写一篇博文，希望能帮助需要的人快速理解，文章中的用图是自己画的。

以上这篇c++ 快速排序算法就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持自由互联。