首页 / 知识
Java常见的排序算法详解
2023-04-11 16:34:00
一、直接插入排序
整个区间被分为
有序区间
无序区间
每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入。
public static void insertSort（int[] arr）{
for （int i = 1; i < arr.length; i++） {
int tmp = arr[i];
int j = i - 1;
for （ ; j >= 0 ; j--） {
if （arr[j] > tmp）{
arr[j + 1] = arr[j];
}else{
//arr[j + 1] = tmp;//只要j回退的时候，遇到了比tmp小的元素，就结束了这次的比较
break;
}
}
//j回退到了小于0的地方
arr[j + 1] = tmp;
}
}
public static void main（String[] args） {
int[] array = {6,10,9,3,5};
insertSort（array）;
System.out.println（Arrays.toString（array））;
}
}
输出结果：
时间复杂度：最好O（N）–>数据本身是有序的；
* 最坏O（N^2）；–>数据逆序；
* 当一组数据，数据量不大且趋近于有序，此时用插入排序时间更快，越有序越快。
空间复杂度：O（1）；
稳定性：稳定的排序；
一个稳定的排序可以实现为不稳定的排序，但是一个本身就不稳定的排序不可以变成稳定的排序。
二、希尔排序
希尔排序法又称缩小增量法。
希尔排序法的本质是插入排序，只不过是将待排序的序列按某种规则分成几个子序列，分别对几个子序列进行直接插入排序。这个规则就是增量，增量选取很重要，增量一般选序列长度一半，然后逐半递减，直到最后一个增量为1，为1相当于直接插入排序。
public static void shell（int[] arr,int gap）{
for （int i = 1; i < arr.length; i++） {
int tmp = arr[i];
int j = i - gap;
for （; j >= 0 ; j-=gap） {
if（tmp < arr[j]）{
arr[j + gap] = arr[j];
}else{
break;
}
}
arr[j+gap] = tmp;
}
}
public static void shellSort（int[] arr） {
int gap = arr.length;
//增量在缩小，最后一组的增量为1
while （gap > 1）{
gap /= 2;
shell（arr,gap）;
}
shell（arr,1）;
}
public static void main（String[] args） {
int[] array = {9,1,2,5,7,4,8,6,3,5};
shellSort（array）;
System.out.println（Arrays.toString（array））;
|
最新内容
相关内容
Python的字典排序
Python的字典排序，代码，数据，培训，字典，函数，表达式，内容，列表，排列，问题，字典是Python语言中的一种数据结构，每一个字典元素是由一对key-valu
python的调用绑定方法和非绑定方法
python的调用绑定方法和非绑定方法，代码，方法，实例，第一，培训，时计，奇数，偶数，参数，定义，在Python中，如果用实例去调用方法，这种限制就被称为Py
Python的经典题目
Python的经典题目，数字，数据，公司，培训，星期六，星期，字母，水仙花，次方，偶数，1、水仙花数用python打印出100-999所有的水仙花数，所谓水仙花数是
python调试的几种方式
python调试的几种方式，代码，位置，信息，状态，培训，数据，分析，变量，函数，方式，python作为一种脚本语言，很多时候我们习惯于它的简洁，习惯于它的修
Python网络编程调用接收数据的三种
Python网络编程调用接收数据的三种方法，数据，代码，基础，通用，通讯，服务，网络，培训，方法，报文，最近在使用python进行网络编程开发一个通用的tc
Python 3 的优点
Python 3 的优点，数据，国家，名称，对比，代码，异常，统一，培训，地方，除法，为进一步提起你的胃口，以下是Python3具备的一些优点。1.Print不再是语
python的单元测试框架
python的单元测试框架，代码，生态，信息，标准，测试，分析，工具，环境，条款，活跃，1、AutotestAutotest是Google、Redhat、IBM公司联合开发的分布式入门Python的4大陷阱
入门Python的4大陷阱，代码，流程，名字，数据，培训，服务，基础，各大，对比，下来，Python以语法简单、关键字少著称，因此经常被各大媒体忽悠其是一门
编写一个简单的游戏来学习 Python
编写一个简单的游戏来学习 Python，数字，标准，概念，名称，异常，软件，基础知识，培训，通用，流程，通过编写一个“猜数字”游戏来探索Python(和其他
如何杀死一个Python线程
如何杀死一个Python线程，状态，线程，代码，标准，意外，工作，控制权，培训，事件，结束，我经常被问到如何杀死一个后台线程，这个问题的答案让很多人不
为何你的Python代码应是扁平与稀疏
为何你的Python代码应是扁平与稀疏的，代码，培训，信息，观察，设计，工具，嵌套，闻闻，程序员，沉思，Python之禅之所以得名，正是由于它那简明扼要的规
python的应用领域
python的应用领域，数据，分析，网络，工作，代码，人工智能，项目，金融，量化交易，业务，应用领域1：人工智能Python语言是目前公认学习人工智能的基础