当前位置：首页 > news >正文

做购物网站优化神马排名软件

news 2025/8/4 21:02:42

做购物网站,优化神马排名软件,北京网页设计公司排名,网站带薪歌手都要怎样做呀心无挂碍，无挂碍故，无有恐怖，远离颠倒梦想，究竟涅槃。地图引子代码地址快速排序核心代码优劣完整代码演示课后习题引子搭嘎好！本人最近看的《啊哈算法》这本书写的确实不错，生动形象，在保…

心无挂碍，无挂碍故，无有恐怖，远离颠倒梦想，究竟涅槃。

地图

引子
代码地址
快速排序
- 核心代码
- 优劣
- 完整代码
- 演示
课后习题

引子

搭嘎好！本人最近看的《啊哈算法》这本书写的确实不错，生动形象，在保持算法讲解准确性的同时又不失趣味性。

但对我来说，稍显遗憾的是，书籍代码是c语言，而不是本人常用的Java。

那就弥补遗憾，说干就干，把这本书的示例语言用java给翻译一遍！！！

于是就有了本篇博客，这是第三篇博客，主要讲解快速排序。
在这里插入图片描述

来不及买纸质书但又想尽快感受算法魅力的童鞋也甭担心，电子版的下载链接已经放到下方了，可尽情下载。

链接：https://pan.baidu.com/s/1imxiElcCorw2F-HJEnB-PA?pwd=jmgs
提取码：jmgs

代码地址

本文代码已开源：

git clone https://gitee.com/guqueyue/my-blog-demo.git

请切换到gitee分支，

然后查看aHaAlgorithm模块下的src/main/java/com/guqueyue/aHaAlgorithm/chapter_1_Sort即可！

快速排序

快速排序，名字听起来就很快！

那么，这么快的排序是怎么实现的呢？我们这里以升序为例（降序的话找数的逻辑相反），把它拆解成以下几步：

选定一个基准值，这里我们一般选取第一个数为基准值
设定双指针，也就是书里面说的哨兵。

2.1 一个哨兵从右往左走找比 基准值小(大) 的数，一个哨兵从左往右找比 基准值大(小) 的数，找到了就交换两个数。

2.2 等到两个哨兵相遇就交换基准值和哨兵

这样数组的左边都是比 基准值小(大) 的数，右边都是比 基准值大(小) 的数。
以 左边界 和 基准值位置-1 为一个数组，右边界 和 基准值位置+1 为一个数组，再进行如上操作。

一直到左右边界相遇，则排序完成。

在这里插入图片描述

当然，这里面采用了递归的编程技巧，实现了分而治之的编程思想，才能达到我们想要的目的。

关于这个，我当初写的关于《算法图解》第三章<递归>、第四章<快速排序>里面也有相应的介绍：

肝了几万字，送给看了《算法图解》却是主攻Java的你和我（上篇）

相比于《算法图解》那本书，这本书讲快速排序明显要更加清晰直观。

下面是快速排序整体的流程图：
在这里插入图片描述

还没懂？列一个快速排序第一次交换的动图，是不是清晰很多了呢？

在这里插入图片描述
如果还是不是很明白，就去看书吧，里面有详细的图文步骤，我这里就不多加赘述啦。

核心代码

话已经说了很多了，直接上代码：

	/*** @Description 快速排序* @Param [arr: 数组, left: 左边界, right: 右边界]* @return void**/private static void quickSort(int[] arr, int left, int right) {if (left > right) { // 左边不能大于右边return;}int temp = arr[left]; // 基准值int i = left, j = right;while (i < j) {// 找到比基准值更小的数，右边先找(为啥一定要右边先找？ - 1 3 2) 防止基准值是最小的数，左边先走，就会把基准值交换掉while (arr[j] >= temp && i < j) {j--;}// 找到比基准值更大的数,这边必须设置等于temp，不然左边的数不会走while (arr[i] <= temp && i < j) {i++;}// 如果没有相遇，则： i == j 时，没必要交换if (i < j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;}}// 基准值归位arr[left] = arr[j];arr[j] = temp;// 这里 i,j 是相等的quickSort(arr, left, j-1); // 左半边继续排序quickSort(arr, j+1, right); // 右半边继续排序}

优劣

空间复杂度为O(N)，属于 原地排序算法 了，即不占用额外的空间。
平均时间复杂度为O(NlogN), 但是有些情况下时间复杂度最高可达O(N^2)，不过问题不大，最坏的情况也就和冒泡排序一样不是？

上面说到快速排序有最坏的情况时间复杂度为O(N^2)，你能想到是哪种情况吗？

想不到的话也没关系，下文有提示。

完整代码

诺：

package com.guqueyue.aHaAlgorithm.chapter_1_Sort;import java.util.Arrays;
import java.util.Scanner;/*** @Author: guqueyue* @Description: 快速排序* @Date: 2024/1/10**/
public class QuickSort {public static void main(String[] args) {// 获取整数数组int[] arr = getArr();System.out.println("输入的数组为：" + Arrays.toString(arr));// 快速排序quickSort(arr, 0, arr.length - 1);System.out.println("排序后的数组为：" + Arrays.toString(arr));}/*** @Description 快速排序* @Param [arr: 数组, left: 左边界, right: 右边界]* @return void**/private static void quickSort(int[] arr, int left, int right) {if (left > right) { // 左边不能大于右边return;}int temp = arr[left]; // 基准值int i = left, j = right;while (i < j) {// 找到比基准值更小的数，右边先找(为啥一定要右边先找？ - 1 3 2) 防止基准值是最小的数，左边先走，就会把基准值交换掉while (arr[j] >= temp && i < j) {j--;}// 找到比基准值更大的数,这边必须设置等于temp，不然左边的数不会走while (arr[i] <= temp && i < j) {i++;}// 如果没有相遇，则： i == j 时，没必要交换if (i < j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;}}// 基准值归位arr[left] = arr[j];arr[j] = temp;// 这里 i,j 是相等的quickSort(arr, left, j-1); // 左半边继续排序quickSort(arr, j+1, right); // 右半边继续排序}/*** @Description 获取整数数组* @Param []* @return int[]**/private static int[] getArr() {Scanner scanner = new Scanner(System.in);System.out.print("请输入数字个数：");int n = scanner.nextInt();int[] arr = new int[n];System.out.printf("请输入%d个数, 中间用空格隔开，再回车：", n);for (int i = 0; i < n; i++) {arr[i] = scanner.nextInt();}return arr;}
}