快速排序(QuickSort):
找一个标准值（枢轴）,将比标准值小的都放在它左侧，将比标准值大的都放在它右侧。标准值的左右两侧就没有必要在进行比较。然后标准值左右两侧重复上述过程。
例如待排数据为8，4，9，12，17，1，6，3，10；数组里最好取到的元素就是第一个元素，和最后一个元素，我们现在取第一个元素8作为标准值，然后进行将数组剩余元素放到8左右两侧的操作，能完成这个操作的方法有很多，我们选择一种经典的方法:“挖坑填补法”。
8作为标准值，拿出来以后，8的位置空出来，从后向前找比8小的，10比8大，10不动，3比8小，3放到前面的坑里，从前找比8大的放在后面的坑里，4比8小，4不动，9比8大，9放在后面的坑里，从后向前找比8小的，6比8小，放到前面的坑里。从前向后找比8大的，12比8大，放在后面的坑里。从后向前找比8小的，1比8小，放到前面的坑里，从前向后找比8大的，17比8大，放到后面的坑里，从后向前找比8小的，两个指针重合，即左边比8小，右边比8大，这个位置就是元素8的位置。
然后8的左右两部分在分别重复上述过程。
3，4，6，1；取标准值3，
然后依旧是左右两边重复上述操作。
重复操作，不是递归，就是循环，我们选择递归。而以上这种问题的解决方法叫做分治法，分而治之，逐个击破。一个复杂的问题可以分解成两个或者更多的相似的子问题，子问题再分解 … …解决了子问题，总的问题自然就解决了。
#include<stdio.h>
int Sort(int arr[],int nBegin,int nEnd)
{
int temp = arr[nBegin];
while(nBegin < nEnd)
{
//从后向前找比标准值小的
while(nBegin < nEnd)
{
if(arr[nEnd] < temp)
{
//放到前面的坑
arr[nBegin] = arr[nEnd];
nBegin++;
break;
}
nEnd--;
}
//从前向后找比标准值大的
while(nBegin < nEnd)
{
if(arr[nBegin] > temp)
{
//放后面的坑
arr[nEnd] = arr[nBegin];
nEnd--;
break;
}
nBegin++;
}
}
//标准值方法入
arr[nBegin] = temp;
return nBegin;
}
void QuickSort(int arr[],int nBegin,int nEnd)
{
if(arr == NULL || nBegin >= nEnd) return;
//标准值
int nIndex = Sort2(arr,nBegin,nEnd);
//分成两部分
QuickSort(arr,nBegin,nIndex-1);
QuickSort(arr,nIndex+1,nEnd);
}
void Printf(int arr[],int nlength)
{
if(arr == NULL||nlength<=0) return;
int i;
for(i = 0;i<nlength;i++)
{
printf("%d ",arr[i]);
}
}
int main()
{
int arr[]={
10,2,11,4,56};
QuickSort(arr,0,sizeof(arr)/sizeof(arr[0])-1);
Printf(arr,sizeof(arr)/sizeof(arr[0]));
printf("\n");
return 0;
}
快排的优化：我们用挖坑填补法确实完成了我们的任务，但是我们的代码有循环嵌套，可是我们每一次的任务就是去找到大的，或者小的，只需要遍历一遍就可以，那么如果我们只找小比标准值小的，把它放在前面，那么是不是自然只剩下大的在标准值后面了。这种方法叫做区间分割。
我们需要两个变量，一个是小区间变量，一个是遍历变量，选择最后的元素6为标准值，12与6比，比6大，小区间不扩张，向后走，4比6小，小区间扩张，小区间扩张一定是从头开始扩张，所以将12与4交换，9和6比，9比6大，继续，2和6比，2比6小，小区间扩张，小区间连成一片，2和12换一下，8和6比，8比6大，继续，3和6比，3比6小，小区间扩张，3和9换一下，5和6比，5比6小，小区间扩张，5和12换一下，再往后操作就是最后元素，
标准值的位置了，那标准值放在哪里，自然是小区间的后面，8和6交换。
（红色箭头代表小区间元素，蓝色箭头用来遍历）
int Sort2(int arr[],int nBegin,int nEnd) //快排优化
{
int nSmall = nBegin-1;
for(nBegin;nBegin < nEnd;nBegin++)
{
if(arr[nBegin] < arr[nEnd])
{
//小区间扩张
if(++nSmall != nBegin)
{
//小区间的下一个位置与小于标准值的元素交换
arr[nSmall] = arr[nSmall]^arr[nBegin];
arr[nBegin] = arr[nSmall]^arr[nBegin];
arr[nSmall] = arr[nSmall]^arr[nBegin];
}
}
}
//标准值放入
if(++nSmall != nEnd)
{
arr[nSmall] = arr[nSmall]^arr[nEnd];
arr[nEnd] = arr[nSmall]^arr[nEnd];
arr[nSmall] = arr[nSmall]^arr[nEnd];
}
return nSmall;
}
转载：https://blog.csdn.net/scarificed/article/details/113274028