/ * 希尔排序：
* 不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法，
* 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度为 O(N*(logN)2)，
* 没有快速排序算法快 O(N*(logN))，因此中等大小规模表现良好，对规模非常大的数据排序不是
* 最优选择。但是比O(N2）复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。
* 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏
* 的情况下执行的效率会非常差。
*
* 专家门提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，
* 再改成快速排序这样更高级的排序算法。
*
* 本质上讲，希尔排序算法的一种改进，减少了其复制的次数，速度要快很多。
* 原因是，当N值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。
* 当N值减小时每一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。
* 正是这两种情况的结合才使希尔排序效率比插入排序高很多。
*/
////////////////////////////////////////////////////////////////////////////////
class Array {
private long[] theArray;
private int nElems;
public Array(int max) {
theArray = new long[max];
nElems = 0;
}
public void insert(long value) {
theArray[nElems] = value;
nElems++;
}
public void display() {
System.out.print("A=");
for (int j = 0; j < nElems; j++) {
System.out.print(theArray[j] + " ");
}
System.out.println("");
}
public void shellSort() {
int inner, outer;
long temp;
int h = 1;
while (h <= nElems / 3) {
h = 3 * h + 1;
}
while (h > 0) {
for (outer = h; outer < nElems; outer++) {
temp = theArray[outer];
inner = outer;
while (inner > h - 1 && theArray[inner - h] >= temp) {
theArray[inner] = theArray[inner - h];
inner = inner - h;
}
theArray[inner] = temp;
}
h = (h - 1) / 3;
}
}
}
class ShellSortApp {
public static void main(String[] args) {
int maxSize = 30;
Array arr = new Array(maxSize);
for (int j = 0; j < maxSize; j++) {
long n = (int) (java.lang.Math.random() * 99);
arr.insert(n);
}
arr.display();
arr.shellSort();
arr.display();
}
}
////////////////////////////////////////////////////////////////////////////////
/**
* 运行结果：
* A=29 14 28 16 40 64 29 11 58 27 88 96 41 63 19 30 55 82 6 10 83 93 86 13 29 19 20 83 83 8
* A=6 8 10 11 13 14 16 19 19 20 27 28 29 29 29 30 40 41 55 58 63 64 82 83 83 83 86 88 93 96
*/
/**
* 总结：
* 希尔排序是对插入排序的一种强有力的改进，极大的提升了其效率，特别是当排序的
* 数据项增加的时候。
* 例子为随机生成30个数，然后将其用希尔算法排序再输出。
*/
////////////////////////////////////////////////////////////////////////////////// |
收藏
淘帖
踩
