复旦大学961-数据结构-第四章-排序（三）合并排序,基数排序；排序算法复杂度总结

╰+攻爆jí腚メ 2022-12-13 01:50 140阅读 0赞

[961全部内容链接][961]

### 文章目录 ###

*  合并排序（归并排序）
 *  基数排序
 *  排序算法总结

# 合并排序（归并排序） #

归并排序与快速排序都是基于分治（分而治之）思想。基本思想为：将数组分为两部分，然后分别对这两部分进行排序，然后再将其合并。而对于这两部分的排序，也是用归并排序递归进行。

关键在于如何合并（Merge）。基本思想为：申请有一个数组，这个数组的大小是两个要合并数组的总和，然后依次对比这两个数组中的元素，然后填充到新数组中。

例如：

合并前，A数组有个i指针指向数组第一个元素。B数组为指针j，也指向第一个元素。然后比较A\[i\]和B\[j\]，将小的那个放入新数组，然后移动小的那个指针。比如第一次 A\[0\] < B\[0\]，那么 i=0+1, j不动。直到两个数组中的元素都被放入到新数组中。

Java代码如下：

public static void mergeSort(Comparable[] array) { 
        mergeSort(array, 0 ,array.length - 1);  // 对整个数组进行归并排序
    }
    
    private static void mergeSort(Comparable[] array, int left, int right) { 
        if (left >= right) return;  // 如果left>=right，则说明只有一个元素或没有元素，所以不用归并。
    
        int mid = (right + left) / 2; // 求中间位置，这个是易错点。
        mergeSort(array, left, mid);  // 将左边递归的进行归并排序
        mergeSort(array, mid + 1, right);  // 将右边递归的进行归并排序
        merge(array, left, right);  // 将递归排序后的左右两边进行合并
    }
    
    private static void merge(Comparable[] array, int left, int right) { 
        int mid = (right + left) / 2;
        Comparable[] temp = new Comparable[mid - left + 1];  // 申请一个辅助空间，大小为左数组的大小
        for (int i=0; i <temp.length;i++) {   // 将左数组复制到放入辅助空间中
            temp[i] = array[left + i];
        }
    
        int i=0, j = mid + 1;  // 记录左数组（辅助空间）和右数组合并到的位置
        while (i<temp.length && j < right + 1) {   // 若左数组合并完或右数组合并完，则跳出循环
            if (temp[i].compareTo(array[j]) < 0) {   // 若左数组的元素大，则将左数组元素复制到left的位置，并将i++
                array[left] = temp[i];
                i++;
            } else { 
                array[left] = array[j];  // 若右数组的元素大，则将右数组元素复制到left的位置，并将j++
                j ++;
            }
            left++; // 最后将left++
        }
    
        for (; i < temp.length; i++) {   // 复制完成后，若左数组还有剩余，将左数组剩下的全部复制过去。
            array[left] = temp[i];
            left++;
        }
    
        // 若右数组还有剩余，则什么都不用做，因为本身就在数组中，没有动。
    }

易错点：

1.  递归的mergeSort中，if (left >= right) return;别忘了
2.  求mid时，是 left+(right-left)/2 = (left+right)/2

复杂度分析：  
空间复杂度：O(n)  
时间复杂度：O(n \* log n) 不管元素长什么样，都是一个步骤，不会有差别。

稳定性：稳定。归并时并不会改变相同元素的相对位置。

适用性：只适用于顺序存储

# 基数排序 #

基数排序不同于其他的排序，他不是一个基于比较的排序。举个例子，比如对这一串数据进行排序

89,75,61,77,55,42,78,62,41

它的特点是①由数字组成，②每位数字不超过2位数（根据位数决定几趟排序）。

由于数字只有十位数（称为**基数（radix）**），所以首先新建一个10大小的数组，该数组的每个格子称为一个**桶**。

1.  然后开始第一趟排序，第一趟排序是按照个位，将个位的值放入对应的数组下标中。个位重复的话，就使用链表串起来，该过程称为**分配**，如图所示

然后对数组中的数据进行收集，从0开始依次将其串联起来，该过程称为**收集**。

61->41->42->62->75->55->77->78->89

1.  然后开始进行第二趟排序，与第一趟一样，这次是按照十位来放入数组对应的下标中，结果如图：

再次进行收集操作，得下列序列  
41->42->55->61->62->75->77->78->89  
排序完成

Java代码如下：

public static void radixSort(Integer[] array, int n) { 
        LinkedList<Integer> numList = new LinkedList<Integer>(); // 将array数据存放到linkedList中，方便操作
        for (int i = 0; i < array.length; i++) { 
            numList.add(array[i]);
        }
    
        LinkedList<Integer>[] lists = new LinkedList[10]; // 初始化10个桶。用于匹配下标后的数据
        for (int i = 0; i < lists.length; i++) { 
            lists[i] = new LinkedList<>();
        }
    
        for (int i = 1; i < Math.pow(10, n); i = i *10) {   // 根据位数循环，2位循环两次，3位循环3次
            Integer item = null;
            while (numList.peekFirst() != null) {   // 查看链表中是否还有数据未分配到桶中
                item = numList.removeFirst(); // 从链表中取一个元素，放入桶中
                lists[item/i%10].add(item);
            }
    
    
            for (int j = 0; j < lists.length; j++) {  // 进行收集操作，收集完该桶后，清空该桶，用于下一轮排序
                numList.addAll(lists[j]);
                lists[j].clear();
            }
        }
        for (int i = 0; i < numList.size(); i++) {   // 链表的数据已经有序，重新放回数组
            array[i] = numList.get(i);
        }
    }

复杂度分析：  
空间复杂度：因为申请了一个数组，该数组的大小为基数大小( r )，所以空间复杂度为O( r )。  
时间复杂度：整个基数排序需要经过 d 趟的排序（d为数据的最大位数），每趟排序要经历分配和收集两个过程，分配过程要遍历n个（排序数组大小）元素，收集要遍历r（基数）大小的数组。所以时间复杂度为 O(d(n+r))

稳定性：稳定。在收集和分配过程中，并不存在两个相同的元素相对位置被交换。所以是稳定的。鸡(基)你太美（稳）

适用性：可以适用于顺序存储和链式存储。但只适用与元素位数相对固定，且每位的基数大小固定。字母也可以排序，它的基数是26(26个英文字母)

# 排序算法总结 #

<table> 
 <thead> 
  <tr> 
   <th>算法名称</th> 
   <th>最优时间复杂度</th> 
   <th>平均时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
   <th>适用性</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>直接插入排序</td> 
   <td>O(n)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
   <td>顺序存储和链式存储</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>O(n<sup>1.3</sup>)</td> 
   <td>O(n<sup>1.3</sup>)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
   <td>顺序存储</td> 
  </tr> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(n)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
   <td>顺序存储和链式存储</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(n*log n)</td> 
   <td>O(n*log n)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n)</td> 
   <td>不稳定</td> 
   <td>顺序存储</td> 
  </tr> 
  <tr> 
   <td>简单选择排序</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
   <td>顺序存储和链式存储</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(n*log n)</td> 
   <td>O(n*log n)</td> 
   <td>O(n*log n)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
   <td>顺序存储</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>O (n*log n)</td> 
   <td>O (n*log n)</td> 
   <td>O (n*log n)</td> 
   <td>O(n)</td> 
   <td>稳定</td> 
   <td>顺序存储</td> 
  </tr> 
  <tr> 
   <td>基数排序</td> 
   <td>O(d*(n+r))</td> 
   <td>O(d*(n+r))</td> 
   <td>O(d*(n+r))</td> 
   <td>O ( r )</td> 
   <td>稳定</td> 
   <td>顺序存储和链式存储，元素需可基</td> 
  </tr> 
 </tbody> 
</table>

[961]: https://blog.csdn.net/zhaohongfei_358/article/details/111414370