排序算法(二)

¶排序算法(二)

¶概述:

前面看到的冒泡，插入，选择排序是比较基础也比较常见的排序算法，适用于数据量不大的场景进行排序的需求，它们的时间复杂度的都是O(n^2)。接下来要了解的是复杂度为O(nlogn)两种排序算法:归并排序,快速排序；它们都用到了分治思想；
先抛出一个待解决的问题：如何在数组中查找到第K大的元素？

¶归并排序

概念：
1. 将待排序数组从中间分成两部分
2. 对前后部分分别进行排序
3. 合并排序后的数组
4. 说实话，光看这几句话，对前后排序再合并，合并数组的依据是什么?合并的数组如果前后部分如果刚好倒序，还得进行一次排序才能产生最终有序的数组，那之前的分开排序意义有多大？
思路分析：
1. 将问题划分成两部分：对数组的部分进行排序，合并排序后的数组
2. 对数组的部分进行排序，我觉得数组的两部分不一定要划分得完全规整，奇数长数组前后部分相差1也可以；但是需要确定何时开始对划分的子数组进行合并？这也是退出递归的条件。
3. 合并排序的数组，之前的部分只是直接依据数组长度进行划分，没有任何排序的动作；直到数组无法再划分，才开始对最后产生的子数组合并再排序，然后向上返回合并排序后的数组进行上一层的合并排序，直到返回到递归的顶级
4. 从2，3两点来看，分治法的思想十分明显：将一个无序数组的排序划分成了规模更小的数组的划分，合并，排序；递归求解的思路是：需要求解最小条件，并且关联父级递归和子递归，而不是人为地尝试展开所有结果去推导递归的解，实现困难且效率低还容易出错。

实现：


//顺序思维考虑实现的归并排序
//保存已求解的计算
static List<Integer> nums= new ArrayList<>();

public static int[] mergeSort(int[] a,int start,int end){

    if(start >= end){
        if(nums.contains(a[start])){
            return new int[]{};
        }else {
            nums.add(a[start]);
            return new int[]{a[start]};
        }
    }else{
        int a1[] = mergeSort(a,start,end/2 -1);
        int a2[] = mergeSort(a,end/2,end-1);
        return mergeArray(a1,a2);
    }
}

//合并数组
private static int[] mergeArray(int[] a,int[] b){

    int[] c = new int[a.length + b.length];
    int k =0;
    while(k<c.length){
        for(int i = 0;i<a.length;i++){
            c[k] = a[i];
            k++;
        }
        for(int j = 0;j<b.length;j++){
            c[k] = b[j];
            k++;
        }
    }
    //之前实现的冒泡排序
    NormalSearch.bubbleSearch(c);
    return c;
}

//测试数据
public static void main(String[] args) {
    int[] a ={11,8,3,9,7,1,2,5,23,45,12,13,76,54,32,24};
    int n=a.length;
    a = mergeSort(a,0,2*(n-1));
}

这个实现的方式也不知道符不符合归并排序的要求，并没有直接对数组进行划分再去递归，而是不停地将数组区间缩小，直到区间长度为1，开始返回进行数组合并，向上回递值；
毫无疑问有几个问题很明显：
1. 使用了保存递归计算结果的 nums 列表，防止递归的重复计算，在这个版本的实现中无法省略
2. 调用这个方法的参数 end 值为 2(n-1)，因为在第16行的第一次递归计算完成之后，end值最终被缩小为n/2，导致第17行的第二次递归结束下标缩小，丢失了后面的值
3. mergeArray(int[] a,int[] b)方法的最后使用了一次排序算法，这个应该是有问题的，合并数组原本就是为了对数组进行排序，直接调用排序算法，多半不符合规范，需要重新修改合并数组并排序的方法
4. 虽然最终实现了数组的有序合并，第三点多半是最大的问题
归并排序要求是基于数组分割来实现，尝试修改这部分的逻辑:


public static int[] mergeSortByArrayCopy(int[] a,int start,int end){

    if(start == 0 && start==end){
       return new int[]{a[0]};
    }
    int[] b = Arrays.copyOfRange(a,start,end);
    int[] c = Arrays.copyOfRange(a,end,a.length);
    //数组返回的条件
    return mergeArray(mergeSortByArrayCopy(b,0,(b.length)/2),
                      mergeSortByArrayCopy(c,0,(c.length)/2));
}

改进的地方是不需要存储已计算递归值的的nums列表，节省了至少n次保存动作
代码更加简洁，比较符合递归的思路
数组合并的次数为15次，之前的实现中为26次，最明显的优化，效率得到了提升
剩下的问题依旧是数组的合并排序，有这样几个思路：
1. 数组的排序能否在合并中进行？是可以的，因为原本就是在进行遍历，再加上比较插入的操作即可
2. 两个有序数组的合并，能否有更高效的方法？有的，最好时间复杂度为O(1)，当其中一个数组的末位，大于等于另一个数组的首位，直接将小的数组整体移动即可
3. 分割数组的操作比较直观，复杂实现是不是在数组的有序合并？是的，最坏情况下，如果前后数组刚好处于同样下标位置都大小相反的情况，且彼此又是数字间隔，那么就需要完全遍历两个数组才能做到有序合并
4. 暂时只想到这几点

进行数组合并方法的优化:

在数组合并中进行排序；
通过边界条件确定是否可以快速完成合并；
是否具备其他合并方式

优化实现:


private static int[] mergeArray(int[] a,int[] b){
    int al = a.length;
    int bl = b.length;
    if(null == a && null == b || (al == 0 && bl==0)){
        return new int[]{};
    }
    int[] c = new int[a.length + b.length];
    int k =0;
    int i = 0;
    int j = 0;
    //这种方式可以保证其中一个数组的数据全部移动到临时数组中
    //也就意味着剩下的元素顺序上大于c[k]，直接进行尾部插入
    while(i<al && j <bl){
        //判断应该插入哪个数组的数据
        if(a[i]<=b[j]){
            c[k++] = a[i++];
        }else{
            c[k++] = b[j++];
        }
    }
    //判断哪个数组还有剩余元素，直接进行最后的尾部插入
    if(i>al-1 && j<bl){
        while(j<bl){
            c[k++]=b[j++];
        }
    }else{
        while(i<al){
            c[k++]=a[i++];
        }
    }
    count++;
    return c;
}

思路有两点
1. 在遍历的过程中进行元素的排序和插入
2. 当一边的元素遍历到了末尾，说明剩余数组的剩余元素在顺序上都大于当前总数组的末尾数组
3. 测试的结果中是可以对数组进行排序的，而且提前设置循环终止的信号，提高效率

归并排序中合并数组这一部分是每一次递归到最后都要进行的，进行一次次的子数组合并，所以就是考虑顺序插入数组
思路中借鉴来的一点觉得很好：if(i>al-1 && b<bl) ，这意味着当一次遍历结束，剩余数组的剩余元素可以直接顺序插入

¶快速排序

概念 :
1. 对于待排序数组a[q…r] ,选择q~r中的任意一点作为分区点 p
2. 将所有小于p的元素放到左边，将大于p的元素放在右边，p放在中间
3. 然后对于左右分区采用同样的分治思想进行处理
4. 这里有两种实现模式：
  1. 在分区时使用临时数组保存拆分结果，然后进行数组合并
  2. 将拆分过程实现成原地排序，不使用临时空间存储

通过临时数组保存元素实现:


public static int[] quickSort(int[] a) {
	//空数组和单个元素的数组无需再进行排序
    if (null == a || a.length <= 1) {
        return a;
    }
    int n = a.length;
    //默认取了当前数组的最后一个元素作为排序的分区点
    int q = a[n - 1];
    //先按照将数组拆分的思路实现一次
    //这里将临时数组的长度都声明为n-1原因是防止出现极端分布的情况
    int[] lower = new int[n-1];
    int[] bigger = new int[n-1];
    int j = 0;
    int k = 0;
    for (int i = 0; i < a.length; i++) {
        if (a[i] < q) {
            lower[j] = a[i];
            j++;
        } else if (a[i] > q) {
            bigger[k] = a[i];
            k++;
        }
    }
    int[] lr = Arrays.copyOf(lower, j);
    int[] br = Arrays.copyOf(bigger, n - j - 1);
    //一次排序之后只能保证按照分区点元素a[q]将数组的数组排成了大于a[q]和小于a[q]两部分
    //递归
    return mergeArray(quickSort(lr), quickSort(br), q);
}


//合并拆分的数组,这里只做合并，不做排序
public static int[] mergeArray(int[] lower, int[] bigger, int q) {

    int[] result = new int[lower.length + bigger.length + 1];
    int k = 0;
    for (int i = 0; i < lower.length; i++) {
        result[k] = lower[i];
        k++;
    }
    result[k] = q;
    k++;
    for (int i = 0; i < bigger.length; i++) {
        result[k] = bigger[i];
        k++;
    }
    return result;
}

这个完全是按照使用临时数组保存数据然后再进行一次合并的思路实现的，消耗了额外的内存空间，原则上来说不可取，因为需要排序的数组越大，申请几乎两倍大小的临时空间代价也就越昂贵
从实现思路看，这个很类似于归并排序，只不过我的归并排序的排序动作在数组合并里面，这里的排序动作在递归方法里面

优化成原地排序：

优化思路:

不使用临时数组保存分区排序元素
基于数组的特性考虑，再不拆分数组的情况下如何进行部分数据的排序？
基于第二点的实现挺考验思维的，如果局限在正常的数组排序比较思路，想不出来


//基于原地分区排序实现的快排
public static void quickSortNew(int[] a,int start,int end) {

    if (null == a || start >= end) {
        return;
    }
    //获取当前数组的分区点，然后进行前后分区的排序
    int pindex = partition(a,start,end);
    quickSortNew(a,start,pindex);
    quickSortNew(a,pindex+1,end);
}


public static int partition(int[]a,int start,int end){

    //假设默认选择数组的末尾作为分区元素
    if(start>=end){
        return start;
    }
    //哨兵
    int p = a[end-1];
    // i 用来记录分区点的变化位置
    int i=0;
    for(int j=0;j<end-1;j++){
        if(a[j]<p){
            int temp = a[j];
            a[j]=a[i];
            a[i]=temp;
            //代表着start~i 的元素 <=p
            i++;
        }
    }
    //交换a[i] 和 a[end-1]
    int temp = a[i];
    a[i]=a[end-1];
    a[end-1]=temp;

    return i;
}

分区排序的重点在记录分区点的位置，这里使用的方法是设置哨兵节点 p ,使用 i 来记录分区点最终的位置
这也反映出一个思路：想在不改变数组后续遍历顺序的情况下，完成特定信息的记录，需要设置额外的记录点，就是所谓的哨兵，在带头节点的链表中也是同样的思路

与归并排序进行比较：

归并排序是将数组先拆分成两份，直到不可拆分时，进行数据的排序，然后合并
快速排序是先按照分区点将数组排序，然后再根据分区点继续划分更小的分区进行排序
从这一点看它们的区别就是先进行排序还是先进行数组的分区操作

开篇问题 : 如何在数组中查找第 K 大个元素

思路分析：

查找第K大，意味着需要知道数组元素的大小顺序
在对数组遍历的过程中记录第N大个元素的信息，但是不能影响后续的遍历，可以添加哨兵来实现
这个问题能否转换成别的更好实现的角度来思考？例如并不需要对元素进行完全的排序，只需要知道某个元素之前是否存在K-1个大于它的元素，就能确认该元素是否是第K大个元素


public static int findKNum(int[] a,int k){
    int n=a.length;
    int i =0;
    int kmax = a[n-1];
    for(int j=0;j<n;j++){
        if(a[j]>kmax){
            int temp = a[j];
            a[j]=a[i];
            a[i]=temp;
            i++;
        }
    }
    int temp = a[i];
    a[i]=a[n-1];
    a[n-1]=temp;
    //问题可以转换成前面有 k-1 个大于它的元素的元素是哪个
    if(i+1==k){
        return a[i];
    }else{
        return  i < k ? findKNum(a,k) : findKNum(Arrays.copyOf(a,i),k);
    }
}

借助之前分区方法进行改造，对数组进行排序，当数组被划分成大于 p 和小于 p 两部分时，对于位于 pindex 的 p 元素来说，有 pindex -1 个大于 p 的元素和 n-pindex 个小于它的元素，p是第 pindex+1 大的元素
在划分后的数组中查找第K大，有两种情况：
1. 一次分区排序之后，p位置大于等于 k 时，意味着第K大的元素在 p 之前
2. 反之，p 的位置小于 k时，说明第K大的元素位于 p 位置之后

¶小结

归并排序和快速排序是区别于冒泡，选择，插入排序的另外两种排序算法，从实现的思路看，它们都是对数组分区，进行排序，只是归并排序会先将数组划分至最小，再进行排序合并；快排是根据分区点进行数组排序，然后将划分成更小的分区进行排序
和其他三种排序相比，归并和快排都基于递归的思路，将数组的排序和合并划分成更小单元的数组排序和合并，典型的分治思想