目录
高快省的排序算法
排序算法显神威
总结
高快省的排序算法
有没有既不节约空间又能够快一点的排序算法呢？那就是“疾速排序”啦！光听这个名字是不是就感觉很高端呢。
假如咱们当初对“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在序列的第1位。咱们的指标是将6挪到序列两头的某个地位，假如这个地位是k。当初就须要寻找这个k，并且以第k位为分界点，右边的数都小于等于6，左边的数都大于等于6。想一想，你有方法能够做到这点吗？
排序算法显神威
办法其实很简略：别离从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，而后替换他们。这里能够用两个变量i和j，别离指向序列最右边和最左边。咱们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最右边（即i=1），指向数字6。让哨兵j指向序列的最左边（即=10），指向数字。
首先哨兵j开始出动。因为此处设置的基准数是最右边的数，所以须要让哨兵j先出动，这一点十分重要（请本人想一想为什么）。哨兵j一步一步地向左移动（即j–），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右移动（即i++），直到找到一个数大于6的数停下来。最初哨兵j停在了数字5背后，哨兵i停在了数字7背后。
当初替换哨兵i和哨兵j所指向的元素的值。替换之后的序列如下：
6 1 2 5 9 3 4 7 10 8
到此，第一次替换完结。接下来开始哨兵j持续向左移动（再情谊揭示，每次必须是哨兵j先登程）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也持续向右移动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行替换，替换之后的序列如下：
6 1 2 5 4 3 9 7 10 8
第二次替换完结，“探测”持续。哨兵j持续向左移动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i持续向右挪动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3背后。阐明此时“探测”完结。咱们将基准数6和3进行替换。替换之后的序列如下：
3 1 2 5 4 6 9 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 1 3 5 4
OK，当初3曾经归位。接下来须要解决3右边的序列“2 1”和左边的序列“5 4”。对序列“2 1”以2为基准数进行调整，处理完毕之后的序列为“1 2”，到此2曾经归位。序列“1”只有一个数，也不须要进行任何解决。至此咱们对序列“2 1”已全副处理完毕，失去序列是“1 2”。序列“5 4”的解决也仿照此办法，最初失去的序列如下：
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 class QuickSort {
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp就是基准位
temp = arr[low];
while (i<j) {
//先看左边，顺次往左递加
while (temp<=arr[j]&&i<j) {
j--;
}
//再看右边，顺次往右递增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则替换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最初将基准为与i和j相等地位的数字替换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}
public static void main(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
总结
本篇文章就到这里了，心愿能给你带来帮忙
转载请注明原文链接：关于java:java实现快速排序图文详解
