排序（二）：分而治之——快速排序 && 归并排序

1. 在待排序的N个记录中任取一个元素(通常取第一个记录)作为基准，称为基准记录；
2. 定义两个索引 left 和 right 分别表示“首索引” 和 “尾索引”，key 表示“基准值”；
3. 首先，尾索引向前扫描，直到找到比基准值小的记录(left != right)，并替换首索引对应的值；
4. 然后，首索引向后扫描，直到找到比基准值大于的记录(left != right)，并替换尾索引对应的值；
5. 若在扫描过程中首索引等于尾索引(left >= right)，则一趟排序结束；将基准值(key)替换首索引所对应的值；
6. 再进行下一趟排序时，待排序列被分成两个区:[0,left-1]，[right+1,end]
7. 对每一个分区重复步骤2~6，直到所有分区中的记录都有序，排序成功。

示意图如下：

class Solution {
    public int[] sortArray(int[] nums) {
        quicksort(nums, 0, nums.length-1);
        return nums;
    }

    public void quicksort(int[] nums, int left, int right){
        if(left > right)  //一定要加，否则当left < 0 或 left >= nums.length 时越界
            return;
        int pos = partition(nums, left, right);
        quicksort(nums, left, pos-1);
        quicksort(nums, pos+1, right);
    }

    public int partition(int[] nums, int low, int high){
        int base = nums[low];       
        int left = low, right = high;
        while(left < right){
            while(left < right && nums[right] >= base)
                right--;
            if(left < right)
                nums[left] = nums[right];
            while(left < right && nums[left] < base)
                left++;
            if(left < right)
                nums[right] = nums[left];
        }
        nums[left] = base;  
        return left;   
    }

内部循环的另一种写法，该方法需要自己编写一个数组元素交换函数 void swap(int[] nums, int left, int right)：

while (left=base) right--;  
    while (left 
时间复杂度 
最坏情况：最坏情况是序列已经有序，且选取的枢轴是最小的元素，导致划分后的问题规模是 0 和 n-1，然后接下来枢轴仍然是最小值。给出一个例子，”1, 2, 3, 4, 5, 6, 7, 8, 9, 10“，假设每次选取第一个元素作为枢轴，那么这个序列就对应着最坏情况，需要交换 
     
      
       
        
         
          2
         
         
          
           n
          
          
           (
          
          
           n
          
          
           −
          
          
           1
          
          
           )
          
         
        
       
       
        frac{2}{n(n-1)}
       
      
     n(n−1)2​。时间复杂度为 
     
      
       
        
         W
        
        
         (
        
        
         n
        
        
         )
        
        
         
          ∈
         
         
          O
         
         
          (
         
         
          
           n
          
          
           2
          
         
         
          )
         
         
          )
         
        
       
       
        W(n) displaystyle in O(n^2))
       
      
     W(n)∈O(n2)) 。
平均时间复杂度：
     
      
       
        
         A
        
        
         (
        
        
         n
        
        
         )
        
        
         
          ∈
         
         
          O
         
         
          (
         
         
          n
         
         
          l
         
         
          o
         
         
          g
         
         
          (
         
         
          n
         
         
          )
         
         
          )
         
         
          )
         
        
       
       
        A(n) displaystyle in O(nlog(n)))
       
      
     A(n)∈O(nlog(n)))
 
代码优化 
改进措施：
 
递归：因为递归调用过程是要消耗计算资源的，因此可以改为非递归
小排序问题：对于数量较小的数组，排序可以使用其他排序算法。例如在 C++的STL库中，sort() 函数在 num < 16 时采用的是插入排序。
枢轴的选取–随机打乱、随机选择等等方法，一种方法是选择数组首元素、尾元素和中位元素的中位数作为枢轴，防止选到数组中最小元素。
 
*快排起始方向的选择问题：为什么一定要从右边开始 
 
 
参考链接：https://blog.csdn.net/he37176427/article/details/97795963
 
 
因为选择的基准值key一般都是最左边的元素。
 
假设左哨兵为i， 右哨兵为j， 选择的 key 为最左边的元素。也就是说，当首先从右边开始先执行时，循环的条件是:
 
while (i < j && array[j] >= key) j--;
 
最后 i、j 停留的位置的值一定是要小于 key 的，此时交换索引 i 和最左边元素 key 符合将小于 key 的值放到 key 左边这一条件。比较抽象，可以自己画一下图！
 
当首先从左边开始执行时
 
while (i < j && array[i] <= key) i++;
 
循环结束后的 i、j 停留的位置的大于 key，此时再交换 key 与索引位置 i 相当于把比key大的值放到了 key 左边，违背了快排的条件。
 
如果想先从左往右查找，只需把 key 设置在右侧即可。
 
同理，假如想排降序的也要从相反方向开始， 将两个循环条件的 >=、<= 的方向调换即可：
 
while (i < j && array[j] <= key) j--;

while (i < j && array[i] >= key) i++;
 
归并排序 
过程 
归并排序的思想是：将待排序序列划分成若干个有序子序列；将两个或两个以上的有序子序列合并为一个有序序列。
 
 归并排序特点：
 
有序子序列的数据元素的个数≤Merge算法的比较次数
Merge算法的比较次数≤2个子序列数据元素个数和-1
 
代码 
class Solution {
    //朴素归并排序
    public int[] sortArray(int[] nums) {
        mergesort(nums, 0, nums.length-1);
        return nums;
    }

    public void mergesort(int[] nums, int left, int right){
        if(left < right){
            int mid = (left + right)/2;
            mergesort(nums, left, mid);
            mergesort(nums, mid+1, right);
            merge(nums, left, mid, right);
        }
    }

    public void merge(int[] nums, int left, int mid, int right){
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = mid+1;
        int k = 0;
        while(i <= mid && j <= right){
            if(nums[i] < nums[j])
                temp[k++] = nums[i++];
            else
                temp[k++] = nums[j++];
        }
        while(i <= mid)
            temp[k++] = nums[i++];
        while(j <= right)
            temp[k++] = nums[j++];
        for(k = 0; k <= right - left; k++)
            nums[k+left] = temp[k];
    }
}
 
时间复杂度 
最坏情况：是最后一次比较两个有序子序列各自剩最后一个数据元素。例如（1,3,5,7）和（2,4,6,8）这个两个子序列合并一共需要比较n-1次，是最坏情况。此时时间复杂度为：
    
     
      
       
        W
       
       
        (
       
       
        n
       
       
        )
       
       
        
         ∈
        
        
         O
        
        
         (
        
        
         n
        
        
         l
        
        
         o
        
        
         g
        
        
         n
        
        
         )
        
       
      
      
       W(n) displaystyle in O(nlogn)
      
     
    W(n)∈O(nlogn)
 
最优情况：例如（1,2,3,4）和 (5,6,7,8) 这两个序列，只需要比较 n/2=8/2=4 次即可。此时时间复杂度为：
    
     
      
       
        B
       
       
        (
       
       
        n
       
       
        )
       
       
        
         ∈
        
        
         O
        
        
         (
        
        
         n
        
        
         l
        
        
         o
        
        
         g
        
        
         n
        
        
         )
        
       
      
      
       B(n) displaystyle in O(nlogn)
      
     
    B(n)∈O(nlogn)
 
平均时间复杂度：综上，归并排序是一种稳定的排序方法，平均时间复杂度为：
    
     
      
       
        A
       
       
        (
       
       
        n
       
       
        )
       
       
        
         ∈
        
        
         O
        
        
         (
        
        
         n
        
        
         l
        
        
         o
        
        
         g
        
        
         n
        
        
         )
        
       
      
      
       A(n) displaystyle in O(nlogn)
      
     
    A(n)∈O(nlogn)
 
代码优化 
有以下几种优化策略：
 
消除递归：避免递归过程的时间消耗。
最长无逆序子序列：我们经过分析知道，归并排序的基础是两个有序子序列的合并，那么我们可以通过寻找最长无逆序子序列来优化归并排序的比较次数。例如，（4，5，6，3，7，1）这个序列，我们找到三个无逆序子序列（[4]、[5]、[6]），直接对这三个子序列进行合并，减少比较次数。
小排序问题：划分为小序列时选用插入排序，合并到较长序列时采用归并排序。
不回写：重点 一般归并排序存在将备用序列 temp 写回原序列的 *** 作，这种写回 *** 作在大排序问题时非常浪费时间，思考一种不回写策略来解决这个问题。
 
优化一：二路归并排序：化递归为循环。将n个待排序的数据直接划分成n个规模为1的子序列，依次合并两个相邻有序子序列，直到只剩下一个有序子序列为止。
 
class Solution {
    //二路归并排序
    public void merge2(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = mid+1;
        int k = 0;
        while(i <= mid && j <= right){
            if(nums[i] < nums[j])
                temp[k++] = nums[i++];
            else
                temp[k++] = nums[j++];
        }
        while(i <= mid)
            temp[k++] = nums[i++];
        while(j <= right)
            temp[k++] = nums[j++];
        for(k = 0; k <= right - left; k++)
            nums[k+left] = temp[k];
    }
    
    // [i, i+len-1], [i+len, i+2*len-1]
    public int[] sortArray(int[] nums){
        int n = nums.length;
        int len = 1;
        while (len <= n) {
            int i;
            for (i = 0; i < n + 1 - 2 * len; i = i + 2 * len) {
                merge2(nums, i, i + len - 1, i + 2 * len - 1);
            }
            //剩余两个子列
            if (i + len - 1 < n) {
                merge2(nums, i, i + len - 1, n - 1);
            }
            //剩余1个子列 
            else;
            len *= 2;
        }
        return nums;
    }
}
 
优化二：不回写。奇数趟从原数组 nums[] 写到备用数组 temp[] ，偶数趟从 temp[] 写到 nums[]。如果做了奇数趟，排序结束，则需要将数据从 temp[] 写到 nums[]。
 
class Solution {    
    public void merge3(int[] nums, int[] temp, int left, int mid, int right) {
        int i = left;
        int j = mid+1;
        int k = left;
        while(i <= mid && j <= right){
            if(nums[i] < nums[j])
                temp[k++] = nums[i++];
            else
                temp[k++] = nums[j++];
        }
        while(i <= mid)
            temp[k++] = nums[i++];
        while(j <= right)
            temp[k++] = nums[j++];
    }

    public int[] sortArray(int[] nums) {
        int n = nums.length;
        int temp[] = new int[n];
        int len = 1;
        int flag = 1;
        while (len <= n) {
            if (flag == 1) {//通过flag来判定当前是奇数回合还是偶数回合
                flag = 0;
                int i;
                for (i = 0; i < n + 1 - 2 * len; i = i + 2 * len) {
                    merge3(nums, temp, i, i + len - 1, i + 2 * len - 1);
                }
                if (i + len - 1 < n) {
                    merge3(nums, temp, i, i + len - 1, n - 1);
                } else {
                    for (; i < n; i++) temp[i] = nums[i];
                }
                len *= 2;
            } 
            else {
                flag = 1;
                int i;
                for (i = 0; i < n + 1 - 2 * len; i = i + 2 * len) {
                    merge3(temp, nums, i, i + len - 1, i + 2 * len - 1);
                }
                if (i + len - 1 < n) {
                    merge3(temp, nums, i, i + len - 1, n - 1);
                } else {
                    for (; i < n; i++) nums[i] = temp[i];
                }
                len *= 2;
            }
        }
        if (flag == 0) {
            for (int p = 0; p < n; p++) {
                nums[p] = temp[p];
            }
        }
        return nums;
    }
}
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5694429.html