最近在学习排序算法，网上快速排序教程很多，看了不少，有很多思想讲解非常精彩细致，但代码运行好像有问题，自己选择了一种比较容易接受的排序思想进行学习。
一.思想
1.选择一个基准数（基准数就是数组元素之间相互比较的一个参考系），一般选择最左边的数和最右边的数作为基准；
2.如果是从小到大的排序，则按照一定的方法（这个方法就会使用到基准数，和基准数进行比较）将比基准数小的数放在基准数左边，将比基准数大的数放在基准数右边；
3.当一轮排序结束后，基准数左边的数比基准数小，基准数有的数比基准数大；
4.将基准数左边、右边的数列均看作要排序的子序列，使用同样的方法进行排序。
以上为快速排序的基本思想，有区别的地方在于第2点中的按照一定的方法达到第3点的效果时的方法具体是怎样的，这个地方应该就是算法可以创新的地方，网上的方法可谓百花齐放，网上比较流行的有“挖坑填数+分治”、“经过一轮排序后将基准数与左右指针相遇时的数进行交换”等等。
本文采用的方法是：
（1）.以最右边的数为基准数，首先移动左指针（左指针从数组最左边开始，右指针从数组最右边开始），从左至右寻找比基准数大的数，若没找到，左指针向右移动；若找到了，左指针指向的数与右指针指向的数进行交换，左指针与基准数交换；（从整体上看，小的数放在了左边，大的数放在了右边）
（2）第一步的交换完成后，再移动右指针，从右至左寻找比基准数小的数，如果没找到，右指针向左移动；若找到了，则将右指针指向的数与左指针指向的数进行交换；（小的数）
（3）重复步骤（1）、（2），直至不满足left < right,说明一轮排序结束，进行下一轮。
快速排序的时间复杂度为：O(nlogn)
网上有一篇高分帖以左边的数为基准数，i为左指针，j为右指针，文章描述首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么），当时我看到这里我就在想这点为什么重要，为什么要要按照这样的方式执行，如果从基准数的这边开始移动，会出现什么问题吗？确实可以思考下。
二.代码实现
public static void sort(int[] array,int left,int right){ //如果left>=right,则说明已排好序，不需要递归排序了 if(left < right){ int res = res(array,left,right); sort(array,left,res-1); sort(array,res+1,right); } } //返回一轮排序后basic元素所在的位置 public static int res(int[] arr,int left,int right){ //基准数 int basic = arr[right]; //进行一轮排序 while(left < right){ //先移动左指针,找大数,比basic大的数 while(arr[left] <= basic && left < right){ ++left; } //如果找到了，就交换，大数arr[left]与basic交换，交换后左指针所在位置的数变成了basic if(left < right){ int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } //移动右指针，找小数，比basic小的数 while(arr[right] >= basic && left < right){ --right; } //如果找到了，就交换，小数与左指针交换，也就是小数arr[right]与basic交换 //两次交换中basic作为了中介，第一次交换大数被换到basic右边，第二次交换 //小数被换到basic左边,两次交换虽然外观上表显示为是arr[left]和arr[right] //的交换，但实际上每次交换中arr[left]和arr[right]中有一个元素为basic，所以 //每次都是和basic进行的交换，而当初找到的数也是和basic进行比较才得出来的 //谁比basic大，谁比basic小,最终表现形式为小的数被换到左边，大的数被换到右边 if(left < right){ int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } } return left; }
