插入排序

每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到全部待排序记录全部插入为止。

直接插入排序

public class InsertSort implements IArraySort {
    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {
            // 记录要插入的数据
            int tmp = arr[i];
            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
        return arr;
    }
}

时间复杂度：

• 最好情况下（待排序记录递增有序），总的比较次数为n-1次，记录不需要移动。
• 最坏情况下（待排序记录递减有序），总的比较次数和移动次数均为n^2 / 2 。
• 平均情况下，比较次数和移动次数都为n^2 / 4

空间复杂度：
只需要一个辅助空间arr[0]，因此空间复杂度为O(1)

算法特点：
1、稳定排序
2、适用于顺序存储结构和链式存储结构
3、适用于初始记录基本有序的情况，当初始记录无序，n较大时，此算法时间复杂度较高，不宜采用

折半插入排序

基本思想同直接插入排序，不同点在于，在有序集合中搜索插入位置时折半插入采用二分搜索，可以有效的减少比较次数。
算法特点：

1. 稳定排序
2. 只能适用于顺序结构，不用于链式结构
3. 适合初始记录无序，n较大的情况

希尔排序

也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

public class ShellSort implements IArraySort {
    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        int gap = 1;
        while (gap < arr.length/3) {
            gap = gap * 3 + 1;
        }
        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = tmp;
            }
            gap = (int) Math.floor(gap / 3);
        }
        return arr;
    }
}

交换排序

两两比较待排序记录关键字，当两个关键字不满足次序要求时进行交换，直到整个序列满足要求为止。

冒泡排序

两两比较，每次冒出一个最大（小）的数到数组尾

public class BubbleSort implements IArraySort {
    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        for (int i = 1; i < arr.length; i++) {
            // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
            boolean flag = true;
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
        return arr;
    }
}

时间复杂度：

• 最好情况（初始序列正序），只需进行一次排序，在排序过程中进行n-1次关键字的比较，不移动记录
• 最坏情况（初始序列逆序），进行n-1次排序，总的关键字比较次数为 n^2 / 2 ，记录移动次数为 （3n^2 ）/ 2
• 平均情况，比较次数和记录移动次数分别为 n^2 / 2 ,3n^2 / 4, 时间复杂度为O(n^2)

空间复杂度：
仅需arr[0]作为交换辅助空间，故空间复杂度为O(1)

算法特点：
1、稳定排序
2、可用于链式存储结构
3、记录移动次数较多，算法平均性能比直接插入排序差，当初始记录无序时，n较大时，不宜采用

快速排序

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序； ```java public class QuickSort implements IArraySort {

   @Override public int[] sort(int[] sourceArray) throws Exception {

    // 对 arr 进行拷贝，不改变参数内容
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    return quickSort(arr, 0, arr.length - 1);

   }

   private int[] quickSort(int[] arr, int left, int right) {

    if (left < right) {
        int partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;

   }

   private int partition(int[] arr, int left, int right) {

    // 设定基准值（pivot）
    int pivot = left;
    int index = pivot + 1;
    for (int i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;

   }

   private void swap(int[] arr, int i, int j) {

    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;

   }

}

时间复杂度：
- 最好情况（每次排序后序列被分成两个大小大致相等的子表），定位枢轴所需的时间为O(n)，总的排序时间为O(nlog2 n)
- 最坏情况（待排序列有序），递归树成为单支树，关键字的比较次数为n^2 / 2 ,这种情况下快速排序的速度已经退化为简单排序的水平。枢轴记录的合理选择可以避免最坏情况的出现，例如，可在待排序列中随机选择枢轴，并将枢轴交换到第一个位置。
-  平均情况，时间复杂度为O(nlog2 n)
空间复杂度：<br /> 快速排序时递归的，最大递归调用次数与递归树的深度一致，因此最好情况为O(log2 n)，最坏情况为O(n)
算法特点：<br /> 1、不稳定排序<br /> 2、适用于顺序结构，很难用于链式结构<br /> 3、当n较大时，在平均情况下时所有内部排序方法中最快的一种，适用于初始记录无序，n较大的情况<br />[<br />](https://blog.csdn.net/qq_39471489/article/details/118684044)
<a name="UCMml"></a>
# 选择排序
<a name="nFEn8"></a>
## 简单选择排序
   1. 首先在未排序序列中找到最小（大）元素，存放（**交换**）到排序序列的起始位置
   1. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
   1. 重复第二步，直到所有元素均排序完毕。
```java
function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

时间复杂度：
最好情况（正序），记录不需要移动。
最坏情况（逆序），移动3(n-1)次。
无论记录的初始状态如何，所进行的关键字之间的比较次数相同，均为n^2 / 2 ，因此时间复杂度为O(n^2)

空间复杂度：
仅用arr[0]作为交换辅助空间，因此空间复杂度为O(1)

算法特点：
1、算法本身是稳定排序，也可以变成是不稳定排序
2、可以用于链式存储结构
3、移动次数少，当每一个记录占用的空间较多时，此方法比直接插入排序快。

堆排序

归并排序

该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。