当前位置：首页 > 编程日记 > 正文

java 快排_八大排序-快速排序（搞定面试之手写快排）

编程日记 2024-05-15 23:40:00

概要

快速排序由C. A. R. Hoare在1960年提出，是八大排序算法中最常用的经典排序算法之一。其广泛应用的主要原因是高效，核心算法思想是分而治之。快速排序经常会被作为面试题进行考察，通常的考察思路是快排思想、编码实践之手写快排以及进一步对快排的优化。事实上在Java标准库中Arrays类的sort方法里源码也正是使用了优化后的快速排序(具体源码以及优化分析后续会推文讲解)，掌握快排算法对于数据结构与算法入门极为重要。

原理

快速排序的核心思想是分治：选择数组中某个数作为基数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数都比基数小，另外一部分的所有数都都比基数大，然后再按此方法对这两部分数据分别进行快速排序，循环递归，最终使整个数组变成有序。

基数选择

由于快速排序需要选定一个基数进行划分排序，关于基数选择有很多方式，而基数选择直接关系到快排的效率。事实上，选取基准元素应该遵循平衡子问题的原则：即使得划分后的两个子序列的长度尽量相同本篇以待排序数组首元素作为基数进行说明。本篇以最常见的使用数组首元素作为基数进行快速排序原理说明。

一趟排序

以数组int n[] = { 6, 5, 2, 7, 3, 9, 8, 4, 10, 1 }为例：

以第一个数字6作为基数，使用双指针i,j进行双向遍历：

1、i从左往右寻找第一位大于基数(6)的数字，j从右往左寻找第一位小于基数(6)的数字；
2、找到后将两个数字进行交换。继续循环交换直到i>=j结束循环；
3、最终指针i=j,此时交换基数和i(j)指向的数字即可将数组划分为小于基数(6)/基数(6)/大于基数(6)的三部分，即完成一趟快排；

伪代码

见编码注释

编码实践

public class Test {

public static void main(String[] args) {

int n[] = { 6, 5, 2, 7, 3, 9, 8, 4, 10, 1 };

quicksort(n);

System.out.print("快排结果：");

for (int m : n) {

System.out.print(m + " ");

}

public static void quicksort(int n[]) {

sort(n, 0, n.length - 1);

}

public static void sort(int n[], int l, int r) {

if (l < r) {

// 一趟快排，并返回交换后基数的下标

int index = patition(n, l, r);

// 递归排序基数左边的数组

sort(n, l, index - 1);

// 递归排序基数右边的数组

sort(n, index + 1, r);

}

public static int patition(int n[], int l, int r) {

// p为基数，即待排序数组的第一个数

int p = n[l];

int i = l;

int j = r;

while (i < j) {

// 从右往左找第一个小于基数的数

while (n[j] >= p && i < j) {

j--;

}

// 从左往右找第一个大于基数的数

while (n[i] <= p && i < j) {

i++;

}

// 找到后交换两个数

swap(n, i, j);

}

// 使划分好的数分布在基数两侧

swap(n, l, i);

return i;

}

private static void swap(int n[], int i, int j) {

int temp = n[i];

n[i] = n[j];

n[j] = temp;

}

结果

快排结果：1 2 3 4 5 6 7 8 9 10

结语

本篇以最简单的形式讲解八大排序之一的快速排序的核心思想和具体实现，快速排序是相对其他排序出现频率最高的排序算法。关于8大排序算法，建议的0基础学习路线是先理解算法思想再进行编码实践。最后,如果觉得本篇对你有所启发或帮助，不妨关注一波0.0

关注订阅号获取更多干货～

https://www.dkcj.cn/info/6416.html

java 快排_八大排序-快速排序（搞定面试之手写快排）

相关文章：

maven命令简介

分治策略解决幂乘问题

用java实现一个计算器程序_1.2第一个java程序——hello world

linux valgrind Memcheck--内存检查工具

Cassandra 1.2 发布，NoSQL 数据库

CQRS实践(3): Command执行结果的返回

iOS学习——核心动画之Layer基础

linux valgrind memCheck ---内存检查工具的可视化方法valkyrie

屏幕为什么要正负压供电_负压变换器的设计

DataCleaner 3.1.1 发布，数据质量分析管理

IIS负载均衡-Application Request Route详解第三篇：使用ARR进行Http请求的负载均衡（上）...

云主机启动提示Booting from Hard Disk GRUB

函数 tostring_Kotlin实战之Fuel的高阶函数

linux valgrind 安装和使用

UIPopoverController在ARC环境下用法注意

CPLD的分频语言

彻底解决web开发中遇到的路径问题（上）

关于Page翻页效果--Page View Controller

linux平台下QtCreator中集成Valgrind系列工具

python输入参数改变图形_Python基于Tensor FLow的图像处理操作详解

CSS层叠样式

windows下 Source Monitor代码度量工具的使用

MVVM 数据绑定

linux配置文件怎么把某行后几个字符替换_vim（Linux运维）

Debian 6.0 安装过程及中文乱码

git 提交丢失Warning, you are leaving 2 commits behind,

一台支持vlan管理的交换机_关于交换机的VLAN技术你了解多少？

需要反射时使用dynamic

Linux平台下QtCreator集成代码静态分析工具clang-tidy和Clazy

JAVA swing初级教程(四)