排序算法 - 归并&快排

布满荆棘的人生 2022-12-26 07:29 137阅读 0赞

### 文章目录 ###

*  1. 归并排序
 *   *  借助额外空间和并
     *  空间优化
 *  2. 快速排序
 *   *  递归写法
     *  非递归写法
     *  性能改进

# 1. 归并排序 #

> 平均时间复杂度：O(nlogn)  
> 最佳时间复杂度：O(n)  
> 最差时间复杂度：O(nlogn)  
> 空间复杂度：O(n)  
> 排序方式：In-place  
> 稳定性：稳定

归并排序的思想就是将问题细分成小问题，最后将容易的小问题汇集就解决了全局的问题。一句话来说，**局部有序 ·合并· 成全局有序。**

## 借助额外空间和并 ##

写归并排序建议先从合并写起，我们的基础条件就是将两个有序的数组合并成一个大数组，且这个大数组在合并过程中要保持他有序。并且后面优化的时候，基本上就是在merge方法上进行优化。

/** * 合并保证 合并的区间有序 * @param left 输入区间有序 * @param right 输入区间有序 * @return */
        private int[] merge(int[] left, int[] right) { 
            int le_len = left.length;
            int ri_len = right.length;
    
            int[] merge = new int[ri_len + le_len];
            //当前的左右指针位置
            int left_index = 0, right_index = 0;
            for (int i = 0; i < merge.length; i++) { 
                //是否已经获取完
                if (left_index >= le_len) { 
                    merge[i] = right[right_index++];
                } else if (right_index >= ri_len) { 
                    merge[i] = left[left_index++];
                } else if (left[left_index] > right[right_index]) { 
                    merge[i] = right[right_index++];
                } else { 
                    merge[i] = left[left_index++];
                }
            }
            return merge;
        }

if else太多？来看下面一个版本

public static int[] merge(int[] left, int[] right) { 
            int[] merge = new int[left.length + right.length];
            int l = 0, r = 0;
            for (int i = 0; i < merge.length; i++) { 
                if (l == left.length) { 
                    merge[i] = right[r++];
                    continue;
                }
                if (r == right.length) { 
                    merge[i] = left[l++];
                    continue;
                }
                merge[i] = left[l] <= right[r] ? left[l++] : right[r++];
            }
            return merge;
        }

通过测试我们merge两个有序数组是没有问题的，接着来写排序的主体函数，因为我们现在已经解决了两个数组的有序。那么我们该如何将整个数组逐渐的划分呢？

思路便是 - 迭代 or 递归。

我们取数组中间的index起将数组进行划分，直到我们将数组划分成一个元素的时候停止。即二分。并且划分过程中，我们不考虑节省空间问题，每划分一次就划分出一个新数组。

代码如下：

public static int[] mergeSort(int[] arr) { 
            int len = arr.length;
            if (len < 2) return arr;
            int[] left = Arrays.copyOfRange(arr, 0, len / 2);
            int[] right = Arrays.copyOfRange(arr, len / 2, len);
            return merge(mergeSort(left), mergeSort(right));
        }

## 空间优化 ##

由于我们上面使用了  
![在这里插入图片描述][20201203174326559.png]  
这么多额外的空间，那么我们是否可以将我们要划分的数组放在原数组呢？  
显而易见，我们是可以的，只是我们需要将每次合并后的数组拷贝会原数组，这样我们能够重复利用原数组的空间，而且不会造成数据紊乱，毕竟我们只是排序数据，原有数据仍然在原数组内。

那么我们需要对原merge方法进行修改，因为需要合并的操作放到了一个数组内，那么我们需要三个指针来区分，要合并的两个区间。并且使用一个额外空间来进行存放合并后的数据，在合并完成后再将数据拷贝回原数组。至此，我们不再需要返回值。最终源arr即为排序好的结果。

代码如下：

/** * @param arr * @param left 左数组起始位置 * @param left_end 左数组结束位置+1 * @param right_end 左右数组长度之和 */
        public static void merge(int[] arr, int left, int left_end, int right_end) { 
            int[] merge = new int[right_end - left];
            int l = left, r = left_end;
            for (int i = 0; i < merge.length; i++) { 
                if (l == left_end) { 
                    merge[i] = arr[r++];
                    continue;
                }
                if (r == right_end) { 
                    merge[i] = arr[l++];
                    continue;
                }
                merge[i] = arr[l] <= arr[r] ? arr[l++] : arr[r++];
            }
    
            //拷贝回原数组
            for (int i = 0; i < merge.length; i++) { 
                arr[left + i] = merge[i];
            }
        }

首先得把merge测试通过。再写mergeSort：  
因为我们也得把arr给划分，那么我们需要用l，r，来代表这次需要划分的区域是那一部分，l指向该区间最左，r指向该区间最右。

public static void mergeSort(int[] arr, int l, int r) { 
            if (l < r) { 
                int mid = (l + r) / 2;
                //区间划分
                mergeSort(arr, 0, mid);
                mergeSort(arr, mid + 1, r);
                //区间划分好后，和自己的merge函数参数对照，因为我的merge方法左边界和右边界都是需要+1的，所以将区间参数和merge对应上即可。
                merge(arr, l, mid+1, r+1);
            }
        }

最后测试

public static void main(String[] args) { 
    // //left_end 设定 /2+1 right 就是数组长度
            int[] arr = { 5, 6, 7, 8, 9, 1, 2, 2, 3};
    // merge(arr, 0, 4, 8);
    // System.out.println(Arrays.toString(arr));
            //------------------------------------------------
            mergeSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
        }

建议先奇数个元素再测偶数个元素，再测乱序。一步步达成目标。

--------------------

现在再来回顾的话，我们的这次优化是省去了很大一部分空间的。那么还有可以优化的地方吗?  
我们来看看哪里还用到了空间。  
![在这里插入图片描述][20201203180954901.png]

很明显，我们在merge方法内每次merge都new了一个缓冲数组来存放存好了的数据。很显然这部分空间是可以复用的，修改merge代码，复用缓冲空间，通过在封装一层，我们的归并排序就已经接近完美了。

public class MergeSortDemo2 { 
        public static void mergeSort(int[] arr) { 
            int[] temp = new int[arr.length];
            //复用缓冲空间
            mergeSortHelper(arr, 0, arr.length - 1, temp);
        }
    
        public static void mergeSortHelper(int[] arr, int l, int r, int[] temp) { 
            if (l < r) { 
                int mid = (l + r) / 2;
                mergeSortHelper(arr, 0, mid, temp);
                mergeSortHelper(arr, mid + 1, r, temp);
                merge(arr, l, mid + 1, r + 1, temp);
            }
        }
    
        public static void main(String[] args) { 
    // //left_end 设定 /2+1 right 就是数组长度
            int[] arr = { 1, 2, 3, 5, 4, 6, 8, 7, 4, 2, 5, 6, 3, 1};
    // merge(arr, 0, 4, 8);
    // System.out.println(Arrays.toString(arr));
            //------------------------------------------------
            mergeSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        /** * @param arr * @param left 左数组起始位置 * @param left_end 左数组结束位置+1 * @param right_end 左右数组长度之和 * @param temp 缓冲区 */
        public static void merge(int[] arr, int left, int left_end, int right_end, int[] temp) { 
            int temp_le = right_end - left;
            int l = left, r = left_end;
            for (int i = 0; i < temp_le; i++) { 
                if (l == left_end) { 
                    temp[i] = arr[r++];
                    continue;
                }
                if (r == right_end) { 
                    temp[i] = arr[l++];
                    continue;
                }
                temp[i] = arr[l] <= arr[r] ? arr[l++] : arr[r++];
            }
    
            //拷贝回原数组
            for (int i = 0; i < temp_le; i++) { 
                arr[left + i] = temp[i];
            }
        }
    }

如果在想不使用这个缓冲区，那么有什么比较好的算法可以修改merge方法吗？  
其实可以想到，既然我们需要合并一个连续的两个区间，那么就是一个排序算法了，是否可以嵌套一个O（N2）的不需要额外空间的算法呢？其实没有这个必要，大多数时候，我们都有一个思想叫做空间换时间，如果，为了节省空间还走回原来的O（N2）的算法，那么我们突破效率也就没有什么意义了。或者说，根本上我们成为了将算法变成了分段排序，这本没有什么意义了，但是换个角度想，此乃外排序是也？  
以上个人拙见。

public static void mergehelper(int[] arr, int left, int right_end) { 
            Arrays.sort(arr, left, right_end+1);
        }
            public static void mergeSortHelper(int[] arr, int l, int r, int[] temp) { 
            if (l < r) { 
                int mid = (l + r) / 2;
                mergeSortHelper(arr, 0, mid, temp);
                mergeSortHelper(arr, mid + 1, r, temp);
    // merge(arr, l, mid + 1, r + 1, temp);
                mergehelper(arr, l, r);
            }
        }

# 2. 快速排序 #

快速排序是由冒泡排序改进而得到的，是一种分区交换排序方法。

> 平均时间复杂度：O(nlogn)  
> 最佳时间复杂度：O(nlogn)  
> 最差时间复杂度：O(n2)  
> 空间复杂度：O(logn)  
> 排序方式：In-place  
> 稳定性：不稳定

1、最坏情况

快速排序的最坏情况发生在当数组已经有序或者逆序排好的情况下。这样的话划分过程产生的两个区域中有一个没有元素，另一个包含n-1个元素。此时算法的运行时间可以递归地表示为：T(n) = T(n-1)+T(0)+Θ(n)，递归式的解为T(n)=Θ(n^2)。可以看出，快速排序算法最坏情况运行时间并不比插入排序的更好。

2、最好情况

如果我们足够幸运，在每次划分操作中做到最平衡的划分，即将数组划分为n/2:n/2。此时得到的递归式为T(n) = 2T(n/2)+Θ(n)，根据主定理的情况二可得T(n)=Θ(nlgn)。

3、平均情况

假设一：快排中的划分点非常偏斜，比如每次都将数组划分为1/10 : 9/10的两个子区域，这种情况下运行时间是多少呢？运行时间递归式为T(n) = T(n/10)+T(9n/10)+Θ(n)，使用递归树解得T(n)=Θ(nlgn)。可以看出，当划分点非常偏斜的时候，运行时间仍然是Θ(nlgn)。

--------------------

快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。在第一种情况中，递归调用发生在处理整个数组之前；在第二种情况中，递归调用发生在处理整个数组之后。在归并排序中，一个数组被等分为两半；在快速排序中，切分（partition）的位置取决于数组的内容。

核心要素就是基准元素怎么处理。这里主要探究他的递归写法和非递归写法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 1]

## 递归写法 ##

我们先来看看我们找到的一趟的快排方法应该如何写。  
首先我们确定第一个元素为基准元素，我们还需要一个首尾的指针。

public static void quickSortHelper(int[] arr) { 
            int pivot;
            int l = 0, r = arr.length - 1;
            pivot = arr[0];
            while (l < r) { 
                // 当队尾的元素大于等于基准数据时,向前挪动high指针
                // 我们需要找到一个比基准元素小的位置，第一个放入0 的位置，随后放入l的位置
                while (l < r && arr[r] >= pivot) { 
                    r--;
                }
                arr[l] = arr[r];
                while (l < r && arr[l] <= pivot) { 
                    l++;
                }
                arr[r] = arr[l];
            }
            //当我们的循环跳出的时候，我们还有个pivot 应当处理,应该放入哪儿?
            //debug 或者原理推导就可以发现 r = l
            arr[l] = pivot;
        }

测试方法如下：

//生成随机数组
     public static int[] gennerateArray(int len, int max) { 
            int[] arr = new int[len];
            for (int i = 0; i < arr.length; i++) { 
                arr[i] = (int) (Math.random() * max);
            }
            return arr;
        }
        public static void main(String[] args) { 
    
            QuickSort quickSort = new QuickSort();
            int[] nums = gennerateArray(10, 20);
            System.out.println("input: " + Arrays.toString(nums));
            quickSortHelper(nums);
            System.out.println("sorted: " + Arrays.toString(nums));
        }

![在这里插入图片描述][20201203202316886.png]  
![在这里插入图片描述][20201203222116222.png]

![在这里插入图片描述][20201203202346428.png]  
通过很多组测试发现，一次处理后，pivot的位置左边全部是比它小的，右边全部是比他大的，那么显而易见，我们接下来就是需要处理，它左边的区间和右边的区间，直到区间的长度为1，或者说，区间的首位指针相等。  
通过上面的书写，首位指针相等的条件是什么？

if(l<r)

我们需要给pivot加一个返回值，其值代表最后一次pivot的位置。而且为了节约空间，我们的操作选择在原数组上，那么我们就要修改quickSortHelper的方法，增加arr 上的区间处理。

public static int quickSortHelper(int[] arr, int low, int high) { 
            int pivot;
    
            int l = low, r = high;
            pivot = arr[low];
            System.out.println("pivot is: " + pivot);
            while (l < r) { 
                // 当队尾的元素大于等于基准数据时,向前挪动high指针
                // 我们需要找到一个比基准元素小的位置，第一个放入0 的位置，随后放入l的位置
                while (l < r && arr[r] >= pivot) { 
                    r--;
                }
                arr[l] = arr[r];
                while (l < r && arr[l] <= pivot) { 
                    l++;
                }
                arr[r] = arr[l];
            }
            //当我们的循环跳出的时候，我们还有个pivot 应当处理,应该放入哪儿?
            //debug 或者原理推导就可以发现 r = l
            arr[l] = pivot;
            return l;
        }

接下来就是写quickSort的主方法，将每次得到pivot从区间移除，取其左右区间，逐步缩小各区间，直到区间长度为1。退出递归体。

public static void quickSort(int[] arr, int left, int right) { 
            int pivot_index;
            if (left < right) { 
                pivot_index = quickSortHelper(arr, left, right);
                // 得到分界index 递归左右 知道 left >= right
                quickSort(arr, left, pivot - 1);
                quickSort(arr, pivot + 1, right);
            }
        }

## 非递归写法 ##

既然是非递归，那我们要知道，我们每次递归我们的方法栈中是保存了什么，或者说复用了什么。其实很容易就知道，当我们退出递归时，返回上一层，我们的该层方法中复用的是该层所匹配的pivot\_index与left和right，来进行下一次quickSort，而left和right又依赖于上一次的pivot\_index。既然是方法栈，那么我们就可以使用栈来实现这个简单的问题。

通过维护一个low ，high，每次循环只处理这么一个区间。处理一次我们可以通过得到pivot\_index 与存下的low，high进行比较，来判断是否能分出区间再进行处理。  
**但是得注意压栈与弹栈的顺序 push high low -> pop low high**

/** * 一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。 */
        public static void quickSort2(int[] arr) { 
            Stack<Integer> stack = new Stack<>();
            
            //注意:先push high 取得时候先pop low
            stack.push(arr.length - 1);
            stack.push(0);
    
            //这个时候的 left = 0 left_end = pivot_index - 1
            // right = arr.length - 1 right_start = pivot_index + 1
            while (!stack.isEmpty()) { 
                int low = stack.pop();
                int high = stack.pop();
    
                int pivot_index = quickSortHelper(arr, low, high);
                if (pivot_index + 1 < high) { 
                    stack.push(high);
                    stack.push(pivot_index + 1);
    
                }
                if (pivot_index - 1 > low) { 
                    stack.push(pivot_index - 1);
                    stack.push(low);
                }
            }
        }

## 性能改进 ##

和大多数递归排序算法一样，改进快速排序性能的一个简单办法基于以下两点：

*  对于小数组，快速排序比插入排序慢；
 *  因为递归，快速排序的sort()方法在小数组中也会调用自己。

**在排序小数组时应该切换到插入排序。**

/** * @param arr * @param left 要进行区分区间的左边界 * @param right 区间有边界 * @param M 认为需要进行直接排序的 区间大小 */
        public static void quickSortV2(int[] arr, int left, int right, int M) { 
            int pivot;
            if (left < right) { 
                if (left + M >= right) { 
                // 这里代替使用Arrays.sort
                    Arrays.sort(arr, left, right+1);
                    return;
                }
                pivot = quickSortHelper(arr, left, right);
                // 得到分界index 递归左右 知道 left >= right
                quickSortV2(arr, left, pivot - 1, M);
                quickSortV2(arr, pivot + 1, right, M);
            }
        }

**三取样切分**

改进快速排序性能的第二个办法是使用子数组的一小部分元素的中位数来切分数组。这样做得到的切分更好，但代价是需要计算中位数。  
即取最左最右最中间三个值的中位数作为pivot。

**Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割**

具体实现可百度。

[20201203174326559.png]: /images/20221120/1e0d63207f6140969ef16265ae8d18e8.png
[20201203180954901.png]: /images/20221120/eeefec7800034c24a17e8712c058f113.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70]: /images/20221120/ff69e5e933f340b1b9955aa19010e7a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 1]: /images/20221120/77e8e4bd6f654037a785cf4d5c2a2635.png
[20201203202316886.png]: https://img-blog.csdnimg.cn/20201203202316886.png
[20201203222116222.png]: https://img-blog.csdnimg.cn/20201203222116222.png
[20201203202346428.png]: https://img-blog.csdnimg.cn/20201203202346428.png