排序算法(Sorting Algorithms)

By Long Luo

1. 冒泡排序(Bubble Sort)

思路与算法：

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;
}

复杂度分析：

• 时间复杂度：$O(N^2)$，其中 $N$ 是数组 $\textit{nums}$ 的长度。
• 空间复杂度：$O(1)$。

2. 选择排序(Select Sort)

思路与算法：

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;
}

复杂度分析：

• 时间复杂度：$O(N^2)$，其中 $N$ 是数组 $\textit{nums}$ 的长度。
• 空间复杂度：$O(1)$。

3. 插入排序(Insert Sort)

思路与算法：

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;
}

复杂度分析：

• 时间复杂度：$O(N^2)$，其中 $N$ 是数组 $\textit{nums}$ 的长度。
• 空间复杂度：$O(1)$。

4. 希尔排序(Shell Sort)

思路与算法：

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;
}

复杂度分析：

• 时间复杂度：$O(N^2)$，其中 $N$ 是数组 $\textit{nums}$ 的长度。
• 空间复杂度：$O(1)$。

5. 堆排序(Heap Sort)

思路与算法：

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;
}

复杂度分析：

• 时间复杂度：$O(NlogN)$，其中 $N$ 是数组 $\textit{nums}$ 的长度。
• 空间复杂度：$O(1)$。

6. 归并排序(Merge Sort)

思路与算法：

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++];
    }
}

复杂度分析：

• 时间复杂度：$O(NlogN)$，其中 $N$ 是数组 $\textit{nums}$ 的长度。
• 空间复杂度：$O(1)$。

7. 快速排序(Quick Sort)

思路与算法：

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;
}

复杂度分析：

• 时间复杂度：$O(NlogN)$，其中 $N$ 是数组 $\textit{nums}$ 的长度。
• 空间复杂度：$O(1)$。

排序算法总结

Array Sorting Algorithms
Algorithm Time Complexity Space Complexity
Best Average Worst Worst
Quicksort Ω(n log(n)) Θ(n log(n)) O(n^2) O(log(n))
Mergesort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n)
Timsort Ω(n) Θ(n log(n)) O(n log(n)) O(n)
Heapsort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(1)
Bubble Sort Ω(n) Θ(n^2) O(n^2) O(1)
Insertion Sort Ω(n) Θ(n^2) O(n^2) O(1)
Selection Sort Ω(n^2) Θ(n^2) O(n^2) O(1)
Tree Sort Ω(n log(n)) Θ(n log(n)) O(n^2) O(n)
Shell Sort Ω(n log(n)) Θ(n(log(n))^2) O(n(log(n))^2) O(1)
Bucket Sort Ω(n+k) Θ(n+k) O(n^2) O(n)
Radix Sort Ω(nk) Θ(nk) O(nk) O(n+k)
Counting Sort Ω(n+k) Θ(n+k) O(n+k) O(k)
Cubesort Ω(n) Θ(n log(n)) O(n log(n)) O(n)

参考资料

1. Sorting Visualization
2. Sorting Algorithms
3. 常用的排序算法总结
4. 八大经典排序算法详解
5. 复习基础排序算法
6. Big O Cheat Sheet
7. 手撕九大经典排序算法，看我就够了！
8. 常用排序算法复杂度分析
9. 排序算法全解析