Shell排序算法
Shell排序算法严格来说基于插入排序的思想,其又称为希尔排序或者缩小增量排序。Shell排序算法的排序流程如下:
(1)将有n个元素的数组分成n/2个数字序列,第1个数据和第n/2+1个数据为一对,……
(2)一次循环使每一个序列对排好顺序。
(3)然后,再变为n/4个序列,再次排序。
(4)不断重复上述过程,随着序列减少最后变为一个,也就完成了整个排序。
为了更好地理解Shell排序算法的执行过程,下面举一个实际数据的例子来一步一步地执行Shell排序算法。6个整型数据127、118、105、101、112、100是一组无序的数据。对其执行Shell排序过程,如图所示。
java示例:
public class ClassP4_4 { static void shellSort(int[] arr) { int r, temp, j; for (r = arr.length / 2; r >= 1; r /= 2) {//划组排序 System.out.println("每组序列r:" + r); for (int i = r; i < arr.length; i++) { temp = arr[i]; j = i - r; while (j >= 0 && temp < arr[j]) { arr[j + r] = arr[j]; arr[j] = temp; System.out.println("交换," + (j + r) + "<->" + j + ":" + ArrayUtils.toString(arr)); j -= r; } } } } public static void main(String[] args) { shellSort(new int[]{ 9, 8, 7, 6, 5, 4, 3, 2, 1}); } }
结果:
每组序列r:4 交换,4<->0:{5,8,7,6,9,4,3,2,1} 交换,5<->1:{5,4,7,6,9,8,3,2,1} 交换,6<->2:{5,4,3,6,9,8,7,2,1} 交换,7<->3:{5,4,3,2,9,8,7,6,1} 交换,8<->4:{5,4,3,2,1,8,7,6,9} 交换,4<->0:{1,4,3,2,5,8,7,6,9} 每组序列r:2 交换,3<->1:{1,2,3,4,5,8,7,6,9} 交换,7<->5:{1,2,3,4,5,6,7,8,9} 每组序列r:1
文章:Java常用算法手册4.5