算法

前言 说到快速排序，在学数据结构的时候都已经学到了，不过当时总是有些云里雾里的，就算是照着书上的代码敲出来，也不是很明白是什么意思。后来在大三上学期的时候又接触到了快速排序，虽然实现的方法不一样。数据结构将的时候右边和右边一起向中间靠近，而算法导论将的是从做往右靠近，其实大概的思路都是差不多的。这里不想说一些时间复杂度，算法分析什么的，网上的资料很多，也不班门弄斧了。只是把自己的一点理解写出来，也许有后来的新手对于快速排序有相同的一点疑问，而且恰好看到我这偏文章并得以解惑，那就很是不错了。 分析 快速排序主要的思想就是在待排序的数组中取一个数字作为标兵，暂且就这么理解了。然后以这个标兵为界，把比标兵小的放在标兵的左边，把比标兵大的放在标兵的右边，这样我们可以知道不管左边或者右边的是怎么样，但是这个标兵已经处于排好序的数组中的正确的位置了。当然这是升序排序，降序也是一样的道理，思想就是这么简单。但是这个数字怎么取，取哪一个，然后怎么实现标兵的左边大，右边小，这就是重点所在了。最理想的情况当然是每次取到最中间大小的那个数，因为这样的话每次两边都刚好可以分到一半；而最坏的情况就是取到最大或者最小的，这样每次标兵虽然在正确的位置，但会存在一边没有元素，而另一边则是剩下的所有元素，这已经退化为插入排序了。所以为了尽量得到好的标兵，优化的快速排序算法有三数取中快速排序，随机化的快速排序，随机化三数取中快速排序等。三数取中指的是从数组的开头、结尾、中间的中取一个中间大小的数作为标兵，这样取出的数很可能靠近最优标兵；而随机化指的是随机从数组取出一个数作为标兵；而随机化三数取中则是前面两种算法的集中。 partition 为什么要一直说这个标兵呢？标兵为什么这么重要？那就不得不说快速排序的最重要的操作 partition 了。 partition 接受一个待排序的数组作为参数，返回标兵的正确位置。另外，这里的一个编程技巧是将标兵移到最后一个位置，这样在遍历数组的过程中便于交换。完整的 partition 函数如下： /** * @param A 传入的数组 * @param l 最左边位置 * @param r 最右边位置 * @return 标兵的位置 */ int partition(int A[], int l, int r) { //最后一个元素 int x = A[r]; int i = l - 1; for (int j = l; j < r; j++) { //如果不大于最后一个元素，就放在i的左边，并且i的位置加1 if (A[j] <= x) { i++; int temp = A[i]; A[i] = A[j]; A[j] = temp; } } //交换i位置与最后位置的元素，这样i的左边的元素都小于A[i]，右边的元素都大于A[i] int temp = A[i + 1]; A[i + 1] = A[r]; A[r] = temp; //返回标兵的位置 return i + 1; } 完整的代码 #include <iostream> using namespace std; void quick_sort(int A[], int p, int r); int partition(int A[], int l, int r); void print(int A[], int length); int main(int argc, char const *argv[]) { int length; cout << "请输入待排序的个数："; cin >> length; int A[length]; cout << "请输入排序的数字，以空格分开："; for (int i = 0; i < length; ++i) { cin >> A[i]; } quick_sort(A, 0, length - 1); print(A, length); return 0; } /** * @param A 传入的数组 * @param l 最左边位置 * @param r 最右边位置 * @return 标兵的位置 */ int partition(int A[], int l, int r) { //最后一个元素 int x = A[r]; int i = l - 1; for (int j = l; j < r; j++) { //如果不大于最后一个元素，就放在i的左边，并且i的位置加1 if (A[j] <= x) { i++; int temp = A[i]; A[i] = A[j]; A[j] = temp; } } //交换i位置与最后位置的元素，这样i的左边的元素都小于A[i]，右边的元素都大于A[i] int temp = A[i + 1]; A[i + 1] = A[r]; A[r] = temp; //返回标兵的位置 return i + 1; } void print(int *A, int length) { for (int i = 0; i < length; i++) { cout << A[i] << " "; } cout << endl; } void quick_sort(int A[], int p, int r) { if (p < r) { //q即是标兵的正确位置 int q = partition(A, p, r); //对左边部分继续调用quick_sort quick_sort(A, p, q - 1); //对右边部分继续调用quick_sort quick_sort(A, q + 1, r); } } 结语 算法一道真的是博大精深，作为一个计算机专业的，我的算法其实也是很差，比较汗颜。回想刚接触这个专业时什么都不懂，到现在更是觉得学海无涯。有道是一入 IT 深似海，从此妹纸是路人，咳，不是，从此青春是路人。且行且学习吧。 ...