C++ 快速排序（c++实现快速排序算法）

介绍

快速排序是对冒泡排序算法的一种改进，快速排序算法通过多次比较和交换来实现排序。

流程如下：

C++ 快速排序（c++实现快速排序算法）

实现

以下有两种实现方式，说是两种，其实就是在交换元素时具体细节上有点不同罢了。

方式一

int Partition(int A[],int low,int high){ int pivot=A[low];//第一个元素作为基准 while(low<high){ while(low<high && A[high]>=pivot) high--; A[low]=A[high]; while(low<high && A[low]<=pivot) low++; A[high]=A[low]; } A[low]=pivot; return low; } void QuickSort(int A[],int low,int high){ if(low<high){ int pivotpos=Partition(A,low,high); QuickSort(A,low,pivotpos-1); QuickSort(A,pivotpos+1,high); } }

该方式，先把基准元素保存起来

如下图数组，把49看作基准元素，先移动high指针，当指向27时退出while循环，把27放到low位置

C++ 快速排序（c++实现快速排序算法）

这时候，high位置就空出来一个，那么让low移动，移动到下图所示时，65>49，退出while循环，再将65放到high位置

C++ 快速排序（c++实现快速排序算法）

这样low这个位置又空出来了，再移动high，如此反复。

C++ 快速排序（c++实现快速排序算法）

最后得到如下图的情况：

C++ 快速排序（c++实现快速排序算法）

这样我们就按照“49”，把数组分为了左右两部分。

对左右两部分分别进行上述操作即可。

C++ 快速排序（c++实现快速排序算法）

方式二

void Quick_sort(int left,int right,int arr[]){ if(left>=right)return; int i,j,base,temp; i=left,j=right; base=arr[left]; while(i<j){ while(arr[j]>=base && i<j)j--; while(arr[i]<=base && i<j)i++; if(i<j){ temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } } arr[left]=arr[i]; arr[i]=base; Quick_sort(left,i-1,arr); Quick_sort(i+1,right,arr); }

对于第二种方式，看下图即可很好理解。

高低指针不是轮流替换空余位置，而是同时找到不符合的元素，然后交换二者。

最后，高低指针相遇，再把基准元素与相遇位置上的元素交换即可。

C++ 快速排序（c++实现快速排序算法）