具体代码
#include<stdio.h> //定位 int Patrition(int* R, int start, int end) { int standard = R[start]; int i = start; int j = end; //寻找恰当位置（下文会细讲这里） while(i!=j) { while(i<j&&R[j]>=standard) j--; if(i<j&&R[j]<standard) { R[i] = R[j]; i++; } while(i<j&&R[i]<=standard) i++; if(i<j&&R[i]>standard) { R[j] = R[i]; j--; } } R[i] = standard; return i; } //这里统一用物理位置来表示 void QuickSort(int* R, int start, int end) { if(start<end) { int index = Patrition(R,start,end); QuickSort(R,start,index-1); QuickSort(R,index+1,end); } } int main() { int M[6] = {9,5,3,7,8,4}; QuickSort(M,0,5); for(int i=0;i<6;i++) { printf("%d ", M[i]); } } |
过程分析
快速排序的本质，说白了就是，在一个数组中，把某个数按照大小顺序放到正确的位置，将数组分为两个小的数组。如此操作，直到每个数都在自己正确的位置。
快速排序主要由两个部分组成：
1.排序操作（QuickSort），通过递归的方式，得到有序的排列。其内部工作原理就是先将数组中的一个元素定位，分为两小个，再将两小数组排序，最后整个数组就是有序的了。（另外若数组被划分为只有一个元素的情况，则直接返回）
2.定位操作（Patrition），通过逐个对比的方式，将这个数放置到正确的位置（比如A元素在数组中是第4小，那么A元素就会被放置到4号位置去）。这样一轮操作之后，这个数的左边全是小于它的，右边全是大于它的。（但是顺序不一定对）
比如说对下面这个数组的排序：
当我们调用QuickSort函数的时候，则会依次发生Patrition（定位）和两次对划分后的小数组的QuickSort操作。
Patrition操作
结合代码和图，我一步一步分析：
第一步，选择目标（也就是你要给哪个元素找到对应位置，这里我选的是首个元素）
int standard = R[start];
第二步， 准备从两侧依次对数组进行遍历，所以把指针准备好：
int i = start;
int j = end;
第三步，核心步骤，寻找正确位置：
在i和j相遇之前，逐个筛选元素，若是大于基准，则放到右边去，若是小于基准，则放到左边去。
while(i!=j)
{.....}
不过需要注意的是，放元素的位置不能使原数组的数据丢失。
一开始，第一个位置的元素5已经被作为基准了，所以第一个位置现在是空的，可以存放元素。
按要求，需要从右边开始，把比基准小的元素放过来，现在j指针指的3就符合条件，所以，移动。
现在，j的内容被写了，所以现在j指针对应的位置是可写的，于是从右边开始寻找有没有比基准大的？
很显然，7就是，所以7移过去
现在又应该从右边开始找了，于是乎，0也符合条件，写到i指针所指的7的位置去。
现在可写的位置到右边去了，所以右边继续找比基准大的：
现在又该j指针动了，6比5大，不管。4比5小，写过去！
现在i指针动起来，2可以，过！1可以，也过！
当i指到4的时候，i指针和j指针相遇了，说明这其实就是基准元素5应该在的位置，所以把5写过来。
定位完成！
我再补充一下代码里的每一步的作用：
while(i<j&&R[j]>=standard) j--; //右指针，如果大于基准条件，就一直向左走 if(i<j&&R[j]<standard) //如果小了，那么就把元素写过去 { //Ps.另外一边的指针的位置 R[i] = R[j]; //永远是指的可写的 i++; //所以直接R[i] = R[j] } while(i<j&&R[i]<=standard) i++;//左指针，如果大于基准条件，就一直向左走 if(i<j&&R[i]>standard) //如果大了，写过去 { R[j] = R[i]; j--; } //继续循环直到i==j （这一堆代码都在while里） |
第四步，把值放到对应的位置（对应上面最后一幅图）
R[i] = standard;
第五步，返回这个基准的位置，代表两边已经被分化好了，接下来分别对两边的数组进行QuickSort即可
return i;
QuickSort
承接上面的图：
分别再对两边的数组进行同样的操作即可。
排序成功！
性能分析
本文内容不用于商业目的，如涉及知识产权问题，请权利人联系博为峰小编(021-64471599-8017)，我们将立即处理。
