排序

测试类

public class Testmysort {

public static void main(String[] args) throws IOException {

int n,e,f;

Vnode[] data=null;

ArrayList<Vnode> list=new ArrayList<Vnode>();

BufferedReader br=new BufferedReader(new FileReader("123.txt"));

String str1=br.readLine();

String[] str;

while((str1=br.readLine())!=null){

Vnode node =new Vnode();

str=str1.split(" ");

node.name=str[0].trim();

node.Chinese=Integer.parseInt(str[1].trim());

node.Math=Integer.parseInt(str[2].trim());

node.English=Integer.parseInt(str[3].trim());

node.sum=node.Chinese+node.Math+node.English;

list.add(node);

}

br.close();

data=new Vnode[list.size()];

list.toArray(data);

Scanner read=new Scanner(System.in);

Mysort gg=new Mysort(data);

System.out.println("------------------------");

System.out.println("操作选项菜单：");

System.out.println("1.按语文名字排序");

System.out.println("2.按数学成绩");

System.out.println("3.按英语成绩");

System.out.println("4.按总分排序");

System.out.println("0.退出");

System.out.println("------------------------");

do{

System.out.println("请输入操作选项：");

e=read.nextInt();

switch(e){

case 1:{

System.out.println("1.直接插入排序 2.希尔排序");

f=read.nextInt();

if(f==1){

gg.insertSort();

}else{

gg.shellSort();

}

break;

}

case 2:{

System.out.println("1.直接选择排序 2.希堆排序");

f=read.nextInt();

if(f==1){

gg.selectSort();

}else{

gg.heapSort();

}

break;

}

case 3:{

System.out.println("1.冒泡排序 2.快速排序");

f=read.nextInt();

if(f==1){

gg.bubbleSort();

}else{

gg.quickSort();

}

break;

}

case 4:{

System.out.println("1.二路归并排序 2.基数排序");

f=read.nextInt();

if(f==1){

gg.mergeSort();

}else{

gg.radixSort();

}

break;

}

}while(e!=0);

read.close();

}

主方法类主要有5类常用排序算法插入排序选择排序交换排序并归排序基数排序

public class Mysort{

Vnode[] data=null;

Vnode[] data1=null;

public Mysort(Vnode[] data){

int n=data.length;

data1=new Vnode[n];

this.data=data;

for(int i=0;i<data.length;i++){

this.data1[i]=data[i];

}

//插入排序

public void insertSort(){//直接插入排序

this.data=refelsh();

for(int i=1;i<data.length;i++){

if((data[i].Chinese>data[i-1].Chinese)||//名字按字典升序

((data[i].Chinese==data[i-1].Chinese)&&(data[i].name.compareTo(data[i-1].name)<0))){

Vnode temp=data[i];

System.out.print(data[i].name+" ");//测试计算过程

int j=0;

for(j=i-1;j>=0&&((temp.Chinese>data[j].Chinese)||

((temp.Chinese==data[j].Chinese)&&(temp.name.compareTo(data[j].name)<0)));j--){

data[j+1]=data[j];

}

data[j+1]=temp;

}

System.out.println();

showdata(data);

}

public void shellSort(){//希尔排序

this.data=refelsh();

int i,j,d;//d为增量

int num=data.length/3;//增量的起始值为总长度的1/3

for(int m=num;m>0;m--){

d=m;

for(i=d;i<data.length;i++){

if((data[i].Chinese>data[i-d].Chinese)){

Vnode temp=data[i];

System.out.print(data[i].name+" ");//测试计算过程

for(j=i;j>=d&&(data[j].Chinese>data[j-d].Chinese);j=j-d){

data[j]=data[j-d];

}

data[j]=temp;

}

System.out.println();

showdata(data);

}

//选择排序

public void selectSort(){//直接选择排序

this.data=refelsh();

int k,temp;

for(int i=0;i<data.length-1;i++){

k=i;

for(int j=i+1;j<data.length;j++){

if(data[j].Math>data[k].Math)

k=j;

}

System.out.print(data[k].name+" ");

if(k!=i){

temp=data[i].Math;

data[i].Math=data[k].Math;

data[k].Math=temp;

}

System.out.println();

showdata(data);

}

public void heapSort(){//堆排序

this.data=refelsh();

heap(data,0,data.length-1);

showdata(data);

}

public static void heap(Vnode[] data,int low,int high){

int i;

Vnode top;

int N=data.length-1;

for(i=N/2;i>=0;i--){//创建初始堆

siftdown(data,i,N);

}

for(i=0;i<=N;i++)

System.out.print(i!=N?data[i].name+" ":data[i].name);

System.out.println();

for(i=N;i>0;i--){

//取出堆顶元素放在数组的最后面，数组最后的数放在堆顶再向下调整，数组的0位置不用来存储堆数据，用来交换数据的时候暂存数据

top=data[0];

data[0]=data[i];

data[i]=top;

siftdown(data,0,i-1);

}

public static void siftdown(Vnode[] data,int low,int high){

int k=low;

int j=2*k+1;

Vnode temp=data[k];

while(j<=high){

//判断右子节点是否存在，并比较左右节点的大小，和最大的交换

if((j<high)&&(j+1<=high)&&(data[j].Math>data[j+1].Math))

++j;

if(temp.Math>data[j].Math){//调整完之后继续向下调整

data[k]=data[j];

k=j;

j=2*k+1;

}else{

break;

}

data[k]=temp;//找到该点的合适位置

}

//选择排序

public void bubbleSort(){//冒泡排序

this.data=refelsh();

boolean exchange;

Vnode tmp;

int n=data.length;

for(int i=1;i<n;i++){

exchange=false;

for(int j=0;j<n-i;j++){

if(data[j].English<data[j+1].English){

tmp=data[j+1];

data[j+1]=data[j];

data[j]=tmp;

exchange=true;

}

System.out.print(data[n-i].name+" ");

if(exchange==false)//当不发生交换式视为数据排序完毕无需继续向下遍历

break;

}

System.out.println();

showdata(data);

}

public void quickSort(){//快速排序

this.data=refelsh();

QSort(data,0,data.length-1);

System.out.println();

showdata(data);

}

public void QSort(Vnode[] R,int low,int high){

Vnode base=R[low];

int i=low+1;

int j=high;

Vnode temp;

while(i<j){

while((i<j)&&(R[j].English<=base.English))

--j;

while((i<j)&&(R[i].English>=base.English))

++i;

if(i<j){

temp=R[i];

R[i]=R[j];

R[j]=temp;

}

if(i==low+1&&R[i].English<R[low].English){

i=low;

j=low;

}

/* 比如 120 100 110 115从大到小排列。其中的100会排序失败

因为在第一轮排序时100比120小最后i=j都指向100

再把100两边的数组分开，100就被拉下了，100虽然比120小但是不一定

就比100右边的小*/

if(R[j].English>R[low].English){

temp=R[low];

R[low]=R[j];

R[j]=temp;

}

System.out.print(base.name+" ");

if(i-low>1)

QSort(R,low,i-1);

if(high-j>1)

QSort(R,j+1,high);

}

//归并排序

public void mergeSort(){//二路归并排序

this.data=refelsh();

int k=1;

while(k<data.length){

MSort(data,k);

k*=2;

}

System.out.println();

showdata(data);

}

public void MSort(Vnode[] data,int len){

int m=0,l1=0,l2,h1,h2,i=0,j=0;//第一二组开始和结束位置

Vnode[] tmp=new Vnode[data.length];//临时存储排序的数据

while(l1+len<data.length){//最后不能分出一组退出

l2=l1+len;

h1=l2-1;

h2=(l2+len-1<data.length)?l2+len-1:data.length-1;

j=l2;

i=l1;

while((i<=h1)&&(j<=h2)){//两小组比较存储

if(data[i].sum>=data[j].sum) tmp[m++]=data[i++];

else tmp[m++]=data[j++];

}

while(i<=h1) tmp[m++]=data[i++];//有一组还有剩余的情况

while(j<=h2) tmp[m++]=data[j++];

l1=h2+1;

}

i=l1;

while(i<data.length) tmp[m++]=data[i++];//剩下没有分组也没排序的直接存在数组后面

for(i=0;i<data.length;i++) data[i]=tmp[i];

if(len==1){

for(int t=0;t<data.length;t++)

System.out.print(data[t].sum+" ");

}

//基数排序

public void radixSort(){

this.data=refelsh();

int k,l,power=1;

RadixNode p,q;

RadixNode[] head=new RadixNode[10];//顺序链表

Vnode max=new Vnode();

max.sum=data[0].sum;

for(int i=1;i<data.length;i++){//找出数组中最大的数据

if(data[i].sum>max.sum){

max.sum=data[i].sum;

}

int d=0;

while(max.sum>0){//确定最大数字有多少位，决定分配排序次数

max.sum/=10;

d++;

}

for(int i=0;i<d;i++){

if(i==0)

power=1;

else

power*=10;//每次循环去不同的位作为分组指标

for(int j=0;j<10;j++){//创建实例对象

head[j]=new RadixNode();

}

for(int j=0;j<data.length;j++){

k=data[j].sum/power-(data[j].sum/(power*10))*10;//取位第一次个位第二次十位。。。。

q=new RadixNode();

q.data=data[j];//把data中的数据按位分组

q.next=null;

p=head[k].next;

if(p==null)

head[k].next=q;

else{

while(p.next!=null)

p=p.next;

p.next=q;

}

l=0;

for(int j=9;j>=0;j--){//把数据收集到data，每次收集一个head中，位相同的数总是在连续的一块

p=head[j].next;//比如40 45 第一次：。45。。。40 。第二次：。。45 40 。。。。

while(p!=null){

data[l++]=p.data;

p=p.next;

}

if(i==0)

for(int t=0;t<data.length;t++)

System.out.print(data[t].sum+" ");

}

System.out.println();

showdata(data);

}

static class RadixNode{

public Vnode data;

public RadixNode next;

}

public Vnode[] refelsh(){//把数组数据还原

for(int i=0;i<data.length;i++){

data[i]=data1[i];

}

return data;

}

public void showdata(Vnode[] data){

System.out.println("姓名中文数学英语总分");

for(int i=0;i<data.length;i++){

System.out.println(data[i].name+" "+data[i].Chinese+" "+data[i].Math+" "+data[i].English+" "+data[i].sum);

}

数据结构类

public class Vnode {//排序对象学生语数外成绩以及总分

public int Chinese=0;

public int Math=0;

public int English=0;

public int sum=0;

public String name=null;

}

本例利用文件读取数据所在在工程根目录加入数据的txt文件用时第一行要空出来

ab 91 105 113

cd 95 103 114

bc 95 102 115

gh 93 106 112

ef 92 104 111

ce 92 104 111

de 96 101 116

jk 99 110 120

fg 97 107 118

op 98 103 114

xj 50 100 100

xh 51 100 101

小编整理了一些java进阶学习资料和面试题，需要资料的请加JAVA高阶学习Q群：701136382 这是小编创建的java高阶学习交流群，加群一起交流学习深造。群里也有小编整理的2019年最新最全的java高阶学习资料！

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,445评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,889评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,047评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,760评论 1赞 276
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,745评论 5赞 367
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,638评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,011评论 3赞 398
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,669评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,923评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,655评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,740评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,406评论 4赞 320
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,995评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,961评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,197评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,023评论 2赞 350
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,483评论 2赞 342

排序

推荐阅读更多精彩内容