排序算法之希尔排序的思想以及Java实现

1 基本思想

shell排序又称之为缩小增量排序，基本思想是，先将待排序序列分割成若干个特殊的子表，分别进行插入排序，当整个表中元素”基本有序”时，再对全体记录进行一次直接插入排序。该方法实质上是一个分组插入方法。

2，算法的实现(Java)

package Algorithm;

public class ShellSort {

    /**

     * @param args

     */

    public static void main(String[] args) {

        int[] data = new int[] {11,10,55,78,100,111,45,56,79,90,345,1000};

        System.out.println("排序之前：");

        ShellSort.output(data);

        System.out.println();

        System.out.println("排序之后：");

        ShellSort.Shell_Sort(data);

        ShellSort.output(data);

    }

    //带增量的插入排序

    public static  void Shell_Sort(int[] arr){

            int s = 1;

            while (s < arr.length)

              s = s * 3 + 1;

            while (s >= 1) {

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

                for (int j = i; j >= s; j = j - s) {

                  if (arr[j] < arr[j - s]) {

                      int temp = arr[j];

                      arr[j]=  arr[j-s];

                      arr[j-s] = temp;

                  } else{

                      break;

                  }

                }

              }

              s = s / 3;

            }

        }

    //输出打印

        public static void output(int[] arr){

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

                System.out.print(arr[i]+"\t");

            }

        }

}

最终结果显示如下：

3，性能分析

shell排序需要一个记录的辅助空间，它是一种不稳定的排序。

巴特西

排序算法之希尔排序的思想以及Java实现

最新文章

热门文章