常用排序算法(三)归并排序、堆排序、基数排序

迈不过友情╰ 2022-05-16 04:35 223阅读 0赞

## [常用排序算法(一)插入排序、希尔排序、冒泡排序][Link 1] ##

## [常用排序算法(二)选择排序、快速排序][Link 2] ##

# 归并排序 #

**1. 基本思想：**  
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。  
首先考虑下如何将2个有序数列合并。这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

//将有序数组a[]和b[]合并到c[]中
    void MemeryArray(int a[], int n, int b[], int m, int c[])
    {
     int i, j, k;
    
     i = j = k = 0;
     while (i < n && j < m)
     {
         if (a[i] < b[j])
             c[k++] = a[i++];
         else
             c[k++] = b[j++]; 
     }
    
     while (i < n)
         c[k++] = a[i++];
    
     while (j < m)
         c[k++] = b[j++];
    }

解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成2组A，B，如果这2组组内的数据都是有序的，那么就可以很方便的将这2组数据进行排序。如何让这2组组内数据有序了？  
可以将A，B组各自再分成2组。依次类推，当分出来的小组只有1个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的2个小组就可以了。这样通过**先递归的分解数列**，**再合并数列**就完成了归并排序。

**2. 过程：**

![5550][]

归并排序

**3. 平均时间复杂度：**O(NlogN)  
归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N\*logN)。

**4. 代码实现：**

public static void merge_sort(int a[],int first,int last,int temp[]){
    
      if(first < last){
          int middle = (first + last)/2;
          merge_sort(a,first,middle,temp);//左半部分排好序
          merge_sort(a,middle+1,last,temp);//右半部分排好序
          mergeArray(a,first,middle,last,temp); //合并左右部分
      }
    }
    //合并 ：将两个序列a[first-middle],a[middle+1-end]合并
    public static void mergeArray(int a[],int first,int middle,int end,int temp[]){     
      int i = first;
      int m = middle;
      int j = middle+1;
      int n = end;
      int k = 0; 
      while(i<=m && j<=n){
          if(a[i] <= a[j]){
              temp[k] = a[i];
              k++;
              i++;
          }else{
              temp[k] = a[j];
              k++;
              j++;
          }
      }     
      while(i<=m){
          temp[k] = a[i];
          k++;
          i++;
      }     
      while(j<=n){
          temp[k] = a[j];
          k++;
          j++; 
      }
    
      for(int ii=0;ii<k;ii++){
          a[first + ii] = temp[ii];
      }
    }

# 堆排序 #

1.  **基本思想：**
    
    ![6660][]
    
     *  **图示：** （88,85,83,73,72,60,57,48,42,6）
        
        ![7770][]
        
        Heap Sort
2.  **平均时间复杂度：**O(NlogN)  
    由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N \* logN)。
3.  java代码实现

//构建最小堆
    public static void MakeMinHeap(int a[], int n){
     for(int i=(n-1)/2 ; i>=0 ; i--){
         MinHeapFixdown(a,i,n);
     }
    }
    //从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2  
    public static void MinHeapFixdown(int a[],int i,int n){
    
       int j = 2*i+1; //子节点
       int temp = 0;
    
       while(j<n){
           //在左右子节点中寻找最小的
           if(j+1<n && a[j+1]<a[j]){   
               j++;
           }
    
           if(a[i] <= a[j])
               break;
    
           //较大节点下移
           temp = a[i];
           a[i] = a[j];
           a[j] = temp;
    
           i = j;
           j = 2*i+1;
       }
    }
    
    public static void MinHeap_Sort(int a[],int n){
      int temp = 0;
      MakeMinHeap(a,n);
    
      for(int i=n-1;i>0;i--){
          temp = a[0];
          a[0] = a[i];
          a[i] = temp; 
          MinHeapFixdown(a,0,i);
      }     
    }

# 基数排序 #

BinSort

1.  **基本思想：**  
    BinSort想法非常简单，首先创建数组A\[MaxValue\]；然后将每个数放到相应的位置上（例如17放在下标17的数组位置）；最后遍历数组，即为排序后的结果。
2.  **图示：**
    
    ![88808][]
    
    BinSort
    
     *  **问题：** 当序列中存在较大值时，BinSort 的排序方法会浪费大量的空间开销。
    
    RadixSort
    
    1.  **基本思想：** 基数排序是在BinSort的基础上，通过基数的限制来减少空间的开销。
    2.  **过程：**
        
        ![10101001][]
        
        过程1
        
        ![9990][]
        
        过程2
    
    （1）首先确定基数为10，数组的长度也就是10.每个数34都会在这10个数中寻找自己的位置。  
    （2）不同于BinSort会直接将数34放在数组的下标34处，基数排序是将34分开为3和4，第一轮排序根据最末位放在数组的下标4处，第二轮排序根据倒数第二位放在数组的下标3处，然后遍历数组即可。
3.  **java代码实现：**

public static void RadixSort(int A[],int temp[],int n,int k,int r,int cnt[]){
    
       //A:原数组
       //temp:临时数组
       //n:序列的数字个数
       //k:最大的位数2
       //r:基数10
       //cnt:存储bin[i]的个数
    
       for(int i=0 , rtok=1; i<k ; i++ ,rtok = rtok*r){
    
           //初始化
           for(int j=0;j<r;j++){
               cnt[j] = 0;
           }
           //计算每个箱子的数字个数
           for(int j=0;j<n;j++){
               cnt[(A[j]/rtok)%r]++;
           }
           //cnt[j]的个数修改为前j个箱子一共有几个数字
           for(int j=1;j<r;j++){
               cnt[j] = cnt[j-1] + cnt[j];
           }
           for(int j = n-1;j>=0;j--){      //重点理解
               cnt[(A[j]/rtok)%r]--;
               temp[cnt[(A[j]/rtok)%r]] = A[j];
           }
           for(int j=0;j<n;j++){
               A[j] = temp[j];
           }
       }
    }

[Link 1]: https://blog.csdn.net/u010183728/article/details/81348339
[Link 2]: https://blog.csdn.net/u010183728/article/details/81625010
[5550]: /images/20220516/fcd148cdaa964fdba7a195763bf74403.png
[6660]: /images/20220516/07465bb52add41d88adb49ac2b447212.png
[7770]: /images/20220516/1eef415f0e7b4eabb5815e4bf0ef6c82.png
[88808]: /images/20220516/61db02f19f324022bf09c3831bdb604f.png
[10101001]: /images/20220516/28a220faae264a61afe4e241b821dbc0.png
[9990]: /images/20220516/b6d4c3327bb84d129c914a59099fa4b5.png