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

本文主要是介绍常用排序算法(三)归并排序、堆排序、基数排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

常用排序算法(一)插入排序、希尔排序、冒泡排序

常用排序算法(二)选择排序、快速排序

归并排序

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++];elsec[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. 过程：

归并排序

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. 基本思想：

   

   • 图示： （88,85,83,73,72,60,57,48,42,6）

     

     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. 图示：

   

   BinSort

   • 问题： 当序列中存在较大值时，BinSort 的排序方法会浪费大量的空间开销。

   RadixSort

   1. 基本思想： 基数排序是在BinSort的基础上，通过基数的限制来减少空间的开销。
   2. 过程：

      

      过程1

      

      过程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];}}
}

 

这篇关于常用排序算法(三)归并排序、堆排序、基数排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---