快速排序，时间复杂度为O（NlogN），属于排序中相对快的那一列，以下是快排的模拟实现：
法一：左右指针交换法
void swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}//交换函数
int getmid(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[right])
{
if (a[mid] > a[right])
{
return right;
}
else
{
if (a[mid] > a[left])
{
return mid;
}
else
{
return left;
}
}
}
else //left大于right
{
if (a[mid] < a[right])
{
return right;
}
else
{
if (a[mid] < a[left])
{
return mid;
}
else
{
return left;
}
}
}
}//三数取中
int PartSort1(int* a, int left, int right)
{
int mid = getmid(a, left, right);
int keyi = left;
while (left < right)
{
while (left < right && a[right]>=a[keyi])
{
right--;
}
while (left < right && a[left] <=a[keyi])
{
left++;
}
swap(&a[left], &a[right]);
}
swap(&a[keyi], &a[left]);
return left;
}
void sort(int* arr, int left, int right)
{
if (left < right)
{
int mid = PartSort1(arr, left, right);
sort(arr, left, mid - 1);
sort(arr, mid + 1, right);
}
}
本思路是以left下标所指的元素为分界线，left指针向右移动找比分界元素大的，right指针向左移动找比分解元素小的，然后两者交换。通过这样循环，使得左侧的元素都是比分界元素小的，右侧元素都是比分界元素大的，且此时分界元素已经放在了排好序后的正确位置上。再对分界元素左侧、右侧调用同样的方法，最后就能实现排序。三数取中是一种优化方式，使得left下标所指向的元素更加贴近当前left到righ范围内的中间值。最后之所以用left指向位置和keyi指向位置进行交换，是因为left此时所指元素一定小于等于keyi所指向的元素。下面会证明为什么left此时所指元素一定小于等于keyi所指向的元素：
当循环停止以后，循环前的最后一次移动分两种情况，一种是right指针左移动碰到left，一种是left指针右移动碰到right。对于第一种情况，此时left指针所指的位置是前面left和right所指元素交换后的，所以此时left所指元素一定是小于keyi的。对于第二种情况，此时right指针已经结束移动，所指向的位置也是小于keyi的元素。所以left此时所指元素一定小于等于keyi所指向的元素。当然，如果先移动left指针再移动right指针，就不能符合上述结论。
法二：挖坑法
// 挖坑法
int PartSort2(int* a, int left, int right)
{
int mid = getmid(a, left, right);
swap(&a[left], &a[mid]);
//三数取中
int key = a[left];
int hole = left;
while (left < right)
{
while (left < right && a[right] >= key)
{
right--;
}
a[hole] = a[right];
hole = right;
while (left < right && a[left] <= key)
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}
void sort(int* arr, int left, int right)
{
if (left < right)
{
int mid = PartSort2(arr, left, right);
sort(arr, left, mid - 1);
sort(arr, mid + 1, right);
}
}该方法的思路是先把left所指的位置视为坑，保存最左的元素到可以中 ，此后利用right指针和left指针移动找元素填坑和创建新坑。此时整个数组中一直保持着有一个下标指向坑，最后再将最开始保存的key放入坑中，形成完整的数组。left和right指针的移动规则仍然是left找比key大的，right找比key小的。
法三：前后指针法
int PartSort3(int* a, int left, int right)
{
int prev = left;
int cur = left+1;
while (cur <= right)
{
while(cur <= right&&a[cur] <= a[left])
{
prev++;
swap(&a[cur], &a[prev]);
cur++;
}
if (cur > right)
{
break;
}
while (cur <= right && a[cur] > a[left])
{
cur++;
}
if (cur > right)
{
break;
}
}
swap(&a[prev], &a[left]);
return prev;
}
void sort(int* arr, int left, int right)
{
if (left < right)
{
int mid = PartSort2(arr, left, right);
sort(arr, left, mid - 1);
sort(arr, mid + 1, right);
}
}
思路是让prev的下一位元素是比a[left]大的元素，cur所指的元素是比a[left]小的元素，然后交换，使得小于a[left]的元素往左移动，比a[left]大的元素不断往右移动。
