1 冒泡算法
冒泡算法是一个很简单的排序算法，通过每次相邻的两个元素进行比较，如果前面的比后面的大就交换两个元素（也可以比较是否是小，取决于是升序排序还是降序排序），可以理解的是，通过n-1次比较就排序排好了，同时也可以发现不管初始序列的状态如何，冒泡排序的时间复杂都是O(n^2).
1.1 算法过程描述
1.从第一个开始，比较相邻的两个元素，如果第一个比第二大，则交换
2.对每一相邻元素做相同的工作，从开始第一对到结尾的最后一对，这样第一次就将最大的数放到了数组结尾了
3.针对所有的元素重复以上步骤
4.重复步骤1~3，直到排序完成
1.2 动图演示
1.3 代码实现
public static void bubbleSort(int[] nums) {
/**
* 养成良好的习惯，一定要对程序的鲁棒性进行判断，处理异常输入的能力
**/
if (nums == null || nums.length <= 0) {
return;
}
int length = nums.length;
// 排序n - 1次就完成了排序了
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - 1 - i; j++) {
//如果前面比后面大，就开始交换
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}
2 选择排序
选择排序是一种简单的排序算法，每次在未排序的序列中选出最小（大）的一个元素，存放到序列的起始位置，然后再从剩余未排序的元素中继续寻找最小（大）元素，放到已排序序列的末尾，以此类推，直到所有元素均排序完成。
2.1 算法描述过程
1.初始状态：无序区为R[1...n],有序区为空
2.第i趟排序（i=1,2,3...n-1）开始时，当前有序区和无序区分别为R[1...i-1]和R(i..n)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n]分别变为记录个数，增加1个的新有序区和记录个数减少1个的新无序区；
3.n-1趟结束，数组有序化了
2.2 动图演示
2.3 代码实现
public static void selectSort(int[] nums) {
if (nums == null || nums.length <= 0) {
return;
}
int minIndex, temp, length = nums.length;
for (int i = 0; i < length - 1; i++) {
// 从第i个开始，先标记最开始这个为最小的数
minIndex = i;
for (int j = i + 1; j < length; j++) {
if (nums[j] < nums[minIndex]) {
// 如果后面出现了更小的数，则记下该数的下标，因为后面需要将最小的数放到最前面
minIndex = j;
}
}
temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
}
3 插入排序
插入排序是一种相对也比较简单直观的排序算法，工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
3.1 算法描述
1.从第一个元素，该元素可以认为已经被排序；
2.取出下一个元素，在已经排序的元素中从后向前扫描；
3.如果该元素（已排序的元素）大于新元素，将该元素移到下一位置；
4.重复步骤3，直到找到已排序的元素小于或等于新元素的位置；
5.将新元素插入到该位置;
6.重复步骤2~5.
3.2 动图演示
3.3 代码实现
public static void inserSort(int[] nums) {
if (nums == null || nums.length <= 0) {
return;
}
int length = nums.length;
for (int i = 1; i < length; i++) {
// 用来记录比当前元素小或者等于当前元素的那个位置，则当前元素就应该插入到该元素后面一个
preIndex = i - 1;
// 记录当前需要插入的元素
current = nums[i];
while (preIndex >= 0 && nus[preIndex] > current) {
// 只要preIndex指向的元素值大于当前元素，则就应该将该元素一直往后移
nums[preIndex + 1] = nus[preIndex];
preIndex--;
}
// 将需要插入的元素插入到属于它的位置
nums[preIndex + 1] = current;
}
}
4 希尔排序
希尔排序是第一个突破O(n^2)的排序算法，是简单插入排序的改进版，它与插入排序不同之处在于，它会优先比较距离较远的元素。希尔排序又叫作缩小增量排序。
4.1 算法描述
先将整个待排序的序列分割为若干子序列分别进行直接插入排序，具体算法描述：
1.选择一个增量序列t1,t2,....,tk,其中ti>tj，tk=1；
2.按增量序列个数k，对序列进行k趟排序；
3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
4.2 动图演示
4.3 代码实现
public static void shellSort(int[] nums) {
if (nums == null || nums.length <= 0) {
return;
}
int length = nums.length;
// 一开始的增量一般设置为length/2，然后一直gap/2
for (int gap = length / 2; gap > 0; gap = gap / 2) {
for (int i = gap; i < length; i++) {
//先把分割好的第一个拿到，开始处理它的前面的相隔gap个距离的数字
int j = i;
int temp = nums[j];
// 如果当前元素比它前面的那个相距gap的那个元素小时
if (nums[j] < nums[j - gap]) {
//一直往前找，如果一直小，就一直往前找
while (j - gap >= 0 && temp < nums[j - gap]) {
nums[j] = nums[j - gap];
j -= gap;
}
// 找到刚开始那个元素的位置，然后插进去
nums[j] = temp;
}
}
}
}
5 归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序，若将两个有序表合并成一个有序表，称为2-路归并。
5.1 算法描述
1.把长度为n的输入序列分成两个长度为n/2的子序列；
2.对这两个子序列分别采用归并排序
3.将两个排序好子序列合并成一个最终的排序序列。
5.2 动图演示
5.3 代码实现
public static void mergeSort(int[] nums, int left, int right) {
if (nums == null || nums.length <= 0 || left > right) {
return;
}
int mid = (left + right) >> 1;
// 递归排序左边
mergeSort(nums, left, mid);
// 递归排序右边
mergeSort(nums, mid + 1, right);
// 合并排完序的两边的序列
merge(nums, left, mid, right);
}
public static void merge(int[] nums, int left, int mid, int right) {
// 新建一个数组用来存储临时合并的序列
int[] temp = new int[nums.length];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
// 谁小(如果是逆序，也就可以大)谁先进序列
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 如果还剩下，直接全进去
while (i <= mid) {
temp[k++] = nums[i++];
}
// 如果还剩下，直接全进去
while (j <= right) {
temp[k++] = nums[j++];
}
// 将合并好的数据拷贝到原来的序列当中
for (i = 0; i < k; i++) {
nums[left + i] = temp[i];
}
}
6 快速排序
基本思想：通过一趟排序将待排记录分割成独立的部分，其中一部分记录的关键字均比另一部分小，则可分别对这两部分记录进行排序，以达到整个序列有序。
6.1 算法描述
快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体描述如下：
1.从数列中挑出一个元素，称为基准；
2.重新排序数列，所有元素比基准小的摆放在基准前面，所有元素比基准值大的放在基准的后面，在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；
3.递归地把小于基准值元素地子数列和大于基准地元素地子序列排序。
6.2 动图演示
6.3 代码实现
public static void quickSort(int[] nums, int left, int right) {
int i = left, j = right, base = nums[left];
// 开始从两边开始遍历
while(i < j) {
// 先从右边开始往前遍历，知道发现比base小的值，停下来
while (nums[j] >= base && j > i) {
j--;
}
// 这个条件很必须
if (j > i) {
// 将前面发现地比base小的值与i指向的值交换
nums[i] = nums[j];
// 换个方向，从左边开始往后面遍历，
i++;
// 直到找到比base大的值与此时的j交换
while (nums[i] <= base && j > i) {
i++;
}
if (i < j) {
nums[j] = nums[i];
j--;
}
}
}
nums[i] = base;
// 开始递归排序左边的序列
if (left < (i - 1)) {
quickSort(nums, left, i - 1);
}
// 开始递归排序右边的序列
if ((j + 1) < right) {
quickSort(nums, j + 1, right);
}
}
快排的非递归实现，也可以看看
// 这个partition方法就是为了找出一个序列中的中间值，这个方法在很多算法中也有很大的使用率，是一个很重的方法
private int partition(int[] numbers, int left, int right) {
int i = left, j = right, base = numbers[left];
while (i < j) {
while (i < j && numbers[j] > base) {
j--;
}
numbers[i] = numbers[j];
if (i < j) {
i++;
while (i < j && numbers[i] < base) {
i++;
}
numbers[j] = numbers[i];
}
}
numbers[i] = base;
// 返回中间值的下标
return i;
}
private void quickSort(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return;
}
// 其实操作系统实现递归也是在用栈实现，所以咱们这里实现非递归的快排肯定需要使用到stack
Stack<Integer> stack = new Stack<>();
int left = 0, right = numbers.length - 1;
int mid = partition(numbers, left, right);
// 这里将以mid分割的两个序列的头尾分别入栈，因为我们等下分别用到这两份头尾用来处理
if (mid - 1 > left) {
stack.push(left);
stack.push(mid - 1);
}
if (mid + 1 < right) {
stack.push(mid + 1);
stack.push(right);
}
while (!stack.isEmpty()) {
// 第一个子序列的首尾
int high = stack.pop();
int low = stack.pop();
//然后使用相同的方法，获取这一个序列的中间值
int middle = partition(numbers, low, high);
//然后将其分割好的序列首尾入栈（前提是可以入栈）
if (middle - 1 > low) {
stack.push(low);
stack.push(middle - 1);
}
if (middle + 1 < high) {
stack.push(middle + 1);
stack.push(high);
}
}
}
7 堆排序
堆排序是指利用堆这种数据结构设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
7.1 算法描述
1.将初始待排序关键字序列（R1, R2, R3...Rn）构建成大顶堆，此堆为初始的无序区；
2.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,R3...Rn-1)和新的有序区(Rn),且满足R[1,2,3...n-1]<=R[n];
3.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2...Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2...Rn-1)和新的有序区(Rn-1,Rn).不断重复此过程直到有序区的元素个数为n-1.
7.2 动图演示
7.3 代码实现
private void heapSort(int[] numbers) {
if (numbers == null || numbers.length <= 0) {
return;
}
// 从中间的值，其实就是倒数第二层的节点开始调整堆，使其满足堆的性质
for (int i = numbers.length/2 - 1; i >= 0; i--) {
buildBigHeap(numbers, i, numbers.length);
}
// 这里进行每一次建堆完成之后的交换工作，循环就行n - 1次就是排序完成了
for (int j = numbers.length - 1; j > 0; j--) {
int temp = numbers[j];
numbers[j] = numbers[0];
numbers[0] = temp;
//每次交换完成之后需要重新调整堆
buildBigHeap(numbers, 0, j);
}
}
// 对某一个有子节点的节点进行堆调整
private void buildBigHeap(int[] numbers, int current, int length) {
int temp = numbers[current];
// 从需要调整的节点自己开始，其左子节点的下标为2 * current + 1
for (int k = 2 * current + 1; k < length; k = 2 * k + 1) {
// 找到其右子节点并跟左子节点比较，因为堆父节点应该是最大的
if (k + 1 < length && numbers[k] < numbers[k + 1]) {
k++;
}
// 把最大的赋给父节点
if (numbers[k] > temp) {
numbers[current] = numbers[k];
current = k;
}else {
break;
}
}
numbers[current] = temp;
}
总结
本文有很多是借鉴于十大经典排序算法（动图演示）
同时，我们还需要直到每个算法的时间复杂度和空间复杂度一些问题
