一、排序的概念及引用
1.1. 排序的概念
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断的在内外存之间移动数据的排序。
1.2. 排序的应用
1.3. 常见的排序算法
二、常见排序算法的实现
2.1. 直接插入排序
类比一下，在玩扑克牌的时候，从牌堆中拿取一张牌进行排序，就用到了插入排序。插入排序的过程：让 i 从第二个元素为起始位置，j=i-1，当 arr[j]>arr[i]，用 tmp 接收 i 下标的值，让 j 下标的元素向前移，然后让 j--，如果 tmp 的值大于 j 下标的值，就把 tmp 的插入 j 的后面；如果 tmp 一直比 j 下标的值小，就让 j 一直--，当 j<0 时，那么 tmp 的值就插入第一个位置。上述过程就能保证 i 下标之前的元素保持是有序的。当 i 走到最后一个元素时，就完成了这个插入排序。
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
for (int j = i - 1; j >= 0; j--) {
if (array[j] > tmp) {
array[j + 1] = array[j];
} else {
array[j + 1] = tmp;
}
}
}
上述代码我们还可以进行优化，如果数组本身就是有序的，再来一个更大的数，不用再让 j 向前移动了，直接 break 就可以了。如果 j 走到了 -1 的位置，就说第一个元素已经挪开了，就不会再走 for 循环了，我们再把 tmp 的值放回来。
public class Sort {
public void InsertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int j = i - 1;
for (; j >= 0; j--) {
if (array[j] > tmp) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = tmp;
}
}
}
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
int[] array = {87, 5, 32, 55, 43, 26};
Sort sort = new Sort();
sort.InsertSort(array);
System.out.println(Arrays.toString(array));
}
}
我们来分析一下时间复杂度：当 i 为 1 的时候，j 最多回退 1 次；当 i 为 2 的时候，j 最多回退 2 次，那么时间复杂度的计算为
，时间复杂度为
，这是最坏情况下。如果数组本身就是有序的，那么时间复杂度为
。空间上，我们没有使用额外的数组，空间复杂度为
。所以插入排序适合应用于数组本身就趋向于有序的情况。
我们再思考一下插入排序的稳定性，上面的代码中，array[j] > tmp，才会执行，两个数相等则不会。如果我们改成 array[j]>=tmp，就会变得不稳定。所以，如果排序本身就是稳定的，可以调整为不稳定的；如果排序本身就是不稳定的，则是无法变为稳定的。
我们要想更直观的看到运行消耗的时间，我们可以写出一个方法，来计算我们运行的时间：
import java.util.Arrays;
import java.util.Random;
/**
* @author: gao
* @create-date: 2025/3/7 12:47
*/
public class Solution {
public static void Order(int[] array) {
for (int i = 0; i < array.length; i++) {
array[i] = i;
}
}
public static void ReverseOrder(int[] array) {
for (int i = 0; i < array.length; i++) {
array[i] = array.length - i;
}
}
public static void DisOrder(int[] array) {
Random ran = new Random();
for (int i = 0; i < array.length; i++) {
array[i] = ran.nextInt(array.length);
}
}
public static void TestInsertSort(int[] array) {
long System.currentTimeMillis();
();
sort.InsertSort(array);
System.currentTimeMillis();
System.out.println( + (EndTIme - StartTime));
}
{
[] array = [];
ReverseOrder(array);
TestInsertSort(array);
}
}
2.2. 希尔排序
希尔排序又称'缩小增量排序'，可以看作是直接插入排序的优化。所谓'缩小增量'，就是采用分组的思想，在组内进行插入排序。比如说，我们可以 5 个一组进行连续地划分（如下图所示），有的人可能会说，进行跳跃式地分组，但这样分组会出现的一种情况，就是尽可能把大的数据往后放，小的数据往前放。很明显第一种分组明显优于第二种。
当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进⾏性能测试的对比。
上面我们采用的是 gap=5，接下来缩小间距，gap=2 划分区间。这里不能写成 i+=gap，这样会导致有些组没有参与排序。i++ 才能让每一组进行交互式排序。所以说不管 gap 为几，本质上还是执行插入排序。
我们接下来思考的问题是为什么要缩小增量。组数越大，组内数据越少；组数越小，组内数据越多，效率就越低。在增量缩小的过程中，数组就趋向于有序。
public class Sort {
public void ShellSort(int[] array) {
int gap = array.length / 2;
while (gap > 0) {
Shell(array, gap);
gap /= 2;
}
}
public void Shell(int[] array, int gap) {
for (int i = gap; i < array.length; i++) {
int tmp = array[i];
int j = i - gap;
for (; j >= 0; j -= gap) {
if (array[j] > tmp) {
array[j + gap] = array[j];
} else {
break;
}
}
array[j + gap] = tmp;
}
}
}
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
int[] array = {5, 11, 7, 2, 3, 17};
Sort sort = new Sort();
sort.ShellSort(array);
System.out.println(Arrays.toString(array));
}
}
希尔排序是不稳定的，不同组交换期间很可能导致元素的相对位置发生改变。空间上，没有申请额外的内存空间，空间复杂度为
。时间复杂度上，我们假设有 n 个数据，每次除 2，都会
……当 gap=1 时，循环结束，所以外循环的时间复杂度
。希尔排序的时间复杂度的分析至今还非常困难，难度在于弄清比较次数和移动对象与增量选择的关联，并给出完整的数学分析。如果 gap 非常大的时候，那么 j 回退的次数就越少，几乎可以认为是常数。当 gap 非常小的时候，j 需要分的组也很小，整体时间复杂度也趋近于常数级。
