目录
高快省的排序算法
排序算法显神威
总结
高快省的排序算法
有没有既不节约空间又能够快一点的排序算法呢？那就是“疾速排序”啦！光听这个名字是不是就感觉很高端呢。
假如咱们当初对“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
总结
本篇文章就到这里了，心愿能给你带来帮忙