java 数据结构与算法 (快速排序法)
快速排序法：
顾名思议，快速排序法是实践中的一种快速的排序算法，在c++或对java基本类型的排序中特别有用。它的平均运行时间是0（N log N）。该算法之所以特别快，主要是由于非常精练和高度优化的内部循环。
快速排序是对冒泡法的一种改进。通过一趟排序将要排序的的数据分割成独立的两部分，其中一部分的所有数据都比另一部分所有的数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
示意图：
这里 定义最左边元素 为left 最右边元素为right
p 元素的值 就是 2对应的索引 0 加上 5对应的索引 7 之和 除以2 得到 索引为3 对应的元素7
用左边大于 7的数跟右边小于7的数进行 交换位置 一直进行 并且 中间的p也要一直变化位置
直到 排完
代码实现：
import java.util.Arrays;
public class kuaisu {
public static void main(String[] args) {
int arrays[]=new int[]{2,9,4,7,3,3,6,5};
sort(arrays,0,arrays.length-1);
System.out.println(Arrays.toString(arrays));
}
public static void sort(int arrays[],int left,int right){
int l=left ;//给定下标
int r=right;//给定下标
int temp; //定义一个变量 作为中间值 交换 左右两边的元素位置
int pivot=arrays[(left+right)/2];//中间值
while(l<r){
//在左边查找小于中间值得元素
while(arrays[l]<arrays[pivot]){
l++;
}
//同理在右边查找大于中间值得元素
while(arrays[r]>arrays[pivot]){
r--;
}//直到左边元素大于右边元素就结束
if(l>=r){
break;
}
temp=arrays[l];
arrays[l]=arrays[r];
arrays[r]=temp;
//交换完arrays[l]=pivot
if(arrays[l]==pivot){
r--;
}
if(arrays[r]==pivot){
l++;
}
if(r==l){ //要让左边元素 往左边移 右边元素往右边移 错开
l++;
r--;
} //对左边进行递归
if(left<r){
sort(arrays,left,r);
}//对右边进行递归
if(right>l){
sort(arrays,l,right);
}
}
}
}
控制台输出结果 如下：
到此这篇关于java 数据结构与算法 (快速排序法)的文章就介绍到这了,更多相关java 数据结构与算法 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
深入了解Java数据结构和算法之堆
目录 1.堆的定义 2.遍历和查找 3.移除 4.插入 5.完整的Java堆代码 总结 1.堆的定义 ①.它是完全二叉树,除了树的最后一层节点不需要是满的,其它的每一层从左到右都是满的.注意下面两种情况,第二种最后一层从左到右中间有断隔,那么也是不完全二叉树. ②.它通常用数组来实现. 这种用数组实现的二叉树,假设节点的索引值为index,那么: 节点的左子节点是 2*index+1, 节点的右子节点是 2*index+2, 节点的父节点是 (index-1)/2. ③.堆中的每一个节点的关键字
-
Java数据结构之基于比较的排序算法基本原理及具体实现
目录 1. 七大基于比较的排序-总览 1.1常见基于比较的排序分类 1.2时间复杂度,空间复杂度以及稳定性. 2.直接插入排序 2.1 直接插入排序的基本思想 2.2 直接插入排序动画演示 2.3 代码示例 2.4 时间复杂度,空间复杂度以及稳定性 3. 希尔排序 3.1 算法思想 3.2 图片演示 3.3 代码示例 3.4 时间复杂度,空间复杂度以及稳定性 4.选择排序 4.1 算法思想 4.2 动画演示 4.3 代码示例 4.4 时间复杂度,空间复杂度以及稳定性 5.堆排序 5.1 算法思想
-
带你了解Java数据结构和算法之哈希表
目录 1.哈希函数的引入 ①.把数字相加 ②.幂的连乘 2.冲突 3.开放地址法 ①.线性探测 ②.装填因子 ③.二次探测 ④.再哈希法 4.链地址法 5.桶 6.总结 1.哈希函数的引入 大家都用过字典,字典的优点是我们可以通过前面的目录快速定位到所要查找的单词.如果我们想把一本英文字典的每个单词,从 a 到 zyzzyva(这是牛津字典的最后一个单词),都写入计算机内存,以便快速读写,那么哈希表是个不错的选择. 这里我们将范围缩小点,比如想在内存中存储5000个英文单词.我们可能想到每个单词
-
带你了解Java数据结构和算法之无权无向图
目录 1.图的定义 ①.邻接: ②.路径: ③.连通图和非连通图: ④.有向图和无向图: ⑤.有权图和无权图: 2.在程序中表示图 ①.顶点: ②.边: 3.搜索 ①.深度优先搜索(DFS) ②.广度优先搜索(BFS) ③.程序实现 4.最小生成树 5.总结 1.图的定义 我们知道,前面讨论的数据结构都有一个框架,而这个框架是由相应的算法实现的,比如二叉树搜索树,左子树上所有结点的值均小于它的根结点的值,右子树所有结点的值均大于它的根节点的值,类似这种形状使得它容易搜索数据和插入数据,树的边表示
-
Java深入了解数据结构中常见的排序算法
目录 一,概念 1,排序 2,稳定性 二,排序详解 1,插入排序 ①直接插入排序 2,选择排序 ①直接选择排序 ②堆排序 3,交换排序 ①冒泡排序 ②快速排序 4,归并排序 一,概念 1,排序 排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作. 平时的上下文中,如果提到排序,通常指的是排升序(非降序). 通常意义上的排序,都是指的原地排序(in place sort). 2,稳定性 两个相等的数据,如果经过排序后,排序算法能保证其相对位置不发生变化,则我们称该算
-
带你了解Java数据结构和算法之2-3-4树
目录 1.2-3-4 树介绍 2.搜索2-3-4树 3.插入 1.节点分裂 2.根的分裂 4.完整源码实现 5.2-3-4树和红黑树 ①.对应规则 ②.操作等价 6.2-3-4 树的效率 总结 1.2-3-4 树介绍 2-3-4树每个节点最多有四个字节点和三个数据项,名字中 2,3,4 的数字含义是指一个节点可能含有的子节点的个数.对于非叶节点有三种可能的情况: ①.有一个数据项的节点总是有两个子节点: ②.有二个数据项的节点总是有三个子节点: ③.有三个数据项的节点总是有四个子节点: 简而言之
-
java 数据结构与算法 (快速排序法)
快速排序法: 顾名思议,快速排序法是实践中的一种快速的排序算法,在c++或对java基本类型的排序中特别有用.它的平均运行时间是0(N log N).该算法之所以特别快,主要是由于非常精练和高度优化的内部循环.快速排序是对冒泡法的一种改进.通过一趟排序将要排序的的数据分割成独立的两部分,其中一部分的所有数据都比另一部分所有的数据要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 示意图: 这里 定义最左边元素 为left 最右边元素为ri
-
java数据结构与算法之快速排序详解
本文实例讲述了java数据结构与算法之快速排序.分享给大家供大家参考,具体如下: 交换类排序的另一个方法,即快速排序. 快速排序:改变了冒泡排序中一次交换仅能消除一个逆序的局限性,是冒泡排序的一种改进:实现了一次交换可消除多个逆序.通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 步骤: 1.从数列中挑出一个元素,称为 "基准"(piv
-
java数据结构与算法之希尔排序详解
本文实例讲述了java数据结构与算法之希尔排序.分享给大家供大家参考,具体如下: 这里要介绍的是希尔排序(缩小增量排序法). 希尔排序:通过比较相距一定间隔的元素来工作:各趟比较所用的距离(增量)随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止.是插入排序的一种,是针对直接插入排序算法的改进. 算法思想:先将要排序的序列按某个增量d分成若干个子序列,对每个子序列中全部元素分别进行直接插入排序,然后再用一个较小的增量对它进行分组,在每组中再进行排序.当增量减到1时,整个要排序的数被分成一
-
java数据结构与算法之插入排序详解
本文实例讲述了java数据结构与算法之插入排序.分享给大家供大家参考,具体如下: 复习之余,就将数据结构中关于排序的这块知识点整理了一下,写下来是想与更多的人分享,最关键的是做一备份,为方便以后查阅. 排序 1.概念: 有n个记录的序列{R1,R2,.......,Rn}(此处注意:1,2,n 是下表序列,以下是相同的作用),其相应关键字的序列是{K1,K2,.........,Kn}.通过排序,要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn,使得相应关键
-
java数据结构与算法之冒泡排序详解
本文实例讲述了java数据结构与算法之冒泡排序.分享给大家供大家参考,具体如下: 前面文章讲述的排序算法都是基于插入类的排序,这篇文章开始介绍交换类的排序算法,即:冒泡排序.快速排序(冒泡排序的改进). 交换类的算法:通过交换逆序元素进行排序的方法. 冒泡排序:反复扫描待排序记录序列,在扫描的过程中,顺次比较相邻的两个元素的大小,若逆序就交换位置. 算法实现代码如下: package exp_sort; public class BubbleSort { public static void b
-
java数据结构与算法之桶排序实现方法详解
本文实例讲述了java数据结构与算法之桶排序实现方法.分享给大家供大家参考,具体如下: 基本思想: 假定输入是由一个随机过程产生的[0, M)区间上均匀分布的实数.将区间[0, M)划分为n个大小相等的子区间(桶),将n个输入元素分配到这些桶中,对桶中元素进行排序,然后依次连接桶输入0 ≤A[1..n] <M辅助数组B[0..n-1]是一指针数组,指向桶(链表).将n个记录分布到各个桶中去.如果有多于一个记录分到同一个桶中,需要进行桶内排序.最后依次把各个桶中的记录列出来记得到有序序列. [桶-
-
java数据结构排序算法之归并排序详解
本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重
-
Java 数据结构与算法系列精讲之排序算法
概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 冒泡排序 冒泡排序 (Bubble Sort) 是一种简单的排序算法. 它重复地遍历要排序的数列, 一次比较两个元素, 如果他们的顺序错误就把他们交换过来. 遍历数列的工作是重复地进行直到没有再需要交换, 也就是说该数列已经排序完成. 这个算法的名字由来是因为越小的元素会经由交换慢慢 "浮" 到数列的顶端. 冒泡排序流程: 通过比较相邻的元素, 判断两个元素位置是否需要互换 进行 n-1 次比较,
-
Java数据结构与算法实现递归与回溯
目录 1.什么是递归? 2.代码案例一——迷宫问题 3.代码案例二——八皇后问题 1.什么是递归? 简单的说: 递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁. 看个实际应用场景,迷宫问题(回溯), 递归(Recursion) 我列举两个小案例,来帮助大家理解递归,这里在给大家回顾一下递归调用机制 打印问题 阶乘问题 public static void test(int n) { if (n > 2) { test(n - 1); }
-
Java数据结构BFS广搜法解决迷宫问题
目录 1.例题 题目描述 输入 输出 测试数据 2. 思路分析 基本思想 具体步骤 代码实现 3.BFS小结 求解思路: 注意 1.例题 题目描述 迷宫由 n 行 m 列的单元格组成,每个单元格要么是空地,要么是障碍物.其中1表示空地,可以走通,2表示障碍物.给定起点坐标startx,starty以及终点坐标endx,endy.现请你找到一条从起点到终点的最短路径长度. 输入 第一行包含两个整数n,m(1<=n,m<=1000).接下来 n 行,每行包含m个整数(值1或2),用于表示这个二维