公告
c语言快排排序
快速排序（Quick Sort）：
这个算法的霸气程度从它的名字就可以看出来了。快速排序的应用也是非常广的的，各种类库都可以看到他的身影。这当然与它的“快”是有联系的，正所谓天下武功唯快不破。
快速排序的一个特点是，对数组的一次遍历，可以找到一个枢纽元（pivot）确定位置，还可以把这个数组以这个枢纽元分成两个部分，左边的元素值都比枢纽元小，右边的都比枢纽元大。我们递归地解决这两个子数组即可。
我们还是通过一个特殊的例子来看一下快速排序的原理：
我们假设有这样一个数组｛ 4，7，3，2，8，1，5 ｝
对于快速排序来说，第一步就是找出一个枢纽元，而对于枢纽元的寻找是对整个算法的时间性能影响很大的，因为搞不好快速排序会退化成选择排序那样。
对于这个不具有代表性的例子，我们选择的是第一个元素做为枢纽元。
pivot 4
｛｝
其中，红色为左指针，蓝色为右指针。一开始我们从右边开始，找到第一个比pivot小的数。停止，然后将该值赋给左指针，同样，左指针向右移动。
也就是说我们第一次得到的的结果是这样的：
｛ 1，7，3，2，8，1，5 ｝
同样的道理，我们在左边找到一个比pivot大的值，赋值给右指针，同时右指针左移一步。
得到的结果应该是这样的：
｛ 1，7，3，2，，8，7，5 ｝
请注意，我们的这个移动过程的前提都是左指针不能超过右指针的前提下进行的。
这两个过程交替进行，其实就是在对元素进行筛选。这一次得到的结果是：
｛ 1，2，3，2，8，7，5 ｝
黄色高亮表示两个指针重叠了，这时候我们也就找到了枢纽元的位置了，将我们的枢纽元的值插入。
也就是说，我们接下来的工作就是以这个枢纽元为分割，对左右两个数组进行同样的排序工作。
来看看具体的代码是怎么实现的：
public static void sort(int[] array, int start, int end) {
if (start >= end) {
return;
}
int left = start;
int right = end;
int temp = array[left];
while (left < right) {
while (left < right && temp < array[right]) {
right–;
}
if (left < right) {
array[left] = array[right];
left++;
}
while (left < right && temp > array[left]) {
left++;
}
if (left < right) {
array[right] = array[left];
right–;
}
}
array[left] = temp;
sort(array, start, left – 1);
sort(array, left + 1, end);
}
posted on
一个人去旅行，而且是去故乡的山水间徜徉。
