欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-28 17:14:51
快速排序算法的核心是:每次将一个选定的基准数挪到待排序列中的某一位置(假设为位置K),使得以K为分界点,左边的数都小于等于基准数,右边的数都大于等于基准数。 然后以K为分界点,递归操作序列[0, K-1] 和 序列[K+1, n]。假设我们现在对 “6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为 基准数 (就是一个用来参照的数),为了方便,就让 第一个数 6作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基...

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

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

快速排序算法的核心
每次将一个选定的基准数挪到待排序列中的某一位置(假设为位置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 分别指向序列的最左边和最右边。每次我们找到两个违规的数,将他们进行交换。
[Java面试总结] 快速排序  (两种实现思路)
第一次交换:先让 j 从右边往左找到一个比 6 小的数 5,再让 i 从左往右找到一个比 6 大的数 7,
[Java面试总结] 快速排序  (两种实现思路)
交换 i 和 j 所找到的数。
[Java面试总结] 快速排序  (两种实现思路)

第二次交换:先让 j 从右边往左找到一个比 6 小的数 4,再让 i 从左往右找到一个比 6 大的数 9,
[Java面试总结] 快速排序  (两种实现思路)
交换 i 和 j 所找到的数。
[Java面试总结] 快速排序  (两种实现思路)
第三次交换:先让 j 从右边往左找到一个比 6 小的数 3,再让 i 从左往右找到一个比 6 大的数, 当 i == j 时 停止查找。这时i, j 都指向比 6 小的数 3。
[Java面试总结] 快速排序  (两种实现思路)
交换第一个数(基准数)6 和 3。
[Java面试总结] 快速排序  (两种实现思路)
至此一轮的交换法完成,使得 6 左边的数都不大于它,右边的数都不小于它。

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

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

初始状态:
[Java面试总结] 快速排序  (两种实现思路)

j从右往左找到一个比6 小的数5, 将其填入 i 指向的坑中,并在j 处挖一个新坑。
[Java面试总结] 快速排序  (两种实现思路)
i从左往右找到一个比6 大的数7, 将其填入 j 指向的坑中,并在i 处挖一个新坑。
[Java面试总结] 快速排序  (两种实现思路)
以此类推
j从右往左找到一个比6 小的数4, 将其填入 i 指向的坑中,并在j 处挖一个新坑。
[Java面试总结] 快速排序  (两种实现思路)
i从左往右找到一个比6 大的数9, 将其填入 j 指向的坑中,并在i 处挖一个新坑。[Java面试总结] 快速排序  (两种实现思路)
以此类推
j从右往左找到一个比6 小的数3, 将其填入 i 指向的坑中,并在j 处挖一个新坑。
[Java面试总结] 快速排序  (两种实现思路)
i从左往右找到一个比6 大的数, 当 i == j 时停止。将基准数填入 i,j指向的坑中。
[Java面试总结] 快速排序  (两种实现思路)
到此,挖坑填坑结束。

代码实现:

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