常见内部排序算法之插入排序
今天来写写插入排序算法,包括
直接插入,折半插入,希尔排序(Shell)。
插入插入,就是
将数组分成已排序,未排序,然后将未排序中的第一个插入已排序中的适合位置,这样,未排序越来越少,直到没有就算排序完成!而默认
开始则是第一个是已排序,剩下的则是未排序。
直接插入算法:
package test.aglorith;
import java.util.Arrays;
public class InsertSort {
public static void sort(int[] data) {
int data_len=data.length;
for (int i = 1; i < data_len; i++) {//默认第一个(下标是0)是已排序,从未排序中的第二个(下标是1)开始
int temp=data[i];
int j = i-1;
while (j >=0&&temp<data[j]) {
data[j+1]=data[j];
j--;
}
data[j+1]=temp;
System.out.println(Arrays.toString(data));
}
}
public static void main(String[] args) {
int[] data=new int[]{10,9,8,7,6,5,4,3,2,1};
System.out.println("排序之前"+Arrays.toString(data));
sort(data);
}
}
折半插入算法:
package test.aglorith;
import java.util.Arrays;
public class InsertSortBinary {
public static void sort(int[] data) {
int data_len=data.length;
for (int i = 1; i < data_len; i++) {
int temp=data[i];
int mid=getMid(data, i);
swapPass(data, i, mid);
data[mid]=temp;
System.out.println(Arrays.toString(data));
}
}
public static int getMid(int[] data,int i) {
int temp=data[i];
int low=0;
int hight=i-1;
while (low<=hight) {
int mid=(low+hight)/2;
if (temp<data[mid]) {
hight=mid-1;
}else {
low=mid+1;
}
}
return low;//无论如何都是返回low,折中折中,无非最后只剩下两个的时候,选择谁作为被替代者
}
public static void swapPass(int[] data,int i,int mid) {
for (int j = i; j > mid; j--) {
data[j]=data[j-1];
}
}
public static void main(String[] args) {
int[] data=new int[]{11,10,9,8,7,6,5,4,3,2,1};
System.out.println("排序之前"+Arrays.toString(data));
sort(data);
}
}
希尔排序算法:又称缩小增量排序
由于插入排序需要大量的移动数据,因此效率会受到影响。而在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量increment逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按
increment*+3作为距离排过序,使文件较接近于
有序状态,所以新的一趟排序过程也较快。因此,希尔排序在效率上较直接插入排序有较大的改进。
package test.aglorith;
import java.util.Arrays;
public class ShellSort {
//通过增量increment分组进行排序
public static void sortByIncrement(int[] data,int increment) {
int data_len=data.length;
for (int i = increment; i <data_len; i++) {
int temp=data[i];
int j=i-increment;
while (j>=0&&temp<data[j]){
data[j+increment]=data[j];
j=j-increment;
}
data[j+increment]=temp;
}
System.out.println(Arrays.toString(data));
}
//不同的increment分组排序,直到increment=1(相当于直接插入排序,但是由于前面的排序已经使得数组基本上处于有序状态)
public static void sort(int[] data) {
int increment=data.length;
while (increment>1) {
increment=(increment-1)/3;
sortByIncrement(data,increment);
}
}
public static void main(String[] args) {
int[] data=new int[]{13,12,11,10,9,8,7,6,5,4,3,2,1};
System.out.println("排序之前"+Arrays.toString(data));
sort(data);
}
}
分享到:
相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
数据结构 内部排序算法分析 c语言代码
1、本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、待排序表的表的元素的关键字为整数,表长不小于100;其中的数据要用伪随机数产生...
(1)对以下6种常用的内部排序算法进行比较z起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 (2)待排序表的表长不小于1005其中的数据要用伪随机数产生程序产生:至少要用5组不同的输入数据作比较...
本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。
(1)对以下10种常用的内部排序算法进行比较:直接插入排序;折半折入排序;二路插入排序;希尔排序;冒泡排序;快速排序;简单选择排序;堆排序;归并排序;基数排序。 (2)待排序表的表长不少于100;其中的数据要...
(1) 对6种常用内部排序算法进行比较:冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序 (2) 待排序的表长不小于100,其中数据要用伪随机数产生,至少用5组不同的输入数据做比较 (3) 比较...
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组不同的输入数据作比较;比较...
要求对以下6种常用的内部排序算法进行比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。待排序表的表长不小于1000;其中的数据要用伪随机数产生程序产生,至少要用5组不同的输入数据作比较...
(1) 对以下10种内部排序算法进行比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序、折半插入排序、二路插入排序、归并排序、基数排序。 (2) 待排序表的表长不小于100;其中的数据要用伪随机...
1、常见排序算法实现(1-6选择几个算法练习) 1)问题描述:输入一组关键字序列分别实现下列排序。 (1)实现简单选择排序、直接插入排序和冒泡排序。 (2)实现希尔排序算法。 (3)实现折半插入排序。 ...
希尔排序,直接插入排序,折半插入排序算法的实现,c语言实现希尔排序
十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。...常见的内部排序算法有:插入排 序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、 基数排序等。用一张图概括:
几种内部排序算法总结!(冒泡排序、快速排序、直接插入排序、拆半插入排序、简单选择排序)
(1)对以下6种常用的内部排序算法进行比较:冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 (2)待排序表的表长不小于100,其中的数据要用伪随机数产生程序产生,至少要用5组不同的输入...
C++排序算法之插入排序源码