“希爾排序法”是 D.L.Shell 在 1959 年 7 月發明的一種排序法，而該排序法直接以發明者命名，其排序法的原理有點像插入排序法，但它可以減少資料搬移的次數，排序的原則是將資料區分成特定間隔的幾個小區塊，以插入排序法排完區塊內的資料后再漸漸減少間隔的距離，
演算程序
希爾法分析
- 任何情況下的時間復雜度均為 O(n^(3/2))
- 相同的元素可能在各自的插入排序中移動，最后其穩定性就會被打亂，所以希爾排序是不穩定排序
- 只需一個額外空間，所以空間復雜度是最佳的
- 此排序法適用于資料大部分都已排序完成的情況
example1
/** * 希爾排序法 * */ public class ShellSort { public static void main(String[] args) { int data[] = new int[] {6, 9, 2, 3, 4, 7, 5, 1}; System.out.print("原始資料："); showData(data); shell(data); System.out.print("排序后的資料："); showData(data); } private static void shell(int data[]) { int length = data.length; int count = 2; int block = length/count; int i, k, tmp; while (block != 0) { for (i = block; i < length; i++) { tmp = data[i]; k = i; while ((k = k-block) >= 0 && tmp < data[k]) { data[k+block] = data[k]; // data[k] = tmp; } data[k+block] = tmp; } block = block/count; showData(data); } } private static void showData(int data[]) { for (int i = 0; i < data.length; i++) { System.out.printf("[%d]", data[i]); } System.out.printf("%n"); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/199897.html
標籤：其他