基础算法-希尔排序的理解与实现-Android版

希尔排序：直接插入排序的进化版，又称为“缩小增量排序”； 根据key值，将待排序数列分成若干个子序列，针对每一个子序列进行直接插入排序；然后逐步缩小key值，直到key=1,此时即为直接插入排序；

例如：       

a[] = {5, 3, 9, 6, 2, 1, 4, 0, 8, 7};

假如key=5, 可知{5， 1}===>插入排序后{1 , 5}

                   可知{3， 4}===>插入排序后{3 ,4}

                   可知{9， 0}===>插入排序后{0 , 9}

                   可知{6， 8}===>插入排序后{6 , 8}

                    可知{2，7}===>插入排序后{2 , 7}

最后得到的序列为    {1, 3, 0, 6, 2, 5, 4, 9, 8, 7}

然后逐步缩减key值，直到key=1, 完成排序。

代码实现 1： key= a.length/ 2,  即： key = a.length >> 1

int a[] = {5, 3, 9, 6, 2, 1, 4, 0, 8, 7};
for (int i = 0; i < a.length; i++) {
Log.i("chy==数列初始===", "====" + a[i]);
}
/**
* 希尔排序外层循环控制循环次数，就是间隔key减少至1的次数
*/
for (int gap = a.length >> 1; gap > 0; gap = gap >> 1) {
/**
* 每一个key, 可以得到诺干个子序列； 针对每一个子序列做直接插入排序
* 当 key=1 时，整个序列为一个子序列，进行直接插入排序
*/
for (int i = gap; i < a.length; i++) {
for (int j = i; j > gap - 1; j = j - gap) {
if (a[j - gap] > a[j]) {
int temp = a[j];
a[j] = a[j-gap];
a[j-gap] = temp;
} else {
break;
}
}
}
}
for (int i = 0; i < a.length; i++) {
Log.i("chy==输出结果===", "====" + a[i]);
}

代码实现 2： Knuth序列法======>   key= key*3 / 1

int a[] = {5, 3, 9, 6, 2, 1, 4, 0, 8, 7};
for (int i = 0; i < a.length; i++) {
Log.i("chy==初始结果===", "====" + a[i]);
}
/**
* 得到 kunth 相对于整个数组的最大值
*/
int knuth = 1;
while (knuth <= a.length/3){
knuth = knuth * 3 + 1;
}
/**
* 希尔排序外层循环控制循环次数，就是间隔key减少至1的次数
*/
for (int gap = knuth; gap > 0; gap = (gap-1) /3 ) {
/**
* 每一个key, 可以得到诺干个子序列； 针对每一个子序列做直接插入排序
* 当 key=1 时，整个序列为一个子序列，进行直接插入排序
*/
for (int i = gap; i < a.length; i++) {
for (int j = i; j > gap - 1; j = j - gap) {
if (a[j - gap] > a[j]) {
int temp = a[j];
a[j] = a[j-gap];
a[j-gap] = temp;
} else {
break;
}
}
}
}
for (int i = 0; i < a.length; i++) {
Log.i("chy==结果===", "====" + a[i]);
}

希尔排序记忆： 将待排序数列分成不同段，每段进行直接插入排序；从小序列开始，最后连成一片；上两种形式只是key 的取值方法不一致，其他的都是一样的原理

最后

以上就是爱笑小松鼠为你收集整理的基础算法-希尔排序的理解与实现-Android版的全部内容，希望文章能够帮你解决基础算法-希尔排序的理解与实现-Android版所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。