说到排序算法，伙伴们必定很熟悉，包含在做算法题的时候，许多时候是需求将数组排序，然后求得终究的结果，那么此刻咱们就会考虑算法完结的时刻复杂度以及空间复杂度，接下来我会介绍常见的排序算法。
1 冒泡排序
思维
遍历数组中的元素，每轮拿到数组中最大的值，放在数组后面的方位，直到排序完结。
完结
/**
* 冒泡排序
*
* @param arr 无序数组
* @return 有序数组
*/
public static int[] BubbleSort(int[] arr) {
if (arr == null || arr.length < 1) {
return arr;
}
for (int i = 0; i < arr.length; i ) {
//外层控制遍历的次数
for (int j = 0; j < arr.length - i - 1; j ) {
if (arr[j] > arr[j 1]) {
swap(arr,j,j 1);
}
}
}
return arr;
}
经过两个for循环，其间外层的循环用于控制遍历的轮数，内层的循环用于比较巨细，然后交流方位，总是把大的数字往后放，当一轮遍历完结之后，数组中最大的数字放在末尾，此刻内层的循环将缩小查找规模（由外层循环决议），直到遍历完结。
时刻复杂度和空间复杂度
时刻复杂度O(n^2)
空间复杂度O(1)
2 挑选排序
思维
每次遍历悉数的元素，找到数组中最小值的索引，将其放在数组前面的方位，直到遍历完结悉数的元素。
完结
public static int[] SelectSort(int[] arr){
for (int i = 0;i<arr.length;i ){
int index = i;
for (int j = i;j<arr.length;j ){
if(arr[j] < arr[index]){
index = j;
}
}
//交流方位
if (index !=i){
swap(arr,i,index);
}
}
return arr;
}
经过两个for循环，外层循环控制索引的方位，内层循环用于比较巨细，每次默认最小值是外层循环的索引方位，内部循环判别假设有最小的值，那么就更新index的值；
当遍历完结之后，交流方位，有一个小优化，假设后面没有比当时元素更小的值，可以不交流方位，持续下一次遍历。
时刻复杂度和空间复杂度
时刻复杂度O(n^2)
空间复杂度O(1)
3 插入排序
思维
遍历整个数组，每个元素需求判别与前面元素的巨细，假设比前面的元素小，就交流方位。
完结
public static int[] InsertSort(int[] arr){
for (int i = 0;i<arr.length;i ){
int j = i;
while (j > 0){
if (arr[j] < arr[j-1]){
swap(arr,j,j-1);
}
j--;
}
}
return arr;
}
时刻复杂度和空间复杂度
时刻复杂度O(n^2)
空间复杂度O(1)
4 归并排序
思维
归并排序的思维其实便是两个有序的数组，经过两个指针指向两个数组的头部，顺次比较数组中每一个元素，终究合并成一个有序数组。归并的思维在许多算法题中也有表现，链表、数组中涉及到排序的问题。
完结
首要关于数组中每个独自的元素来说，便是有序的，在遍历的进程中，拆分最小颗粒度，由小的有序数组合并成大的有序数组。
public static int[] MergeSort(int[] arr) {
process(arr, 0, arr.length - 1);
return arr;
}
private static void process(int[] arr, int left, int right) {
if (left == right) {
return;
}
//将数组分红两份
int middle = (right left) / 2;
process(arr, left, middle);
process(arr, middle 1, right);
merge(arr,left,middle,right);
}
private static void merge(int[] arr,int left,int middle,int right) {
int[] help = new int[right - left 1];
int p1 = left;
int p2 = middle 1;
int h1 = 0;
while (p1 <= middle && p2 <= right) {
if (arr[p1] < arr[p2]) {
help[h1] = arr[p1];
p1 ;
} else {
help[h1] = arr[p2];
p2 ;
}
h1 ;
}
if (p1 <= middle) {
for (int i = p1; i <= middle; i ) {
help[h1] = arr[p1];
h1 ;
}
}
if (p2 <= right) {
for (int i = p2; i <= right; i ) {
help[h1] = arr[p2];
h1 ;
}
}
for (int i = 0;i<help.length;i ){
arr[left i] = help[i];
}
}
5 快速排序
思维
快速排序其实是“国旗”问题的延伸，给定一个基准值，让一个数组根据此基准值区分，左面均小于基准值，右边均大于基准值，然后经过递归完结整个数组的排序。
荷兰国旗问题
给定一个数组和一个基准值，让小于基准值的数字在左面，大于基准值的数字在右边，不要求左右两边是排序的。
思路
界说一个鸿沟区间，界说一个指针指向数组的第一个方位，主要分为以下几个case
- case1：当时数值假设小于基准值，那么就与鸿沟的下一个方位的元素互换方位，一起鸿沟值 ，指针 ；
- case2：当时数值假设大于基准值，那么指针 。
完结
public static int[] Solution(int[] arr, int num) {
int i = 0;
//鸿沟
int less = -1;
while (i < arr.length) {
if (arr[i] <= num) {
//当时值与鸿沟的下一个元素交流
swap(arr, i, less);
}
i ;
}
return arr;
}
前面咱们说到了，在分组的进程中，咱们不要求有序，只要小于基准值的就放在左面，大于基准值的放在右边，此刻这个问题的升级版便是，闻名的荷兰国旗问题，将数组分为3份，左面小于基准值，中心等于基准值，右边大于基准值。
此刻界说两个鸿沟，左面界是小于基准值的区域，右鸿沟是大于基准值的区域，一起两边推，终究中心的区域便是等于基准值的区域，因而会有以下case：
- case1：假设当时值小于基准值，那么当时值与左面界的下个元素做交流；左面界 ，i ；
- case2：假设当时值等于基准值，i ;
- case3：假设当时值大于基准值，那么当时值与有鸿沟的前一个元素做交流；有鸿沟–，i不动，为啥不动，因为换过来的值可能射中其间某个case，还需求判别。
public static int[] Solution2(int[] arr, int num) {
int i = 0;
//左面界
int less = -1;
//有鸿沟
int more = arr.length;
while (i < more) {
if (arr[i] <= num) {
//当时值与鸿沟的下一个元素交流
swap(arr, i, less);
i ;
} else if (arr[i] == num) {
i ;
} else {
//当时值大于基准值
swap(arr, --more, i);
}
}
return arr;
}
快速排序1.0
当你理解了”荷兰国旗”的原理之后，就会很快理解快速排序的真理。其实快速排序1.0的原理便是如下图所示：
一次partition的进程便是，取数组最终一个元素作为基准值，将数组分为大于基准值和小于基准值的部分，然后将基准值与大于基准值部分的第一个元素交流。此刻基准值一定是在有序数组中的方位
随后在大于基准值和小于基准值的部分别离进行partition的操作，终究完结排序。
这个思维与荷兰国旗的初始版别共同，基准值需求做一次替换，然后定位到有序数组的方位。
快速排序2.0
快速排序2.0则是根据荷兰国旗的升级版，在partition的进程中，就完结分组（>num 、=num、<num），此刻基准值就现已找到了在有序数组的方位，然后在 > num 和 < num的分组中别离进行partition。
public static int[] QuickSort_2(int[] arr) {
return QuickSortInner(arr, 0, arr.length - 1);
}
private static int[] QuickSortInner(int[] arr, int left, int right) {
if (left < right) {
int pos = partition(arr, left, right);
QuickSortInner(arr, left, pos - 1);
QuickSortInner(arr, pos 1, right);
}
return arr;
}
/**
* 回来基准值的方位
*
* @param arr 整个数组
* @param left 需求排序的左面方位
* @param right 需求排序的右边方位
*/
public static int partition(int[] arr, int left, int right) {
//基准值
int num = arr[right];
int i = left;
//左面界
int less = left - 1;
//有鸿沟
int more = right 1;
while (i < more) {
if (arr[i] < num) {
swap(arr, less, i);
i ;
} else if (arr[i] == num) {
i ;
} else {
swap(arr, --more, i);
}
}
return less 1;
}
时刻复杂度和空间复杂度
快速排序其实仍是有3.0版别的，不再以数组的最终一个数字为基准值，而是选用随机数的方法，可是快速排序最差的状况，时刻复杂度为O(n^2)，均匀下来为O(nlogn)，空间复杂度为O(logn)。
6 堆排序
堆排序，其实便是用数组完结彻底二叉树，什么是彻底二叉树？
看上图，假设一棵二叉树的所有节点均存在左右节点，或许从左往右有排满的趋势，那么就认为是彻底二叉树，例如倒数第二棵二叉树，虽然第三层没有满，可是从左往右看是接连的，这便是有排满的趋势，所以是彻底二叉树；可是倒数第一棵二叉树，第三层不是接连的，因而不是彻底二叉树。
而堆则是一种比较特别的彻底二叉树，分为大根堆和小根堆，如下图所示。
大根堆指的是恣意一棵子树，头结点都是这棵树的最大值；小根堆指的是恣意一棵子树，头结点都是这棵树的最小值。
思路
前面咱们主要是讲解了彻底二叉树的一些基础知识，因为数组是接连的，所以构建的彻底二叉树天然也得是接连的，所以关于如何经过索引找到其左节点、右节点、父节点，记住公式：
所以假设要构建一个大根堆，那么在遍历到某个元素时，与自己的父节点比较，假设比自己的父节点小，那么就持续下个元素的比较；假设比自己的父节点值要大，那么就交流，交流完结之后，假设还有父节点就需求一向比较，一向往上窜。
完结大根堆
首要第一步，遍历数组中的元素，构建彻底二叉树，可是要符合大根堆的条件：
当顺次遍历数组中的元素时，开端构建彻底二叉树（脑海中），当遍历到数字8时，此刻二叉树不符合大根堆的条件，此刻需求交流与父节点的方位，此刻index = 3，其父节点的方位为(index-1)/2，交流完结之后，发现仍是不满足大根堆的条件，因而持续往上找，直到符合条件。
交流完结之后，持续遍历，遇到不满足大根堆的条件就进行转换，直到遍历完结，这个进程叫做HeapInsert.
/**
* Heap Insert操作
*
* @param arr 待排序的数组
* @param index 当时遍历的元素
*/
private static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
//当时元素，比父节点要大
swap(arr, index, (index - 1) / 2);
index = (index-1) / 2;
}
}
此刻数组中的第一个节点为最大值，假设要获取这个数组中的最大值，那么直接回来数组中第0个元素即可。
假设删去最大值，还要保证是一个最大堆的条件，那么首要把数组中最终一个元素替换到首位。
在替换完结之后，可能会呈现不满足大根堆的条件，此刻需求从头结点开端，比较左右孩子，拿到最大的值，与头结点替换；替换完结后，此刻头结点到了子节点的方位，还需求持续判别它的左右孩子是否满足大根堆的条件，这是heapify的进程。
/**
* Heapif操作
*
* @param arr 待排序的数组
* @param index 头结点的索引
*/
private static void heapify(int[] arr, int heap_size, int index) {
int left = 2 * index 1;
while (left < heap_size) {
//根节点
int head = arr[index];
//两个孩子的最大节点
int largestChild = left;
//先比较两个孩子
//假设有右孩子，而且右孩子比左孩子大，那么两个孩子的最大节点便是右孩子
//不然便是左孩子
if (left 1 < heap_size && arr[left 1] > arr[left]) {
largestChild = left 1;
}
if (head < arr[largestChild]) {
//交流
swap(arr, index, largestChild);
}
index = largestChild;
left = 2 * index 1;
}
}
如此操作之后，所有最大堆的根节点都被放在的数组的后面，而且仍是排序的，终究拿到的数组便是排序完结的。
public static int[] HeapSort(int[] arr) {
int heap_size = 0;
while (heap_size < arr.length) {
heapInsert(arr, heap_size);
heap_size ;
}
while (heap_size > 0) {
heap_size--;
swap(arr, heap_size, 0);
heapify(arr, heap_size, 0);
}
return arr;
}
时刻复杂度和空间复杂度
时刻复杂度O(nlogn)
空间复杂度O(1)
7 计数排序
前面咱们见到的排序算法，均为数字之间的比较，经过比较巨细交流次序然后完结数组的排序，而计数排序和桶排序，则是在空间上的计数，然后完结排序规矩的复原。
思路
举个例子，有一组职工的年纪数组，咱们知道职工的年纪是在[16-100]这个区间内的，超过或许低于这个区间咱们认为是不合理的，因而咱们可以创立一个数组长度为100的空数组，遍历一次数组，那么在空数组中便可以得到每个数字的计数。
例如：16呈现2次，20呈现3次，21呈现1次，35呈现1次，40呈现2次，那么终究的排序便是[16,16,20,20,20,35,40,40].
所以，此类排序使用的场景有限：假设数组中的元素便是随机数，在-10^5<= num <= 10^5 之间，显然就不能使用这种计数的方法了。
完结
public static int[] CountSort(int[] arr) {
int max = getMaxValue(arr);
int[] res = new int[max 1];
for (int i = 0; i < arr.length; i ) {
res[arr[i]] ;
}
int index = 0;
for (int i = 0; i < res.length; i ) {
while (res[i] > 0) {
arr[index] = i;
index ;
res[i]--;
}
}
return arr;
}
private static int getMaxValue(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i ) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
8 基数排序 & 桶排序
桶排序或许基数排序，是根据计数排序的升级版别，因为计数排序存在的弊端在于，必需要直到数组中的最大值，决议映射数组的长度。
未完待续~
