một số thuật toán sắp xếp viết bằng java [sưu tầm]
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 :: Thảo luận chung-Tin tức-Thông báo
Trang 1 trong tổng số 1 trang
một số thuật toán sắp xếp viết bằng java [sưu tầm]
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);
}
}
}
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);
}
}
}
Similar topics
» bài toán đếm thỏ bằng đệ quy [java]
» bài toán độ phức tạp giải thuật T(n) = 9T(n/3) + n [ java]
» thuat toan hamming trong kiến trúc máy tính [bách khoa tòan thư wikipedia]
» bài toán chèn ko sử dụng đệ quy [java]
» bài toán chèn có sử dụng đệ quy [java]
» bài toán độ phức tạp giải thuật T(n) = 9T(n/3) + n [ java]
» thuat toan hamming trong kiến trúc máy tính [bách khoa tòan thư wikipedia]
» bài toán chèn ko sử dụng đệ quy [java]
» bài toán chèn có sử dụng đệ quy [java]
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 :: Thảo luận chung-Tin tức-Thông báo
Trang 1 trong tổng số 1 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết
|
|