冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

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


    // 只需要排 nums.length - 1 次（而不是 nums.length 次）
    for (int i = 0; i < nums.length - 1; i ++) {
        // flag 表示该次冒泡排序是否存在交换操作，如果没有，说明数组已经全局有序了
        boolean flag = false;

        for (int j = 0; j < nums.length - 1; j ++) {
            if (nums[j] > nums[j + 1]) {
                flag = true;

                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }

        if (!flag) {
            break;
        }
    }

}

平均时间复杂度 O(N^2)

最好情况（全局有序）：O(N)

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

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


    // 只需要排 nums.length - 1 次（而不是 nums.length 次）
    for (int i = 0; i < nums.length - 1; i ++) {
        // 从前往后找到比 nums[i] 小的最小数
        int min = i;
        for (int j = i + 1; j < nums.length; j ++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }

        if (min != i) {
            int temp = nums[i];
            nums[i] = nums[min];
            nums[min] = temp;
        }
    }

}

选择排序无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

快速排序

快速排序是一种非常高效的算法，从其名字可以看出这种排序算法最大的特点就是快。当表现良好时，快速排序的速度比其他主要对手（如归并排序）快2～3倍。

快速排序的基本思想是分治法，排序过程如下：

• 在输入数组中随机选取一个元素作为中间值（pivot），然后对数组进行分区（partition），使所有比中间值小的数据移到数组的左边，所有比中间值大的数据移到数组的右边。
• 接下来对中间值左右两侧的子数组用相同的步骤排序，直到子数组中只有一个数字为止。

这个过程可以用如下所示的递归代码实现：

// sort nums[left, right]
private void quickSort(int[] nums, int left, int right) {
    if (left >= right) {
        return ;
    }
	
    // 选取基准元素下标
    int pivot = partition(nums, left, right);
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}

上述算法中的 Partition 以一个确定的基准元素对数组进行划分，将该基准元素放在最终所在的位置（使所有比基准元素小的数据移到数组的左边，所有比基准元素大的数据移到数组的右边）：

// 选取基准元素下标
private int partition(int[] nums, int left, int right) {
    if (left == right) {
        return left;
    }

    // 一般都是用最左元素作基准元素
    int pivot = left;
    while (left < right) {
        while (left < right && nums[right] >= nums[pivot]) {
            right --;
        }
        while (left < right && nums[left] <= nums[pivot]) {
            left ++;
        }
        // 交换
        if (left < right) {
            swap(nums, left, right);
        }
    }
    // 将基准数放到最终的位置（基准数归位）
    swap(nums, pivot, left);

    return pivot;
}

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

注意下图中框出来的符号：

我们可以引入随机化来加速快排的过程。所谓随机化就是随机 pivot 的取值（并非固定的最左边的数），可以在循环一开始的时候，随机交换第 1 个元素（最左边的元素）与它后面的任意 1 个元素的位置：

int index = left + new Random().nextInt(right - left + 1);
swap(nums, left, index);
int pivot = left;

快排在最坏情况下时间复杂度为 O(n^2)，最好情况下为 O(nlogn)，平均情况下也是 O(nlogn)

快速排序中的 partition 函数经常被用来选择数组中第k大的数字，这是一道非常经典的算法面试题

计数排序

计数排序是一种线性时间的整数排序算法。如果数组的长度为n，整数范围（数组中最大整数与最小整数的差值）为k，对于 k 远小于 n 的场景（如对某公司所有员工的年龄排序），那么计数排序的时间复杂度优于其他基于比较的排序算法（如归并排序、快速排序等）。

⭐ 计数排序的基本思想是先统计数组中每个整数在数组中出现的次数，然后按照从小到大的顺序将每个整数按照它出现的次数填到数组中。

例如，如果输入整数数组[2，3，4，2，3，2，1]，扫描一次整个数组就能知道数组中1出现了1次，2出现了3次，3出现了2次，4出现了1次，于是先后在数组中填入 1 个1、3 个 2、2 个 3及 1 个4，就可以得到排序后的数组 [1，2，2，2，3，3，4]。

public int[] sortArray(int[] nums) {
    // 数组中最大整数与最小整数（用来计算整数范围）
    int min = Integer.MAX_VALUE;    
    int max = Integer.MIN_VALUE;    
    for (int num : nums) { 
        min = Math.min(min, num);
        max = Math.max(max, num);    
    }
    // 根据整数范围 max - min 来构建数组 counts[]
    // 统计数组中数字出现的次数 count[num - min] 对应 num 出现的次数
    int[] counts = new int[max - min + 1];
    for (int num : nums) {        
        counts[num - min]++;    
    }    
    
    int i = 0;
    for (int num = min; num <= max; num ++) {        
        while (counts[num - min] > 0) { 
            // 原地修改 nums 数组
            nums[i ++] = num;
            // num 对应的出现次数 --
            counts[num - min] --;
        }    
    }    
    return nums;
}

上述代码先扫描数组nums得到整数的最大值和最小值，并根据整数范围创建辅助数组counts。数组counts用来统计每个整数出现的次数。

如果数组的长度为 n（第一个循环时间复杂度 O(n)），整数的范围为 k（第一个循环时间复杂度 O(k)），那么计数排序的时间复杂度就是 。由于需要创建一个长度为 的辅助数组counts，因此空间复杂度为 。

• 当 k 较小时，无论从时间复杂度还是空间复杂度来看计数排序都是非常高效的算法。
• 当k很大时，计数排序可能就不如其他排序算法（如快速排序、归并排序）高效。

归并排序

归并排序也是一种基于分治法的排序算法。为了排序长度为n的数组，需要先排序两个长度为n/2的子数组，然后合并这两个排序的子数组，于是整个数组也就排序完毕。

归并排序可以用迭代代码实现。例如，输入一个长度为8的数组[4，1，5，6，2，7，8，3]，可以先合并相邻的长度为1的子数组得到4个排序的长度为2的子数组，然后合并相邻的长度为2的子数组得到2个排序的长度为4的子数组，最后合并相邻的长度为4的子数组，此时整个数组排序完毕

class Solution {

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

    // 归并排序 nums[l, r]
    public void mergeSort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        
        int mid = l + ((l + r) >> 1);
        // 1. 归并排序 nums[l, mid];
        mergeSort(nums, l, mid);
        // 2. 归并排序 nums[mid + 1, r];
        mergeSort(nums, mid + 1, r);
        // 3. merge nums[left, mid] 和 nums[mid + 1, right] 两个数组
        merge(nums, l, r);
    }

    private void merge(int[] nums, int l, int r) {
        // temp 是汇总 2 个有序区的临时区域
        int[] temp = new int[r - l + 1];
        // tmp 下标
        int index = 0;
		
        int mid = l + ((r - l) >> 1);
        int i = l;
        int j = mid + 1;	
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                temp[index ++] = nums[i ++];
            } else {
                temp[index ++] = nums[j ++];
            }
        }
        while (i <= mid) {
            temp[index ++] = nums[i ++];
        }
        while (j <= r) {
            temp[index ++] = nums[j ++];
        }
        
        // 将排序后的到数组 nums 中
        for (int k = 0; k < temp.length; k ++) {
            nums[l + k] = temp[k];
        }
    }
}

由于长度为 n 的数组每次都被分为两个长度为 n/2 的数组，因此不管输入什么样的数组，归并排序的时间复杂度都是 。归并排序需要创建一个长度为 n 的辅助数组。如果用递归实现归并排序，那么递归的调用栈需要 的空间。因此，归并排序的空间复杂度是 。

手写归并排序的代码本身就是很常见的面试题。因此，应深刻理解归并排序的过程，熟悉归并排序的迭代和递归的代码实现。同时，归并排序是应用分治法来解决问题的，类似的思路可以用来解决很多其他的问题