算法-快速排序

最近在学习算法，算法主要有回溯法，贪心法，动态规划法，分治法等。其中分治法又有二分查找，合并排序，快速排序等算法，今天学了一个比较重要的算法：快速排序。整理一下学习内容，如下：

快速排序理论与方法：

快速排序属于分治法的一种，分治法顾名思义“分而治之”，就是将一个大问题分解成几个小问题解决的算法思想。快速排序的思想也是将问题分解成小问题，之后解决每个小问题之间的排序完成数组排序。

方法

（1）在数组的最左边或者最右边找到一个参照物，

（2）之后从数组的最左边和数组的最右边分别取位置left,right， left的顺序是从左到右取比参照物大值，right的顺序是从右向左取比参照物小的值，因为是要从左到右，由小至大排序，因此right先查找，查到到符合标准的位置之后，等待left查找比参照物大的值。

（3）若left和right找到并且没有相遇：则交换两者位置，之后再次执行（2）的操作，注意，下标位置要改变，right变为right-1，left变为left+1;

（4）若left和right相遇在某个位置A，因此right最多移动到left+1的位置，说明该位置的左边和右边都没有符合left和right的查找顺序，说明位置A的左边没有比参照物大的数值，位置A的右边没有比参照物小的数值，将参照物与位置A的数值替换，那么参照物的排序顺序就定下来了。

（5）交换完参照物之后，重新开始新的一轮查找，不过，需要以参照物为分界线，参照物的左边为一个需要排序的数组，参照物的右边为一个需要排序的数组，将两个需要排序的数组重复上面的（1）（2） （3）（4）（5）之后，最终得到正确的排序顺序。

演示

给出一个长度为10的数组：[8,5,10,4,2,1,3,6,7]，由小到大进行排序。说明：（）步骤；【】:下标表示；[]:数组表示；0~9：数值表示。各位不要看混了

步骤：

（1）以8为参照物sign，left为【0】，right为【9】，如下图所示。

（2） right向左移，找比“8”小的数值，找到了下标为【8】的数值7，之后left向右移动，找到了比8大的下标为【2】的元素10,之后将两者交换位置，如图。

（3）之后right继续向左移动查找比8小的元素，找到了下标为【7】的元素6，left向右移动，在下标为【7】的位置与right相遇，此时，需要交换sign与下标为【7】的元素数据，如图。

（4）交换完之后，需要新的一轮排序，但是8的位置已经定了（前面有说替换完参照物之后，参照物的排序已经定了），因此以下标为【7】为参照物，左边[6,5,7,4,2,1,3]为一组排序，右边[10,9]为一组。继续上面步骤进行排序。

（5）排序[6,5,7,4,2,1,3]。以下标为0的【6】为参照物sign，下标【0】作为left，下标【6】为right，right继续向左移动找比6小的元素，找到了数值3，left向右移动，找到了数值7，交换两者位置

（6）继续移动right，找到了元素1，left向右移动与right相遇，交换6和1的位置

（7）因为6的位置已定，因此将数组[1,5,3,4,2,6,7]再分为两个数组：[1,5,3,4,2]和[7]。

（8）排序[1,5,3,4,2]，以1为sign，【0】作为left，【4】作为right，right向左移动,到下标为【0】的位置停下，left与right相遇，sign交换位置之后数据仍为1 ，分组之后变为了数组[5,3,4,2]

（9）对[5,3,4,2]进行排序，以元素5为参照物sign，left为下标【1】，right为下标【4】,right 向左移动，找到了2，left向右移动与right相遇，交换sign数据

（10）再次拆分，以5进行拆分为一个数组：[2,3,4],这个就不说了，和第（8）步一样一样的。将[2,3,4]排序之后变为：

（11）排序完之后还差[7]和[10,9]没排序，[7]排序和（8）排序一样一样的（我都佩服自己怎么能举出这么棒的例子）

（12）排序[10，9]，以10为参照物，left为【8】，right为【9】，right向右查找比10小的数据，查找到了9，left和right相遇，交换10和9的位置

排序完成！

代码

public static void main(String[] args) {
        int[] a = {8,5,10,4,2,1,3,6,7};
        int left = 0;
        int right = a.length - 1;
        QuickSortMain sort = new QuickSortMain();
        sort.sort(a, left, right);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
        }
    }
    private void sort(int[] a, int left, int right) {
        if (left > right) {
            return;
        }
        int i = left;
        int j = right;
        int sign = a[left];
        while (i != j) {
            //查找比sign小的元素位置
            while (a[j] >= sign && i < j) {
                j--;
            }
            //查找比sign大的元素位置
            while (a[i] <= sign && i < j) {
                i++;
            }
            //交换
            if (i < j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        //相遇或者遇到（8）（10）（11）等情况，直接交换
        a[left] = a[j];
        a[j] = sign;

        //分割数组重新排序
        sort(a, left, j - 1);
        sort(a, j + 1, right);
    }
}

运行结果：

总结

快速排序，核心是分组之后再分组，然后将每个组排序，最终排完之后就是有序数组了。至于代码里面的时间复杂度、空间复杂度，后面会加一下。

这里以下是废话，有时间就看，没时间就趁热练习一下快速排序

自从给自己定目标写文章，写文章的初衷很简单，为了学习，为了应付面试入职的时候面试官可能会看一眼的情况（不小心说漏嘴了，偷笑偷笑偷笑），为了一丢丢的虚荣心（尽管我的博客没什么人看，没什么人给我提提意见啥的，倒是有的文章别看只有一两条评论竟然都是夸我写的好的，尽管看到类似这样评论的时候我面不改色，但是我心里却是暗自窃喜）。但是后面慢慢开始发现，但它带给我的收获更多的是潜移默化的，可能有人和我一样，以为自己有过目不忘，心领神会的本领，但是一遇到你要解决它的时候，就会发现自己其实什么都不知道。写文章可以解决大部分问题，因为在研究某个技术的时候，不落在纸上，没有组织语言的过程，其实技术就不是自己的，剖开技术的表层，研究它深层次的逻辑，它才是属于自己的。

另外，写文章也锻炼了我除了技术方面以外的能力，比如排版，找到一些好的辅助说明的画图工具，做一些人生规划之类等等，它是一面好的镜子。比如写博客的时候会用到工具，为了表达的更清晰明了，我常常搜索各种工具，但是总也没有满意的，比如上面的文章，我本来打算用Excel表示排序过程，结果我排完了序，就成了这个样子，我都想把自己拉黑了，后来又从网上找画图工具，都不太理想。后来只能仿照其他文章，一条一条的展示数据，感觉一般般吧。写一篇文章其实也挺考验美感的。

总之一句话，其实我就想让你顶一个，哈哈哈哈哈