插入演算法

㈠ 演算法與數據結構 插入

int inset(palist,p,x)
post-seq pslist;
int p,x;
{
int j;
if(i<0||i>p)
{
printf("i值錯誤！\n");
return 0;
}
else
{
for(j=p-1;j>=i-1;j--) pslist[j+1]=pslist[j];
pslist[i-1]=x;
p++;
return 1;
}

}

㈡ 二叉排序樹的插入演算法

首先執行查找演算法，找出被插結點的父親結點。
判斷被插結點是其父親結點的左、右兒子。將被插結點作為葉子結點插入。
若二叉樹為空。則首先單獨生成根結點。
注意：新插入的結點總是葉子結點。 //在二叉排序樹中插入查找關鍵字keyvoidInsertBST(t，key){if(t==NULL){t=newBiTree;t->lchild=t->rchild=NULL;t->data=key;return;}if(key<t->data)InsertBST(t->lchild,key);elseInsertBST(t->rchild,key);}//n個數據在數組d中，tree為二叉排序樹根voidCreateBiTree(tree,d[],n){tree=NULL;for(i=0;i<n;i++)InsertBST(tree,d[i]);}最小值二叉樹c常式： #include<stdio.h>#include<malloc.h>structpriorityqueue{intcapacity;intsize;structpriorityqueue*elements;}*tryit;structpriorityqueue*initialize(intmaxelements){structpriorityqueue*h;h=malloc(sizeof(structpriorityqueue));h->elements=malloc(sizeof(int)*(maxelements+1));h->capacity=maxelements;h->size=0;h->elements[0]=-23767;returnh;}voidinsert(intx,structpriorityqueue*h){inti;for(i=++h->size;h->elements[i/2]>x;i/=2)h->elements[i]=h->elements[i/2];h->elements[i]=x;}intdeletemin(structpriorityqueue*h){inti,child;intminelement,lastelement;minelement=h->elements[1];lastelement=h->elements[h->size--];for(i=1;i*2<=h->size;i=child){child=i*2;if(child!=h->size&&h->elements[child+1]<h->elements[child])child++;if(lastelement>h->elements[child])h->elements[i]=h->elements[child];elsebreak;}h->elements[i]=lastelement;returnminelement;}main(){tryit=initialize(10);insert(4,tryit);insert(5,tryit);insert(10,tryit);insert(3,tryit);printf(%d ,deletemin(tryit));printf(%d deletemin(tryit));printf(%d ,deletemin(tryit));printf(%d ,deletemin(tryit));getchar();}

㈢ 順序表中元素插入演算法詳細解釋

//將順序表第i-1個元素至最後一個元素全部向後移動一位
for(j=L->last;j>=i-1;j--)
L->data[j+1]=L->data[j]
//將新元素x插入到原第i-1個元素的位置
L->data[i-1]=x;
//更新順序表長度
L->last++;

㈣ 如何使用c語言實現插入演算法

void InsertSort(int arr[], int len, int key)
{
int i, j;
int temp;
for(i=0; i<len-1; i++)
{
temp = arr[i+1];
for(j=i; j>=0 && arr[j] > temp; j--)
arr[j+1] = arr[j];
arr[j+1] = temp;
}
}

㈤ 順序表的插入演算法的實現

#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int status ;
typedef int ElemType ;

typedef struct{
ElemType *elem;
int length,listsize;
}SqList;

status InitList(SqList &L)//初始化
{
L.elem=(int *)malloc(100*sizeof(int));
if(!L.elem) exit(-2);
L.listsize=100;
L.length=0;
return 1;
}

/*先建立新表*/
status Build(SqList &L)
{
int i,n;
printf("請輸入元素個數n和n個元素\n");
scanf("%d",&n);
//if(n>LIST_INIT_SIZE)

for(i=0;i<n;i++)
scanf("%d",L.elem+i);
L.length=n;
return 1;
}
/*輸出表中元素和長度*/
void Print(SqList &L)
{
int i;
for(i=0;i<L.length;i++)
printf("%d ",*(L.elem+i));
printf("\n長度為:%d\n\n",L.length);
}
/*刪除值為X的元素*/
status ListDelete1(SqList &L,int x)
{
int i;
for(i=0;i<L.length;i++)
if(*(L.elem+i)==x)
break;
if(i==L.length)
return 0;
for(i++;i<L.length;i++)
*(L.elem+i-1)=*(L.elem+i);
L.length--;
return 1;
}

/*逆置函數*/
void Inverse(SqList &L)
{
int i,t;
for(i=0;i<L.length/2;i++)
{
t=*(L.elem+i);
*(L.elem+i)=*(L.elem+L.length-i-1);
*(L.elem+L.length-i-1)=t;
}
printf("表逆置成功!!!\n");
}

/*（升序）*/
void Sort(SqList &L)
{
int i,j,t;
for(i=1;i<L.length;i++)
for(j=0;j<L.length-i;j++)
{
if(*(L.elem+j)>*(L.elem+j+1))
{
t=*(L.elem+j);
*(L.elem+j)=*(L.elem+j+1);
*(L.elem+j+1)=t;
}
}
printf("已升序\n");

}

/*合並兩個線性表*/
status Merger(SqList &L,SqList &Lb)
{
int i,j,k;
SqList Lc;
InitList(Lc);
if(Lc.listsize<L.length+Lb.length)
{
Lc.elem=(ElemType *)realloc(Lc.elem,(L.length+Lb.length+LISTINCREMENT)*sizeof(ElemType));
if(!L.elem) exit(-2);
Lc.listsize=L.length+Lb.length+LISTINCREMENT;
}
i=j=k=0;
while(i<L.length && j<Lb.length)
{
if(*(L.elem+i) < *(Lb.elem+j))
{
*(Lc.elem+k)=*(L.elem+i);
k++;i++;
}
else
{
*(Lc.elem+k)=*(Lb.elem+j);
k++;j++;
}
}
while(i<L.length)
{
*(Lc.elem+k)=*(L.elem+i);
k++;i++;
}
while(j<Lb.length)
{
*(Lc.elem+k)=*(Lb.elem+j);
k++;j++;
}
Lc.length=L.length+Lb.length;
L=Lc;
return 1;
}

/*將X插入，使仍然有序*/
status ListInsert(SqList &L,int x)
{
int i,k;
if(L.length>=L.listsize)
{
L.elem=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!L.elem) exit(-2);
L.listsize+=LISTINCREMENT;
}
for(i=0;i<L.length;i++)
if(x<*(L.elem+i))
break;
k=i;
for(i=L.length;i>k;i--)
*(L.elem+i)=*(L.elem+i-1);
*(L.elem+k)=x;
L.length++;
return 1;
}

/*提示函數*/
void Tips()
{
printf("請選擇你的想要的操作：\n");
printf("<1> 輸出順序表及順序表的長度\n");

printf("<2> 刪除值為x的結點\n");

printf("<3> 將順序表逆置\n");
printf("<4> 將順序表按升序排序\n");
printf("<5> 將x插入到順序表的適當位置上\n");
printf("<6> 將兩個有序表合並\n");
printf("<0> 退出\n\n");
}

int main()
{

SqList L,Lb;
InitList(L);
Build(L);
int a,x,flag;
//SqList L,Lb;
Tips();
scanf("%d",&a);
while(a)
{
switch(a)
{

case 1:
{ Print(L);
break;}
case 2:
{ printf("請輸入要刪除的數據X:\n");
scanf("%d",&x);
flag=ListDelete1(L,x);
if(flag)
printf("刪除成功!!\n\n");
else
printf("元素不存在,刪除失敗!!\n\n");
break;}

case 3:
Inverse(L);
break;
case 4:
Sort(L);
break;
case 5:
printf("請輸入要插入的數據X:\n");
scanf("%d",&x);
flag=ListInsert(L,x);

if(flag)
printf("插入成功!!\n\n");
else
printf("插入失敗!!\n\n");
break;

case 6:
printf("請輸入Lb的內容:\n");
InitList(Lb);
Build(Lb);
flag=Merger(L,Lb);
if(flag)
printf("合並成功!!\n\n");
break;
//default;

Tips();
scanf("%d",&a);

}
}
return 0;
}

㈥ c語言插入法排序的演算法步驟

演算法描述
一般來說，插入排序都採用in-place在數組上實現。具體演算法描述如下：
從第一個元素開始，該元素可以認為已經被排序
取出下一個元素，在已經排序的元素序列中從後向前掃描
如果該元素（已排序）大於新元素，將該元素移到下一位置
重復步驟3，直到找到已排序的元素小於或者等於新元素的位置
將新元素插入到該位置後
重復步驟2~5
如果比較操作的代價比交換操作大的話，可以採用二分查找法來減少比較操作的數目。該演算法可以認為是插入排序的一個變種，稱為二分查找排序。
范常式式碼
void insertion_sort(int array[], int first, int last)
{
int i,j;
int temp;
for (i = first+1; i<=last;i++)
{
temp = array[i];
j=i-1;

while((j>=first) && (array[j] > temp))
{
array[j+1] = array[j];
j--;
}
array[j+1] = temp;
}
}

㈦ 如何使用aurora在word中插入演算法

Word中使用Aurora插入演算法偽代碼 1. properties-->packages \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsfonts} \usepackage{mathrsfs} \usepackage{algorithm} \usepackage{algorithmic} \usepackage{multirow} \alglan...

㈧ 單鏈表的元素插入演算法

#include <stdlib.h>#include<stdio.h>typedef struct LNode{
int data;
LNode *next;
}*List,LNode;void Creat(List &L,int n){//創建鏈表
List p;//用於循環創建的節點
L=(List)malloc(sizeof(struct LNode));
L->next=NULL;
for(int i=1;i<=n;i++){
p=(List)malloc(sizeof(struct LNode));
scanf("%d",&p->data);
p->next =L->next;
L->next=p;
}
}//創建成功void Print(List L3){
L3=L3->next;
while(L3){
printf("%d",L3->data);
L3=L3->next;
}
}void Insert(List &L,int i,int e){//在第i個位置之前插入e
List p,s;
p=L;
int j=0; while(p&&j<=i-1){
if(j==i-1){
s=(List)malloc(sizeof(struct LNode));
s->data=e;
s->next=p->next;
p->next=s;
}
j++;
p=p->next;
}
}

int main(){ List L;
int n,i,e;
scanf("%d,%d,%d",&n,&i,&e);
Creat(L,n);
Insert(L,i,e);
Print(L); return 0;
}1

㈨ 誰知道java的插入演算法最好簡潔易懂 三克油了

java排序演算法大全
為了便於管理，先引入個基礎類：
package algorithms;

public abstract class Sorter<E extends Comparable<E>> {

public abstract void sort(E[] array,int from ,int len);

public final void sort(E[] array)
{
sort(array,0,array.length);
}
protected final void swap(E[] array,int from ,int to)
{
E tmp=array[from];
array[from]=array[to];
array[to]=tmp;
}
} 一 插入排序

該演算法在數據規模小的時候十分高效，該演算法每次插入第K+1到前K個有序數組中一個合適位置，K從0開始到N-1,從而完成排序：
package algorithms;
/**
* @author yovn
*/
public class InsertSorter<E extends Comparable<E>> extends Sorter<E> {

/* (non-Javadoc)
* @see algorithms.Sorter#sort(E[], int, int)
*/
public void sort(E[] array, int from, int len) {
E tmp=null;
for(int i=from+1;i<from+len;i++)
{
tmp=array[i];
int j=i;
for(;j>from;j--)
{
if(tmp.compareTo(array[j-1])<0)
{
array[j]=array[j-1];
}
else break;
}
array[j]=tmp;
}
}

}

二 冒泡排序

這可能是最簡單的排序演算法了，演算法思想是每次從數組末端開始比較相鄰兩元素，把第i小的冒泡到數組的第i個位置。i從0一直到N-1從而完成排序。（當然也可以從數組開始端開始比較相鄰兩元素，把第i大的冒泡到數組的第N-i個位置。i從0一直到N-1從而完成排序。)
package algorithms;

/**
* @author yovn
*
*/
public class BubbleSorter<E extends Comparable<E>> extends Sorter<E> {

private static boolean DWON=true;

public final void bubble_down(E[] array, int from, int len)
{
for(int i=from;i<from+len;i++)
{
for(int j=from+len-1;j>i;j--)
{
if(array[j].compareTo(array[j-1])<0)
{
swap(array,j-1,j);
}
}
}
}

public final void bubble_up(E[] array, int from, int len)
{
for(int i=from+len-1;i>=from;i--)
{
for(int j=from;j<i;j++)
{
if(array[j].compareTo(array[j+1])>0)
{
swap(array,j,j+1);
}
}
}
}
@Override
public void sort(E[] array, int from, int len) {

if(DWON)
{
bubble_down(array,from,len);
}
else
{
bubble_up(array,from,len);
}
}

}

三，選擇排序

選擇排序相對於冒泡來說，它不是每次發現逆序都交換，而是在找到全局第i小的時候記下該元素位置，最後跟第i個元素交換，從而保證數組最終的有序。
相對與插入排序來說，選擇排序每次選出的都是全局第i小的，不會調整前i個元素了。
package algorithms;
/**
* @author yovn
*
*/
public class SelectSorter<E extends Comparable<E>> extends Sorter<E> {

/* (non-Javadoc)
* @see algorithms.Sorter#sort(E[], int, int)
*/
@Override
public void sort(E[] array, int from, int len) {
for(int i=0;i<len;i++)
{
int smallest=i;
int j=i+from;
for(;j<from+len;j++)
{
if(array[j].compareTo(array[smallest])<0)
{
smallest=j;
}
}
swap(array,i,smallest);

}

}

}

四 Shell排序

Shell排序可以理解為插入排序的變種，它充分利用了插入排序的兩個特點：
1）當數據規模小的時候非常高效
2）當給定數據已經有序時的時間代價為O(N)
所以，Shell排序每次把數據分成若個小塊，來使用插入排序，而且之後在這若個小塊排好序的情況下把它們合成大一點的小塊，繼續使用插入排序，不停的合並小塊，知道最後成一個塊，並使用插入排序。

這里每次分成若干小塊是通過「增量」 來控制的，開始時增量交大，接近N/2,從而使得分割出來接近N/2個小塊，逐漸的減小「增量「最終到減小到1。

一直較好的增量序列是2^k-1,2^(k-1)-1,.....7,3,1,這樣可使Shell排序時間復雜度達到O(N^1.5)
所以我在實現Shell排序的時候採用該增量序列
package algorithms;

/**
* @author yovn
*/
public class ShellSorter<E extends Comparable<E>> extends Sorter<E> {

/* (non-Javadoc)
* Our delta value choose 2^k-1,2^(k-1)-1, .7,3,1.
* complexity is O(n^1.5)
* @see algorithms.Sorter#sort(E[], int, int)
*/
@Override
public void sort(E[] array, int from, int len) {

//1.calculate the first delta value;
int value=1;
while((value+1)*2<len)
{
value=(value+1)*2-1;

}

for(int delta=value;delta>=1;delta=(delta+1)/2-1)
{
for(int i=0;i<delta;i++)
{
modify_insert_sort(array,from+i,len-i,delta);
}
}

}

private final void modify_insert_sort(E[] array, int from, int len,int delta) {
if(len<=1)return;
E tmp=null;
for(int i=from+delta;i<from+len;i+=delta)
{
tmp=array[i];
int j=i;
for(;j>from;j-=delta)
{
if(tmp.compareTo(array[j-delta])<0)
{
array[j]=array[j-delta];
}
else break;
}
array[j]=tmp;
}

}
}

五 快速排序

快速排序是目前使用可能最廣泛的排序演算法了。
一般分如下步驟：
1）選擇一個樞紐元素（有很對選法，我的實現里採用去中間元素的簡單方法）
2）使用該樞紐元素分割數組，使得比該元素小的元素在它的左邊，比它大的在右邊。並把樞紐元素放在合適的位置。
3）根據樞紐元素最後確定的位置，把數組分成三部分，左邊的，右邊的，樞紐元素自己，對左邊的，右邊的分別遞歸調用快速排序演算法即可。
快速排序的核心在於分割演算法，也可以說是最有技巧的部分。

package algorithms;

/**
* @author yovn
*
*/
public class QuickSorter<E extends Comparable<E>> extends Sorter<E> {

/* (non-Javadoc)
* @see algorithms.Sorter#sort(E[], int, int)
*/
@Override
public void sort(E[] array, int from, int len) {
q_sort(array,from,from+len-1);
}

private final void q_sort(E[] array, int from, int to) {
if(to-from<1)return;
int pivot=selectPivot(array,from,to);

pivot=partion(array,from,to,pivot);

q_sort(array,from,pivot-1);
q_sort(array,pivot+1,to);

}

private int partion(E[] array, int from, int to, int pivot) {
E tmp=array[pivot];
array[pivot]=array[to];//now to's position is available

while(from!=to)
{
while(from<to&&array[from].compareTo(tmp)<=0)from++;
if(from<to)
{
array[to]=array[from];//now from's position is available
to--;
}
while(from<to&&array[to].compareTo(tmp)>=0)to--;
if(from<to)
{
array[from]=array[to];//now to's position is available now
from++;
}
}
array[from]=tmp;
return from;
}

private int selectPivot(E[] array, int from, int to) {

return (from+to)/2;
}

}

六 歸並排序

演算法思想是每次把待排序列分成兩部分，分別對這兩部分遞歸地用歸並排序，完成後把這兩個子部分合並成一個
序列。
歸並排序藉助一個全局性臨時數組來方便對子序列的歸並，該演算法核心在於歸並。
package algorithms;

import java.lang.reflect.Array;

/**
* @author yovn
*
*/
public class MergeSorter<E extends Comparable<E>> extends Sorter<E> {

/* (non-Javadoc)
* @see algorithms.Sorter#sort(E[], int, int)
*/
@SuppressWarnings("unchecked")
@Override
public void sort(E[] array, int from, int len) {
if(len<=1)return;
E[] temporary=(E[])Array.newInstance(array[0].getClass(),len);
merge_sort(array,from,from+len-1,temporary);

}

private final void merge_sort(E[] array, int from, int to, E[] temporary) {
if(to<=from)
{
return;
}
int middle=(from+to)/2;
merge_sort(array,from,middle,temporary);
merge_sort(array,middle+1,to,temporary);
merge(array,from,to,middle,temporary);
}

private final void merge(E[] array, int from, int to, int middle, E[] temporary) {
int k=0,leftIndex=0,rightIndex=to-from;
System.array(array, from, temporary, 0, middle-from+1);
for(int i=0;i<to-middle;i++)
{
temporary[to-from-i]=array[middle+i+1];
}
while(k<to-from+1)
{
if(temporary[leftIndex].compareTo(temporary[rightIndex])<0)
{
array[k+from]=temporary[leftIndex++];

}
else
{
array[k+from]=temporary[rightIndex--];
}
k++;
}

}

}

七 堆排序

堆是一種完全二叉樹，一般使用數組來實現。
堆主要有兩種核心操作，
1）從指定節點向上調整(shiftUp)
2）從指定節點向下調整(shiftDown)
建堆，以及刪除堆定節點使用shiftDwon,而在插入節點時一般結合兩種操作一起使用。
堆排序藉助最大值堆來實現，第i次從堆頂移除最大值放到數組的倒數第i個位置，然後shiftDown到倒數第i+1個位置,一共執行N此調整，即完成排序。
顯然，堆排序也是一種選擇性的排序，每次選擇第i大的元素。
package algorithms;

/**
* @author yovn
*
*/
public class HeapSorter<E extends Comparable<E>> extends Sorter<E> {

/* (non-Javadoc)
* @see algorithms.Sorter#sort(E[], int, int)
*/
@Override
public void sort(E[] array, int from, int len) {
build_heap(array,from,len);

for(int i=0;i<len;i++)
{
//swap max value to the (len-i)-th position
swap(array,from,from+len-1-i);
shift_down(array,from,len-1-i,0);//always shiftDown from 0
}
}

private final void build_heap(E[] array, int from, int len) {
int pos=(len-1)/2;//we start from (len-1)/2, because branch's node +1=leaf's node, and all leaf node is already a heap
for(int i=pos;i>=0;i--)
{
shift_down(array,from,len,i);
}

}

private final void shift_down(E[] array,int from, int len, int pos)
{

E tmp=array[from+pos];
int index=pos*2+1;//use left child
while(index<len)//until no child
{
if(index+1<len&&array[from+index].compareTo(array[from+index+1])<0)//right child is bigger
{
index+=1;//switch to right child
}
if(tmp.compareTo(array[from+index])<0)
{
array[from+pos]=array[from+index];
pos=index;
index=pos*2+1;

}
else
{
break;
}

}
array[from+pos]=tmp;

}

}

八 桶式排序

桶式排序不再是基於比較的了，它和基數排序同屬於分配類的排序，這類排序的特點是事先要知道待排序列的一些特徵。
桶式排序事先要知道待排序列在一個范圍內，而且這個范圍應該不是很大的。
比如知道待排序列在[0,M）內，那麼可以分配M個桶，第I個桶記錄I的出現情況，最後根據每個桶收到的位置信息把數據輸出成有序的形式。
這里我們用兩個臨時性數組，一個用於記錄位置信息，一個用於方便輸出數據成有序方式，另外我們假設數據落在0到MAX,如果所給數據不是從0開始，你可以把每個數減去最小的數。
package algorithms;

/**
* @author yovn
*
*/
public class BucketSorter {

public void sort(int[] keys,int from,int len,int max)
{
int[] temp=new int[len];
int[] count=new int[max];

for(int i=0;i<len;i++)
{
count[keys[from+i]]++;
}
//calculate position info
for(int i=1;i<max;i++)
{
count[i]=count[i]+count[i-1];//this means how many number which is less or equals than i,thus it is also position + 1
}

System.array(keys, from, temp, 0, len);
for(int k=len-1;k>=0;k--)//from the ending to beginning can keep the stability
{
keys[--count[temp[k]]]=temp[k];// position +1 =count
}
}
/**
* @param args
*/
public static void main(String[] args) {

int[] a={1,4,8,3,2,9,5,0,7,6,9,10,9,13,14,15,11,12,17,16};
BucketSorter sorter=new BucketSorter();
sorter.sort(a,0,a.length,20);//actually is 18, but 20 will also work

for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+",");
}

}

}

九 基數排序

基數排序可以說是擴展了的桶式排序，比如當待排序列在一個很大的范圍內，比如0到999999內，那麼用桶式排序是很浪費空間的。而基數排序把每個排序碼拆成由d個排序碼，比如任何一個6位數（不滿六位前面補0）拆成6個排序碼，分別是個位的，十位的，百位的。。。。
排序時，分6次完成，每次按第i個排序碼來排。
一般有兩種方式:
1) 高位優先(MSD)： 從高位到低位依次對序列排序
2）低位優先(LSD)： 從低位到高位依次對序列排序
計算機一般採用低位優先法（人類一般使用高位優先），但是採用低位優先時要確保排序演算法的穩定性。
基數排序藉助桶式排序，每次按第N位排序時，採用桶式排序。對於如何安排每次落入同一個桶中的數據有兩種安排方法：
1）順序存儲：每次使用桶式排序，放入r個桶中，，相同時增加計數。
2）鏈式存儲：每個桶通過一個靜態隊列來跟蹤。
package algorithms;

import java.util.Arrays;

/**
* @author yovn
*
*/
public class RadixSorter {

public static boolean USE_LINK=true;

/**
*
* @param keys
* @param from
* @param len
* @param radix key's radix
* @param d how many sub keys should one key divide to
*/
public void sort(int[] keys,int from ,int len,int radix, int d)
{
if(USE_LINK)
{
link_radix_sort(keys,from,len,radix,d);
}
else
{
array_radix_sort(keys,from,len,radix,d);
}

}

private final void array_radix_sort(int[] keys, int from, int len, int radix,
int d)
{
int[] temporary=new int[len];
int[] count=new int[radix];
int R=1;

for(int i=0;i<d;i++)
{
System.array(keys, from, temporary, 0, len);
Arrays.fill(count, 0);
for(int k=0;k<len;k++)
{
int subkey=(temporary[k]/R)%radix;
count[subkey]++;
}
for(int j=1;j<radix;j++)
{
count[j]=count[j]+count[j-1];
}
for(int m=len-1;m>=0;m--)
{
int subkey=(temporary[m]/R)%radix;
--count[subkey];
keys[from+count[subkey]]=temporary[m];
}
R*=radix;
}

}

private static class LinkQueue
{
int head=-1;
int tail=-1;
}
private final void link_radix_sort(int[] keys, int from, int len, int radix, int d) {

int[] nexts=new int[len];

LinkQueue[] queues=new LinkQueue[radix];
for(int i=0;i<radix;i++)
{
queues[i]=new LinkQueue();
}
for(int i=0;i<len-1;i++)
{
nexts[i]=i+1;
}
nexts[len-1]=-1;

int first=0;
for(int i=0;i<d;i++)
{
link_radix_sort_distribute(keys,from,len,radix,i,nexts,queues,first);
first=link_radix_sort_collect(keys,from,len,radix,i,nexts,queues);
}
int[] tmps=new int[len];
int k=0;
while(first!=-1)
{

tmps[k++]=keys[from+first];
first=nexts[first];
}
System.array(tmps, 0, keys, from, len);

}
private final void link_radix_sort_distribute(int[] keys, int from, int len,
int radix, int d, int[] nexts, LinkQueue[] queues,int first) {

for(int i=0;i<radix;i++)queues[i].head=queues[i].tail=-1;
while(first!=-1)
{
int val=keys[from+first];
for(int j=0;j<d;j++)val/=radix;
val=val%radix;
if(queues[val].head==-1)
{
queues[val].head=first;
}
else
{
nexts[queues[val].tail]=first;

}
queues[val].tail=first;
first=nexts[first];
}

}
private int link_radix_sort_collect(int[] keys, int from, int len,
int radix, int d, int[] nexts, LinkQueue[] queues) {
int first=0;
int last=0;
int fromQueue=0;
for(;(fromQueue<radix-1)&&(queues[fromQueue].head==-1);fromQueue++);
first=queues[fromQueue].head;
last=queues[fromQueue].tail;

while(fromQueue<radix-1&&queues[fromQueue].head!=-1)
{
fromQueue+=1;
for(;(fromQueue<radix-1)&&(queues[fromQueue].head==-1);fromQueue++);

nexts[last]=queues[fromQueue].head;
last=queues[fromQueue].tail;

}
if(last!=-1)nexts[last]=-1;
return first;
}

/**
* @param args
*/
public static void main(String[] args) {
int[] a={1,4,8,3,2,9,5,0,7,6,9,10,9,135,14,15,11,222222222,1111111111,12,17,45,16};
USE_LINK=true;
RadixSorter sorter=new RadixSorter();
sorter.sort(a,0,a.length,10,10);
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+",");
}

}

}

㈩ java數組的插入演算法問題

arr[arr.length-1]=num; 43在這句的時候被num替換掉了
java的數組長度被初始化之後就是固定的 如果你想像裡面加入一個新值
需要重新定義數組，也就是說如果oldarr.length = 5 你想像中見放第六個數是辦不到的
只能重新定義數據 int[] newarr = new int[oldarr+1] 這么來弄