package com.algorithm;
/**
* 插入排序及其变体
*
* List可转化为数组进行排序
* Object数组中的元素必须实现Comparable接口,即元素必须是可比的
*/
public class InsertSort {
/**
* 直接插入排序
*/
public static void insertSort(Object[] a){
Object cur = null; //保存当前遍历到的元素
int len = a.length;
for(int i = 1;i < len;i++){
if(((Comparable)a[i]).compareTo(a[i-1]) < 0){ //如果后一个元素小于前一个
cur = a[i];
a[i] = a[i-1];
int j;
//在前面已经有序的表中查找插入位置,并移动元素
for(j = i-2;j>=0 && ((Comparable)cur).compareTo(a[j]) < 0;j--){
a[j+1] = a[j];
}
a[j+1] = cur;
}
}
}
/**
* 二分插入排序
* 使用二分查找查找插入位置时因为前面元素都已经有序
* 减小查找插入位置的比较次数,但元素移动次数不变
*/
public static void binaryInsertSort(Object[] a){
Object cur = null;
int len = a.length;
for(int i=1;i<len;i++){
if(((Comparable)a[i]).compareTo(a[i-1]) < 0){ //后一个元素小于前一个
cur = a[i];
int low = 0; //下界
int high = i - 1;
while(low <= high){ //找插入位置的索引
int mid = (low + high) / 2;
if(((Comparable)cur).compareTo(a[mid]) < 0){
high = mid - 1;
}else{
low = mid +1;
}
}
for(int j = i -1;j > high;j--){ //把high之后的元素右移
a[j+1] = a[j];
}
a[ high + 1] = cur;
}
}
}
/**
* 2-路插入排序
* 需要一个辅助数组s,及指向s的第一个及最后一个位置的索引,first和last,
* 即从first遍历到final得到的列是有序的
* 2-路插入排序是在二分插入排序的基础上进行改进,
* 减少了排序过程中移动的元素的次数,但增加了辅助空间.
*
*/
public static void twoRoadInsertSort(Object[] a){
int len = a.length;
Object[] s = new Object[len]; //辅助数组
s[0] = a[0];
int first = len;
int last = 0;
for(int i = 1;i < len;i++){
if(((Comparable)a[i]).compareTo(s[0])<0){ //小于s[0],插入到s[0]之前,即从数组最后开始插入
int j;
for(j = first; j < len - 1 && ((Comparable)a[i]).compareTo(s[j])>0;j++){
s[j-1] = s[j];
}
s[j-1] = a[i];
first--;
}else{ //大于s[0],插入到s[0]之后
int j;
//查找插入位置并移动元素
for(j = last; j > 0 && ((Comparable)a[i]).compareTo(s[j])<0;j--){
s[j+1] = s[j];
}
s[j+1] = a[i];
last++;
}
}
System.out.println("first:"+first +" last:"+last);
//重新对a赋值
int count = 0;
for(int i = first;i < len;i++){
a[count++] = s[i];
}
for(int i=0;i<=last;i++){
a[count++] = s[i];
}
}
//test
public static void main(String[] args) {
Integer[] data = {49,38,65,97,76,13,27,49,14};
insertSort(data);
//binaryInsertSort(data);
//twoRoadInsertSort(data);
for(Integer d:data){
System.out.println(d);
}
}
}
希尔排序(改进的插入排序)
package com.sort;
/**
* 希尔排序(它也是一种插入排序)
* 原理:首先根据增量,将相隔增量位置的元素组成一个子序列,
* 对子序列进行插入排序,一趟排序后若干子序列已经有序。
* 然后减少增量,继续重复上述操作,最后一趟排序的增量必为1,
* 即对整个序列进行一次插入排序。最后一趟排序后整个列表有序。
*
* 产生希尔排序的原因:
* 1.若待排记录序列"基本有序",即i记录之前的所有记录中
* 大于i的记录较少,这时候插入排序的效率可以大大提高
* 2.列表元素较少时,插入排序的效率也比较高。
*/
public class ShellSortDemo {
/**
* 根据设置的增量多次排序
*/
public static void shellSort(Object[] a){
//最后一个增量必为1。即对整个序列进行一次插入排序
int[] dks = {5,3,1};
//进行dsk.length插入排序
for(int i=0;i<dks.length;i++){
ShellInsert(a, dks[i]);
}
}
/**
* 某一趟排序,增量为dk。
* 意思为:将相隔dk的记录组成一个子序列。
* 对子序列进行插入排序。
* 比如:增量为5时
* 初始记录 49 38 65 97 76 13 27 49 55 4
* 子序列1: 49 13
* 子序列2: 38 27
* 子序列3: 65 49
* 子序列4: 97 55
* 子序列5: 76 4
* 可对上述自序列分别进行插入排序
*/
private static void ShellInsert(Object[] a,int dk){
int len = a.length;
Object cur = null;
for(int i=dk;i<len;i++){
if(((Comparable)a[i]).compareTo(a[i-dk]) < 0){
cur = a[i];
int j;
//在左边有序表中查找插入位置,查找过程中元素右移
for(j = i -dk; j>=0 && ((Comparable)cur).compareTo(a[j]) < 0;j-=dk){
a[j+dk] = a[j];
}
a[j+dk] = cur; //找到正确插入位置
}
}
}
//just for test
public static void main(String[] args) {
Integer[] data = {49,38,65,97,76,13,27,49,55,4};
shellSort(data);
for(Integer d:data){
System.out.println(d);
}
}
}
分享到:
相关推荐
合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现,原创。
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
本实验含有四部分内容——直接插入排序、希尔排序、选择排序、快速排序,在上述内容的基础上,将所有排序算法整合在一个程序中。学生可参考教材中的伪代码。鼓励学生自创新思路,新算法。
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
10种排序算法代码+综合比较代码(直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、折半插入排序、2路插入排序),其中不仅有各种排序算法的代码,还包含10种代码在关键字...
各种基本排序方法(直接插入、希尔、直接选择、冒泡、快速、堆、二路归并)的大致原理和过程、复杂性和稳定性、相应算法的程序段;
冒泡排序、选择排序、插入排序和希尔排序 冒泡排序、选择排序、插入排序和希尔排序 冒泡排序、选择排序、插入排序和希尔排序
直接插入排序、折半插入排序、希尔排列
C# 排序算法大全参考资料,比较清淅的一个版本。集中介绍了C#中的冒泡算法、选择排序、插入排序、希尔排序等常用算法,并包含示例代码和注意事项等。
插入排序之希尔排序
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
直接插入排序、希尔排序、冒泡排序、直接选择排序、堆排序、归并排序
希尔排序法,最经典的排序法,但不是容易懂。包括希尔插入排序,希尔交换排序
本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序、选择排序、插入排序和希尔排序
c++实现的线性表排序算法 插入排序,希尔排序,冒泡排序,快速排序,堆排序,归并排序等
插入排序,希尔排序,C程序代码,经过运行,决定可用
用C++,模板写的 7中排序. 快速排序, 归并排序,插入排序,选择排序,起泡排序,堆排序,希尔排序