排序

交换、插入、选择、归并

稳定：a在b前，a = b,排序后，a仍在b前。

不稳定：a在b前，a=b，排序后，a可能在b后。

交换排序

• 冒泡 稳定——平均O(n^2)，最好O(n)，最坏O(n^2)
• 快排 不稳定——平均O(NlogN)，最好O(NlogN)，最坏O(N^2)

冒泡排序

package com.sort;

public class BubleSort implements Sort{
    private void swap(int[] nums, int j, int i) {
        int tem = nums[j];
        nums[j] = nums[i];
        nums[i] = tem;
    }

    @Override
    public void sort(int[] nums) {
        for(int i = 0;i < nums.length;i++){
            for(int j = nums.length - 1;j > 0;j--){
                if(nums[j] < nums[j - 1]){
                    swap(nums,j,j - 1);
                }
            }
        }
    }
}

快排

package com.sort;

public class QuickSort implements Sort{


    @Override
    public void sort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    private void quickSort(int[] nums, int i, int j) {
        if (i >= j) return;
        int mid = partition(nums, i, j);
        quickSort(nums, i, mid - 1);
        quickSort(nums, mid + 1, j);
    }

    private int partition(int[] nums, int l, int h) {
        int base = nums[l];
        int i = l + 1, j = h;
        while (i < j) {
            while (i < j && nums[i] < base) i++;
            while (i < j && nums[j] > base) j--;
            swap(nums, i, j);
        }
        swap(nums, i, l);
        return i;
    }

    private void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}

插入排序

• 插入排序 稳定——O(N^2),最坏 O(N^2)，最好O(N)
• 希尔排序 不稳定——O(N^1.3),最坏O(N^2),最好O(N)

插入排序

package com.sort;

public class InsertSort implements Sort {


    @Override
    public void sort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (nums[j] < nums[j - 1]) {
                    swap(nums,j,j - 1);
                }
            }
        }
    }

    private void swap(int[] nums, int j, int i) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}

希尔排序

package com.sort;

public class ShellSort implements Sort{

    @Override
    public void sort(int[] nums) {
        int h = 1;
        while (h < nums.length / 3) {
            h = h * 3 + 1;
        }
        while (h != 0) {
            for (int i = h; i < nums.length; i += h) {
                for (int j = i; j >= h && nums[j] < nums[j - h]; j -= h) {
                    swap(nums, j, j - h);
                }
            }
            h = h / 3;
        }
    }

    private void swap(int[] nums, int j, int i) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}