选择排序
- 算法分析：给定一个序列，每一次从待排序的[数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
- 代码实现(可以对比两个版本的不同)
- 所有算法实现的基类
/**
* . 排序算法基类
*
* @author liyaocai
* @version V1.0
* @date 2018/6/21 13:54
* @since 1.8
*/
public abstract class AbstractSortingAlgorithm {
/**
* . 返回两个值当中小的.
*/
protected boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
/**
* 交换该数组中两个下标处的值.
*/
protected void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
/**
* 单行打印数组.
*/
protected void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i] + " ");
}
}
/**
* 测试数组元素是否有序.
*/
public boolean isSorted(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
if (less(a[i], a[i - 1])) {
return false;
}
}
return true;
}
/**
* 根据不同算法具体实现.
*/
protected abstract void sort(Comparable[] a);
}
- 实现一
protected void sort(Comparable[] a) {
int N = a.length;
// 将a[i]和a[i+1,....N-1]中最小的元素交换
for (int i = 0; i < N; i++) {
// 数组中最小元素的索引
int minIndex = i;
for (int j = i + 1; j < N; j++) {
if (less(a[j], a[i])) {
exch(a, i, minIndex);
}
}
}
}
- 实现二
/**
* 选择排序实现.
*
* @author liyaocai
* @version V1.0
* @date 2018/6/21 13:55
* @since 1.8
*/
public class Selection extends AbstractSortingAlgorithm {
/**
* description sort.
*
* @param a a array to be sorted.
* @author liyaocai
* @date
*/
@Override
protected void sort(Comparable[] a) {
int N = a.length;
// 将a[i]和a[i+1,....N-1]中最小的元素交换
for (int i = 0; i < N; i++) {
// 数组中最小元素的索引
int minIndex = i;
for (int j = i + 1; j < N; j++) {
if (less(a[j], a[i])) {
minIndex = j;
}
}
//避免每次比较都交换元素,在全部比较完之后在交换
if (minIndex != i) {
// 交换数组元素
exch(a, i, minIndex);
}
}
}
插入排序
- 算法分析：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
- 代码实现：
/**
* description 插入排序具体实现.
*
* @author liyaocai
* @version V1.0
* @date 2018/6/21 14:31
* @since 1.8
*/
public class Insertion extends AbstractSortingAlgorithm {
@Override
protected void sort(Comparable[] a) {
// 将a[]按升序排列
int N = a.length;
for (int i = 1; i < N; i++) {
//将a[i]插入到前面适当的位置
for (int j = i; j > 0; j--) {
if (less(a[j], a[j - 1])) {
exch(a, j, j - 1);
}
}
}
}
}
- 实现二（避免了使用交换，而是每次将比较大的元素右移）这种实现效率很高，待会附上测试数据
/**
* description 改进插入排序.
*
* @author liyaocai
* @version V1.0
* @date 2018/6/21 14:38
* @since 1.8
*/
public class ExtInsertion extends AbstractSortingAlgorithm {
@Override
protected void sort(Comparable[] a) {
int N = a.length;
int count = 0;
for (int i = 1; i < N; i++) {
//设置哨兵，不需要每次比较都交换
int j;
Integer temp = (Integer) a[i];
boolean flag = false;
for ( j=i;j > 0 && less(temp, a[j - 1]);j--) {
a[j] = a[j - 1];
}
a[j]=temp;
}
}
}
对上述算法进行测试：
测试代码：
/**
* description 测试算法效率.
*
* @author liyaocai
* @version V1.0
* @date 2018/6/21 16:34
* @since 1.8
*/
public class SortCompareUtil {
private AbstractSortingAlgorithm algorithm;
SortCompareUtil(AbstractSortingAlgorithm algorithm) {
this.algorithm = algorithm;
}
public static double time(AbstractSortingAlgorithm alg, Comparable[] a) {
long startTime = System.nanoTime();
alg.sort(a);
long consumingTime = System.nanoTime() - startTime;
return consumingTime / 1000;
}
public static void test(AbstractSortingAlgorithm alg) {
double total = 0.0;
Comparable[] a = new Comparable[10000];
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10000; j++) {
a[j] = new Random().nextInt(100000) + 1;
}
double t = time(alg, a);
System.out.println(alg.toString() + "第" + i + "次运行时间 ：" + t);
total += t;
}
System.out.println("总共耗时：" + total);
}
public static void main(String[] args) {
Selection selection = new Selection();
Insertion insertion = new Insertion();
ExtInsertion extInsertion = new ExtInsertion();
SortCompareUtil.test(selection);
SortCompareUtil.test(insertion);
SortCompareUtil.test(extInsertion);
}
}
希尔排序
- 算法分析：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
- 代码实现：
@Override
protected void sort(Comparable[] a) {
int N = a.length;
//关于增量的大小，测试发现并不明显，但还是采用如下的方式
int h = 1;
while (h < N / 3) {
h = 3 * h + 1;
}
int j;
while (h >= 1) {
// 将数组变为h有序
for (int i = h; i < N; i++) {
Integer temp = (Integer) a[i];
// 将a[i]insert to a[i-h].....a[i-3h]
for (j = i; j >= h && less(a[j], a[j - h]); j -= h) {
// 采用移动法和交换法都可，具体效率差不多
exch(a,j,j-h);
}
}
h = h / 3;
}
}
- 测试结果
sort.Selection@8807e25第0次运行时间 ：463148.0
sort.Selection@8807e25第1次运行时间 ：343690.0
sort.Selection@8807e25第2次运行时间 ：167455.0
sort.Selection@8807e25第3次运行时间 ：437954.0
sort.Selection@8807e25第4次运行时间 ：597579.0
sort.Selection@8807e25第5次运行时间 ：553570.0
sort.Selection@8807e25第6次运行时间 ：394855.0
sort.Selection@8807e25第7次运行时间 ：205120.0
sort.Selection@8807e25第8次运行时间 ：282842.0
sort.Selection@8807e25第9次运行时间 ：126944.0
总共耗时：3573157.0
sort.Insertion@68fb2c38第0次运行时间 ：371651.0
sort.Insertion@68fb2c38第1次运行时间 ：339894.0
sort.Insertion@68fb2c38第2次运行时间 ：408705.0
sort.Insertion@68fb2c38第3次运行时间 ：355622.0
sort.Insertion@68fb2c38第4次运行时间 ：306110.0
sort.Insertion@68fb2c38第5次运行时间 ：324249.0
sort.Insertion@68fb2c38第6次运行时间 ：279289.0
sort.Insertion@68fb2c38第7次运行时间 ：283586.0
sort.Insertion@68fb2c38第8次运行时间 ：291883.0
sort.Insertion@68fb2c38第9次运行时间 ：291868.0
总共耗时：3252857.0
sort.ExtInsertion@567d299b第0次运行时间 ：79246.0
sort.ExtInsertion@567d299b第1次运行时间 ：71163.0
sort.ExtInsertion@567d299b第2次运行时间 ：79811.0
sort.ExtInsertion@567d299b第3次运行时间 ：69084.0
sort.ExtInsertion@567d299b第4次运行时间 ：65376.0
sort.ExtInsertion@567d299b第5次运行时间 ：63753.0
sort.ExtInsertion@567d299b第6次运行时间 ：80216.0
sort.ExtInsertion@567d299b第7次运行时间 ：119158.0
sort.ExtInsertion@567d299b第8次运行时间 ：74429.0
sort.ExtInsertion@567d299b第9次运行时间 ：86789.0
总共耗时：789025.0
sort.Shelltion@2a098129第0次运行时间 ：27908.0
sort.Shelltion@2a098129第1次运行时间 ：10717.0
sort.Shelltion@2a098129第2次运行时间 ：1925.0
sort.Shelltion@2a098129第3次运行时间 ：3871.0
sort.Shelltion@2a098129第4次运行时间 ：2087.0
sort.Shelltion@2a098129第5次运行时间 ：2312.0
sort.Shelltion@2a098129第6次运行时间 ：6435.0
sort.Shelltion@2a098129第7次运行时间 ：2782.0
sort.Shelltion@2a098129第8次运行时间 ：1781.0
sort.Shelltion@2a098129第9次运行时间 ：6549.0
总共耗时：66367.0
