乐趣区

关于算法:排序算法总览

排序办法 工夫复杂度(均匀) 工夫复杂度(最坏) 工夫复杂度(最好) 空间复杂度 稳定性 复杂性
插入排序 O(n^2) O(n^2) O(n) O(1) 稳固 简略
希尔排序 O(nlogn) O(n^2) O(n^1.3) O(1) 不稳固 较简单

一、插入排序

public static void sort(int[] arr) {for (int i = 1; i < arr.length; i++) {int tmp = arr[i];
    int j;
    for (j = i - 1; j >= 0 && tmp < arr[j]; j--) {arr[j + 1] = arr[j];
    }
    arr[j + 1] = tmp;
  }
}

二、希尔排序(放大增量排序)

public static void sort(int[] arr) {for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {for (int i = 0; i < gap; i++) {for (int j = i + gap; j < arr.length; j += gap) {int tmp = arr[j];
        int k;
        for (k = j - gap; k >= 0 && tmp < arr[k]; k -= gap) {arr[k + gap] = arr[k];
        }
        arr[k + gap] = tmp;
      }
    }
  }
}

…. 待欠缺,最终会把所有罕用排序都放进来

退出移动版