Java数据结构之排序---希尔排序

希尔排序的基本介绍：

希尔排序同之前的插入排序一样，它也是一种插入排序，只不过它是简单插入排序之后的一个优化的排序算法，希尔排序也被称为缩小增量排序。

希尔排序的基本思想：

希尔排序是把数组中给定的元素按照下标的一定增量进行分组，在分组之后，对每组使用直接插入排序算法；随着增量的减少，每组包含的元素越来越多，当增量减少到1的时候，整个数组正好被分成一组，此时该算法终止。通常我们判断增量是通过：第一次的增量=数组的长度/2(取整)，第二次的增量=第一次的增量/2(取整)...一直到增量为1结束。

希尔排序的示意图：

整个希尔排序我们可以通过两种方式来实现：交换法(用交换排序的思想)，移动法(用插入排序的思想)。在这个例子中，我们给定的数组是int[] arr = {8,9,1,7,2,3,5,4,6,0};

(1).交换法

其中交换法是通过两种方式讲述的：分步骤的实现，整体的实现。具体的解释在代码的注释中，观看注释即可。

(1.1)分步骤的实现

	public static void main(String[] args) {

		// TODO Auto-generated method stub

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

		System.out.println("原始的序列：");

		System.out.println(Arrays.toString(arr));

		shellSort(arr);

	}

	//交换法

	//希尔排序

	public static void shellSort(int[] arr){

		//第一趟排序,由于我们数组中打的元素一共有10个，所以我们第一趟选择的增量为10/2=5

		int temp = 0;

		for(int i=5;i<arr.length;i++){   //我们这里令i从5开始

			for(int j=i-5;j>=0;j-=5){    //j代表了与i对应在一个数组中的数。

				if(arr[j]>arr[j+5]){   //这里面就是用来比较在同一个数组里面的数字的大小，并且为它们排序

					temp = arr[j];

					arr[j] = arr[j+5];

					arr[j+5] = temp;

				}

			}

		}

		System.out.println("第一趟结束后的序列：");

		System.out.println(Arrays.toString(arr));

		//第二趟序列,这里面的增量是第一趟的增量/2=5/2=2

		for(int i=2;i<arr.length;i++){

			for(int j=i-2;j>=0;j=j-2){   //同理，跟第一趟相同

				if(arr[j]>arr[j+2]){

					temp = arr[j];

					arr[j] = arr[j+2];

					arr[j+2] = temp;

				}

			}

		}

		System.out.println("第一趟结束后的序列：");

		System.out.println(Arrays.toString(arr));

		//第三趟序列,这里面的增量是第二趟的增量/2=2/2=1

		for(int i=1;i<arr.length;i++){

			for(int j=i-1;j>=0;j=j-1){   //同理，跟第一趟相同

				if(arr[j]>arr[j+1]){

					temp = arr[j];

					arr[j] = arr[j+1];

					arr[j+1] = temp;

				}

			}

		}

		System.out.println("第一趟结束后的序列：");

		System.out.println(Arrays.toString(arr));

	}

　上述代码的最终结果如下：

(1.2)完整的代码

由上述代码，我们可以看到，当我们增量发生改变的时候，我们只是需要改变j的起始值以及定长的值即可，因此我们可以写出完整的代码如下：

	public static void main(String[] args) {

		// TODO Auto-generated method stub

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

		System.out.println("原始的序列：");

		System.out.println(Arrays.toString(arr));

		shellSort(arr);

	}

	//交换法

	//希尔排序

	public static void shellSort(int[] arr){

	//完整的希尔排序算法

		int temp = 0;

		int count = 0;

		//gap的值代表了就是每一趟的增量的值

		for(int gap = arr.length/2;gap>=1;gap = gap/2){

			for(int i=gap;i<arr.length;i++){   //如之前的代码，i从增量的位置开始算起

				for(int j=i-gap;j>=0;j=j-gap){  //这里面同之前的代码，只不过把增量变成了gap

					if(arr[j]>arr[j+gap]){

						temp = arr[j];

						arr[j] = arr[j+gap];

						arr[j+gap] = temp;

					}

				}

			}

			System.out.println("第"+(++count)+"趟排序后的序列是:");

			System.out.println(Arrays.toString(arr));

		}

	}

(2).移动法

上述代码是希尔排序的选择类的写法，它由一定的缺陷，就是效率的问题，我们每一趟都需要进行比较，这样会使整个代码的时间复杂度增加。因此我们用移动法对其进行优化。代码如下：

	public static void main(String[] args) {

		// TODO Auto-generated method stub

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

		System.out.println("原始的序列：");

		System.out.println(Arrays.toString(arr));

		shellSort2(arr);

	}

	//对交换式的希尔排序进行优化，移动法

	public static void shellSort2(int[] arr){

		int count = 0;

		for(int gap = arr.length/2;gap>=1;gap = gap/2){  //这里同上述代码保持不变

			//下面的代码根据我们的插入算法一样，只不过之前的插入算法的增量一直是1，这里面的增量是变化的，具体参照之前一章---插入算法

			for(int i=gap;i<arr.length;i++){

				int minIndex = i-gap;   //待插入位置的下标

				int temp = arr[i];   //要插入的数

				while(minIndex>=0 && temp<arr[minIndex]){

					arr[minIndex+gap] = arr[minIndex];

					minIndex-=gap;

				}

				arr[minIndex+gap] = temp;

			}

			System.out.println("第"+( ++count)+"趟排序的结果:");

			System.out.println(Arrays.toString(arr));

		}

	}

　上述代码的最终结果如下：

巴特西

Java数据结构之排序---希尔排序

最新文章

热门文章