排序算法——快速排序

一、快速排序的原理

二、快速排序的过程

三、代码的实现

四、代码的优化

总结

一、快速排序的原理

快速排序的思想是分治法，将一个大问题分割成几个小问题解决，首先选择一个数作为分水岭，然后让比该数大的都在它的右边，比它小的都在它左边，将一个大问题分割成了两个问题，用同样的方法对两边分别操作，最后呈现出来的就是排好序的整体。（以升序为例）

二、快速排序的过程（以升序为例）

我定义一个数组a[6]来演示，让low指向低下标，high指向高下标

一般让第一个数作为分水岭split=a[0]，然后将split和a[5]进行比较，a[5]>split，不用操作，接着high减一，

然后比较split和a[4]，split<a[4]，任然不用操作，high再减一，

然后将split和a[3]进行比较，split>a[3],将a[3]放到a[0]的位置，然后high减一，由于此时的low任然是0，但是a[0]是刚刚赋的值，已经比较过了，下一次无需再比较，所以移动之后low加一，

然后比较split和a[1]，split<a[1]，将a[1]的值放到a[3]中去，并且low加一，由于a[3]是刚刚赋的值，已经比较过了，下次无需再比较，所以还要high减一，

然后比较split和a[2]，split>a[2]，将a[2]放到a[1]中，并且low加一，high减一，

当low不小于high的时候，将split放回数组中，放到a[low]的位置，（数组中元素的个数为奇数时，low=high结束，为偶数时，low大于high结束，总之只有low<high才进行比较）

此时第一次分割已经完成，split左边的值都比它小，右边的值都比它大，但是很明显，整个数组并没有排序好，但是后面只需对左边和右边进行相同的操作即可，问题的本质没有改变，经过多次分割整个数组就被排好序了。（使用递归实现）

左右分别操作的时候，左边的high变成了split的下标减一，右边的low变成了split的下标加一，把左右当成新数组处理即可。

注意：如果split的初始值是a[0]，就要从high开始比较，如果是最后一位数，就要从low开始比较，并且比较一定是左右交替的！！！

三、代码的实现

//分割操作
int findsplit(int ints[], int low, int high)
{int split = ints[low];while (low < high){while (low < high){if (ints[high] < split){ints[low] = ints[high];low++;//由于会产生一次多余的比较，所以low++规避，减少比较次数break;}high--;}while (low < high){if (ints[low] > split){ints[high] = ints[low];high--;//同上break;}low++;}}ints[low] = split;return low;
}//递归排序
void rapidselect(int ints[], int low, int high)
{//递归函数退出的条件if (low >= high){return;}int splitindex;splitindex = findsplit(ints, low, high);//split左侧排序rapidselect(ints, low, splitindex - 1);//split右侧排序rapidselect(ints, splitindex + 1, high);
}

四、代码的优化

上面的代码存在一点缺陷，如果a[0]是数组中的极值，那么整个过程并没有达到我们想要的效果，因为所有的数据任然在一边，运行速度受到影响。那么可以写一个函数求一下数组的大致中位数，尽量将数组平均分成两部分。代码如下：

int getmid(int a[], int low, int high)
{int mid = (low + high) / 2;//比较三者的关系if (a[low] < a[mid]){if (a[high] > a[mid])return mid;else if (a[low] < a[high])return high;elsereturn low;}else{if (a[mid] > a[high])return mid;else if (a[high] > a[low])return low;elsereturn high;}
}

将split初始化为这个大致的中位数即可做到尽量将数组均分。