因为希尔排序的核心思想是插入排序,所以本篇将两篇排序一起记录
本篇内容:
算法思想:
把n个待排序的元素看成一个有序表和一个无序表,开始时有序表中只有一个元素,无序表中有n-1个元素;
排序过程即每次从无序表中取出第一个元素,将它插入到有序表中,使之成为新的有序表,重复n-1次完成整个排序过程。
代码实现:
(注意:ArrayBase在第一篇中已给出代码)
/**
*
*/
package com.cherish.SortingAlgorithm;
/**
* @author acer
*
*/
public class Chapter_3_插入排序 extends ArrayBase {
/**
*
*/
public Chapter_3_插入排序() {
// TODO 自动生成的构造函数存根
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO 自动生成的方法存根
int[] array = new int[] {3,4,7,9,2,5,1,8,6};
printArray(array);
insertSorting(array);
printArray(array);
}
/*
* 把n个待排序的元素看成一个有序表和一个无序表,开始时有序表中只有一个元素,无序表中有n-1个元素;
* 排序过程即每次从无序表中取出第一个元素,将它插入到有序表中,使之成为新的有序表,重复n-1次完成整个排序过程。
* */
public static void insertSorting(int[] array) {
// TODO 自动生成的方法存根
int arrayLength = array.length;
for(int i = 1 ; i < arrayLength ; i++)
{
for(int j = i ; j > 0;j--)
{
if(array[j]<array[j-1])
{
swap(array,j,j-1);
}
}
printArray(array);
}
}
}
实现结果:
算法思想:
希尔排序的实质就是分组插入排序,又称缩小增量法;
将整个无序序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,
然后依次缩减增量再进行排序,待整个序列中的元素基本有序时,再对全体元素进行一次直接插入排序。
因为直接插入排序在元素基本有序的情况下,效率是很高的,因此希尔排序在时间效率上有很大提高
/**
*
*/
package com.cherish.SortingAlgorithm;
/**
* @author acer
*
*/
public class Chapter_4_希尔排序 extends ArrayBase {
/**
*
*/
public Chapter_4_希尔排序() {
// TODO 自动生成的构造函数存根
}
/**
* @param args
*/
public static void main(String[] args) {
int[] array = new int[] {3,4,7,9,2,5,1,8,6};
printArray(array);
shellSorting(array);
printArray(array);
}
/*
* 希尔排序的实质就是分组插入排序,又称缩小增量法
* 将整个无序序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,
* 然后依次缩减增量再进行排序,待整个序列中的元素基本有序时,再对全体元素进行一次直接插入排序。
* 因为直接插入排序在元素基本有序的情况下,效率是很高的,因此希尔排序在时间效率上有很大提高
* */
public static void shellSorting(int[] array)
{
int arrayLength = array.length;//数组长度
int gap = arrayLength/2;//子序列数
while(gap>=1)
{
for(int i = gap;i < arrayLength;i++)
{
// int j=i-gap;
for(int j = i-gap;j>=0;j--)
{
if(array[j]>array[i])
{
swap(array,j,i);
}
}
}
gap = gap/2;
printArray(array);
}
}
}
实现结果: