正文
插入法堆的java代码的简单介绍
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
插入法排序
用插入法进行排序代码如下
package test;
import java.util.*;
class InsertSort
{
ArrayList al;
public InsertSort(int num,int mod)
{
al = new ArrayList(num);
Random rand = new Random();
System.out.println("The ArrayList Sort Before:");
for (int i=0;inum ;i++ )
{
al.add(new Integer(Math.abs(rand.nextInt()) % mod + 1));
System.out.println("al["+i+"]="+al.get(i));
}
}
public void SortIt()
{
Integer tempInt;
int MaxSize=1;
for(int i=1;ial.size();i++)
{
tempInt = (Integer)al.remove(i);
if(tempInt.intValue()=((Integer)al.get(MaxSize-1)).intValue())
{
al.add(MaxSize,tempInt);
MaxSize++;
System.out.println(al.toString());
} else {
for (int j=0;jMaxSize ;j++ )
{
if
(((Integer)al.get(j)).intValue()=tempInt.intValue())
{
al.add(j,tempInt);
MaxSize++;
System.out.println(al.toString());
break;
}
}
}
}
System.out.println("The ArrayList Sort After:");
for(int i=0;ial.size();i++)
{
System.out.println("al["+i+"]="+al.get(i));
}
}
public static void main(String[] args)
{
InsertSort is = new InsertSort(10,100);
is.SortIt();
}
}
JAVA类实现序例化的方法是实现java.io.Serializable接口
Collection框架中实现比较要实现Comparable 接口和 Comparator 接口
相关问答
Q1: n=2^k时，n是元素的个数。用插入法建立堆，求解元素的比较次数。
元素的比较次数是nlogn-2n+2
#include iostream
#include chrono
#include random
using namespace std;
int cnt;//统计元素比较次数
//作为堆的数组H[]及被上移的元素下标i
//维持堆的性质的数组H[]
templateclass Type
void sift_up(Type H[], int i) {
bool done = false;
while (!donei != 1) {
if (H[i] H[i / 2]) {
cnt++; //比较次数加1
swap(H[i], H[i / 2]);
}
else done = true;
i = i / 2;
}
}
//作为堆的数组H[],堆的元素个数n,被插入的元素x
//维持堆的性质的数组H[]
templateclass Type
void insert(Type H[], int n, Type x) {
n = n + 1;
H[n] = x;
sift_up(H, n);
}
//建造堆的第一种算法
//数组H[]，数组的元素个数n
//n个元素的堆 H[]
templateclass Type
void make_heap1(Type A[], Type H[], int n) {//插入法建立堆
int i, m = 0;
for (i = 0; i = n; i++)
insert(H, m, A[i]);
}
unsigned seedl = std::chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 mt(seedl);
//std::mt19937 mt(0);
int main() {
int A[20000];
int B[20000];
int n;
for (int j = 1; j = 5; j++) {
n = pow(2, j);
for (int i = 0; i n; i++)
A[i] = mt() % (2 * n);
cout "数组A为：";
for (int i = 0; i n; i++)
cout A[i] " ";
cout endl;
cnt = 0;
make_heap1(A, B, n);
cout "堆B为：";
for (int i = 1; i = n; i++)
cout B[i] " ";
cout endl;
cout "比较次数为：" cnt endl;
cout endl;
}
return 0;
}
Q2: 用JAVA编写插入法对一个给定数组进行升序排序的方法
//用冒泡插入法堆的java代码，就是for循环里加if判断就行插入法堆的java代码了。
class Test{
public static void main(String [] args){
int a[10]={2,1,4,5,6,7,8,9,23,44};
for (i=0;ia.length;i++)
{
for (j=0;ja.length-1-i;j++)
{
if (a[j]a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for (i=0;ia.length;i++){
System.out.println(a[i]);
}
}
}
Q3: java程序排序
自己写插入法堆的java代码的三种传统排序法。快排法主要是自己也没怎么搞明白……
（插入法堆的java代码你可以建数组来存数据插入法堆的java代码，就不写完整的了。）
public void insert(int[] a3) {//插入排序法
// TODO Auto-generated method stub
System.out.println("插入法");
int temper=0;
for(int i=1;ia3.length;i++){
for(int j=i;j0;j--){
if(a3[j]a3[j-1]){
temper=a3[j];
a3[j]=a3[j-1];
a3[j-1]=temper;
}else break;
}
}
}
//插入排序法完
//选择排序法
public void select(int[] a2) {
// TODO Auto-generated method stub
System.out.println("选择排序法");
int temper=0;
for (int i = 0; i a2.length-1; i++) {
int min = a2[i];
int minFoot = i;
for (int j = i + 1; j a2.length; j++) {
if (min a2[j]) {
min=a2[j];
minFoot=j;
}
}
temper=a2[i];
a2[i]=min;
a2[minFoot]=temper;
}
}
//选择排序法完
//冒泡排序法
public void Bubbling(int[] a1) {
System.out.println("冒泡排序法");
int temper = 0;
for (int i = 0; i a1.length - 1; i++) {
for (int j = 0; j a1.length - 1 - i; j++) {
if (this.a1[j] this.a1[j + 1]) {
temper = a1[j];
a1[j] = a1[j + 1];
a1[j + 1] = temper;
}
}
}
}
//冒泡排序法完
Q4: 如何根据一个数组建立最大堆
最大堆：根结点的键值是所有堆结点键值中最大者的堆。 最小堆：根结点的键值是所有堆结点键值中最小者的堆。 而最大-最小堆集结了最大堆和最小堆的优点，这也是其名字的由来。 最大-最小堆是最大层和最小层交替出现的二叉树，即最大层结点的儿子属于最小层，最小层结点的儿子属于最大层。 以最大（小）层结n点为根结点的子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。 主要操作不失一般性，只讨论根结点为最小层的情况。插入 只需要将节点插在二叉树的最后一个叶子结点位置，然后比较它对它父亲节点的大小，如果大则停止；如果小则交换位置，然后对父亲节点递归该过程直至根节点。复杂度为O(log(n))。 一般来说，插入的位置可以不是最后一个叶子节点，可以作为任意中间节点的孩子节点插入，将这个叶子节点变为中间节点后，按上文所说的方法调整节点顺序以保证维持堆特性不变。删除 要从堆中删除一个节点，用最后一个节点替换掉根节点，然后调整节点顺序以维持堆特性。建堆既可以用堆调整方法将原数组调整为一个堆，也可以借助往堆中插入元素的方法从无到有的建立一个堆。两种方法比较：（1）借助堆调整建堆的时间复杂度为O(n)。借助插入法建堆的时间复杂度为O(nlgn) ，书上第二问要求证明这个复杂度，但是我认为插入法的复杂度也是O（n），因为它和堆调整的区别在于针对每个节点i，堆调整是自上向下进行调整，插入法是自下向上进行调整。（2）对于同样的输入两个方法建立的堆可能不同。因为堆调整时，是i要跟它的两个子女进行比较，选出最大（小）的，但是插入x时，x只跟它的父节点进行比较。比如输入为2、3、4，堆调整建堆为4、3、2，插入法建堆为4、2、3。插入法建最大堆代码如下：
关于插入法堆的java代码和的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
