快速排序
快速排序的核心:
找到一个key
通常左边的数比key小,右边的数比key大。
找key通常有三种方法:
1.
挖坑法:
代码实现:
//
int _pivot(int* a, int left, int right)
{
int begin = left, end = right;
int index = get_mid(a, left, right);
swap(a[index], a[begin]);
int key = a[begin];
int pivot = begin;
while (begin < end)
{
while (begin < end && a[end] >= key)
{
--end;
}
//swap(a[end], a[pivot]);
a[pivot] = a[end];
pivot = end;
while (begin < end && a[begin] <= key)
{
++begin;
}
//swap(a[begin], a[pivot]);
a[pivot] = a[begin];
pivot = begin;
}
//swap(a[begin], a[pivot]);
pivot = begin;
a[pivot] = key;
return pivot;
}
该代码的注意点为:
如果a[begin]或a[end]与key相等时,key原来在key的那边,while循环后key还在原来那边。
swap交换是错误的例子。
pivot是坑,a[pivot]是图里面类似于马赛克的位置(a[pivot]是空),所以不能是交换,应该是赋值。
左右指针法:(最左侧的一列是其示例图)
图中代码有本质差别,图一正确(左)。
先end--
后end--
二者有质的区别,完全不同
前后指针法:
找到key之后的核心: