1.概述

2.时间复杂度O(n^2)

2.1 冒泡排序

原始版本：

public static void bubble(int[] arr){
    int n=arr.length;
    for(int i=0;i<n-1;i++){
        //总共要比较n-1轮
        for(int j=1;j<n-i;j++){
            //采用比较j和j-1，为了不越下界，从j=1开始，同时j的最大值受i的限制
            //如果采用比较j和j+1，则就是j=0；j<n-i-1
            if(arr[j]<arr[j-1]){
                Zswap.swap(arr,j,j-1);
            }
        }
    }
}
public class Zswap {
    public static void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}
public class ZwapMagic {
    public static void swap(int[] arr,int i,int j){
        /**
        使用按位异或来进行两数的交换
        面试的时候可能会考到
         */
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }
}

版本2.0

public static void bubbleSort(int[] arr) {
    // 初始时 swapped 为 true，否则排序过程无法启动
    boolean swapped = true;
    for (int i = 0; i < arr.length - 1; i++) {
        // 如果没有发生过交换，说明剩余部分已经有序，排序完成
        if (!swapped) break;
        // 设置 swapped 为 false，如果发生交换，则将其置为 true
        swapped = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 如果左边的数大于右边的数，则交换，保证右边的数字最大
                swap(arr, j, j + 1);
                // 表示发生了交换
                swapped = true;
            }
        }
    }
}
// 交换元素
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

2.0版本的最好时间复杂度为O(n)
即如果数组本身就是有序的话，此时只需要一轮就结束了

时间复杂度和空间复杂度
时间复杂度最坏：n-1,n-2,n-3…1
总和为（n-1+1)*(n-1)/2,故为O(n^2）
时间复杂度最好：n-1,即O(n),这个指的是2.0版本
空间复杂度：O(1)

2.2 选择排序

选择排序每次在比较当前轮次最小值的时候，
不是每次比较都交换，而是维护一个最小值的索引，到本轮比较结束时再交换

那怎么

3.时间复杂度O(nlogn)

3.1 堆排序

堆排序

堆排序中有一个不易理解的点是递归
就是当一个子节点与父节点进行交换之后，需要保证以新的子节点为根节点的子树为大顶堆
如果不这样最后的排序就会出错；（{2,4,3,5,1,7}演示一下如果不交换的话会出现3比4大的情况）
即只要发生了交换，就要递归确保交换后的子树依旧为大顶堆。

在介绍堆排序具体实现之前，我们先要了解完全二叉树的几个性质。将根节点的下标视为 0，则完全二叉树有如下性质：
对于完全二叉树中的第 i 个数，它的左子节点下标：left = 2i + 1
对于完全二叉树中的第 i 个数，它的右子节点下标：right = left + 1
对于有 n 个元素的完全二叉树(n≥2)(n≥2)，它的最后一个非叶子结点的下标：n/2 - 1

public static void heapSort(int[] arr) {
    // 构建初始大顶堆
    buildMaxHeap(arr);
    for (int i = arr.length - 1; i > 0; i--) {
        // 将最大值交换到数组最后
        swap(arr, 0, i);
        // 调整剩余数组，使其满足大顶堆
        maxHeapify(arr, 0, i);
    }
}
// 构建初始大顶堆
private static void buildMaxHeap(int[] arr) {
    // 从最后一个非叶子结点开始调整大顶堆，最后一个非叶子结点的下标就是 arr.length / 2-1
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, i, arr.length);
    }
}
// 调整大顶堆，第三个参数表示剩余未排序的数字的数量，也就是剩余堆的大小
private static void maxHeapify(int[] arr, int i, int heapSize) {
    // 左子结点下标
    int l = 2 * i + 1;
    // 右子结点下标
    int r = l + 1;
    // 记录根结点、左子树结点、右子树结点三者中的最大值下标
    int largest = i;
    // 与左子树结点比较
    if (l < heapSize && arr[l] > arr[largest]) {
        largest = l;
    }
    // 与右子树结点比较
    if (r < heapSize && arr[r] > arr[largest]) {
        largest = r;
    }
    if (largest != i) {
        // 将最大值交换为根结点
        swap(arr, i, largest);
        // 再次调整交换数字后的大顶堆
        maxHeapify(arr, largest, heapSize);
    }
}
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/sort-algorithms/eu7ux3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3.2 快速排序

public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int start, int end) {
    // 如果区域内的数字少于 2 个，退出递归
    if (start >= end) return;
    // 将数组分区，并获得中间值的下标
    int middle = partition(arr, start, end);
    // 对左边区域快速排序
    quickSort(arr, start, middle - 1);
    // 对右边区域快速排序
    quickSort(arr, middle + 1, end);
}
// 将 arr 从 start 到 end 分区，左边区域比基数小，右边区域比基数大，然后返回中间值的下标
public static int partition(int[] arr, int start, int end) {
    // 取第一个数为基数
    int pivot = arr[start];
    // 从第二个数开始分区
    int left = start + 1;
    // 右边界
    int right = end;
    // left、right 相遇时退出循环
    while (left < right) {
        // 找到第一个大于基数的位置
        while (left < right && arr[left] <= pivot) left++;
        // 交换这两个数，使得左边分区都小于或等于基数，右边分区大于或等于基数
        if (left != right) {
            exchange(arr, left, right);
            right--;
        }
    }
    // 如果 left 和 right 相等，单独比较 arr[right] 和 pivot
    // 当arr[right] > pivot时，为了保证返回的right的右边的值都大于right当前的值，right需要--
    if (left == right && arr[right] > pivot) right--;
    // 将基数和中间数交换
    if (right != start) exchange(arr, start, right);
    // 返回中间值的下标
    return right;
}
private static void exchange(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/sort-algorithms/eul7hm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

习题：

题中说必须在原数组上操作，不能拷贝额外的数组，Then元素交换；

数组变量作为形参是可以影响实参的，就跟引用一样；

递归的终止条件不一定非得用return，如果递归是有条件的，那么不满足条件递归自然就会终止，如堆排序和快速排序中的递归就是如此；

1.把数组排成最小的数

class Solution {
    public String minNumber(int[] nums) {
        bubble(nums);
        StringBuilder sb=new StringBuilder("");
        for(int i=0;i<nums.length;i++){
            sb.append(nums[i]);
        }
        return sb.toString();
    }
    public void bubble(int[] arr){
        int n=arr.length;
        for(int i=0;i<n-1;i++){
            for(int j=1;j<n-i;j++){
                if(((""+arr[j-1]+arr[j]).compareTo(""+arr[j]+arr[j-1]))>0){
                    int temp=arr[j-1];
                    arr[j-1]=arr[j];
                    arr[j]=temp;
                }
            }
        }
    }
}

原理就是将数字进行排序，
假设数组中a=3在b=30的左边，
如果ab的字符串330大于ba的字符串303
那么就需要交换ab的位置
定义完上面的排序规则后我们可以采用任意一个排序规则来进行升序排列即可

2.移动零（本题双指针的使用和元素交换很有学习意义）

class Solution {
    public void moveZeroes(int[] nums) {
        int left=0;
        int right=0;
        int n=nums.length;
        while(right<n){
            if(nums[right]!=0){
                swap(nums,left,right);
                left++;
            }
            right++;
        }
    }
    public void swap(int[] arr,int left,int right){
        int temp=arr[left];
        arr[left]=arr[right];
        arr[right]=temp;
    }
}

left指的是连续的0的左边第一个，
right的话要么时连续的0的右边第一个，要么是连续的0的右边第一个的再右边一个（此时不是0）
当right指向的不是0时，我们将最左边的0与该位置交换，就能得到另一块连续的0
此时left要向右移一位，指向新的连续的0的左边第一个
一直循环上述操作，知道right超过数组边界

Java

必备排序算法