算法入门必读：8 种排序算法(Sorting Algorithms)的核心思路与实现详解

public static int[] bubbleSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return nums;
    }

    int len = nums.length;
    for (int i = len - 1; i >= 0; i--) {
        boolean isSorted = true;
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                isSorted = false;
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
        if (isSorted) {
            break;
        }
    }

    return nums;
}

public static int[] selectSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return nums;
    }

    int len = nums.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (nums[j] < nums[i]) {
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
    }

    return nums;
}

public static int[] insertSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return nums;
    }

    int len = nums.length;
    for (int i = 1; i < len; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j + 1];
                nums[j + 1] = nums[j];
                nums[j] = temp;
            }
        }
    }

    return nums;
}

public static int[] shellSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return nums;
    }

    int len = nums.length;
    for (int gap = len / 2; gap >= 1; gap /= 2) {
        for (int i = gap; i < len; i++) {
            int j = i;
            while (j - gap >= 0 && nums[j] < nums[j - gap]) {
                int temp = nums[j];
                nums[j] = nums[j - gap];
                nums[j - gap] = temp;
                j -= gap;
            }
        }
    }

    return nums;
}

public static int[] heapSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return nums;
    }

    int len = nums.length;

    // 1. build the Max Heap
    for (int i = len / 2 - 1; i >= 0; i--) {
        maxHeapify(nums, i, len - 1);
    }

    // 2. swap Heap peek with the end, adjust the heap
    for (int i = len - 1; i > 0; i--) {
        swap(nums, 0, i);
        maxHeapify(nums, 0, i - 1);
    }

    return nums;
}

private static void maxHeapify(int[] arr, int start, int end) {
    int parent = start;
    int child = 2 * start + 1;

    while (child <= end) {
        if (child + 1 <= end && arr[child] < arr[child + 1]) {
            child++;
        }

        if (arr[parent] < arr[child]) {
            swap(arr, parent, child);
            parent = child;
            child = 2 * child + 1;
        } else {
            break;
        }
    }
}

private static void swap(int[] nums, int a, int b) {
    int temp = nums[a];
    nums[a] = nums[b];
    nums[b] = temp;
}

public int[] mergeSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return nums;
    }

    int len = nums.length;
    mergeSort(nums, 0, len - 1);
    return nums;
}

public void mergeSort(int[] nums, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
}

public void merge(int[] nums, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int[] temp = new int[nums.length];
    int t = 0;
    while (i <= mid && j <= right) {
        if (nums[i] >= nums[j]) {
            temp[t++] = nums[j++];
        } else {
            temp[t++] = nums[i++];
        }
    }

    while (i <= mid) {
        temp[t++] = nums[i++];
    }

    while (j <= right) {
        temp[t++] = nums[j++];
    }

    t = 0;
    while (left <= right) {
        nums[left++] = temp[t++];
    }
}

public int[] quickSort(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
}

public void quickSort(int[] nums, int low, int high) {
    if (low < high) {
        int pos = partition(nums, low, high);
        quickSort(nums, low, pos - 1);
        quickSort(nums, pos + 1, high);
    }
}

public int partition(int[] nums, int low, int high) {
    int pivot = nums[low];
    while (low < high) {
        while (low < high && nums[high] > pivot) {
            high--;
        }
        if (low < high) {
            nums[low] = nums[high];
        }
        while (low < high && nums[low] < pivot) {
            low++;
        }
        if (low < high) {
            nums[high] = nums[low];
        }
    }
    nums[low] = pivot;
    return low;
}