快速排序

发表于 | 更新于 | 分类于 | 评论数：
本文字数： 5.2k | 阅读时长 ≈ 5 分钟

快速排序简介

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序运算方法

图中由6个数字构成的数组以及用变量temp存储的”哨兵”。left和right初始指向最左值与最右值。

基本操作步骤:

  1. 首先将left和right初始指向最左值与最右值，将最左边的值保存为哨兵(temp)

  2. right指向的值与哨兵值相比较

    1. (right的值小于哨兵值时) 将当前right指向的值赋给当前left的值中

    2. (right的值大于等于哨兵值时)right依次往左边滑动，直到满足right指向的值小于哨兵值

      图中right指向的值为1小于哨兵值5,所以将left的值赋为1

  3. left指向的值与哨兵值相比较

    1. (left的值大于哨兵值时) 将当前left指向的值赋给当前right的值中

    2. (left的值小于等于哨兵值时)left依次往右边移动，直到满足left指向的值大于哨兵值

      图中left指向的值原本是1，因为1<5所以left向右移动。因为移动后left指向的值为8,8>5所以right指向的值被赋值为8

  4. 重复进行第2大步和第3大步的操作，直到left==right时，将left(或者right)指向的值赋为哨兵值。再对left(或者right)的两边分别进行这四大步相同的操作。(当左右只剩下1个或0个值时则不再对左右进行操作)

继续完整演示这个序列的快速排序操作步骤

因为right指向的值为10大于哨兵值5,所以right继续左移

左移后right指向的值4已小于5，所以将当前left指向的值赋为4

因为left指向的值刚刚被赋为比哨兵值5小的数4，所以left右移。右移后left指向的值6>5所以right指向的值被赋为6

right左移，left==right ,将left指向的值赋为哨兵值5。

这个时候，有没有发现5的左边都是小于5的数，而5的右边同样都是大于5的数了

这就算是完成第一步数据筛选了，接着用相同的操作步骤来讨论5的两边，以此类推即可完成整个数组的排序。

最后贴上快速排序的实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void QuickSort(int a[],int left, int right)
{   
	int temp=a[left],choise=0,l=left,r=right;
	while(l<r){
		while(choise%2==0 && l<r){   
			if(a[r]<temp){a[l]=a[r];break;}
			else r--;
		}
		while(choise%2==1 && l<r){
			if(a[l]>temp){a[r]=a[l];break;}
			else l++;
		}
		choise++;
	}
	if(choise>0){ 
		QuickSort(a,left,r-1);
		QuickSort(a,r+1,right);
	}
	a[l]=temp;
}
0%