[Java面试总结] 快速排序 (两种实现思路)

昨天面试, 面试官让我说说快排的实现方法，于是我迅速的说出了我的想法。（这么简单我怎么可能不会），但是我说的是下面的交换法，面试官好像没有明白。。。。说每次只能挖一个坑，怎么能挖两个坑呢？（可能是我说的不够清楚）， 然后面试官说我的解法有问题，给我说了下面的 挖坑填坑法。。。

我一听觉得是对的，但是我的也是对的，可是面试官好像比较执着于第二种 挖坑法（是我表达的问题），我当时就蒙了。。。
于是我决定好好整理一下这两种方法，一探究竟。
感谢面试官，让我弥补了自己的不足点，学会了很多。

快速排序算法的核心是：
每次将一个选定的基准数挪到待排序列中的某一位置（假设为位置K），使得以K为分界点，左边的数都小于等于基准数，右边的数都大于等于基准数。
然后以K为分界点，递归操作序列[0, K-1] 和 序列[K+1, n]。

假设我们现在对 “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 为基准数，这里我们用两个变量 i 和 j 分别指向序列的最左边和最右边。每次我们找到两个违规的数，将他们进行交换。

第一次交换：先让 j 从右边往左找到一个比 6 小的数 5，再让 i 从左往右找到一个比 6 大的数 7,

交换 i 和 j 所找到的数。

第二次交换：先让 j 从右边往左找到一个比 6 小的数 4，再让 i 从左往右找到一个比 6 大的数 9,

交换 i 和 j 所找到的数。

第三次交换：先让 j 从右边往左找到一个比 6 小的数 3，再让 i 从左往右找到一个比 6 大的数， 当 i == j 时 停止查找。这时i, j 都指向比 6 小的数 3。

交换第一个数(基准数)6 和 3。

至此一轮的交换法完成，使得 6 左边的数都不大于它，右边的数都不小于它。

注意：
因为基准数在最左边，所以一定要 j 先要开始从右往左找小于 基准数的数，因为这使得最后当 i == j 时， 它们指定的值一定小于基准数，最后将这个数和基准数交换，就使得小于基准数的数到了左边。

二 挖坑填坑法：
同理，我们从初始序列的两端开始探索。第一个数 6 为基准数（相当于在这挖一个坑），将基准数6存入一个临时变量中。我们用两个变量 i 和 j 分别指向序列的最左边和最右边。每次我们从某一端找到一个违规的数，将其填入坑中，这时违规数的位置就变成了一个坑，再从另一端找到一个违规数，将其填入新的坑中。以此类推。。。

初始状态：

j从右往左找到一个比6 小的数5， 将其填入 i 指向的坑中，并在j 处挖一个新坑。

i从左往右找到一个比6 大的数7， 将其填入 j 指向的坑中，并在i 处挖一个新坑。

以此类推
j从右往左找到一个比6 小的数4， 将其填入 i 指向的坑中，并在j 处挖一个新坑。

i从左往右找到一个比6 大的数9， 将其填入 j 指向的坑中，并在i 处挖一个新坑。
以此类推
j从右往左找到一个比6 小的数3， 将其填入 i 指向的坑中，并在j 处挖一个新坑。

i从左往右找到一个比6 大的数, 当 i == j 时停止。将基准数填入 i,j指向的坑中。

到此，挖坑填坑结束。

代码实现：

package com.STILLxjy; import java.util.Scanner; public class QuickSort { int n; int[] arr = null; //交换法 public void quickSort_swap(int left, int right) { //序列大小为1时返回 if(left >= right) return; int i = left, j = right, tmp; while(i != j) { //先让 j 从右边往左找到一个比 基准数 小的数 while(i != j && arr[j] >= arr[left]) j--; //再让 i 从左往右找到一个比 基准数 大的数 while(i != j && arr[i] <= arr[left]) i++; //当 i != j 时，交换两个违规的数 if(i != j) { tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp; } } //将基准数和最后确定的数进行交换 tmp = arr[left]; arr[left] = arr[j]; arr[j] = tmp; //递归处理左右子序列 quickSort_swap(left, j-1); quickSort_swap(j+1, right); } //挖坑填坑法 public void quickSort_diging(int left, int right) { //序列大小为1时返回 if (left >= right) return; // 将基准数存入临时变量tmp中，i,j指向左右两端 int tmp = arr[left], i = left, j = right; while(i != j) { //j从右往左找到一个比6 小的数， 将其填入 i 指向的坑中，并在j 处挖一个新坑 while(i != j && arr[j] >= tmp) j--; if(i != j) arr[i] = arr[j]; //i从左往右找到一个比6 大的数， 将其填入 j 指向的坑中，并在i 处挖一个新坑。 while(i != j && arr[i] <= tmp) i++; if(i != j) arr[j] = arr[i]; } //当 i == j 时停止。将基准数填入 i,j指向的坑中。 arr[j] = tmp; //递归处理左右子序列 quickSort_diging(left, j-1); quickSort_diging(j+1, right); } public void init() { Scanner in = new Scanner(System.in); n = in.nextInt(); arr = new int[n]; for(int i =0; i < n; i++) { arr[i] = in.nextInt(); } } public static void main(String[] args) { QuickSort qs = new QuickSort(); qs.init(); //qs.quickSort_swap(0, qs.n-1); qs.quickSort_diging(0, qs.n-1); for(int i =0; i < qs.n; i++) { System.out.print(qs.arr[i]); } System.out.println(""); } } 

本文地址：https://blog.csdn.net/STILLxjy/article/details/108847939