一种快速节能的排序算法
有没有不浪费空间，即使一点点也能快速排序的算法？ 那是“快速排序”！ 光是听到这个名字你就觉得高端吗？
假设现在对“6 1 2 7 9 3 4 5 10 8”这10个数进行了排序。 首先，在这个序列中适当地找数量作为基准数。 (请不要被这个名词吓到。 是为了参照的数量。 我知道以后有什么用。 为了方便，以最初的数6为基准数吧。 接下来，需要将该序列中大于基准数的数都配置在6的右侧，将小于基准数的数配置在6的左侧。 如下排列。
3 1 2 5 4 6 9 7 10 8
在初始状态下，数字6位于序列的第一位。 我们的目标是假设这个位置是k，将6移动到序列中间的某个位置。 我现在需要找这个k。 并且，以第k个为边界点，左边的数都在6以下，右边的数都在6以上。 想想看。 你有办法做那个吗？
排序算法发挥神威
方法很简单。 分别从初始排列“6 1 2 7 9 3 4 5 10 8”的两端进行“探测”。 先从右向左找小于6的数，然后从左向右找大于6的数，交换他们。 其中，两个变量I和j可以分别指向序列的最左侧和最右侧。 我们给这两个变量取个好名字“哨兵I”和“哨兵j”。 wgdmz使哨兵I指向序列的最左边(即i=1)，指向数字6。 哨兵j指向序列的最右边=10，然后指向数字。
首先哨兵j开始出动了。 这里设定的基准数是最左边的数，所以哨兵j需要先出动是非常重要的(请自己想想为什么)。 哨兵j一步一步向左移动，直到找到不足6的数量为止。 然后哨兵I再向右移动一步，直到找到数量大于6的数字(即I )。 最后哨兵j停在数字5之前，哨兵I停在数字7之前。
现在交换哨兵I和哨兵j所指要素的值。 更换后的顺序如下
6 1 259 3 4710 8
第一次交换到此结束。 接下来哨兵j继续向左移动。 (友情提醒，每次哨兵j必须先出发。 他发现4 (小于标准数6，满足要求)就停下来了。 哨兵I也继续向右移动，他发现9 (大于标准数6，符合要求)就停下来了。 此时再次进行更换，更换后的顺序如下。
6 1 2 54397 10 8
第二次交换结束，“探测”继续。 哨兵j继续向左移动，他发现3 (小于标准数6，符合要求)又停下来了。 哨兵I继续向右移动，很辛苦！ 哨兵I和哨兵j相遇时，哨兵I和哨兵j都走到3前面。 表示“探测”在此时结束。 交换基准数6和3。 更换后的顺序如下
31 2 5 469 7 10 8
第一次“勘探”到此真的结束了。 此时，以基准数6为边界点，6的左边的数量都在6以下，6的右边的数量都在6以上。 回顾刚才的过程，其实哨兵j的使命是寻找比标准数小的数，哨兵I的使命是寻找比标准数大的数直到I和j见面。
OK，说明结束了。 现在，基准数6已经就位，它正好位于序列的第6位。 这时，我们把原来的序列，以6为边界点分为两个序列。 左边的序列是“3 1 2 5 4”，右边的序列是“9 7 10 8”。 必须分别处理这两个序列。 6因为左边和右边的序列至今仍很混乱。 但是没关系。 我们掌握了方法。 接下来模拟刚才的方法分别处理6的左边和右边的排列就可以了。 首先，让我们处理6的左边序列。
左边的序列是“3 1 2 5 4”。 请以该系列为3为基准数，调整为3的左边数均在3以下，3的右边数均在3以上。 好的，蘸钢笔吧
如果模拟没有错误，则调整完成后的序列顺序如下。
2 135 4
OK，现在3号已经回到座位上了。 接下来需要处理3的左序列“2 1”和右序列“5 4”。 将序列“2 1”调整为基准数2，处理完成后的序列为“1 2”，至此2恢复。 序列“1”只有一个数，不需要任何处理。 这样，排列“2 1”全部被处理，所得到的排列为“1 2”。 序列“54”的处理也仿照该方法，最终得到的序列如下。
1 2 3 4 5 6 9 7 10 8
对于序列“9 7 10 8”，也模拟刚才的过程，直到无法分割新的子序列为止。 最终，可以得到以下序列
1 2 3 4 5 6 7 8 9 10
排序到此结束。 细心的学生可能已经注意到，对快速排序的每一回合的处理，其实都是撤消此回合的基准数，并在所有数都撤消之前排序完毕。 上面霸气的图说明整个算法的处理过程。
为什么会这样呢？
快速排序更快。 因为与泡沫排序相比，每次交换都是跳跃式的。 每次排序时设置一个基准点，基准点以下的数量全部配置在基准点的左侧，基准点以上的数量全部配置在基准点的右侧。 就这样
每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。我们后面还会遇到“二分”思想，到时候再聊。先上代码，如下代码实现：
public classQuickSort {//arr 需要排序的数组//low 开始时最左边的索引=0//high 开始时最右边的索引=arr.length-1
public static void quickSort(int[] arr, int low, inthigh) {inti, j, temp, t;if (low >high) {return;
}
i= low;//左边哨兵的索引
j = high;//右边哨兵的索引//temp就是基准位
temp = arr[low];//以最左边为 基准位
while (i 基准位的数 时//继续从右往左找(同时 j 索引-1)//找到后会跳出 while循环
while (temp <= arr[j] && i
j--;
}//再看左边，依次往右递增//步骤和上面类似
while (temp >= arr[i] && i
i++;
}//如果满足条件则交换
if (i
z =arr[i];
y=arr[j];//左右哨兵 交换数据(互相持有对方的数据)
arr[i] =y;
arr[j]=z;
}
}//这时 跳出了 “while (i
arr[low] = arr[i];//或 arr[low] = arr[j];
arr[i] = temp;//或 arr[j] = temp;//i=j//这时 左半数组
quickSort(arr, low, j - 1);//递归调用右半数组
quickSort(arr, j + 1, high);
}public static voidmain(String[] args) {int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
quickSort(arr,0, arr.length - 1);for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
输出为1
2
2
3
4
4
7
7
8
9
10
19
62