Diễn đàn cntt ĐH-TÔN ĐỨC THẮNG.Thân mời các anh em tham gia để diễn đàn phong phú hơn
Chào mừng bạn ghé thăm diễn đàn, hãy tham gia đăng kí thành viên cùng chúng tôi để có thêm động lực post bài

một số thuật toán sắp xếp viết bằng java [sưu tầm]

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

một số thuật toán sắp xếp viết bằng java [sưu tầm]

Bài gửi by Admin on Wed Mar 21, 2012 7:18 pm

NOTE ! các bài trên có dùng nhập xuất file là mảng số, tạo 1 file in.txt trong project java đó ,vd dữ liệu trong đó viết như sau : 5 7 6 11 3 9 45 , chú ý là có sài dấu cách nhé! sau khi biên dịch chương trình thì nó sẽ tự tạo ra 1 file out.txt cũng nằm trong project đó
import java.io.*;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;
import java.util.*;

public class KiemTraGiuaKy {

/**
* @param i
* @param j
* @param args
*/
public static void swap(int[] a, int j, int i){
int temp=a[i];
a[i]=a[j];
a[j]=temp;

}
//1 heap
public static void heapSoft(int nodes[],int n){
int i=0,x=0,s=0,f=0,cuoiheap=0;
for( i=1;i<n;i++){
x=nodes[i];
s=i;
f=(s-1)/2;
while(s>0 && nodes[f]<x){
nodes[s]=nodes[f];
s=f;
f=(s-1)/2;
}
nodes[s]=x;
}
for(i=n-1;i>0;i--){
cuoiheap=nodes[i];
nodes[i]=nodes[0];
f=0;
if(i==1) s=-1;
else s=1;
if(i>2 && nodes[2]>nodes[1])
s=2;
while(s>=0 && cuoiheap<nodes[s]){
nodes[f]=nodes[s];
f=s;
s=2*f+1;
if(s+1<=i-1&& nodes[s]<nodes[s+1])
s=s+1;
if(s>i-1)
s=-1;
}
nodes[f]=cuoiheap;
}
}
//2 bubble
public static void bubble_sort(int[] a){
for(int i=0;i<a.length;i++)
for(int j=1;j<a.length-i;j++)
if(a[j]>a[j-1])
swap(a,j,j-1);
}
//3insert
public static void insertSort(int[] a,int n){
int x,j;
for(int i=1;i<n;i++){
x=a[i];
for( j=i-1;j>=0&&x<a[j];j--)
a[j+1]=a[j];
a[j+1]=x;
}
}
//4mergesoft
public static void mergeSoft(int nodes[],int n){
int i,j,k,low1,up1,low2,up2,size;

int[] dstam=new int[n];
size=1;
while(size<n){
low1=0;
k=0;
while(low1+size<n){
low2=low1+size;
up1=low2-1;
up2=(low2+size-1<n) ? low2+size-1 : n-1;
for(i=low1,j=low2;i<=up1 && j<=up2;k++)
if(nodes[i]<=nodes[j])
dstam[k]=nodes[i++];
else
dstam[k]=nodes[j++];
for(;i<=up1;k++)
dstam[k]=nodes[i++];
for(;j<=up2;k++)
dstam[k]=nodes[j++];
low1=up2+1;
}
for(i=low1;k<n;i++)
dstam[k++]=nodes[i];
for(i=0;i<n;i++)
nodes[i]=dstam[i];
size*=2;
}
}
//5quick
public static void quickSort(int[] a){
for(int i=0;i<a.length;i++)
for(int j=i+1;j<a.length;j++)
if(a[i]>a[j])
swap(a,i,j);

}
//6 radix
public static void radixSort(int[] arr){
if(arr.length == 0)
return;
int[][] np = new int[arr.length][2];
int[] q = new int[0x100];
int i,j,k,l,f = 0;
for(k=0;k<4;k++){
for(i=0;i<(np.length-1);i++)
np[i][1] = i+1;
np[i][1] = -1;
for(i=0;i<q.length;i++)
q[i] = -1;
for(f=i=0;i<arr.length;i++){
j = ((0xFF<<(k<<3))&arr[i])>>(k<<3);
if(q[j] == -1)
l = q[j] = f;
else{
l = q[j];
while(np[l][1] != -1)
l = np[l][1];
np[l][1] = f;
l = np[l][1];
}
f = np[f][1];
np[l][0] = arr[i];
np[l][1] = -1;
}
for(l=q[i=j=0];i<0x100;i++)
for(l=q[i];l!=-1;l=np[l][1])
arr[j++] = np[l][0];
}
}

//7 counting sort
public static void countingsort(int[] a) {
if (a.length == 0)
return;

int max = a[0], min = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max)
max = a[i];
else if (a[i] < min)
min = a[i];
}
int numValues = max - min + 1;

int[] counts = new int[numValues];
for (int i = 0; i < a.length; i++) {
counts[a[i]-min]++;
}

int outputPos = 0;
for (int i = 0; i < numValues; i++) {
for (int j = 0; j < counts[i]; j++) {
a[outputPos] = i+min;
outputPos++;
}
}

}

public static void main(String[] args) {
// TODO Auto-generated method stub


try
{

Scanner input = new Scanner(new FileInputStream("in.txt"));
PrintWriter output = new PrintWriter(new FileOutputStream("out.txt"));
String s = input.nextLine();
String[] val = null;
val = s.split(" ");
int[] a = new int[val.length];
for (int i=0;i<val.length;i++)
a[i] = Integer.parseInt(val[i]);
//bubble_sort(a);
quickSort(a);
countingsort(a);
//radixSort(a);
//heapSoft(a,7);
String result = "";
for (int j=0;j<a.length;j++)
result+=a[j]+" ";
result.trim();
System.out.print(result);
output.print(result);
output.flush();
input.close();
output.close();
}
catch(Exception e)
{
System.out.println(e);
}

}

}
avatar
Admin
Thiếu Tá
Thiếu Tá

Tổng số bài gửi : 107
Age : 27

Xem lý lịch thành viên http://itam.forumvi.com

Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang

- Similar topics

 
Permissions in this forum:
Bạn không có quyền trả lời bài viết