排序

1、冒泡排序

冒泡排序也叫起泡排序。
执行流程：（以升序为例）：

1、从头开始比较每一对相邻的元素，如果第一个比第二个大，则交换位置。经过一轮后，最末尾的那个元素就是最大的元素。
2、忽略步骤1中的元素，重复执行步骤1，直到全部元素有序。

具体的代码如下：

int len = array.length;
for (int end = len - 1; end > 0; end--) {
    for (int begin = 1; begin <= end; begin++) {
        // 交换位置
        if (cmp(begin - 1, begin) > 0) {
            swap(begin - 1, begin);
        }
    }
}

1.1、冒泡排序的优化一

如果序列已经完全有序，可以提前终止排序

image.png

for (int end = array.length - 1; end > 0; end--) {
    boolean sorted = true;
    for (int begin = 1; begin <= end; begin++) {
        // 交换位置
        if (cmp(begin - 1, begin) > 0) {
            swap(begin-1,begin);
            sorted = false;
        }
    }
    if (sorted)
        break;
}

1.2、冒泡排序优化二

如果序列尾部已经局部有序，可以记录最后一次交换的位置，减少比较次数

image.png
最后一次交换的位置是6.

for (int end = array.length - 1; end > 0; end--) {
    int sortedIndex = 1;
    for (int begin = 1; begin <= end; begin++) {
        // 交换位置
        if (cmp(begin - 1, begin) > 0) {
            swap(begin - 1, begin);
            sortedIndex = begin;
        }
    }
    end = sortedIndex;
}

1.3、冒泡排序的时间复杂度

对于优化后的最终代码来看，冒泡排序的最坏时间复杂度、平均时间复杂度为O(n²)级别的，而最好时间复杂度（序列是已经排好序的）为O(n)。由于冒泡排序没有依赖额外的资源就完成了排序，所以其空间复杂度为O(1)。

2、排序算法的稳定性

如果相等的2个元素，在排序前后位置没有发生变化，那么这个排序算法是稳定的。

排序前：5 , 1，3₁，4 , 7 , 3₂
稳定的排序：1 , 3₁，3₂，4 , 5 , 7
不稳定的排序：1 , 3₂ ，3₁ ，4 ，5 ，7
对于自定义对象的排序，排序的稳定性会影响排序的效果。
冒泡排序属于稳定的排序算法。

3、原地算法

原地算法是指不依赖外部资源或者较少的外部资源，仅依靠输出来覆盖输入。
空间复杂度为O(1)的算法都是原地算法，冒泡排序算法是原地算法。

4、选择排序

选择排序的执行步骤：

• 1、从序列中找出最大的元素，然后与与最末尾元素交换位置。
  执行完一轮后，最末尾的元素是最大元素。
• 2、忽略步骤1中找出的最大的元素，重复步骤1。

for (int end = array.length - 1; end > 0; end--) {
    int maxIndex = 0;
    for (int begin = 1; begin <= end; begin++) {
        if (cmp(begin, maxIndex) > 0) {
            maxIndex = begin;
        }
    }
    swap(maxIndex,end);
}

选择排序交换的次数远小于冒泡排序，可见性能优于冒泡排序。
选择排序最好、最坏、平均时间复杂度均为O(n²)，空间复杂度为O(1)。
选择排序是不稳定的算法。

5、堆排序

选择排序每次扫描都是找最大的元素，所以有点类似于大顶堆的性质。所以可以认为堆排序是选择排序的优化。
堆排序的执行流程：

• 1、对当前序列进行批量建堆（堆顶元素为最大元素）
  a、交换堆顶元素和最末尾元素。
  b、堆数量减一。
  c、对位置为0的元素执行下滤操作，恢复堆的性质。
• 2、循环执行步骤a、b、c，直到堆的数量为1。
  image.png
  代码实现

public class HeapSort<T extends Comparable<T>> extends Sort<T> {
    private int heapSize;

    @Override
    protected void sort() {
        heapSize = array.length;
        // 批量建堆后得到数组中的首元素为最大
        heapify2();
        // 第一个元素和最后一个元素交换位置，然后执行下滤操作
        while (heapSize > 1) {
            swap(0, --heapSize);
            // 对位置0的元素下滤 恢复二叉堆的性质
            siftDown(0);
        }
    }

    /**
     * 批量建堆的方式二：自下而上的下滤 时间复杂度为高度之和=O(n)
     */
    private void heapify2() {
        int half = heapSize >> 1;
        for (int i = half - 1; i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
     * 下滤
     * 
     * @param index
     */
    private void siftDown(int index) {
        T value = array[index];
        int half = heapSize >> 1;
        while (index < half) {
            int childIndex = (index << 1) + 1;
            T childValue = array[childIndex];

            int rightIndex = childIndex + 1;
            if (rightIndex < heapSize && (cmp(array[rightIndex], childValue) > 0)) {
                childIndex = rightIndex;
                childValue = array[rightIndex];
            }
            if (cmp(value, childValue) >= 0)
                break;
            array[index] = childValue;
            index = childIndex;
        }
        array[index] = value;
    }
}

最好、最坏、平均时间复杂度为O(nlogn)，空间复杂度为O(1)。属于不稳定的算法。

6、插入排序

插入排序会将序列分成两个部分：排好序的头部、尾部是待排序的。

image.png

执行流程如下：
从头开始扫描每一个元素，每扫描到一个元素就将它插入到头部合适的位置，使得头部依然有序。
代码实现如下：

//begin默认为1，index为0的认为是头部有序的，后面的元素是待排序的
for (int begin = 1; begin < array.length; begin++) {
    int cur = begin;
    //如果发现比前面的元素小就交换位置，直到遇到当前的元素大于前面的元素
    //最坏的情况是会和cur前面所有元素进行比较，并交换位置
    while (cur > 0 && cmp(cur, cur - 1) < 0) {
        swap(cur, cur - 1);
        cur--;
    }
}

6.1、插入排序-逆序对

• 什么是逆序对？

比如数组{2,3,8,6,1}，共有<2,1>，<3,1>，<8,1>，<8,6>，<6,1> 5条逆序对。

• 插入排序的时间复杂度和逆序对的数量成正比。逆序对的数量越大，插入排序的时间复杂度就越高。

如一个降序的数组，它的逆序对的数量肯定是最大的，下图描述插入排序的过程，发现每扫描到一个元素都会移动到最前面，也就是说其比较次数和位置交换的次数都是最大的，所以复杂度也最高。

image.png

6.2、插入排序的优化一

• 将【交换元素位置】优化成【挪动元素】

• 1、将要插入的元素备份
• 2、头部有序数据比待插入元素大的向尾部挪动1个位置。
• 3、将待插入的元素放入最终合适的位置。

代码如下：

for (int begin = 1; begin < array.length; begin++) {
    int cur = begin;
    T v = array[cur];
    while (cur > 0 && cmp(v, array[cur - 1]) < 0) {
        //头部有序数据比待插入的元素大的元素向后挪动1个位置
        array[cur] = array[cur - 1];
        cur--;
    }
    //cur就是最终要插入的位置
    array[cur] = v;
}

6.3、二分搜索（Binary Search）

如何确定一个元素在数组中的位置。

• 1、如果是无序数组，从头开始扫描去查找，平均时间复杂度为O(n)

  
  image.png

• 2、如果是有序数据，利用二分法查找，最坏时间复杂度为O(logn)

  
  image.png

6.3.1、二分搜索的思路

• 1、假设在[begin，end)范围内搜索某个元素v，mid=(begin + end)/2。
• 2、如果v < m，则在范围[begin , mid)中进行二分搜索。
• 3、如果v > m，则在范围[mid+1 , end)中进行二分搜索。
• 4、如果v = m，则返回mid。
  image.png

6.3.2、二分搜索的实例

image.png

6.3.3、二分搜索的实现

/**
 * @return 返回元素在数组的位置
 */
public int indexOf(int[] array, int v) {
    if (array == null || array.length == 0)
        return -1;
    int start = 0;
    int end = array.length;
    while (end > start) {
        int mid = (start + end) >> 1;
        if (v < array[mid]) {
            end = mid;
        } else if (v > array[mid]) {
            start = mid + 1;
        } else { // 表示v==array[mid]
            return mid;
        }
    }
    return -1;
}

- 问：如果数组中存在多个重复的值，那么会返回哪一个呢？
- 答：不确定

6.4、插入排序-二分法搜索的优化

插入排序会将序列分成两部分，头部已排好序的部分和尾部待排序的部分。待插入的元素需要和头部已排好序的元素一一进行比较，然后找到合适的位置插入。
如果使用二分法搜索进行查找元素的插入位置，那么就可以减少比较的次数，二分法查找的时间复杂度为O(logn)。

• 在元素v插入过程中，可以先二分搜索出合适的插入位置，然后再将元素v插入。
  image.png
• 二分搜索插入的位置：第一个比v大的元素的位置
  a、如果v是5，插入的位置是2
  b、如果v是1，插入的位置是0
  c、如果v是15，插入的位置是7
  d、如果v是8，插入的位置是5

6.4.1、插入排序 - 二分搜索的优化思路

• 1、假设在范围[begin ，end)范围内搜索某个元素v，mid=（begin+end）/2
• 2、如果v < m，则在范围[begin , mid)中二分法查找
• 3、如果v >= m，则在范围[mid+1 , end)中二分法查找
  image.png

6.4.2、插入排序 - 二分搜索的优化-实例

image.png
image.png
image.png

6.4.3、插入排序 - 二分搜索的优化-代码实现

二分法搜索查找插入的位置

@Override
protected void sort() {
    for (int begin = 1; begin < array.length; begin++) {
        //找到begin元素要插入的位置
        int insertIndex = search(begin);
        T v = array[begin];
        //将大于v的元素向后挪动一位
        for (int i = begin; i > insertIndex; i--) {
            array[i] = array[i - 1];
        }
        //将元素插入到最终的位置
        array[insertIndex] = v;
    }
}

/**
 * @param index 等于end
 * @return 返回插入的位置
 */
private int search(int index) {
    int begin = 0;
    int end = index;
    T v = array[index];
    while (end > begin) {
        int mid = (begin + end) >> 1;
        if (cmp(v, array[mid]) < 0) {
            end = mid;
        } else {
            begin = mid + 1;
        }
    }
    return begin;
}

需要注意的是：使用了二分法搜索优化了插入排序后的时间复杂度仍然是O(n²)，并不是O(nlogn)，因为只是减少了比较次数，但是依然需要挪动，而挪动的平均时间复杂度仍是O(n)。
完整代码

/**
 * 插入排序的优化：二分法查找插入的位置（减少比较次数）
 * 
 * @param <T>
 */
public class InsertionSort3<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            //找到begin元素要插入的位置
            int insertIndex = search(begin);
            T v = array[begin];
            //将大于v的元素向后挪动一位
            for (int i = begin; i > insertIndex; i--) {
                array[i] = array[i - 1];
            }
            //将元素插入到最终的位置
            array[insertIndex] = v;
        }
    }

    /**
     * @param index 等于end
     * @return 返回插入的位置
     */
    private int search(int index) {
        int begin = 0;
        int end = index;
        T v = array[index];
        while (end > begin) {
            int mid = (begin + end) >> 1;
            if (cmp(v, array[mid]) < 0) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        return begin;
    }

}

7、归并排序

归并排序的执行流程：

• 1、不断将序列分割成2个子序列
  直到不能分割为止（序列中只剩下一个元素）。
• 2、不断的将2个子序列合并成一个有序序列
  直到不能合并为止，只剩一个有序序列
  image.png

7.1、归并排序-divide的实现

@Override
protected void sort() {
    sort(0, array.length);
}

private void sort(int begin, int end) {
    if (end - begin < 2)
        return;
    int mid = (begin + end) >> 1;
    sort(begin, mid);
    sort(mid, end);
}

7.2、归并排序-merge的实现

7.2.1、如何将两个数组合并成一个新的序数组

image.png

执行流程：

1、将数组一中元素3和数组二中的元素6进行比较，将较小的元素3存入到新数组中，ai++，li++，ri不变。
2、将数组一种的元素8和数组二中的元素6进行比较，将较小的元素6存入新数组中，ai++，ri++，li不变。
3、元素8和元素10比较，将8存入新数组中，ai++，li++，ri不变。
4、数组一已经结束，将数组二中剩下的元素存入新数组中，ri++，ai++。

7.2.2、如何将同一数组中的两个子序列合并成有序数组（原地）

• 1、需要merge的两个序列在同一数组中，并且是挨在一起的

  
  image.png
• 2、为了更好的执行merge操作，需要将其中一部分备份出来，比如[begin，mid)
  image.png

7.2.3、归并排序-merge

image.png

7.2.4、归并排序-merge-左边先结束

image.png
左边先结束的话，右边剩余的元素不用变即可。

7.2.5、归并排序-merge-右边先结束

image.png
如果右边先结束的话，将左边数组中剩余的元素依次放入到array中。

7.2.5、归并排序-merge的实现

/**
 * [begin,mid)  [mid,end)
 */
private void merge(int begin, int mid, int end) {
    // li le ri re ai
    int li = 0, le = mid - begin; //针对leftArray,故li为0
    int ri = mid, re = end;//针对array
    int ai = begin;//array的索引
    // 拷贝左边数组
    for (int i = li; i < le; i++) {
        leftArray[i] = array[begin + i];
    }

    // 左边数组先结束，右边就不用管了
    while (li < le) {
        //增加条件ri>re，在右边数组结束后，左边数组依次放入array中
        if (ri < re && cmp(leftArray[li], array[ri]) > 0) {
            array[ai++] = array[ri++];
        } else { // leftArray[li]>=array[ri]
            array[ai++] = leftArray[li++];
        }
    }
}

完整代码如下

public class MergeSort<T extends Comparable<T>> extends Sort<T> {
    private T[] leftArray;

    @Override
    protected void sort() {
        leftArray =  (T[]) new Comparable[array.length >> 1];
        sort(0, array.length);
    }

    private void sort(int begin, int end) {
        if (end - begin < 2)
            return;
        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);
        merge(begin, mid, end);
    }

    /**
     * [begin,mid)  [mid,end)
     */
    private void merge(int begin, int mid, int end) {
        // li le ri re ai
        int li = 0, le = mid - begin; //针对leftArray,故li为0
        int ri = mid, re = end;//针对array
        int ai = begin;//array的索引
        // 拷贝左边数组
        for (int i = li; i < le; i++) {
            leftArray[i] = array[begin + i];
        }

        // 左边数组先结束，右边就不用管了
        while (li < le) {
            //增加条件ri>re，在右边数组结束后，左边数组依次放入array中
            if (ri < re && cmp(leftArray[li], array[ri]) > 0) {
                array[ai++] = array[ri++];
            } else { // leftArray[li]>=array[ri]
                array[ai++] = leftArray[li++];
            }
        }
    }

}

7.3、归并排序的复杂度

• 归并排序花费的时间

//sort()方法耗时T(n) 注意不同于O(n)
private void sort(int begin, int end) {
    if (end - begin < 2)
        return;
    int mid = (begin + end) >> 1;
    sort(begin, mid);   //耗时T(n/2)
    sort(mid, end);   //耗时T(n/2)
    merge(begin, mid, end);   //耗时O(n)
}

T(n)=2 * T(n/2)+O(n)
T(1)=O(1)
T(n)/n=T(n/2) * (n/2)+O(1)

• 令S(n)=T(n)/n

S(1)=O(1)
S(n)=S(n/2)+O(1)=S(n/4)+O(2)=S(n/8)+O(3)=S(n/2^k)+O(k)=S(1)+O(logn)=O(logn)
T(n)=n*S(n)=O(nlogn)

• 由于归并排序总是平均分割子序列，所以最好、最坏、平均时间复杂度为O(nlogn)，属于稳定排序。
• 从代码中不难看出空间复杂度=O(n/2)+O(logn)=O(n)，n/2用于临时存放左侧数组，logn用于递归调用。

7.4、常见递推式与复杂度

image.png

8、快速排序

快速排序的执行流程：

• 1、从序列中选择一个轴点元素
  假设每次选择0位置的元素为轴点元素
• 2、利用pivot将序列分割成2个子序列
  将小于pivot的元素放在pivot的左边
  将大于pivot的元素放在pivot的右边
  等于pivot的元素放在哪边都可以
• 3、对子序列执行1、2的操作，直到不能再分割为止（子序列只有一个元素）
  image.png
  快速排序的本质：逐渐将每一个元素变成轴点元素。

8.1、快速排序-轴点的构造

image.png

8.2、快速排序的时间复杂度

• 1、在轴点左右元素数量分布比较均匀的时候，同时也是最好的情况

T(n)=T(n/2)+O(n)=O(nlogn)

• 2、如果轴点左右元素数量分布不均匀的时候，最坏的情况

T(n)=T(n-1)+O(n)=O(n²)

• 3、为了降低最坏的情况，需要随机选择轴点元素。
• 4、快速排序最好、平均时间复杂度为O(logn)，最坏时间复杂度为O(n²)。
• 5、由于递归调用的缘故，空间复杂度为O(logn)
• 6、快速排序属于不稳定排序。

8.3、快速排序的实现

@Override
protected void sort() {
    sort(0, array.length);
}

/**
 * 对 [begin, end) 范围的元素进行快速排序
 * @param begin
 * @param end
 */
private void sort(int begin, int end) { 
    if (end - begin < 2) return;
    
    // 确定轴点位置 O(n)
    int mid = pivotIndex(begin, end);
    // 对子序列进行快速排序
    sort(begin, mid); 
    sort(mid + 1, end); 
} 

/**
 * 构造出 [begin, end) 范围的轴点元素
 * @return 轴点元素的最终位置
 */
private int pivotIndex(int begin, int end) {
    // 随机选择一个元素跟begin位置进行交换
    swap(begin, begin + (int)(Math.random() * (end - begin)));
    
    // 备份begin位置的元素
    T pivot = array[begin];
    // end指向最后一个元素
    end--;
    
    while (begin < end) {
        while (begin < end) {
            if (cmp(pivot, array[end]) < 0) { // 右边元素 > 轴点元素
                end--;
            } else { // 右边元素 <= 轴点元素
                array[begin++] = array[end];
                break;
            }
        }
        while (begin < end) {
            if (cmp(pivot, array[begin]) > 0) { // 左边元素 < 轴点元素
                begin++;
            } else { // 左边元素 >= 轴点元素
                array[end--] = array[begin];
                break;
            }
        }
    }
    
    // 将轴点元素放入最终的位置
    array[begin] = pivot;
    // 返回轴点元素的位置
    return begin;
}

8.4、快速排序-和轴点相等的元素

image.png
任何和轴点相等的元素，利用目前的算法实现，可以将序列分割成2个均匀分布的子序列。

9、希尔排序

• 希尔排序将序列当做是一个矩阵，分成m列，逐列进行排序。

• m从某个整数逐渐变为1
• m变成1时序列排序完成。

• 矩阵的列数取决于步长序列

• 比如步长序列为{1,5，19，41，109，....}，就代表依次分成109列、41列、19列、5列、1列进行排序
• 不同的步长序列执行效率也不同

9.1、希尔排序的实例一

• 希尔本人给出的的步长序列是n/2^k，如果序列长度为16，那么步长序列为{8,4,2,1}。

  
  image.png

• 分成8列进行逐列排序

  
  image.png

• 分成4列进行逐列排序

  
  image.png

• 分成2列进行逐列排序

  
  image.png

• 分成1列进行逐列排序

  
  image.png
• 不难看出从8列变成1列的过程中，逆序对的数量在减少

因此希尔排序底层一般使用插入排序来实现对每一列进行排序。

9.2、希尔排序的实例二

• 假设有11个元素，步长序列为{1,2,5}

  
  image.png
• 假设元素在第col列，第row行，步长为step。那么这个元素在数组中的索引为col+row*step.
• 比如9在序列的第2列，第0行，那么它排序前的索引为2+0*5=2
• 比如4在序列的第2列，第1行，那么它排序前的索引为2+1*5=7

9.3、希尔排序的实现

public class ShellSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        List<Integer> stepSequence = shellStepSequence();
        for (Integer step : stepSequence) {
            sort(step);
        }
    }
    
    /**
     * 分成step列进行排序
     */
    private void sort(int step) {
        // col : 第几列，column的简称
        for (int col = 0; col < step; col++) { // 对第col列进行排序
            // col、col+step、col+2*step、col+3*step
            for (int begin = col + step; begin < array.length; begin += step) {
                int cur = begin;
                while (cur > col && cmp(cur, cur - step) < 0) {
                    swap(cur, cur - step);
                    cur -= step;
                }
            }
        }
    }
    
    private List<Integer> shellStepSequence() {
        List<Integer> stepSequence = new ArrayList<>();
        int step = array.length;
        while ((step >>= 1) > 0) {
            stepSequence.add(step);
        }
        return stepSequence;
    }
    
}

9.4、希尔排序的时间复杂度

• 最好情况是步长序列只有1，且序列几乎有序，时间复杂度为O(n)。
• 希尔给出的步长序列，最坏时间复杂度为O(n²)，目前已知最好的步长序列，最坏的时间复杂度为O(n^(4/3))，由Robert Sedgewick提出的。
• 希尔排序的平均时间复杂度取决于步长序列。
• 希尔排序的空间复杂度为O(1)，属于不稳定的排序。