Java实现折半插入排序算法的示例代码
目录
- 排序算法介绍
- 折半插入排序
- 原理
- 代码实现
- 复杂度分析
- 算法实践
排序算法介绍
排序算法是通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。最终序列按照一定的规律进行呈现。
在排序算法中，稳定性和效率是我们经常要考虑的问题。
稳定性：稳定是指当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。
复杂度分析：
（1）时间复杂度：即从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量。
（2）空间复杂度：就是从序列的初始状态经过排序移位变换的过程一直到最终的状态所花费的空间开销。
常见的排序算法分为以下几种：
折半插入排序
原理
折半插入排序（Binary Insertion Sort）是对插入排序算法的一种改进。不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
代码实现
在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为 a[low] ，末元素设置为 a[high] ，则每轮比较时将待插入元素与 a[m] ，其中 m = (low+high)/2 相比较，如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择 a[m+1] 到 a[high] 为新的插入区域（即low=m+1），如此直至low<=high 不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。
总之：利用已排好的元素有序的特点，使用折半查找的特点来快速找到要插入的位置。
// Binary Insertion Sort method
private static void binaryInsertSort(int[] array){
for(int i = 1; i < array.length; i++){
int temp = array[i];
int low = 0;
int high = i - 1;
while(low <= high){
int mid = (low + high) / 2;
if(temp < array[mid]){
high = mid - 1;
}else{
low = mid + 1;
}
}
for(int j = i; j >= low + 1; j--){
array[j] = array[j - 1];
}
array[low] = temp;
}
}
复杂度分析
折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。
时间复杂度
最好的情况：O(n)。如果元素排序正向有序，开始的时候就直接找到了位置，不需要寻找和移位。
最坏的情况：O(n^2)。如果元素排序反向有序，那么每次都需要进行数据查找。
平均复杂度：O(n^2)。
空间复杂度：O(1)。仅需几个存储空间用于记录信息的关键单元，即空间复杂度为O(1)。
示例：
算法实践
算法的整体思想已经在上面讲述了，下面直接使用一个例子来试试水。
折半插入排序
题目描述：
给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104
class Solution {
public int[] sortArray(int[] nums) {
for(int i = 1; i < nums.length; i++){
int temp = nums[i];
int low = 0;
int high = i - 1;
while(low <= high){
int mid = (low + high) / 2;
if(temp < nums[mid]){
high = mid - 1;
}else{
low = mid + 1;
}
}
for(int j = i; j >= low + 1; j--){
nums[j] = nums[j - 1];
}
nums[low] = temp;
}
return nums;
}
}
这个题目非常nice，你可以尝试去使用不同的排序方法去测试。
到此这篇关于Java实现折半插入排序算法的示例代码的文章就介绍到这了,更多相关Java折半插入排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
Java编程实现直接插入排序代码示例
算法描述:对于给定的一个数组,初始时假设第一个记录自成一个有序序列,其余记录为无序序列.接着从第二个记录开始,按照记录的大小依次将当前处理的记录插入到其之前的有序序列中,直至最后一个记录插入到有序序列中为止. 直接插入排序Java实现教程 示例1 public class Insert { public static void main(String[] args) { int a[] = {9,3,28,6,34,7,10,27,1,5,8}; show(a); for (int i=1;i
-
Java 十大排序算法之插入排序刨析
目录 插入排序原理 插入排序API设计 插入排序代码实现 插入排序的时间复杂度分析 插入排序原理 ①把所有元素分成已排序和未排序两组 ②找到未排序组的第一个元素,向已经排序的组中进行插入 ③倒序遍历已经排好的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他元素向后移动一位 插入排序API设计 类名 Insertion 构造方法 Insertion():创建Insertion对象 成员方法 1.public static void sort
-
Java经典排序算法之二分插入排序详解
一.折半插入排序(二分插入排序) 将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较,即可得到折半插入排序算法.在处理A[i]时,A[0]--A[i-1]已经按关键码值排好序.所谓折半比较,就是在插入A[i]时,取A[i-1/2]的关键码值与A[i]的关键码值进行比较,如果A[i]的关键码值小于A[i-1/2]的关键码值,则说明A[i]只能插入A[0]到A[i-1/2]之间,故可以在A[0]到A[i-1/2-1]之间继续使用折半比较:否则只能插入A[i-1/2]到A[i-1]之间,故可
-
Java实现插入排序
问题描述 利用插入排序把一列数组按从小到大或从大到小排序 (一).插入排序思想 以从小到大为例: 1.第一轮插入,从第二个数开始,与前面的数依次比较,遇到比自己小的数,就插入到该数后面的位置 2.第二轮插入,从第三个数开始,与前面的数依次比较,遇到比自己小的数,就插入到该数后面的位置 3.如此循环,直到所有数从小到大排列 (二).问题分析 1. 输入数组 根据用户输入的进行排序的数字数量n,建立一个长度为n的数组 public static void main (String[] args){
-
Java实现直接插入排序和折半插入排序算法示例
直接插入排序 1 排序思想: 将待排序的记录Ri插入到已经排好序的记录R1,R2,--,R(N-1)中. 对于一个随机序列而言,就是从第二个元素开始,依次将这个元素插入到它之前的元素中的相应位置.它之前的元素已经排好序. 第1次排序:将第2个元素插入到前边的有序列表(此时前边只有一个元素,当然是有序的),之后,这个序列的前2个元素就是有序的了. 第2次排序:将第3个元素插入到前边长度为2的有序列表,使得前2个元素是有序的. 以此类推,直到将第N个元素插入到前面长度为(N-1)的有序列表中. 2
-
Java经典排序算法之插入排序
一.算法原理 插入排序法:所谓插入排序法乃是将一个数目插入该占据的位置. 假设我们输入的是 "53,27,36,15,69, 42" 我们从第二个数字开始,这个数字是27,我们的任务只要看看27有没有正确的位置,我们的做法是和这个数字左边的数字来比,因此我们比较27和53,27比53小,所以我们就交换27和53,原来的排列就变成了"27, 53, 36, 15, 69, 42 " 接下来,我们看第3个数字有没有在正确的位置.这个数字是36,它的左边数字是53,36
-
Java实现直接插入排序与折半插入排序的示例详解
目录 1.直接插入排序 2. 折半插入排序 1.直接插入排序 插入排序的基本思想: 主要分为两个区间, 无序区间和有序区间, 每次选择无序区间的第一个元素, 在有序区间内选择合适的位置进行插入操作. 插入过程如下图所示: 代码: public class InsertSort { public static void insertSort(int[] array) { for (int i = 1; i < array.length; i++) { int tmp = array[i]; int
-
Java实现折半插入排序算法的示例代码
目录 排序算法介绍 折半插入排序 原理 代码实现 复杂度分析 算法实践 排序算法介绍 排序算法是通过特定的算法因式将一组或多组数据按照既定模式进行重新排序.最终序列按照一定的规律进行呈现. 在排序算法中,稳定性和效率是我们经常要考虑的问题. 稳定性:稳定是指当两个相同的元素同时出现于某个序列之中,则经过一定的排序算法之后,两者在排序前后的相对位置不发生变化. 复杂度分析: (1)时间复杂度:即从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量. (2)空
-
Java实现基本排序算法的示例代码
目录 1. 概述 2. 插入排序 2.1 直接插入排序 2.2 希尔排序(缩小增量排序) 3. 选择排序 3.1 直接选择排序 3.2 堆排序 4. 交换排序 4.1 冒泡排序 4.2 快速排序 5. 归并排序 6. 计数排序(非比较类型的排序) 7. 排序算法总结 1. 概述 排序概念:就是将一串记录按照其中某个或某些关键字的大小,递增或递减的排列起来的操作. 稳定性:通俗的将就是数据元素不发生有间隔的交换,例如: 内部排序:数据元素全部放在内存中的排序 外部排序:数据元素太多不能一次加载到内
-
Java实现拓扑排序算法的示例代码
目录 拓扑排序原理 1.点睛 2.拓扑排序 3.算法步骤 4.图解 拓扑排序算法实现 1.拓扑图 2.实现代码 3.测试 拓扑排序原理 1.点睛 一个无环的有向图被称为有向无环图.有向无环图是描述一个工程.计划.生产.系统等流程的有效工具.一个大工程可分为若干子工程(活动),活动之间通常有一定的约束,例如先做什么活动,有什么活动完成后才可以开始下一个活动. 用节点表示活动,用弧表示活动之间的优先关系的有向图,被称为 AOV 网. 在 AOV 网中,若从节点 i 到节点 j 存在一条有向路径,则称
-
Java实现高效随机数算法的示例代码
前言 事情起源于一位网友分享了一个有趣的面试题: 生成由六位数字组成的ID,要求随机数字,不排重,不可自增,且数字不重复.ID总数为几十万. 初次解答 我一开始想到的办法是 生成一个足够大的ID池(其实就是需要多少就生成多少) 对ID池中的数字进行随机排序 依次消费ID池中的数字 可惜这个方法十分浪费空间,且性能很差. 初遇梅森旋转算法 后面咨询了网友后得知了一个高效的随机数算法:梅森旋转(Mersenne Twister/MT).通过搜索资料得知: 梅森旋转算法(Mersenne twiste
-
Java实现8种排序算法的示例代码
冒泡排序 O(n2) 两个数比较大小,较大的数下沉,较小的数冒起来. public static void bubbleSort(int[] a) { //临时变量 int temp; //i是循环次数,也是冒泡的结果位置下标,5个数组循环5次 for (int i = 0; i < a.length; i++) { //从最后向前面两两对比,j是比较中下标大的值 for (int j = a.length - 1; j > i; j--) { //让小的数字排在前面 if (a[j] <
-
Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)
目录 1.查找概述 2.顺序查找 3.二分查找 3.1 二分查找概述 3.2 二分查找实现 4.插值查找 4.1 插值查找概述 4.2 插值查找实现 5.斐波那契查找 5.1 斐波那契查找概述 5.2 斐波那契查找实现 5.3 总结 1.查找概述 查找表: 所有需要被查的数据所在的集合,我们给它一个统称叫查找表.查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合. 查找(Searching): 根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录).
-
Java实现常见的排序算法的示例代码
目录 一.优化后的冒泡排序 二.选择排序 三.插入排序 四.希尔排序 五.快速排序 六.随机化快速排序 七.归并排序 八.可处理负数的基数排序 一.优化后的冒泡排序 package com.yzh.sort; /* 冒泡排序 */ @SuppressWarnings({"all"}) public class BubbleSort { public static void BubbleSort(int[]a){ for (int i = 0; i <a.length-1 ; i+
-
Java语言字典序排序算法解析及代码示例
字典序法就是按照字典排序的思想逐一产生所有排列. 在数学中,字典或词典顺序(也称为词汇顺序,字典顺序,字母顺序或词典顺序)是基于字母顺序排列的单词按字母顺序排列的方法. 这种泛化主要在于定义有序完全有序集合(通常称为字母表)的元素的序列(通常称为计算机科学中的单词)的总顺序. 对于数字1.2.3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的.例如对于5个数字的排列 12354和12345,排列12345在前,排列12354在后.按照这样的规定,5个数字的所有的
-
JAVA用递归实现全排列算法的示例代码
求一个n阶行列式,一个比较简单的方法就是使用全排列的方法,那么简述以下全排列算法的递归实现. 首先举一个简单的例子说明算法的原理,既然是递归,首先说明一下出口条件.以[1, 2]为例 首先展示一下主要代码(完整代码在后面),然后简述 //对数组array从索引为start到最后的元素进行全排列 public void perm(int[]array,int start) { if(start==array.length) { //出口条件 for(int i=0;i<array.length;i
-
Java实现雪花算法的示例代码
一.介绍 SnowFlow算法是Twitter推出的分布式id生成算法,主要核心思想就是利用64bit的long类型的数字作为全局的id.在分布式系统中经常应用到,并且,在id中加入了时间戳的概念,基本上保持不重复,并且持续一种向上增加的方式. 在这64bit中,其中``第一个bit是不用的,然后用其中的41个bit作为毫秒数,用10bit作为工作机器id,12bit`作为序列号.具体如下图所示: 第一个部分:0,这个是个符号位,因为在二进制中第一个bit如果是1的话,那么都是负数,但是我们生成