转载:http://blog.csdn.net/pzhtpf/article/details/7560312
7、归并排序
(1)基本排序:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
(2)实例:
(3)用java实现
- import java.util.Arrays;
- public class mergingSort {
- int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
- public mergingSort(){
- sort(a,0,a.length-1);
- for(int i=0;i<a.length;i++)
- System.out.println(a[i]);
- }
- public void sort(int[] data, int left, int right) {
- // TODO Auto-generated method stub
- if(left<right){
- //找出中间索引
- int center=(left+right)/2;
- //对左边数组进行递归
- sort(data,left,center);
- //对右边数组进行递归
- sort(data,center+1,right);
- //合并
- merge(data,left,center,right);
- }
- }
- public void merge(int[] data, int left, int center, int right) {
- // TODO Auto-generated method stub
- int [] tmpArr=new int[data.length];
- int mid=center+1;
- //third记录中间数组的索引
- int third=left;
- int tmp=left;
- while(left<=center&&mid<=right){
- //从两个数组中取出最小的放入中间数组
- if(data[left]<=data[mid]){
- tmpArr[third++]=data[left++];
- }else{
- tmpArr[third++]=data[mid++];
- }
- }
- //剩余部分依次放入中间数组
- while(mid<=right){
- tmpArr[third++]=data[mid++];
- }
- while(left<=center){
- tmpArr[third++]=data[left++];
- }
- //将中间数组中的内容复制回原数组
- while(tmp<=right){
- data[tmp]=tmpArr[tmp++];
- }
- System.out.println(Arrays.toString(data));
- }
- }
8、基数排序
(1)基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
(2)实例:
(3)用java实现
- import java.util.ArrayList;
- import java.util.List;
- public class radixSort {
- int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,25,53,51};
- public radixSort(){
- sort(a);
- for(int i=0;i<a.length;i++)
- System.out.println(a[i]);
- }
- public void sort(int[] array){
- //首先确定排序的趟数;
- int max=array[0];
- for(int i=1;i<array.length;i++){
- if(array[i]>max){
- max=array[i];
- }
- }
- int time=0;
- //判断位数;
- while(max>0){
- max/=10;
- time++;
- }
- //建立10个队列;
- List<ArrayList> queue=new ArrayList<ArrayList>();
- for(int i=0;i<10;i++){
- ArrayList<Integer> queue1=new ArrayList<Integer>();
- queue.add(queue1);
- }
- //进行time次分配和收集;
- for(int i=0;i<time;i++){
- //分配数组元素;
- for(int j=0;j<array.length;j++){
- //得到数字的第time+1位数;
- int x=array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
- ArrayList<Integer> queue2=queue.get(x);
- queue2.add(array[j]);
- queue.set(x, queue2);
- }
- int count=0;//元素计数器;
- //收集队列元素;
- for(int k=0;k<10;k++){
- while(queue.get(k).size()>0){
- ArrayList<Integer> queue3=queue.get(k);
- array[count]=queue3.get(0);
- queue3.remove(0);
- count++;
- }
- }
- }
- }
- }
相关推荐
数据结构排序选择排序归并排序基数排序PPT学习教案.pptx
数据结构课件:第10章 排序2选择排序归并排序基数排序.pptx
本文主要介绍了五种内部排序算法:插入排序、交换排序、选择排序、归并排序和基数排序。 1. **插入排序**: 插入排序的基本思想是从未排序的序列中取出一个元素,然后将其插入到已排序序列的正确位置,以保持序列...
### 数据结构:归并排序与基数排序详解 #### 归并排序详解 归并排序(Merging Sort)是一种高效的排序算法,属于分治法的一种应用。它的核心思想是将数组分成若干个小数组,然后逐一合并这些小数组,最终形成一个...
- C# 实现基数排序时,需要创建多个桶,按位进行分配和收集,适用于处理整数排序。 8. **希尔排序**(Shell Sort): - 希尔排序是插入排序的改进版,通过设置间隔序列来减少元素的比较次数,使元素能够更快地...
2.归并排序;3.基数排序。 北工大电控学院《数据结构与算法》课程的其它章节实验及作业程序代码亦已在本站上传,需要的同学可进入作者的空间或通过搜索获取。本代码为上传者原创,仅供个人学习参考使用,请勿自行在...
以下是关于"插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序"这十大经典排序算法的详细解释: 1. 插入排序:插入排序是一种简单的排序算法,它通过构建有序...
归并排序和基数排序是两种不同的排序算法,它们在实现方式和效率特点上存在显著差异。 **归并排序**是一种基于分治策略的排序算法。它的基本思想是将待排序的序列分成两个长度相等(或近似相等)的部分,分别对这两...
试通过随机数据比较归并排序、基数排序各算法的关键字比较次数和关键字移动次数。 (1)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有。关键字...
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
C语言所有排序大全,解决了您日常上课考试学习的需要,在这里每一个程序都没有错误,其中压缩包包括了归并排序;基数排序;快速排序;冒泡排序;选择排序;折半排序;希尔排序这些日常排序,因为是全集所以大家踊跃...
- 基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。 - 在C++中,基数排序通常用到多路归并的思想,利用数组或队列存储每一位的值,并按照从小到大的顺序进行...
"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式基数排序。 基本要求: 待排序表的表长不...
理解归并排序的算法思想及其算法...本资源摘要信息详细介绍了归并排序和基数排序的算法思想及其算法设计,涵盖了这些算法的定义、算法思路、实现过程、时间复杂度分析等方面的内容,为读者提供了一个系统的学习指南。
归并排序和基数排序是两种不同的排序算法,它们在数据结构和算法领域有着重要的应用。 归并排序(Merge Sort)是一种基于分治策略的排序算法。它的主要思想是将大问题分解成小问题来解决,然后将小问题的解合并成大...
在提供的代码片段中,`MergeSort1`函数展示了归并排序的另一种实现方式,即迭代版本的归并排序。 ```cpp void Merge(int r[], int r1[], int s, int m, int t) { int i = s, j = m + 1, k = s; while (i ) { if ...
采用c++描述了各种排序算法,包括选择排序 冒泡排序 插入排序 基数排序 快速排序 归并排序 。实验内容 1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、*基数排序、*快速排序、*归并排序。 3、*能够...
在计算机科学领域,排序...而当需要稳定排序且数据量较大时,归并排序和基数排序是更好的选择;对于大规模无序数据,快速排序和堆排序通常能提供较高的性能。在实际编程中,根据具体需求选择合适的排序算法至关重要。