Home > Java > javaTutorial > A brief analysis of java Hill sorting (Shell) algorithm

A brief analysis of java Hill sorting (Shell) algorithm

高洛峰
Release: 2017-01-17 13:20:00
Original
1441 people have browsed it

First take an integer d1 less than n as the first increment, and divide all records in the file into d1 groups. All records whose distance is a multiple of dl are placed in the same group. First perform direct insertion sorting within each group; then, take the second increment d2This method is essentially a group insertion method.

Schematic diagram:

浅析java 希尔排序(Shell)算法

##Source code

package com.zc.manythread;
/**
 * 
 * @author 偶my耶
 *
 */
public class ShellSort {
    public static int count = 0;
    public static void shellSort(int[] data) {
        // 计算出最大的h值
        int h = 1;
        while (h <= data.length / 3) {
            h = h * 3 + 1;
        }
        while (h > 0) {
            for (int i = h; i < data.length; i += h) {
                if (data[i] < data[i - h]) {
                    int tmp = data[i];
                    int j = i - h;
                    while (j >= 0 && data[j] > tmp) {
                        data[j + h] = data[j];
                        j -= h;
                    }
                    data[j + h] = tmp;
                    print(data);
                }
            }
            // 计算出下一个h值
            h = (h - 1) / 3;
        }
    }
    public static void print(int[] data) {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + "\t");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] data = new int[] { 4, 3, 6, 2, 1, 9, 5, 8, 7 };
        print(data);
        shellSort(data);
        print(data);
    }
}
Copy after login

Running results:

浅析java 希尔排序(Shell)算法

Shell sorting is unstable, its space overhead is also O(1), and the time overhead is estimated to be between O(N3/2)~O(N7/6)

More analysis of java Hill For articles related to sorting (Shell) algorithms, please pay attention to the PHP Chinese website!


Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template