学习了插入排序算法,记录下以作备查
public class InsertSort {
public static void main(String[] args) {
int[] data = {261,53,48,11,13,48,32,15};
// binsort(data);
// data = new int[]{261,53,48,48,32,15,13,11};
// binsort(data);
// sort2(data);
data = new int[]{261,53,48,48,32,15,13,11};
// sort.sort2(data);
shellsort(data);
for(int a: data){
System.out.print(a+" ");
}
}
/**
* 这样排序很失败
*/
public static void sort(int[] r){
int bi=0,ci=0;
for(int c=0; c<r.length; c++){
for(int i=0; i< c; i++){
bi++;
if(r[c] < r[i]){
//插入i。后移
int temp = r[c];
for(int j=c;j>i;j--){
r[j] = r[j-1];
ci++;
}
r[i] = temp;
}
}
}
System.out.println("比较="+bi+",移动="+ci);
}
/**
* 正宗的插入排序
*/
public static void sort2(int[] r){
int bi=0,ci=0;
//从第2个数据开始
for(int i=1; i< r.length; i++){
bi++;
if(r[i] < r[i-1]){//如果比有序的最后一个小,则需要插入到前面的有序数据中
int temp = r[i];//保存该值,因为会被移动替换掉
r[i] = r[i-1];//先把最后一个数据交换,无论是否需要移动,该值一定会被交换
int j = i-2;//有序的倒数第二个
for(;j>=0 && temp < r[j]; j--){//不越界范围类倒数找到(不断比较查找)插入位置,并且移动
r[j+1] = r[j];
ci++;
}
//替换
r[j+1] = temp;
}
}
System.out.println("比较="+bi+",移动="+ci);
}
/**
* 折半插入排序
*/
public static void binsort(int[] r){
int bi=0,ci=0;
for(int i=1; i< r.length; i++){
int temp = r[i];//保存
int hi = i-1, lo = 0;//查找区间
while(lo <= hi){
int mid = (hi + lo)/2;
if(temp < r[mid]){
hi = mid - 1;//折半最后一步
}else{
lo = mid + 1;
}
bi++;
}
//折半查找,查找到比r[hi]大比r[lo]小的这个位置
for(int j=i-1; j> hi;j--){//移动
r[j+1] = r[j];
ci++;
}
r[hi+1] = temp;//插入
}
System.out.println("比较="+bi+",移动="+ci);
}
/**
* 希尔排序
*/
public static void shellsort(int[] r){
int[] delta = {5,3,1};
for(int k=0; k < delta.length; k++){
shellInsert(r, 0, r.length -1, delta[k]);
}
}
/**
* 以某步长进行希尔排序
*/
private static void shellInsert(int[] r, int low, int high, int delta){
for(int i= low + delta; i<=high; i++){
if(r[i] < r[i-delta]){
int temp = r[i];//保存该值,因为会被移动替换掉
int j = i-delta;//有序的倒数第二个
for(;j>=low && temp < r[j]; j-=delta){//不越界范围类倒数找到(不断比较查找)插入位置,并且移动
r[j+delta] = r[j];
}
//替换
r[j+delta] = temp;
}
}
}
}
分享到:
相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
插入排序算法(动态数组实现) printf("--------插入排序算法的实现--------\n"); printf("输入数组的大小length:\n"); int length=0; scanf("%d",&length); /****动态分配内存初始化数组*********************...
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
java编写的插入排序算法
Java语言实现的直接插入排序算法,代码里头有详细注释,注释皆为简单英文,因为这个算法比较简单,欢迎新手下载学习使用,欢迎后期的学习交流!
八大排序java实现版本,直接插入排序、折半插入排序、冒泡排序、简单选择排序、希尔插入排序、快速排序 、堆排序、2-路归并排序 、基数排序,并有时间比较,博文...
排序算法:排序算法汇总--各类排序算法 冒泡,选择,插入,快排,归并,堆排
冒泡排序算法选择排序算法插入排序c语言实现
该资源提供了Java中实现插入排序的全面指南。文档中涵盖了插入排序的基本概念,包括如何对数组进行排序以及如何在Java中实现插入排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现插入排序,包括详细的...
各类排序算法整理--C语言描述--本人编写 排序算法种类有: 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序
希尔排序,直接插入排序,折半插入排序算法的实现,c语言实现希尔排序
java实现的插入排序 都是静态的例子 很简单
插入排序算法java代码,望对大家有帮助
用java实现了以下算法: 1、冒泡排序、冒泡排序的两种改进。 2、插入排序。 3、选择排序。 4、希尔排序。 5、归并排序。 6、快速排序。
Python算法之---冒泡,选择,插入排序算法.py
插入排序算法c++实现,程序实现插入排序十万个数(调用)。可以改成输入。并附加了程序运行计时,用于测试时间复杂度,可以移除。绝对能用
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 void Init_Random();//数组随机数初始化函数声明 void Show_Array();//展示...
用蛮力法实现选择排序,冒泡排序程序;用减治法实现插入排序;分治法应用-快排,合并排序,0-1背包问题;Prim算法求最小生成树。伪代码以及java代码实现
总结了常用的八大排序算法:(交换式:1、冒泡,2、快排; 选择式:3、选择, 4、堆排; 插入式:5、插入, 6、希尔; 其他:7、归并, 8、基数排序)。 并包含了Java实现的源代码。