排序

快速排序（Quick Sort）：是一种基于分治思想的算法

选择一个枢纽（pivot）元素，将数组分成两部分：

• 一部分所有元素均小于或等于枢纽，
• 另一部分所有元素均大于枢纽。

对这两个部分递归采用相同的排序策略，最后将所有排序部分合并。

package com.zhangkai;
 
public class QuickSort {
    public static void quickSort(int[] data, int low, int high) {
        int i, j, temp, t;
        if (low > high) {
            return;
        }
        i = low;
        j = high;
        //temp就是基准位
        temp = data[low];
        System.out.println("基准位：" + temp);
 
        while (i < j) {
            //先看右边，依次往左递减
            while (temp <= data[j] && i < j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp >= data[i] && i < j) {
                i++;
            }
            //如果满足条件则交换
            if (i < j) {
                System.out.println("交换：" + data[i] + "和" + data[j]);
                t = data[j];
                data[j] = data[i];
                data[i] = t;
                System.out.println(java.util.Arrays.toString(data));
            }
        }
        //最后将基准位与i和j相等位置的数字交换
        System.out.println("基准位" + temp + "和i、j相遇的位置" + data[i] + "交换");
        data[low] = data[i];
        data[i] = temp;
        System.out.println(java.util.Arrays.toString(data));
        //递归调用左半数组
        quickSort(data, low, j - 1);
        //递归调用右半数组
        quickSort(data, j + 1, high);
    }
 
    public static void main(String[] args) {
        int[] data = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
        quickSort(data, 0, data.length - 1);
        System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
    }
}

上述代码的思想是使用双指针：

• 使用两个指针 i 和 j，分别从低端和高端开始，向中间移动。
• 先从右侧开始：当 data[j] 不小于枢纽时递减 j；
• 再从左侧开始：当 data[i] 不大于枢纽时递增 i；
• 当两个指针未相遇时，交换两者指向的元素。
• 当 i 和 j相遇时，再把枢纽（最初存储在 data[low]）与相遇位置的元素交换，确保枢纽在最终位置上。

复杂度

• 时间复杂度为 O(nlog⁡n)、非自适应排序：在平均情况下，哨兵划分的递归层数为 log⁡n ，每层中的总循环数为 n ，总体使用 O(nlog⁡n) 时间。在最差情况下，每轮哨兵划分操作都将长度为 n 的数组划分为长度为 0 和 n−1 的两个子数组，此时递归层数达到 n ，每层中的循环数为 n ，总体使用 O(n2) 时间。
• 空间复杂度为 O(n)、原地排序：在输入数组完全倒序的情况下，达到最差递归深度 n ，使用 O(n) 栈帧空间。排序操作是在原数组上进行的，未借助额外数组。
• 非稳定排序：在哨兵划分的最后一步，基准数可能会被交换至相等元素的右侧。

 插入排序

思想：

逐步构建有序序列插入排序通过将待排序的数组分为已排序和未排序两部分，每次从未排序的部分中取出一个元素，插入到已排序部分的适当位置，从而使得已排序部分保持有序状态。

逐元素插入它的具体过程是：从数组第二个元素开始，依次将每个元素与前面的已排序部分进行比较，找出合适的位置，然后将后面的元素依次后移，为新元素腾出空间，最后将该元素放入空出的位置。

时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
      最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1) 

public class InsertSort {
    public static void insertSort(int[] arr, int n){
        int j,tmp;//定义tmp变量暂存要插入的元素
        for(int i=1;i<n;i++){//i是将数组从头遍历到为，寻找要插入的元素
            if (arr[i] < arr[i-1]){//判断是否比前一个小
                tmp = arr[i];//如果比前一个小，就是要插入的元素
                for(j=i-1;j>=0 && tmp<arr[j];j--){//利用j遍历已经有序的数组，将大于该插入元素的数据依次后移
                    arr[j+1] = arr[j];//后移
                }
                arr[j+1] = tmp;//后移完成后再插入
            }
        }

    }
    public static void main(String[] args) {
        int []arr={2,5,8,3,6,9,1,4,7};
        insertSort(arr,arr.length);
        for(int i = 0 ;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
}

冒泡排序

基本思想是：通过相邻元素之间的比较和交换，把每一对相邻元素中较小的元素“浮”到前面，较大的元素“沉”到后面。

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
   ！！要注意的一个点就是j的判断条件应该是j<arr.length-i-1，减i是为了每轮寻找出最大的那个就不用再比较了，-1是为了防止第一次循环遍历时数组越界，因为下标从0开始

时间复杂度：最坏情况：O(N^2)
      最好情况：O(N)
空间复杂度：O(1) 

public class BubbleSort {
    public static void bubbleSort(int []arr){
            for(int i=0;i<arr.length-1;i++){//外层循环控制排序的趟数，最差为O(n),也就是n趟
                for (int j=0;j< arr.length-i-1;j++){//内层循环控制比较的元素，挨个遍历，每一个循环都会找到最大的一个，然后让j的遍历减少一次
                if(arr[j]>arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
            System.out.println(java.util.Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[]arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        bubbleSort(arr);
        System.out.println(java.util.Arrays.toString(arr));
    }
}

选择排序

基本思路是：在待排序的序列中反复找到最小（或最大）的元素，将其放到序列的起始位置，然后再对剩余的部分重复同样的操作，从而逐步构建出排序好的序列。

有几个地方需要注意，只需要额外定义一个在循环内最小值的下表和用于对换的tmp即可

• 初始状态：假设有一个包含 n 个元素的数组，未排序的部分为整个数组，有序的部分为空。
• 第一趟排序：在整个数组中查找最小的元素，然后将该元素与数组第一个元素交换。此时，数组的第一个位置为最小元素，有序部分增加一个元素。
• 第二趟排序：从剩余的 n-1 个未排序元素中查找最小元素，并将其与未排序序列的首位元素交换。这样，有序序列长度增加到2。
• 依次类推：重复上述过程，对于第 i 趟排序，从剩余的 n-i 个元素中选取最小元素，并交换到位置 i（假设数组下标从0开始）。当只剩下一个元素时，排序完成。

时间复杂度：最坏情况：O(N^2)
      最好情况：O(N^2)
空间复杂度：O(1) 

import java.util.Arrays;

public class SelectSort {
    public static void ss(int []arr){
        int minindex,tmp;
        for(int i=0;i<arr.length;i++){
            minindex = i;//刚上来将第一个数据作为最小值的下表索引，然后在内层循环中遍历找到更小的
            int j;//在外层定义j，是为了方便在内层找到最小值之后，在外层进行互换
            for(j=i+1;j<arr.length;j++){
                if(arr[minindex] > arr[j]){
                    minindex = j;//找到后，只需要更新最小值的下表索引即可
                }
            }
            tmp = arr[minindex];
            arr[minindex] = arr[i];
            arr[i] = tmp;
            System.out.println(Arrays.toString(arr));
        }

    }
    public static void main(String[] args) {
        int[]arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        ss(arr);
        System.out.println(Arrays.toString(arr));
    }
}

希尔排序

希尔排序（Shell Sort）是一种改进的插入排序算法，它的基本思想是先将整个待排序的记录序列分割成若干子序列分别进行直接插入排序，然后逐步缩小子序列之间的间隔，最后进行一次标准的插入排序。这样做的目的是使得序列中“较远距离”的元素可以提前移动到接近最终位置，从而减少后续插入排序中元素移动的次数，提高整体排序效率。

• 分组插入排序：希尔排序先根据一个步长（也称为增量）将数据划分为多个子序列。每个子序列由距离为步长的元素组成。对每个子序列使用插入排序进行排序。
• 逐步缩小增量：排序完成一轮后，缩小增量，通常的做法是逐步将步长减半（例如：n/2, n/4, …, 1）。当步长缩小到1时，整个数组已经基本有序，最后一遍插入排序的效率会很高。
• 最终有序：当增量为1时，所有元素都在同一个序列内，执行标准的插入排序便可以得到最终排序结果。

public class ShellSort {

    // 希尔排序算法实现
    public static void shellSort(int[] arr) {
        int n = arr.length;
        // 初始步长设置为数组长度的一半
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 从 gap 开始对整个数组进行插入排序
            for (int i = gap; i < n; i++) {
                int temp = arr[i];   // 保存当前元素
                int j = i;
                // 对间隔为 gap 的元素序列进行直接插入排序
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
            // 每次排序后可以打印数组状态，便于观察排序过程
            System.out.println("gap = " + gap + "时的数组状态：" + Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[] arr = {23, 45, 1, 3, 12, 8, 34, 19};
        System.out.println("初始数组：" + Arrays.toString(arr));
        shellSort(arr);
        System.out.println("排序后的数组：" + Arrays.toString(arr));
    }
}