「合并排序java算法」合并排序算法排序过程

admin 2023-01-07 07:21:09 640

本篇文章给大家谈谈合并排序java算法，以及合并排序算法排序过程对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

1、java中归并排序
2、JAVA归并排序算法，有两行代码看不懂
3、java十大算法
4、java合并排序
5、JAVA中的数组合并问题
6、java编程合并排序算法

java中归并排序

1、归并排序实现：

public static void main(String[] args) {

int a[]={1,8,2,6,5,4};

int[] arr= sort(a,0,a.length-1);

for(int rr=0;rr=5;rr++)

System.out.printf("%d\t", arr[rr]);

System.out.printf("\n");

}

public static int[] sort(int[] a,int low,int high){

int mid = (low+high)/2;

if(lowhigh){

sort(a,low,mid);

sort(a,mid+1,high);

//左右归并

merge(a,low,mid,high);

}

return a;

}

public static void merge(int[] a, int low, int mid, int high) {

int[] temp = new int[high-low+1];

int i= low;

int j = mid+1;

int k=0;

// 把较小的数先移到新数组中

while(i=mid j=high){

if(a[i]a[j]){

temp[k++] = a[i++];

}else{

temp[k++] = a[j++];

}

// 把左边剩余的数移入数组

while(i=mid){

temp[k++] = a[i++];

}

// 把右边边剩余的数移入数组

while(j=high){

temp[k++] = a[j++];

}

// 把新数组中的数覆盖nums数组

for(int x=0;xtemp.length;x++){

a[x+low] = temp[x];

}

2、简单的数组排序

public static void main(String[] args) {

int a[]={1,8,2,6,5,4};

Arrays.sort(a);

for(int rr=0;rr=5;rr++)

System.out.printf("%d\t", a[rr]);

System.out.printf("\n");

}

JAVA归并排序算法，有两行代码看不懂

以var a = [4,2,6,3,1,9,5,7,8,0];为例子。

1.希尔排序。希尔排序是在插入排序上面做的升级。是先跟距离较远的进行比较的一些方法。

过程输出：

[4, 9] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [2, 5] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [6, 7] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [3, 8] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "gap:5" [4, 2, 6, 3, 0, 9, 5, 7, 8, 1] [4, 6, 0, 5, 8] "gap:2" [0, 2, 4, 3, 5, 9, 6, 7, 8, 1] [2, 3, 9, 7, 1] "gap:2" [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1" [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

由输出可以看到。第一轮间隔为5。依次对这些间隔的数组插入排序。

间隔为5：

间隔为2：

[4, 2, 6, 3, 0, 9, 5, 7, 8, 1] 4 6 0 5 8 2 3 9 7 1

排序后：

[0, 1, 4, 2, 5, 3, 6, 7, 8, 9]

间隔为1：

排序后：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。

2.快速排序。把一个数组以数组中的某个值为标记。比这个值小的放到数组的左边，比这个值得大的放到数组的右边。然后再递归对左边和右边的数组进行同样的操作。直到排序完成。通常以数组的第一个值为标记。

代码:

3.归并排序。把一系列排好序的子序列合并成一个大的完整有序序列。从最小的单位开始合并。然后再逐步合并合并好的有序数组。最终实现归并排序。

合并两个有序数组的方法：

归并排序：

排序[4,2,6,3,1,9,5,7,8,0]输出：

left:4 right:2 left:6 right:3 left:1 right:9 left:5 right:7 left:8 right:0 left:2,4 right:3,6 left:1,9 right:5,7 left:0,8 right: left:2,3,4,6 right:1,5,7,9 left:0,8 right: left:1,2,3,4,5,6,7,9 right:0,8

看出来从最小的单位入手。

第一轮先依次合并相邻元素：4,2; 6,3; 1,9; 5,7; 8,0

合并完成之后变成： [2,4,3,6,1,9,5,7,0,8]

第二轮以2个元素为一个单位进行合并：[2,4],[3,6]; [1,9],[5,7]; [0,8],[];

合并完成之后变成：[2,3,4,6,1,5,7,9,0,8]

第三轮以4个元素为一个单位进行合并：[2,3,4,6],[1,5,7,9]; [0,8],[]

合并完成之后变成： [1,2,3,4,5,6,7,9,0,8];

第四轮以8个元素为一个单位进行合并： [1,2,3,4,5,6,7,9],[0,8];

合并完成。 [0,1,2,3,4,5,6,7,8,9];

java十大算法

算法一：快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤：

1 从数列中挑出一个元素，称为 "基准"（pivot），

2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

算法二：堆排序算法

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序的平均时间复杂度为Ο(nlogn) 。

算法步骤：

创建一个堆H[0..n-1]

把堆首（最大值）和堆尾互换

3. 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

4. 重复步骤2，直到堆的尺寸为1

算法三：归并排序

归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法步骤：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置

3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4. 重复步骤3直到某一指针达到序列尾

5. 将另一序列剩下的所有元素

java合并排序

从

代码

可以看出楼主是一个

新手

，你的这个错误是

Comparable

a[]

{3,

12,

};这里，

3,6,4这些数据不是Comparable

实现类，为什么会不是呢？为什么会在这里出错呢？我猜测楼主的这个代码曾经在别的环境下可以运行的，你这里错误的应该是

你现在

的JDK是1.4的，活着你的编译环境是1.4的，而要Comparable

a[]

{3,

12,

};能被正常编译需要在1.5的环境下，因为1.5的

特性

使得3,6,4这些

数字

可以当作一个Integer

对象

来处理，而Integer类是实现了Comparable

接口

的。

下面是如果你是用eclipse的话，右键点击项目－－properties---JAVA

compiler修改编译环境

JAVA中的数组合并问题

首先~~你必须明白Arrays.sort()的作用

我解释下sort()是根据元素的自然顺序，对指定对象数组按升序进行排序。数组中的所有元素都必须实现

Comparable

接口。此外，数组中的所有元素都必须是可相互比较的（也就是说，对于数组中的任何

和

元素而言，e1.compareTo(e2)

不得抛出

ClassCastException）。

保证此排序是稳定的：不会因调用

sort

方法而对相等的元素进行重新排序。

该排序算法是一个经过修改的合并排序算法（其中，如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并）。此算法提供可保证的

n*log(n)

性能。n*log(n)指的是执行时间

该例子中

Student类实现了Comparable接口compareTo()是接口中指定的排序函数~~实现了这个函数sort()方法会自动去进行比较从而实现排序

为什么常量放在前面？

~~这只是习惯问题

name.compareTo(ss.name);这句调用的是String中的compareTo方法而不是Student类中的

Student

(Student)o;是对传入的对象o进行强制转化为Student类型转化的对象为ss，个人觉得可以不写

result

num

ss.num

:(num==ss.num

-1)这句要从后面()之间的看起，如果this.num==ss.num的话返回0的值，否则返回-1，前面的意思是如果this.num大于ss.sum的话返回1，其他情况由后面的定也就是对Student对象根据num属性进行排序

学java的话~~我可以发给帮助文档给你~~~

java编程合并排序算法

package p1;

import java.util.Arrays;

public class Guy

{

/**

* 归并排序

private static void mergeSort ( int[] array, int start, int end, int[] tempArray )

{

if (end = start)

{

return;

}

int middle = ( start + end ) / 2;

mergeSort (array, start, middle, tempArray);

mergeSort (array, middle + 1, end, tempArray);

int k = 0, leftIndex = 0, rightIndex = end - start;

System.arraycopy (array, start, tempArray, 0, middle - start + 1);

for ( int i = 0; i end - middle; i++ )

{

tempArray[end - start - i] = array[middle + i + 1];

}

while (k end - start + 1)

{

if (tempArray[rightIndex] tempArray[leftIndex]) // 从小到大

{

array[k + start] = tempArray[leftIndex++];

}

else

{

array[k + start] = tempArray[rightIndex--];

}

k++;

}

public static void main ( String[] args )

{

int[] array = new int[] { 11, 213, 134, 65, 77, 78, 23, 43 };

mergeSort (array, 0, array.length - 1, new int[array.length]);

System.out.println (Arrays.toString (array));

}

关于合并排序java算法和合并排序算法排序过程的介绍到此就结束了，不知道你从中找到你需要的信息了吗？如果你还想了解更多这方面的信息，记得收藏关注本站。

标签：合并排序java算法