直接插入排序
适合原本基本有序的序列.
时间复杂度 O(n^2).
代码
- public class Main {
- public static void main(String args[]) {
- int[] arr= {3,5,1};
- insertSort(arr);
- for(int num:arr) {
- System.out.print(num);
- }
- }
- public static void insertSort(int[] arr) {
- for(int i=1;i<arr.length;++i) {
- for(int j=i-1;j>=0&&arr[j]>arr[j+1];--j) {
- swap(arr,j,j+1);
- }
- }
- }
- private static void swap(int[] arr, int i, int j) {//
- int temp=arr[i];
- arr[i]=arr[j];
- arr[j]=temp;
- }
- }
希尔排序
设置初始增量, 增量慢慢变为原来的 1/2, 保证增量条约对应的一组组数内部有序, 采用直接插入排序.
是改进的插入排序, 就是为了使数组基本有序: 指小的基本在前面, 中的基本在中间, 大的基本在后面.(区分于局部有序). 这样可以大大减少交换次数.
时间复杂度与增量的选取有关, 平均 O(nlogn).
代码
- public class Main {
- public static void main(String args[]) {
- int[] arr= {3,5,1};
- shellSort(arr);
- for(int num:arr) {
- System.out.print(num);
- }
- }
- public static void shellSort(int arr[]) {
- int len = arr.length;
- for(int gap=len/2; gap>=1; gap=gap/2){
- for(int i=gap+1; i<len; i++){
- for(int j=i-gap; j>=0&&arr[j]>arr[j+gap]; j=j-gap){
- swap(arr,j,j+gap);
- }
- }
- }
- }
- private static void swap(int[] arr, int i, int j) {
- int temp=arr[i];
- arr[i]=arr[j];
- arr[j]=temp;
- }
- }
[排序] 直接插入排序, 希尔排序
来源: http://www.bubuko.com/infodetail-3097820.html