Java 选择排序、插入排序、希尔算法实例详解
1、基本思想：
在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
2、实例
3、算法实现
/**
* 选择排序算法
* 在未排序序列中找到最小元素，存放到排序序列的起始位置
* 再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。
* 以此类推，直到所有元素均排序完毕。
* @param numbers
*/
public static void selectSort(int[] numbers)
{
int size = numbers.length; //数组长度
int temp = 0 ; //中间变量
for(int i = 0 ; i < size ; i++)
{
int k = i; //待确定的位置
//选择出应该在第i个位置的数
for(int j = size -1 ; j > i ; j--)
{
if(numbers[j] < numbers[k])
{
k = j;
}
}
//交换两个数
temp = numbers[i];
numbers[i] = numbers[k];
numbers[k] = temp;
}
}
二、插入排序
1、基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。
2、实例
3、算法实现
/**
* 插入排序
*
* 从第一个元素开始，该元素可以认为已经被排序
* 取出下一个元素，在已经排序的元素序列中从后向前扫描
* 如果该元素（已排序）大于新元素，将该元素移到下一位置
* 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
* 将新元素插入到该位置中
* 重复步骤2
* @param numbers 待排序数组
*/
public static void insertSort(int[] numbers)
{
int size = numbers.length;
int temp = 0 ;
int j = 0;
for(int i = 0 ; i < size ; i++)
{
temp = numbers[i];
//假如temp比前面的值小，则将前面的值后移
for(j = i ; j > 0 && temp < numbers[j-1] ; j --)
{
numbers[j] = numbers[j-1];
}
numbers[j] = temp;
}
}
4、效率：
时间复杂度：O（n^2）.
三、希尔算法
1、基本思想：
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
2、操作方法：
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
希尔排序的示例：
3、算法实现：
/**希尔排序的原理:根据需求，如果你想要结果从大到小排列，它会首先将数组进行分组，然后将较大值移到前面，较小值
* 移到后面，最后将整个数组进行插入排序，这样比起一开始就用插入排序减少了数据交换和移动的次数，可以说希尔排序是加强
* 版的插入排序
* 拿数组5, 2, 8, 9, 1, 3，4来说，数组长度为7，当increment为3时，数组分为两个序列
* 5，2，8和9，1，3，4，第一次排序，9和5比较，1和2比较，3和8比较，4和比其下标值小increment的数组值相比较
* 此例子是按照从大到小排列，所以大的会排在前面，第一次排序后数组为9, 2, 8, 5, 1, 3，4
* 第一次后increment的值变为3/2=1,此时对数组进行插入排序，
*实现数组从大到小排
*/
public static void shellSort(int[] data)
{
int j = 0;
int temp = 0;
//每次将步长缩短为原来的一半
for (int increment = data.length / 2; increment > 0; increment /= 2)
{
for (int i = increment; i < data.length; i++)
{
temp = data[i];
for (j = i; j >= increment; j -= increment)
{
if(temp > data[j - increment])//如想从小到大排只需修改这里
{
data[j] = data[j - increment];
}
else
{
break;
}
}
data[j] = temp;
}
}
}
4、效率
时间复杂度：O（n^2）.
4、各种算法的时间复杂度
以上所述是小编给大家介绍的Java 选择排序、插入排序、希尔算法实例详解，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！
相关推荐
-
Java对数组实现选择排序算法的实例详解
一. 算法描述 选择排序:比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成. 以下面5个无序的数据为例: 56 12 80 91 20(文中仅细化了第一趟的选择过程) 第1趟:12 56 80 91 20 第2趟:12 20 80 91 56 第3趟:12 20 56 91 80 第4趟
-
Java排序算法总结之选择排序
本文实例讲述了Java排序算法总结之选择排序.分享给大家供大家参考.具体分析如下: 选择排序的基本操作就是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完.算法不稳定,O(1)的额外的空间,比较的时间复杂度为O(n^2),交换的时间复杂度为O(n),并不是自适应的.在大多数情况下都不推荐使用.只有在希望减少交换次数的情况下可以用. 基本思想 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果: ①初始状态:
-
JAVA简单选择排序算法原理及实现
简单选择排序:(选出最小值,放在第一位,然后第一位向后推移,如此循环)第一位与后面每一个逐个比较,每次都使最小的置顶,第一位向后推进(即刚选定的第一位是最小值,不再参与比较,比较次数减1) 复杂度: 所需进行记录移动的操作次数较少 0--3(n-1) ,无论记录的初始排列如何,所需的关键字间的比较次数相同,均为n(n-1)/2,总的时间复杂度为O(n2):空间复杂度 O(1) 算法改进:每次对比,都是为了将最小的值放到第一位,所以可以一比到底,找出最小值,直接放到第一位,省去无意义的调换移动操作
-
java实现选择排序算法
java实现选择排序算法 public static void selectSort(int[] array) { for (int i = 0; i < array.length - 1; i++) { int min = i; for (int j = i + 1; j < array.length; j++) { if (array[j] < array[min]) { min = j; } } Sort.swap(array, i, min);//交换i和min } } 选择排序
-
java数据结构排序算法之树形选择排序详解
本文实例讲述了java数据结构排序算法之树形选择排序.分享给大家供大家参考,具体如下: 这里我们就来说说选择类排序之一的排序:树形选择排序 在简单选择排序中,每次的比较都没有用到上次比较的结果,所以比较操作的时间复杂度是O(N^2),想要降低比较的次数,则需要把比较过程中的大小关系保存下来.树形选择排序是对简单选择排序的改进. 树形选择排序:又称锦标赛排序(Tournament Sort),是一种按照锦标赛的思想进行选择排序的方法.首先对n个记录的关键字进行两两比较,然后在n/2个较小者之间再进
-
Java实现选择排序算法的实例教程
选择排序概念 选择排序也是一种交换排序算法,和冒泡排序有一定的相似度,因此个人认为选择排序可以视为冒泡排序的一种改进算法.它的思路是这样的: 设现在要给数组arr[]排序,它有n个元素. 1对第一个元素(Java中,下标为0)和第二个元素进行比较,如果前者大于后者,那么它一定不是最小的,但是我们并不像冒泡排序一样急着交换.我们可以设置一个临时变量a,存储这个目前最小的元素的下标.然后我们把这个目前最小的元素继续和第三个元素做比较,如果它仍不是最小的,那么,我们再修改a的值.如此直到和最后一个元素
-
java排序算法之_选择排序(实例讲解)
选择排序是一种非常简单的排序算法,从字面意思我们就可以知道,选择就是从未排序好的序列中选择出最小(最大)的元素,然后与第 i 趟排序的第 i-1(数组中下标从 0 开始) 个位置的元素进行交换,第 i 个元素之前的序列就是已经排序好的序列.整个排序过程只需要遍历 n-1 趟便可排好,最后一个元素自动为最大(最小)值. 举个小例子: arr[] = {3,1,2,6,5,4} 第 1 趟排序: index = 0, min = 1, 交换后 --> 1,3,2,6,5,4 第 2 趟排序: in
-
Java 选择排序、插入排序、希尔算法实例详解
1.基本思想: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换:然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止. 2.实例 3.算法实现 /** * 选择排序算法 * 在未排序序列中找到最小元素,存放到排序序列的起始位置 * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾. * 以此类推,直到所有元素均排序完毕. * @param numbers */ public static void selectSort(int[] nu
-
java 中模式匹配算法-KMP算法实例详解
java 中模式匹配算法-KMP算法实例详解 朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的
-
Java 归并排序算法、堆排序算法实例详解
基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]较小的存入辅助数组
-
JavaScript算法系列之快速排序（Quicksort）算法实例详解
"快速排序"的思想很简单,整个排序过程只需要三步: (1)在数据集之中,选择一个元素作为"基准"(pivot). (2)所有小于"基准"的元素,都移到"基准"的左边:所有大于"基准"的元素,都移到"基准"的右边. (3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止. 举例来说,现在有一个数据集{85, 24, 63, 45,
-
Java版超大整数阶乘算法代码详解-10,0000级
当计算超过20以上的阶乘时,阶乘的结果值往往会很大.一个很小的数字的阶乘结果就可能超过目前个人计算机的整数范围.如果需求很大的阶乘,比如1000以上完全无法用简单的递归方式去解决.在网上我看到很多用C.C++和C#写的一些关于大整数阶乘的算法,其中不乏经典但也有很多粗糙的文章.数组越界,一眼就可以看出程序本身无法运行.转载他人文章的时候,代码倒是仔细看看啊.唉,粗糙.过年了,在家闲来蛋疼,仔细分析分析,用Java实现了一个程序计算超大整数阶乘.思想取自网上,由我个人优化和改进. 这个方法采用"数
-
LRU LFU TinyLFU缓存算法实例详解
目录 简介 一.LRU和LFU算法 LRU算法 LFU算法 小结: 二.TinyLFU 三.Window-TinyLFU 简介 前置知识 知道什么是缓存 听完本节公开课,你可以收获 掌握朴素LRU.LFU算法的思想以及源码 掌握一种流式计数的算法 Count-Min Sketch 手撕TinyLFU算法.分析Window-TinyLFU源码 一.LRU和LFU算法 LRU算法 LRU Least Recently Used 最近最少使用算法 LRU 算法的思想是如果一个数据在最近一段时间没有被访
-
java实现可安装的exe程序实例详解
java实现可安装的exe程序实例详解 通过编写Java代码,实现可安装的exe文件的一般思路: 1.在eclipse中创建java项目,然后编写Java代码,将编写好的Java项目导出一个.jar格式的jar包: 2.通过安装exe4j软件,将导出的.jar格式的文件制作成.exe格式的可执行的文件,(注意:此时的.exe文件只是可以执行,还不能够安装): 3.通过安装Inno setup软件,将可执行的.exe格式的文件..jar格式的文件以及其它需要的文件制作成一个可安装的.exe格式的文
-
Java 生成随机字符串数组的实例详解
Java 生成随机字符串数组的实例详解 利用Collections.sort()方法对泛型为String的List 进行排序.具体要求: 1.创建完List<String>之后,往其中添加十条随机字符串 2.每条字符串的长度为10以内的随机整数 3.每条字符串的每个字符都为随机生成的字符,字符可以重叠 4.每条随机字符串不可重复 将涉及到的知识有: String.StringBuffer.ListArray.泛型.Collections.sort.foreach.Random等相关知识,算是
-
java 设计模式（DAO）的实例详解
java 设计模式(DAO)的实例详解 应用场景:在Java程序中,经常需要把数据持久化,也需要获取持久化的数据,但是在进行数据持久化的过程中面临诸多问题(如:数据源不同.存储类型不同.供应商不同.访问方式不同等等),请问如何能以统一的接口进行数据持久化的操作? 其实这个我没学号(≧ ﹏ ≦).我的理解就是一个产品面向的用户不是单一的,所以我们要兼容许多情况如前面提到的数据源不同.存储类型不同.供应商不同.访问方式不同等等. ★ 解决方案 DAO的理解: 1.DAO其实是利用组合工厂模式来解决问
-
java 查找list中重复数据实例详解
java 查找list中重复数据实例详解 需求: 查找一个List集合中所有重复的数据,重复的数据可能不止一堆,比如:aa, bb, aa, bb, cc , dd, aa这样的数据.如果有重复数据,则给这些重复数据加上编号,上述数据改为:aa1, bb1, aa2, bb2, cc, dd. 算法如下: public static void same(List<String> list) { String [] indexArr ; Map<String, String> map