リライトソート
4475 ワード
int配列の場合、配列要素をソートする挿入ソートアルゴリズムを作成します.int配列Aおよび配列のサイズnを指定し、ソート後の配列を返します.
試験例:[1,2,3,5,2,3],6[1,2,2,3,5]
****1.ソート****を挿入
****2.集計ソート****
****3.クイックソート****
****4.スタックソート****
****5.ヒルソート****
****6.カウントソート****
****7.基数ソート****
試験例:[1,2,3,5,2,3],6[1,2,2,3,5]
****1.ソート****を挿入
import java.util.*;
public class InsertionSort {
public int[] insertionSort(int[] A, int n) {
// write code here
if(null==A||n<=0)
return A;
for(int i=1;i0;--j){
if(A[j]
****2.集計ソート****
import java.util.*;
public class MergeSort {
public int[] mergeSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
int start = 0,end = n-1;
int[] copy = new int[n];//
merge(A,copy,start,end);
return A;
}
private void merge(int[] A, int[] copy, int start, int end){
if(start==end)
return;
int mid = (start+end)>>1;
merge(A,copy,start,mid);
merge(A,copy,mid+1,end);
for(int i=start;i<=end;i++)//
copy[i] = A[i];
int id = start;
int m = start;
int n = mid+1;
while(m<=mid&&n<=end){
if(copy[m]<=copy[n]){
A[id++] = copy[m++];
}else{
A[id++] = copy[n++];
}
}
while(m<=mid)
A[id++] = copy[m++];
while(n<=end)
A[id++] = copy[n++];
}
}
****3.クイックソート****
import java.util.*;
public class QuickSort {
public int[] quickSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
int start = 0,end=n-1;
quick(A,start,end);
return A;
}
private void quick(int[] A, int start, int end){
if(start>=end)
return;
int key = A[start];//
int i=start,j;
// , i+1 , i 1,
for(j=start+1;j<=end;j++){
if(A[j]
****4.スタックソート****
import java.util.*;
public class HeapSort {
public int[] heapSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
for(int i=0;i=0;i--){// lastIndex
int k = i;//
while((2*k+1)<=lastIndex){// ,
int bigIndex = 2*k+1;//
if(bigIndex
****5.ヒルソート****
import java.util.*;
public class ShellSort {
public int[] shellSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
int increment,i,j,temp;
for(increment = n/2;increment>=1;increment/=2){// 1
for(i=increment;i=0)&&(A[j]>temp);j-=increment)
A[j+increment] = A[j];
A[j+increment] = temp;// ,
}
}
return A;
}
}
****6.カウントソート****
import java.util.*;
public class CountingSort {
public int[] countingSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
int NUM = 999;
int[] B = new int[NUM];
for(int i=0;i0){
k++;
A[k] = i;
j--;
}
}
return A;
}
}
****7.基数ソート****
import java.util.*;
public class RadixSort {
public int[] radixSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
radix(A,10,3,n);
return A;
}
private void radix(int[] A, int radix, int d,int n){// d 3( )
int[] temp = new int[n];//
int[] buckets = new int[radix];//radix 10, 10 (10 )
// rate , rate=10
for(int i=0,rate=1;i=0;m--){
int subKey = (temp[m]/rate)%radix;
A[--buckets[subKey]] = temp[m];
}
rate *= radix;
}
}
}