目录
一、排序
排序：就是使一串记录序列，按照其中某个或某些关键字的大小，进行递增或递减的排列操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序后，这些记录的相对次序保持不变，则称这种排序算法是稳定的；否则称为不稳定。
例如，在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，若排序后的序列中，r[i] 仍在 r[j] 之前，则排序算法稳定，反之即不稳定。
二、插入排序
2.1 直接插入排序
核心思想：从第二个元素开始遍历，每次遍历将该元素与其前方元素对比，做出相应交换。
public static void insertSort(int[] array) {
//初始 i 下标指向第二个元素
for (int i = 1; i < array.length; i++) {
//将 i下标的值放入 temp 中
int temp = array[i];
//初始 j 下标指向 i 下标的前一位
int j = i-1;
for (; j >= 0; j--) {
//若 j 下标的值比 temp 中的值大，则将其往后移一位
if (array[j] > temp) {
array[j+1] = array[j];
} else {
break;
}
}
//循环结束将原本 i 的值放至 j 下标的后一位中
array[j+1] = temp;
}
}【总结】
时间复杂度：
最坏情况下：O(n^2)
最好情况下：O(n)
空间复杂度：O(1)
稳定性：稳定
适用性：待排序序列接近有序
2.2 希尔排序
希尔排序也叫缩小增量排序，基本思想：选定一个整数 gap，将待排序序列分为 gap 组，所有距离为 gap 的元素为同一组，每组分别进行直接插入排序；然后缩小 gap，继续分组排序，直至 gap = 1 时，所有元素为一组，最后进行一次直接插入排序。
public static void shellSort(int[] array) {
int gap = array.length;
//gap>1 都属于预排序
while (gap > 1) {
//取 gap 为全部元素的一半
gap /= 2;
//每组排序
shell(array, gap);
}
}
private static void shell(int[] array, int gap) {
//初始 i 下标指向 gap，即每组的第二个元素
for (int i = gap; i < array.length; i++) {
//将 i下标的值放入 temp 中
int temp = array[i];
//初始 j 下标指向 i 下标的前 1gap 位
//j 每次往前 1gap 位
int j = i-gap;
for (; j >= 0; j-=gap) {
//若 j 下标的值比 temp 中的值大，则将其往后移 1gap 位
if (array[j] > temp) {
array[j+gap] = array[j];
} else {
break;
}
}
//循环结束将原本 i 的值放至 j 下标的后 1gap 位中
array[j+gap] = temp;
}
}【总结】
1、希尔排序是对直接插入排序的优化。
2、当 gap>1 时，都是预排序，是为了让序列趋于有序。
3、稳定性：不稳定
三、选择排序
3.1 直接选择排序
核心思想：遍历每个元素，每次遍历确定一个最小值令其有序。
public static void selectSort(int[] array) {
//遍历每个元素
for (int i = 0; i < array.length; i++) {
//初始化 minIndex 用于指向最小值
int minIndex = i;
//i 下标与后方每个元素对比
for (int j = i+1; j < array.length; j++) {
//确保 minIndex 指向 i 下标及其后方元素的最小值
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
//交换 i 下标与 minIndex 下标的值
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}【总结】
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定
3.2 堆排序
① 创建大根堆，初始化 end = array.length-1，即 end 指向最后一个结点；
② 将栈顶元素交换至 end 下标。由于大根堆中栈顶元素最大，故交换一次，end--，保证每次交换后的栈顶元素位置不变；
③ 重新向下调整为大根堆；
④ 重复 ②、③ 操作，直至排序完成。
//创建大根堆
private static void createHeap(int[] array) {
//从最后一棵子树开始调整，依次往前，直至根结点
//父亲结点 = (孩子结点-1) / 2
//usedSize-1 是树中最后一个结点
for (int parent = (array.length-1-1) / 2; parent >= 0; parent--) {
//向下调整
siftDown(array, parent,array.length);
}
}
//堆排序
public static void heapSort(int[] array) {
//创建大根堆
createHeap(array);
int end = array.length-1;
while (end > 0) {
//将大根堆中栈顶元素交换至 end
swap(array, 0, end);
//向下调整为大根堆
siftDown(array, 0, end);
//保证每次调整的栈顶元素位置不变
end--;
}
}
//向下调整
private static void siftDown(int[] array, int parent, int length) {
//左孩子结点 = 父亲结点*2 + 1
int child = parent*2 + 1;
//首先保证该结点有左孩子结点
while (child < length) {
//再次确定该结点有右孩子结点，再进行比较
//保证 child 引用指向孩子结点中最大值
if ((child+1) < length && array[child] < array[child+1]) {
//若右孩子的值大于左孩子，则 child 引用指向右孩子
child = child + 1;
}
if (array[child] > array[parent]) {
//若 child 比 parent 大，则交换元素
swap(array, child, parent);
//parent 指向 child 位置，向下调整至下方无子树
parent = child;
child = parent*2 + 1;
} else {
//子结点都比父结点小
break;
}
}
}
//交换元素
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}【总结】
时间复杂度：O(n*log n)
空间复杂度：O(1)
稳定性：不稳定
四、交换排序
4.1 冒泡排序
核心思想：进行 array.length-1 趟比较，每次确定一个最大值元素。
public static void bubbleSort(int[] array) {
//i 表示趟数
for (int i = 0; i < array.length-1; i++) {
//设置一个标签，检测该趟是否发生交换
boolean flag = false;
//j 表示该趟比较次数
for (int j = 0; j < array.length-1-i; j++) {
//每趟确定一个最大值
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
//若交换，则改变标签状态
flag = true;
}
}
//若标签状态未改变，则序列已经有序
if (!flag) {
break;
}
}
}【总结】
时间复杂度：O(n^2)，若加上 flag 优化，则最好可以达到 O(n)
空间复杂度：O(1)
稳定性：稳定
4.2 快速排序
1、Hoare版
核心思想：以 0 下标元素为基准，保证每次排序后，基准左侧元素小于基准，右侧大于基准，分别在左序列与右序列进行递归排序。
public static void quickSort(int[] array) {
quick(array, 0, array.length-1);
}
private static void quick(int[] array, int start, int end) {
// start < end 时才需要排序
if (start >= end) {
return;
}
//找到基准的下标
int pivot = partitionHoare(array, start, end);
//左序列
quick(array, start, pivot-1);
//右序列
quick(array, pivot+1, end);
}
private static int partitionHoare(int[] array, int left, int right) {
//保存基准的值
int temp = array[left];
//保存基准的下标
int index = left;
while (left < right) {
//在右侧找到比基准小的数
while (left < right && array[right] >= temp) {
right--;
}
//在左侧找到比基准小的数
while (left < right && array[left] <= temp) {
left++;
}
swap(array, left, right);
}
//保证基准左侧都比基准小，右侧都比基准大
swap(array, index, left);
//确定基准的位置时，left = right
return left;
}2、挖坑版
核心思想：以 0 下标元素为基准，0 下标处为第一个坑位，从右侧开始遍历，找到比基准小的元素放至 left 下标 (初始即 0 下标) 处；然后从左侧遍历到比基准大的放至 right 下标处，循环至 left 与 right 相遇，将基准放入最后一个坑位。
public static void quickSort(int[] array) {
quick(array, 0, array.length-1);
}
private static void quick(int[] array, int start, int end) {
// start < end 时才需要排序
if (start >= end) {
return;
}
//找到基准的下标
int pivot = partition(array, start, end);
//左序列
quick(array, start, pivot-1);
//右序列
quick(array, pivot+1, end);
}
private static int partition(int[] array, int left, int right) {
//保存基准的值
int temp = array[left];
//保存基准的下标
int index = left;
while (left < right) {
//在右侧找到比基准小的数
while (left < right && array[right] >= temp) {
right--;
}
//找到放置左边的坑位
array[left] = array[right];
//在左侧找到比基准小的数
while (left < right && array[left] <= temp) {
left++;
}
//找到放置右边的坑位
array[right] = array[left];
}
//将基准值放入最后一个坑中
array[left] = temp;
//确定基准的位置时，left = right
return left;
}【总结】
时间复杂度：O(n*log n)
空间复杂度：O(log n)
稳定性：不稳定
五、归并排序
将两个有序序列合并成一个有序序列的操作，称为二路归并。
核心步骤：先分解再合并。
public static void mergeSort(int[] array) {
merge(array, 0, array.length-1);
}
private static void merge(int[] array, int start, int end) {
// start < end 时才需要排序
if (start >= end) {
return;
}
//标记序列中间下标
int mid = (start+end)/2;
//左序列
merge(array, start, mid);
//右序列
merge(array, mid+1, end);
//排序, 合并
mergeMethod(array, start, mid, end);
}
private static void mergeMethod(int[] array, int left,int mid, int right) {
//指向左右序列最小值
int min1 = left;
int min2 = mid+1;
//定义一个新的空间用于排序
int[] sort = new int[right-left+1];
//新空间的下标
int k = 0;
//保证左右序列都有元素
while (min1 <= mid && min2 <= right) {
//左右序列从最左侧(最小值)开始比较
if (array[min1] <= array[min2]) {
sort[k++] = array[min1++];
} else {
sort[k++] = array[min2++];
}
}
//表示右序列中无元素，即左序列剩下元素比右序列都要大
while (min1 <= mid) {
sort[k++] = array[min1++];
}
//表示左序列中无元素，即右序列剩下元素比左序列都要大
while (min2 <= right) {
sort[k++] = array[min2++];
}
//将排序好的数组，拷贝回原数组
for (int i = 0; i < sort.length; i++) {
//利用 left 下标(每个序列起始下标) 保证右序列可以顺利拷贝
array[i+left] = sort[i];
}
}【总结】
时间复杂度：O(n*log n)
空间复杂度：O(n)
稳定性：稳定
适用性：更多是在解决磁盘中的外排序问题
六、排序算法分析
| 排序方法 | 最好 | 平均 | 最坏 | 空间复杂度 | 稳定性 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 希尔排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n*log n) | O(n*log n) | O(n*log n) | O(1) | 不稳定 |
| 快速排序 | O(n*log n) | O(n*log n) | O(n^2) | O(log n) ~ O(n) | 不稳定 |
| 归并排序 | O(n*log n) | O(n*log n) | O(n*log n) | O(n) | 稳定 |
总结
1、希尔排序是对直接插入排序的优化。
2、直接选择排序效率不高，很少使用；堆排序效率高。
3、快速排序综合性能和使用场景都是比较好的。
4、归并排序更多是在解决磁盘中的外排序问题。
