排序算法

    public static int[] swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        return nums;
    }

1.快速排序

核心的思路是取第一个元素（或者最后一个元素）作为分界点，把整个数组分成左右两侧，左边的元素小于或者等于分界点元素，而右边的元素大于分界点元素，然后把分界点移到中间位置，对左右子数组分别进行递归，最后就能得到一个排序完成的数组。当子数组只有一个或者没有元素的时候就结束这个递归过程。

算法步骤

• ​选择基准值(pivot)​​：从数列中挑出一个元素作为基准值 ​- 分区操作(partition)​​：重新排序数列，所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准后面
• ​递归排序​：递归地将小于基准值的子数列和大于基准值的子数列排序

时间复杂度

• ​最优情况​：O(n log n) - 每次分区都能将数组均匀分成两部分 ​- 平均情况​：O(n log n) - 随机数据分布时
• ​最坏情况​：O(n²) - 当输入数组已经有序或所有元素相等时

空间复杂度

​- 最优/平均情况​：O(log n) - 递归调用栈的深度 ​- 最坏情况​：O(n) - 递归树退化为链表

    public static void quickSort(int[] nums, int left, int right) {
        if (left > right) return;
        int key = nums[left];
        int l = left;
        int r = right;
        while (l < r) {
            while (nums[r] >= key && l < r)
                r--;
            while (nums[l] <= key && l < r)
                l++;
            if (l < r)
                swap(nums, r, l);
        }

        nums[left] = nums[r];
        nums[r] = key;

        quickSort(nums, left, r - 1);
        quickSort(nums, r + 1, right);
    }

2.归并排序

归并排序是建立在归并操作上的一种有效排序算反，采用的是分治思想。这一算法充分利用了完全二叉树深度是log2(n+1)的特性，因此效率比较高。其基本原理如下：

对于给定的一组记录，利用递归与分支技术将数据划分为越来越小的半子表，再对半子表排序，最后利用递归方法将排序好的半子表合并为越来越大的有序表。

经过第一轮比较后得到最小的记录，然后将该记录的位置与第一个记录的位置交换；接着对不包括第一个记录以外的其他记录进行第二次比较，得到最小记录与第二个位置记录交换；重复这个过程直到进行比较的记录剩下一个为止。

算法步骤

​分割阶段(Divide)​​：

• 将当前数组从中间位置分为两个子数组
• 递归地对左右子数组进行分割，直到每个子数组只包含一个元素(天然有序)

​合并阶段(Conquer)​​：

• 创建临时数组存放合并结果
• 设置两个指针分别指向两个子数组的起始位置
• 比较指针所指元素，将较小者放入临时数组并移动相应指针
• 当某子数组元素全部合并后，将另一子数组剩余元素直接复制到临时数组
• 将临时数组内容复制回原数组相应位置

时间复杂度

• ​最优情况​：O(n log n)
• ​最坏情况​：O(n log n)
• ​平均情况​：O(n log n)

归并排序的时间复杂度非常稳定，无论输入数据的分布如何，都能保持O(nlogn)的性能。这是因为每次分割都将问题规模减半(对数复杂度)，而每次合并都需要线性时间。

空间复杂度

归并排序需要额外的O(n)空间用于临时数组存储合并结果。这也是归并排序的主要缺点

动画演示

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

    public static void merge(int[] a, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int leftPointer = left;
        int rightPointer = mid + 1;
        int i = 0;
        while (leftPointer <= mid && rightPointer <= right) {
            if (a[leftPointer] <= a[rightPointer]) {
                temp[i++] = a[leftPointer++];
            } else {
                temp[i++] = a[rightPointer++];
            }
        }
        while (leftPointer <= mid) {
            temp[i++] = a[leftPointer++];
        }
        while (rightPointer <= right) {
            temp[i++] = a[rightPointer++];
        }
        if (temp.length >= 0) {
            System.arraycopy(temp, 0, a, left, temp.length);
        }
    }

参考连接

4.选择排序

选择排序(Selection Sort)的基本思想是：​每次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。重复这个过程，直到所有元素均排序完毕。

算法步骤

• ​初始化​：将整个待排序序列分为已排序区间(初始为空)和未排序区间(初始为整个序列)
• ​查找最小值​：在未排序区间中遍历查找最小元素 ​- 交换位置​：将找到的最小元素与未排序区间的第一个元素交换位置
• ​调整区间​：将未排序区间的起始位置后移一位，扩大已排序区间 ​- 重复过程​：重复步骤2-4，直到未排序区间为空

时间复杂度

• ​最好情况​：O(n²) - 即使数组已经有序，仍需完整比较
• ​最坏情况​：O(n²) - 数组完全逆序时 ​- 平均情况​：O(n²) - 比较次数固定为n(n-1)/2次

空间复杂度

• O(1) - 原地排序，仅需常数级额外空间

    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        // 外层循环控制已排序区间的末尾
        for (int i = 0; i < n - 1; i++) {
            // 假设当前元素是最小的
            int minIndex = i;
            
            // 内层循环在未排序区间查找最小值
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            // 将找到的最小值与当前位置交换
            if (minIndex != i) {
                swap(arr, i, minIndex);
            }
        }
    } 

3.冒泡排序

冒泡排序从左到右依次比较两个相邻的元素，如果前一个元素比较大，就把前一个元素和后一个元素交换位置，完成一趟循环后保证了最大的元素在最后一位。接下来进行第二趟排序，第二趟排序完成后第二大的元素在倒数第二位。依次遍历直至整个数组排序完成。

算法步骤

​- 比较相邻元素​：从序列的第一个元素开始，比较相邻的两个元素

• ​交换位置​：如果它们的顺序错误(如前一个大于后一个)，则交换它们的位置
• ​重复遍历​：对序列的每一对相邻元素重复这个过程，直到序列末尾
• ​缩小范围​：排除已排序好的末尾元素，对剩余未排序序列重复上述过程
• ​终止条件​：当一趟遍历中没有发生任何交换时，排序完成

时间复杂度

• ​最优情况​：O(n) - 当输入数组已经有序时，只需一次遍历即可完成排序
• ​最坏情况​：O(n²) - 当输入数组完全逆序时，需要进行n(n-1)/2次比较和交换
• ​平均情况​：O(n²) - 随机数据分布时

空间复杂度

冒泡排序是原地排序算法，只需要一个额外的临时变量用于交换元素，因此空间复杂度为O(1)

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