排序

測試類

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.按數(shù)學(xué)成績");

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.基數(shù)排序");

? ? ? ? f=read.nextInt();

? ? if(f==1){

? ? gg.mergeSort();

? ? }else{

? ? gg.radixSort();

? ? }

? ? break;

? ? }

}

}while(e!=0);

read.close();

}

主方法類主要有5類常用排序算法 ?插入排序選擇排序交換排序并歸排序基數(shù)排序?

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--){//創(chuàng)建初始堆

? ? ? ? ? ? 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--){

? ? ? ? //取出堆頂元素放在數(shù)組的最后面淡溯，數(shù)組最后的數(shù)放在堆頂再向下調(diào)整，數(shù)組的0位置不用來存儲堆數(shù)據(jù)砚著，用來交換數(shù)據(jù)的時候暫存數(shù)據(jù)

? ? ? ? ? ? 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){

? ? //判斷右子節(jié)點是否存在痒钝，并比較左右節(jié)點的大小，和最大的交換

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

? ? ++j;

? ? if(temp.Math>data[j].Math){//調(diào)整完之后繼續(xù)向下調(diào)整

? ? ? 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)//當(dāng)不發(fā)生交換式視為數(shù)據(jù)排序完畢無需繼續(xù)向下遍歷

? ? 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兩邊的數(shù)組分開澜建，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;//第一二組開始和結(jié)束位置

? Vnode[] tmp=new Vnode[data.length];//臨時存儲排序的數(shù)據(jù)

? 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++];//剩下沒有分組也沒排序的直接存在數(shù)組后面

? 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+" ");

? }

? //基數(shù)排序

? 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++){//找出數(shù)組中最大的數(shù)據(jù)

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

? max.sum=data[i].sum;

? }

? int d=0;

? while(max.sum>0){//確定最大數(shù)字有多少位蝌以，決定分配排序次數(shù)

? max.sum/=10;

? d++;

? }

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

? if(i==0)

? power=1;

? else

? power*=10;//每次循環(huán)去不同的位作為分組指標(biāo)

? for(int j=0;j<10;j++){//創(chuàng)建實例對象

? 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中的數(shù)據(jù)按位分組

? 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--){//把數(shù)據(jù)收集到data，每次收集一個head中徊件，位相同的數(shù)總是在連續(xù)的一塊

? 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(){//把數(shù)組數(shù)據(jù)還原

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

? ? data[i]=data1[i];

? }

? return data;

? }

? public void showdata(Vnode[] data){

System.out.println("姓名? ? ? 中文? ? 數(shù)學(xué)? ? ? 英語? ? ? 總分");

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);

}

? }

}

數(shù)據(jù)結(jié)構(gòu)類

public class Vnode {//排序?qū)ο? 學(xué)生語數(shù)外成績以及總分

public int Chinese=0;

public int Math=0;

public int English=0;

public int sum=0;

public String name=null;

}

本例利用文件讀取數(shù)據(jù)所在在工程根目錄加入數(shù)據(jù)的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進(jìn)階學(xué)習(xí)資料和面試題，需要資料的請加JAVA高階學(xué)習(xí)Q群：701136382 這是小編創(chuàng)建的java高階學(xué)習(xí)交流群窄绒，加群一起交流學(xué)習(xí)深造贝次。群里也有小編整理的2019年最新最全的java高階學(xué)習(xí)資料！

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末彰导，一起剝皮案震驚了整個濱河市蛔翅，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌位谋，老刑警劉巖山析，帶你破解...
沈念sama閱讀 221,695評論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異掏父，居然都是意外死亡笋轨，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,569評論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門赊淑，熙熙樓的掌柜王于貴愁眉苦臉地迎上來爵政，“玉大人，你說我怎么就攤上這事陶缺〖匦” “怎么了？”我有些...
開封第一講書人閱讀 168,130評論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵饱岸，是天一觀的道長掺出。經(jīng)常有香客問我，道長苫费，這世上最難降的妖魔是什么汤锨？我笑而不...
開封第一講書人閱讀 59,648評論 1贊 297
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮百框，結(jié)果婚禮上闲礼，老公的妹妹穿的比我還像新娘。我一直安慰自己铐维，他們只是感情好柬泽，可當(dāng)我...
茶點故事閱讀 68,655評論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著方椎，像睡著了一般聂抢。火紅的嫁衣襯著肌膚如雪钧嘶。梳的紋絲不亂的頭發(fā)上棠众，一...
開封第一講書人閱讀 52,268評論 1贊 309
城市分裂傳說
那天，我揣著相機(jī)與錄音，去河邊找鬼闸拿。笑死空盼，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的新荤。我是一名探鬼主播揽趾，決...
沈念sama閱讀 40,835評論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼苛骨！你這毒婦竟也來了篱瞎？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,740評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤痒芝，失蹤者是張志新（化名）和其女友劉穎俐筋，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體严衬，經(jīng)...
沈念sama閱讀 46,286評論 1贊 318
?護(hù)林員之死
正文獨居荒郊野嶺守林人離奇死亡澄者，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 38,375評論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了请琳。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片粱挡。...
茶點故事閱讀 40,505評論 1贊 352
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖俄精，靈堂內(nèi)的尸體忽然破棺而出询筏，到底是詐尸還是另有隱情，我是刑警寧澤嘀倒，帶...
沈念sama閱讀 36,185評論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布屈留，位于F島的核電站，受9級特大地震影響测蘑，放射性物質(zhì)發(fā)生泄漏灌危。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,873評論 3贊 333
男人毒藥：我在死后第九天來索命
文/蒙蒙一碳胳、第九天我趴在偏房一處隱蔽的房頂上張望勇蝙。院中可真熱鬧，春花似錦挨约、人聲如沸味混。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,357評論 0贊 24
一樁弒父案诫惭，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽翁锡。三九已至，卻和暖如春夕土，著一層夾襖步出監(jiān)牢的瞬間馆衔，已是汗流浹背瘟判。一陣腳步聲響...
開封第一講書人閱讀 33,466評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留角溃，地道東北人拷获。一個月前我還...
沈念sama閱讀 48,921評論 3贊 376
代替公主和親
正文我出身青樓，卻偏偏與公主長得像减细，于是被迫代替她去往敵國和親匆瓜。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 45,515評論 2贊 359

排序

推薦閱讀更多精彩內(nèi)容