升序排序为例
交换元素的通用代码：
/**
* 交换元素
* @param arr
* @param idx1
* @param idx2
*/
private void swap(int[] arr, int idx1, int idx2) {
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}一、交换排序——冒泡排序
冒泡排序：
相邻两个元素两两比较，若逆序则交换
每一轮会确定一个最大值到它最后的位置上,只需n-1轮排序
优化：如果某一轮排序从头至尾没有发生交换，说明已经有序，结束
/**
* 交换排序：稳定，O(n^2)
* 1. 冒泡排序：
* 相邻两个元素两两比较，若逆序则交换
* 每一轮会确定一个最大值到它最后的位置上,只需n-1轮排序
* 优化：如果某一轮排序从头至尾没有发生交换，说明已经有序，结束
* @param array 待排序列
*/
public void bubble_Sort(int[] array) {
int n = array.length;
for(int i = 0; i < n - 1; i++) { // n-1轮排序
boolean flag = true;
for (int j = 0; j < n - 1 -i; j++) { // 每轮会确定一个最值
if(array[j] > array[j + 1]) { // 逆序则交换
swap(array, j, j + 1);
flag = false; // 本轮发生了交换
}
}
if (flag) { // 提前结束
break;
}
}
}二、交换排序——快速排序
快速排序：不稳定，O(nlogn)
随机选出一个元素作为基准pivot，此处选第一个元素array[0]
从序列的两端开始探测，哨兵 i 从前向后找比pivot大的，哨兵 j 从后向前找比pivot小的，然后交换i和j指向的元素；每次都让哨兵j先动
直到哨兵相遇，交换相遇点和pivot
以pivot为基准前后分区，递归左右两个子序列
为什么每次要让哨兵j先动？因为pivot取在左侧
左侧哨兵i先动，i会找到第一个大于pivot的位置，但哨兵j可能会因为 i小于j 的限制而没有落在小于pivot的位置上，提前结束探测而与i相遇，此时交换，结果是错误的
/**
* 交换排序：
* 2. 快速排序：不稳定，O(nlogn)
* 随机选出一个元素作为基准pivot，此处选第一个元素array[0]
* 从序列的两端开始探测，哨兵 i 从前向后找比pivot大的，哨兵 j 从后向前找比pivot小的，然后交换i和j指向的元素；每次都让哨兵j先动
* 直到哨兵相遇，交换相遇点和pivot
* 以pivot为基准前后分区，递归左右两个子序列
*
* 为什么每次要让哨兵j先动？因为pivot取在左侧
* 左侧哨兵i先动，i会找到第一个大于pivot的位置，但哨兵j可能会因为 i小于j 的限制而没有落在小于pivot的位置上，提前结束探测而与i相遇，此时交换，结果是错误的
* @param array
*/
public void quick_Sort(int[] array, int low, int high) {
if (low >= high) {
return;
}
int pivot = array[low]; // 基准
int i = low; // 哨兵
int j = high;
while(i < j) {
// i < j 确保哨兵在相同处停下(i == j)，防止越界
while (array[j] >= pivot && i < j) { //从右往左找比基准值小的数
j--;
}
while (array[i] <= pivot && i < j) { //从左往右找比基准值大的数
i++;
}
if (i < j) {
swap(array, i, j);
}
}
array[low] = array[j]; // 交换基准与哨兵相遇处的元素
array[j] = pivot;
quick_Sort(array, low, j - 1);
quick_Sort(array, j + 1, high);
}三、插入排序——直接插入
直接插入：稳定，O(n^2)
将array[0]视为初始的有序表，从下一个元素开始，逐个插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表
双层循环：外层循环遍历除array[0]外的所有元素，内层循环对当前元有序表进行待插入位置查找(从后向前)，并进行移动
/**
* 插入排序
* 1. 直接插入：稳定，O(n^2)
* 将array[0]视为初始的有序表，从下一个元素开始，逐个插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表
* 双层循环：外层循环遍历除array[0]外的所有元素，内层循环对当前元有序表进行待插入位置查找(从后向前)，并进行移动
* @param array
*/
public void insert_Sort(int[] array) {
int n = array.length;
for(int i = 1; i < n; i++) {
for(int j = i; j >= 1; j--) {
if(array[j] < array[j - 1]) { // 从后向前比较，找到插入的位置
swap(array, j, j - 1);
}else { // 比有序表的最后一个元素都大，直接插在末尾
break;
}
}
}
}四、插入排序——希尔排序
希尔排序：不稳定，O(n^1.3)
直接插入的改进：分组，组内插入排序
根据增量对序列进行分组，在组内通过直接插入排序，每个组都排好序后，增量减半，再次分组排序，直到增量为1
/**
* 插入排序：
* 2. 希尔排序：不稳定，O(n^1.3)
* 直接插入的改进：分组，组内插入排序
* 根据增量对序列进行分组，在组内通过直接插入排序，每个组都排好序后，增量减半，再次分组排序，直到增量为1
* @param array
*/
public void shell_Sort(int[] array) {
for(int gap = array.length / 2; gap >=1; gap = gap / 2) { // gap初始为长度/2, 后逐步/2
for (int i = gap; i < array.length; i++) { // 从每个分组中的第二个元素开始，进行直接插入排序
int tmp = array[i]; // 当前待插入的元素
int j = i - gap; // 从后向前比较有序表，j为当前比较到哪个下标了
while(j >= 0 && array[j] > tmp) {
array[j + gap] = array[j]; // 逆序，a[j] 后移
j -= gap;
}
array[j + gap] = tmp; // while结束，j是不满足的下标，需+gap，将tmp插在此处
}
}
}五、选择排序——简单选择
简单选择排序：不稳定， O(n^2)
每轮在待排序列中找min，将其添加至有序表的末尾
/**
* 选择排序：
* 1. 简单选择排序：不稳定， O(n^2)
* 每轮在待排序列中找min，将其添加至有序表的末尾
* @param array
*/
public void select_Sort(int[] array) {
int n = array.length;
for(int i = 0; i < n - 1; i++) { // 当前待插入位置，有序表的最末max
int min_index = i;
for(int j = i + 1; j < n; j++) { // 找min的下标
if (array[min_index] > array[j]) {
min_index = j;
}
}
if (min_index != i) {
swap(array, i, min_index);
}
}
}六、选择排序——堆排序
堆排序：升序使用大根堆（父节点大于左右孩子的完全二叉树），不稳定，O(nlogn)
将待排序列构造小根堆：建堆O(n)，然后调整成一个小根堆
将堆顶与最后一个元素交换，再从堆顶开始调整，将原堆顶脱离大根堆，即序列的max，逐步得到当前堆的堆顶max
/**
* 选择排序：
* 2. 堆排序：升序使用大根堆（父节点大于左右孩子的完全二叉树），不稳定，O(nlogn)
* 将待排序列构造小根堆：建堆O(n)，然后调整成一个小根堆
* 将堆顶与最后一个元素交换，再从堆顶开始调整，将原堆顶脱离大根堆，即序列的max，逐步得到当前堆的堆顶max
*
* @param array
*/
public void heap_Sort(int[] array) {
int n = array.length;
// 建堆：向下调整建堆O(n)和向上调整建堆O(nlogn)
// 子节点i的父节点下标：(i- 1)/2,从最后一个节点父节点开始
for (int i = (n - 1 - 1) / 2; i >= 0; i--) { // 从后向前，可以保证子树已经是大根堆，这样才能使用向下调整
heapify(array, n, i);
}
// 堆顶与最末交换,调整
for (int i = n - 1; i >= 0; i--) {
swap(array, n - 1, 0); // 交换
n--; // 使交换至末尾的max脱离堆
heapify(array, n, 0); // 调整堆
}
}
/**
* 调整、维护堆(大根堆)
* @param array
* @param n 数组长度
* @param i 待维护节点下标
*/
public void heapify(int[] array, int n ,int i) {
int lson = 2 * i + 1;
int rson = 2 * i + 2;
int max_index = i; // 假设当前节点是最小值
// 找到最小节点的下标
if(lson < n && array[max_index] < array[lson]) { // min_index > 左，调整
max_index = lson;
}
if (rson < n && array[max_index] < array[rson]) { // min_index > 右，调整
max_index = rson;
}
if (max_index != i) { // 父节点不是min，与min交换调整
swap(array, max_index, i);
heapify(array, n, max_index); // 调整后可能导致子树不符合规定，递归调整
}
}七、归并排序
归并排序：稳定，O(nlogn)
分治思想
将序列从中间一分为二，递归拆分，直到包含单一元素，将其视为有序表
从左右数组中选择小的元素放入到临时空间，后移下标，直到某一数组的下标达到尾部，将另一序列剩下的所有元素依次放入临时空间，将临时空间的数据依次放入原数据数组
/**
* 归并排序：稳定，O{nlogn)
* 分治思想：将序列从中间一分为二，递归拆分，直到包含单一元素，将其视为有序表
* 从左右数组中选择小的元素放入到临时空间，后移下标，直到某一数组的下标达到尾部，将另一序列剩下的所有元素依次放入临时空间，将临时空间的数据依次放入原数据数组
* @param array
*/
public void merge_Sort(int[] array, int left, int right, int[] tmp_array) {
if (left >= right) { // 递归出口：每组只有一个元素left == right
return;
}
int mid = (right + left) / 2;
merge_Sort(array, left, mid, tmp_array);
merge_Sort(array, mid+1, right, tmp_array);
merge(array, left, mid, right, tmp_array); // 合并
}
public void merge(int[] array, int left, int mid, int right, int[] tmp_array) {
int i = left; // i j 分别指向两个数组的第一个元素
int j = mid + 1;
// int[] tmp_array = array.clone(); //克隆，遍历tmp_array，改变array——>占用空间，传入一个克隆，但注意每次合并完后更新tmp_array与array保持一致
int tmp_index = left;
while(i <= mid && j <= right) {
if(tmp_array[i] < tmp_array[j]) {
array[tmp_index] = tmp_array[i];
i++;
tmp_index++;
}else {
array[tmp_index] = tmp_array[j];
j++;
tmp_index++;
}
}
// 其中一个序列结束了，但另一个还有元素，直接加入(肯定是有序的)
while (i <= mid) {
array[tmp_index] = tmp_array[i];
i++;
tmp_index++;
}
while (j <= right) {
array[tmp_index] = tmp_array[j];
j++;
tmp_index++;
}
// 一次合并后临时数组要和nums同步
for(i = left; i <= right; i++)
tmp_array[i] = array[i];
}
