Leetcode 912.排序数组

公共交换函数

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

1. 选择排序

每轮找出最小的值放在左侧

private void selectionSort(int[] nums) {
   
    for (int i=0;i<nums.length;i++) {
   
        int min = i;
        for (int j=i+1;j<nums.length;j++) {
   
            if (nums[j]<nums[min]) min = j;
        }
        swap(nums, i, min);
    }
}

2. 插入排序

假设前i有序，把i+1的元素，通过交换插入到前面的i个中

private void insertSort(int[] nums) {
   
    for (int i=1;i<nums.length;i++) {
   
        for (int j=i;j>0 && nums[j]<nums[j-1];j--)
            swap(nums, j, j-1);
    }
}

3. 希尔排序

对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。

希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

    private void shellSort(int[] nums) {
   
        int h = 1;
        while (h < nums.length/3) h = h*3 + 1;
        while (h>=1) {
   
            for (int i=h; i<nums.length; i++) {
   
                for (int j=i;j>=h && nums[j]<nums[j-h];j-=h)
                    swap(nums, j, j-h);
            }
            h /= 3;
        }
    }

4. 冒泡排序

比较交换，大的向后交换

// 慢的超时
    private void bubbleSort(int[] nums) {
   
        for (int i=nums.length-1; i>=0; i--) {
   
            for (int j=0; j<i; j++)
                if (nums[j]>nums[j+1]) swap(nums, j, j+1);
        }
    }

5. 归并排序

排左排右，然后归并（将两个有序数组合并为一个）

private void mergeSort(int[] nums) {
   
    mergeSort(nums, 0, nums.length-1);
}
private void mergeSort(int[] nums, int l, int h) {
   
    if (h<=l) return;
    int m = l + (h-l)/2;
    mergeSort(nums, l, m);
    mergeSort(nums, m+1, h);
    merge(nums, l, m, h);
}
private void merge(int[] nums, int l, int m, int h) {
   
    int i = l, j = m+1;
    int[] tmp = new int[nums.length];
    for (int k=l; k<=h; k++) tmp[k] = nums[k];
    for (int k=l; k<=h; k++) {
   
        if (i>m) nums[k] = tmp[j++];
        else if (j>h) nums[k] = tmp[i++];
        else if (tmp[i]<=tmp[j]) nums[k] = tmp[i++];
        else nums[k] = tmp[j++];
    }
}

6. 快速排序

快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。

parition返回的j左侧都是小于nums[l]的，右侧都是大于nums[l]的

private void quickSort(int[] nums) {
   
    quickSort(nums, 0, nums.length-1);
}
private void quickSort(int[] nums, int l, int h) {
   
    if (l>=h) return;
    int j = partition(nums, l, h);
    quickSort(nums, l, j-1);
    quickSort(nums, j+1, h);
}
private int partition(int[] nums, int l, int h) {
   
    int i = l, j = h+1;
    while (true) {
   
        while (nums[++i]<nums[l] && i!=h) ;
        while (nums[--j]>nums[l] && j!=l) ;
        if (i >= j) break;
        swap(nums, i, j);
    }
    swap(nums, l, j);
    return j;
}

7. 堆排序

public static void heapSort(int[] nums) {
   
	// 建立大顶堆
    for(int i=nums.length-1; i>=0; i--)
        heapify(nums, i, nums.length);
    for(int i=nums.length-1; i>=0; i--) {
   
    	// 将大顶堆的最大值，也就是数组中的第一个元素移到最尾部
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // 由于根节点与叶子节点互换，此时需要再次对根节点进行大顶堆操作，就这样依次循环
        heapify(nums, 0, i);
    }
}
private static void heapify(int[] nums, int i, int bound) {
   
	// 得到左右孩子节点数组下标
    int left = 2*i+1, right = 2*i+2, max = i;
    // 将最大值移动到根节点，保证所有的根节点都大于孩子节点
    if (left==nums.length-1) {
   
        if (left<bound && nums[left]>nums[max])
            max = left;
    } else{
   
        if (left<bound && nums[left]>nums[max])
            max = left;
        if (right<bound && nums[right]>nums[max])
            max = right;
    }
    if (max != i) {
   
        int tmp = nums[i];
        nums[i] = nums[max];
        nums[max] = tmp;
        // 移动之后需检查孩子节点，如果孩子节点为非叶子节点，互换之后导致孩子节点不满足大顶堆特性，需继续对该孩子节点做大顶堆操作
        heapify(nums, max, bound);
    }
}