Java实现初级排序算法之——希尔排序算法

标签: java  希尔排序

算法原理:

希尔排序算法是基于插入排序算法的快速排序算法,希尔算法为了加快速度简单的改进了插入排序,交换不相邻的元素以对数组的局部进行排序,并最终用插入排序将局部有序的数组进行排序。其思想是使数组中的任意间隔为 h 的元素都是有序的

算法特点:

  • 权衡子数组的规模和有序性
  • 高效

算法实现:

package com.example;

/**
 * 
 * @Description : 用希尔算法对数组排序
 * @ClassName   : ShellSort
 * @author      : RelaxOne
 * @date        : 2018年8月18日 下午4:18:02
 */
public class ShellSort {
	
	/**
	 * 
	 * @Description: 按升序方式排列数组
	 * @author : RelaxOne
	 * @date   : 2018年8月18日
	 * @param arr
	 * @return
	 */
	public static Double[] sort_up(Double[] arr){
		for(int gap = arr.length/2;gap>0;gap/=2) {
			for(int i=gap;i<arr.length;i++) {
				int j = i;
				double temp = arr[j];
				if(arr[j] < arr[j-gap]) {
					while(j-gap >=0 && temp < arr[j-gap]) {
						arr[j] = arr[j-gap];
						j -= gap;
					}
					arr[j] = temp;
				}
			}
		}
		return arr;
	}
	
	/**
	 * 
	 * @Description: 按降序方式排列数组
	 * @author : RelaxOne
	 * @date   : 2018年8月18日
	 * @param arr
	 * @return
	 */
	public static Double[] sort_down(Double[] arr){
		for(int gap = arr.length/2;gap>0;gap/=2) {
			for(int i=gap;i<arr.length;i++) {
				int j = i;
				double temp = arr[j];
				if(arr[j] > arr[j-gap]) {
					while(j-gap >=0 && temp > arr[j-gap]) {
						arr[j] = arr[j-gap];
						j -= gap;
					}
					arr[j] = temp;
				}
			}
		}
		return arr;
	}
	
}

测试代码:

package com.example;

public class Test {
	public static void main(String[] args) {
		Double[] arr = new Double[] {1.2,-4.2,2.5,3.8,1.9};
		arr = ShellSort.sort_down(arr);
		printArray(arr);
	}
	
	public static void printArray(Double[] arr) {
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
}

测试结果:

原文链接:加载失败,请重新获取