Quick_sort(快速排序)

原理:

  1. 选序列的第一个数为基数
  2. 从后向前找一个比基数小的数,从前向后找一个比基数大的数,swap
  3. 依次迭代,得到基数的正确位置
  4. 基数前后的两个序列递归进行上述过程

图解:
Quick_sort(快速排序)
Quick_sort(快速排序)
Quick_sort(快速排序)
Quick_sort(快速排序)
Quick_sort(快速排序)
low与high相遇时为基数正确位置
图解来自https://blog.csdn.net/nrsc272420199/article/details/82587933

代码:

#include <iostream>
#include <algorithm>
using namespace std;
int Partion(int* a, int left, int right)   //划分过程
{
	int cardinal = a[left];
	int i = left, j = right;
	while (i < j)
	{
		while (i<j&&a[j]>cardinal)
			--j;
		if (i < j)
			std::swap(a[i++], a[j]);
		while (i < j&&a[i] < cardinal)
			++i;
		if (i < j)
			std::swap(a[j--], a[i]);
	}
	a[i] = cardinal;
	return i;
}
void Quick_sort(int* a, int left, int right)
{
	if (right > left)
	{
		int pos = Partion(a, left, right);
	    Quick_sort(a, left, pos - 1);
	    Quick_sort(a, pos + 1, right);
	}
}
int main(int argc, char** argv)
{
	int a[5] = { 2,4,1,3,5 };
	Quick_sort(a, 0, 4);
	for (int i = 0; i <= 4; i++)
		cout << a[i] << " ";
	return 0;
}

结果:1 2 3 4 5

上一篇:龟速乘


下一篇:EasyTouch5手势组件中文解释(Quick Gesture)