✅作者简介：热爱Java后端开发的一名学习者，大家可以跟我一起讨论各种问题喔。
🍎个人主页：Hhzzy99
🍊个人信条：坚持就是胜利！
💞当前专栏：【Java数据结构与算法】
🥭本文内容：Java数据结构与算法中的比较高级的排序，希尔排序、归并排序、快速排序、计数排序
文章目录
上一篇文章我们介绍了Java中的简单排序传送门🚩，本文介绍Java中的高级排序，希尔排序、归并排序、快速排序、计数排序
| 排序方法 | 时间复杂度（平均） | 时间复杂度（最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 希尔排序 | O(n1.5) | O(n²) | O(n) | O(1) | 不稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 |
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 快速排序 | O(nlog2n) | O(n²) | O(nlog2n) | O(nlog2n) | 不稳定 |
| 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 |
描述：
第一批突破O(n2)时间复杂度的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，他会优先比较距离较远的元素。希尔排序又叫 缩小增量排序
算法的核心思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接 插入排序，具体算法描述：
实现：
分解1： 先将数组根据长度分为length/2组（增量），并且将第一组的元素进行插入排序
可以先实现获取第一组的元素:
第一轮：增量10/2=5组
public static void main(String[] args) {
int[] arrs = new int[]{8,6,1,7,2,5,4,12,9,3};
//分组
int group = arrs.length / 2;
System.out.println("输出第一组的元素");
for (int j = 0; (j + group) < arrs.length; j += group){
int insert = j + group;
while ((insert - group) >= 0){
if(arrs[insert - group] > arrs[insert]){
//交换
int temp = arrs[insert - group];
arrs[insert - group] = arrs[insert];
arrs[insert] = temp;
//插入的指针向前移动
insert = insert - group;
}else {
break;
}
}
}
for (int i = 0; i < arrs.length; i++){
System.out.print(arrs[i] + ",");
}
}
分解2： 将第一轮分好的所有的组都进行插入排序。
第二轮：增量5/2=2组
外面嵌套一个小于group的循环
for (int i = 0; i < group; i++) {
for (int j = i; (j + group) < arrs.length; j += group){
int insert = j + group;
while ((insert - group) >= 0){
if(arrs[insert - group] > arrs[insert]){
//交换
int temp = arrs[insert - group];
arrs[insert - group] = arrs[insert];
arrs[insert] = temp;
//插入的指针向前移动
insert = insert - group;
}else {
break;
}
}
}
}
分解3： 执行完第一轮之后，再继续分组执行分解1和分解2的操作，最终到无法分组，排序完成
public static void main(String[] args) {
int[] arrs = new int[]{8,6,1,7,2,5,4,12,9,3};
//分组
int group = arrs.length;
//等于1时说明无法再分组了
while (group != 1){
//分组
group = group / 2;
for (int i = 0; i < group; i++) {
for (int j = i; (j + group) < arrs.length; j += group){
int insert = j + group;
while ((insert - group) >= 0){
if(arrs[insert - group] > arrs[insert]){
//交换
int temp = arrs[insert - group];
arrs[insert - group] = arrs[insert];
arrs[insert] = temp;
//插入的指针向前移动
insert = insert - group;
}else {
break;
}
}
}
}
}
/*int j = i;
while ((j + group) < arrs.length){
int insert = j + group;
while((insert - group) >= 0){
if(arrs[insert - group] > arrs[insert]){
//进行交换
int temp = arrs[insert - group];
arrs[insert - group] = arrs[insert];
arrs[insert] = temp;
//插入的指针向前移动
insert = insert - group;
}else {
break;
}
}
//j进行增量
j += group;
}*/
for (int i = 0; i < arrs.length; i++){
System.out.print(arrs[i] + ",");
}
}
描述：
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略即将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案 “修补” 在一起，即分而治之 。
归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了 名为TimSort的排序算法，就是归并排序的优化版本。每次合并操作的平均时月复杂度为O(n)，而完全二叉树的深度为|1og2n|。总的平均时间复杂度为O(nlogn)。而旦，归并排序的最好，最坏，平均时间复杂度均为o(nlogn)。
归井排序核心思想是先分再治,具体算法描述如下：
先将未排序数组/2进行分组,然后再将分好组的数组继续/2再次分组,直到无法分组,这个就是分的过程。
然后再将之后把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的，同时在合并的过程中完成数组的排列，最终直到全部小的数组合并起来，这个就是治的过程。
实现
分解1： 先实现分的思想，将数组分解进行实现
先获取数组的中轴，然后以中轴将数组分为两个部分
使用递归分别执行左右两部分分解
public static void main(String[] args) {
int[] arrs = {8,6,3,7,2,5,4,1};
mergeSort(arrs,0,arrs.length-1);
}
//实现归并排序
public static void mergeSort(int[] arrs, int first, int last){
//实现递归推出的条件
if(first >= last){
return;
}
//求出当前数组的中间值
int mid = (first + last)/2;
//将左边的数组继续分解
mergeSort(arrs,first,mid);
//将右边的数组继续分解
mergeSort(arrs,mid + 1, last);
//输出分组情况
//先输出左边的数组
for (int i = first; i <= mid; i++){
System.out.print(arrs[i] + " ");
}
System.out.print("--------");
//输出右边的数组
for (int i = mid + 1; i <= last; i++) {
System.out.print(arrs[i] + " ");
}
System.out.println(" ");
}
分解2： 实现具体治的过程，将左右两个数组合并到一个临时数组中
分别设计两指针i和j，遍历左右两个数组，取出元素进行比较，将小的元素放入到临时数组中。
然后将左右剩下的元素放入到数组中
将排序好的临时数组中的元素返回到未排序的数组中
public static void main(String[] args) {
int[] arrs = {8,6,3,7,2,5,4,1};
mergeSort(arrs,0,arrs.length-1);
//输出排序结果
for (int i = 0; i < arrs.length; i++) {
System.out.print(arrs[i] + " ");
}
}
//实现归并排序
public static void mergeSort(int[] arrs, int first, int last) {
//实现递归推出的条件
if (first >= last) {
return;
}
//求出当前数组的中间值
int mid = (first + last)>>>1;
//将左边的数组继续分解
mergeSort(arrs, first, mid);
//将右边的数组继续分解
mergeSort(arrs, mid + 1, last);
//治，实现插入并完成排序
int[] temp = new int[last + 1];
//定义两个指针
int i = first;//左边数组的遍历指针
int j = mid + 1;//右边数组的遍历指针
int t = 0;//临时数组的指针
//遍历左右两个数组，将较小的元素插入到临时数组中
while (i <= mid && j <= last) {
if (arrs[i] <= arrs[j]) {
//将左边的指针指向的元素插入到临时数组中
temp[t++] = arrs[i++];
} else {
//将右边的指针指向的元素插入到临时数组中
temp[t++] = arrs[j++];
}
}
//再将左右剩余的元素插入到临时数组中
while (i<=mid){
temp[t++] = arrs[i++];
}
while (j<=last){
temp[t++] = arrs[j++];
}
//还需要将临时数组中的元素复制到原始数组中
//先将t重置
t = 0;
//将t指向的值，复制到first指向的原始数组的位置
while (first <= last){
arrs[first++] = temp[t++];
}
}
描述:
快速排序是对冒泡排序的一种改进，通过分而治之的思想减少排序中交换和遍历的次数，整个过程可以通过递归的方式完成。
具体描述如下：
1.首先通过比较算法，找到基准数，比较过程通过交换最终达到基准数左边的数字都比右边的小。
2.然后以基准数作为中轴，将数组分为两部分，分别执行步骤1的算法（可以通过递归实现），直到无法再次分割排序完毕
递归
一个含直接或间接调用本函数语句的函数被称之为递归函数，他必须满足以下两个条件：
1）在每一次调用自己时，必须是（在某种意义上）更接近于解；
2）必须有一个终止处理或计算的准则；
基本格式
void func()
{
//递归条件
if(condition)
func();
else
//退出递归
}
实现
分解1： 创建左右两个指针，将最后一个值作为基准值，通过不断交换将数组分为两部分，左边的比右边的要小。
public static void main(String[] args) {
int[] arrs = {3,9,8,7,2,5,4,1,6};
//执行快速排序
quickSort(arrs);
for (int i = 0; i < arrs.length; i++) {
System.out.print(arrs[i] + " ");
}
}
//定义快速排序方法
public static void quickSort(int[] arrs){
//定义左指针
int left = 0;
//定义右指针
int right = arrs.length - 1;
//定义基准值
int pos = arrs.length - 1;
while (left != right){
//判断左指针是否比基准值大，如果大就停止移动
while(arrs[left] <= arrs[pos]){
left++;
}
if(left == right)
break;
//判断右指针是否比基准值小，如果小就停止移动
while (arrs[right] >= arrs[pos]){
right--;
}
if(left < right){
//交换左右指针指向的值
int temp = arrs[left];
arrs[left] = arrs[right];
arrs[right] = temp;
}
}
//当left和right重合之后，需要将重合的值和基准值进行交换
int temp = arrs[left];
arrs[left] = arrs[pos];
arrs[pos] = arrs[left];
}
分解2： 将以left和right的重复位置作为中轴，将数组分为两部分，左右分别执行分解1的操作，直到排序完成
public static void main(String[] args) {
int[] arrs = {3,9,8,7,2,5,4,1,6};
//执行快速排序
quickSort(arrs, 0, arrs.length-1);
for (int i = 0; i < arrs.length; i++) {
System.out.print(arrs[i] + " ");
}
}
//定义快速排序方法
public static void quickSort(int[] arrs, int first, int last){
//设置一下递归退出条件
if(first >= last)
return;
//定义左指针
int left = first;
//定义右指针
int right = last;
//定义基准值
int pos = last;
//当left不等于right
while (left != right){
//判断左指针是否比基准值大，如果大就停止移动
while(arrs[left] <= arrs[pos]){
left++;
}
//判断右指针是否比基准值小，如果小就停止移动
while (arrs[right] >= arrs[pos] && left < right){
right--;
}
if(left < right){
//交换左右指针指向的值
int temp = arrs[left];
arrs[left] = arrs[right];
arrs[right] = temp;
}
}
//当left和right重合之后，需要将重合的值和基准值进行交换
int temp = arrs[left];
arrs[left] = arrs[pos];
arrs[pos] = temp;
//将左边的数组执行快速排序
quickSort(arrs, first,left - 1);
//将右边的数组执行快速排序
quickSort(arrs,right + 1,last);
}
描述：
计数排序是一个非基于比较的排序算法，该算法于1954年由Harold H.Seward，提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为o(n+k)(其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n))，如归并排序，堆排序)
计数排序是一种适合于最大值和最小值的差值不是不是很大的排序，也就是说重复的数据会比较多的情况。
实现
分解1： 找到最大的数字，并且以数字的大小创建一个统计数组
//分解1：根据最大值创建统一数组
//遍历数组找到最大的值
int max = arrs[0];
for (int i = 0; i < arrs.length; i++) {
if(arrs[i] > max){
max = arrs[i];
}
}
//根据最大值创建统一数组
int[] countArrs = new int[max];
分解2： 遍历未排序的数组，统计每个数字出现的次数，根据下标添加到新的统计数组中
for (int i = 0; i < arrs.length; i++) {
//以arrs[i]作为下标++
countArrs[arrs[i]]++;
}
分解3： 将排序的结果返回到原先的数组中
public static void main(String[] args) {
int[] arrs = {0,2,1,3,0,2,0,1,1};
//分解1：根据最大值创建统一数组
//遍历数组找到最大的值
int max = arrs[0];
for (int i = 0; i < arrs.length; i++) {
if(arrs[i] > max){
max = arrs[i];
}
}
//分解2：
//根据最大值创建统一数组
int[] countArrs = new int[max + 1];//注意考虑0，要加一个
//遍历原先数组
for (int i = 0; i < arrs.length; i++) {
//以arrs[i]作为下标++
countArrs[arrs[i]]++;
}
//分解3:将统计数组对应的下标的数字返回到排序数组中
int k = 0;//统计数组的下标
int index = 0;//排序数组的下标
while (k < countArrs.length){
//判断统计数组中的值是否大于0
while(countArrs[k] > 0){
//将对应的下标，返回到排序数组中
arrs[index++] = k;
//统计的数字减少一个
countArrs[k]--;
}
k++;
}
//输出结果
for (int i = 0; i < arrs.length; i++) {
System.out.print(arrs[i] + " ");
}
}
统计数组优化
如果待排序的数字很大，那么在创建数组的时候会浪费没有空间，同时也会导致创建的数组，所以需要进行优化;
可以通过使用最大数字减去最小数字求出需要数组的大小。
public static void main(String[] args) {
int[] arrs = {90,92,91,93,90,92,90,91,91};
//分解1：根据最大值创建统一数组
//遍历数组找到最大和最小的值
int max = arrs[0];
int min = arrs[0];
for (int i = 0; i < arrs.length; i++) {
if(arrs[i] > max){
max = arrs[i];
}
if(arrs[i] < min){
min = arrs[i];
}
}
//分解2：
//根据最大值创建统一数组
int[] countArrs = new int[max - min + 1];//注意考虑0，要加一个
//遍历原先数组
for (int i = 0; i < arrs.length; i++) {
//以arrs[i]作为下标++
//获取值时需要减去min
countArrs[(arrs[i] - min)]++;
}
//分解3:将统计数组对应的下标的数字返回到排序数组中
int k = 0;//统计数组的下标
int index = 0;//排序数组的下标
while (k < countArrs.length){
//判断统计数组中的值是否大于0
while(countArrs[k] > 0){
//将对应的下标，返回到排序数组中
//需要还原成之前的值+min
arrs[index++] = k + min;
//统计的数字减少一个
countArrs[k]--;
}
k++;
}
//输出结果
for (int i = 0; i < arrs.length; i++) {
System.out.print(arrs[i] + " ");
}
}
本文的内容主要是Java数据结构与算法中的高级排序，大家如果感兴趣可以点点赞，关注一下，你们的支持是我最强大的动力，非常感谢您的阅读(❁´◡`❁)
我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/
有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳
我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www
给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最
我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我
什么是ruby的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht
我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_
无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD