排序：归并排序和快速排序

梦里梦外; 2023-09-28 16:36 40阅读 0赞

力扣leetcode：912.排序数组，可以用来练习排序算法

题目：给你一个整数数组 `nums`，请你将该数组升序排列。

**目录**

归并排序

快速排序

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

归并和快排都运用了递归和分治的思想。归并：二叉树的后续遍历；快排：二叉树的前序遍历。

为什莫这么说呢？排序的核心代码框架：

归并排序
    public void sort(int[] nums,int low,int high){
            if(low == high) return;
            int mid = low + (high - low)/2;
            //对左半数组排序，nums[low...mid]
            sort(nums,low,mid);
            //对右半边数组排序，nums[mid+1...high]
            sort(nums,mid+1,high);
            
            //二叉树遍历的后续位置，合并nums[low...mid]和nums[mid+1...high]
            merge(nums,low,mid,high);
    }

先对左右数组进行排序，再合并。

快速排序
    public void sort(int[] nums,int low,int high){
            if(low >= high) return;
            //二叉树的前序位置，进行划分
            int p = partition(nums,low,high);
    
            //对划分的左半nums[low...p-1]进行排序
            sort(nums,low,p - 1);
            //对划分的右半nums[p+1...high]进行排序
            sort(nums,p + 1,high);
    }

先构造分界点，然后去左右子树组构造分界点。

#### 归并排序 ####

过程：

*  先将要进行排序的数组分为两部分Left和Right
 *  对Left部分排序
 *  对Right部分排序
 *  合并Left和Right两部分，合并成一个有序数组

代码：

class Solution {
        int[] temp; //归并排序的辅助数组
        public int[] sortArray(int[] nums) {
            //归并
            temp = new int[nums.length];
            sort(nums,0,nums.length-1);
            return nums;
    
        }
    
        public void sort(int[] nums,int low,int high){
            if(low == high) return;
            //有效防止溢出，其实和(low + high)/2等价
            int mid = low + (high - low)/2;
            //对左半数组排序
            sort(nums,low,mid);
            //对右半边数组排序
            sort(nums,mid+1,high);
            merge(nums,low,mid,high);
        }
    
        public void merge(int[] nums,int low,int mid,int high){
            //先将nums[low...high]的值存入辅助数组temp中
            for(int i = low;i <= high;i++){
                temp[i] = nums[i];
            }
            //双指针合并
            int i = low,j = mid + 1;
            for(int m = low; m <= high; m++){
                if(i == mid + 1) nums[m] = temp[j++];
                else if( j == high + 1) nums[m] = temp[i++];
                else if(temp[i] > temp[j]) nums[m] = temp[j++];
                else nums[m] = temp[i++]; 
            }
        }
    }

#### 快速排序 ####

快速排序是先将一个元素排好序，再将剩下的元素排好序。核心函数是partition函数：

过程：

*  是在nums\[low...high\]中寻找一个分界点p
 *  交换元素使得nums\[low...p-1\]的元素都小于等于nums\[p\]
 *  nums\[p+1...high\]的元素都大于nums\[p\]

partition其实就是把nums\[p\]这个元素排好序了

![233430ca956e49ad90dcec821dff191d.png][]

代码：

class Solution {
        public int[] sortArray(int[] nums) {
           //快排
           sort(nums,0,nums.length - 1);
           return nums;
        }
        public void sort(int[] nums,int low,int high){
            if(low >= high) return;
            //对nums[low...high]进行划分
            //使得nums[low...p-1] <= nums[p] < nums[p+1...high]
            int p = partition(nums,low,high);
            sort(nums,low,p - 1);
            sort(nums,p + 1,high);
        } 
    
        public int partition(int[] nums,int low,int high){
            int pivot = nums[low];
            int i = low + 1,j = high;
            while(i <= j){ //不断交换，直到满足左边都小于，右边都大于
                while(i < high && nums[i] <= pivot) i++; //该while结束的时候num[i] > pivot
                while(j > low && nums[j] > pivot) j--; //该while结束的时候num[j] <= pivot 
                if(i >= j) break;
                swap(nums,i,j); //将这两交换
            }
            //将pivot放到合适的位置上，pivot左边的元素比它小，pivot右边的元素比它大
            swap(nums,low,j);
            return j;
        }
        public void swap(int[] nums,int a,int b){
            int temp = nums[b];
            nums[b] = nums[a];
            nums[a] = temp;
        }
    }

![2f347f0401334e6a8d52c25ab5d4931e.png][]

[233430ca956e49ad90dcec821dff191d.png]: https://img-blog.csdnimg.cn/233430ca956e49ad90dcec821dff191d.png
[2f347f0401334e6a8d52c25ab5d4931e.png]: https://img-blog.csdnimg.cn/2f347f0401334e6a8d52c25ab5d4931e.png