リライトソート

4475 ワード

int配列の場合、配列要素をソートする挿入ソートアルゴリズムを作成します.int配列Aおよび配列のサイズnを指定し、ソート後の配列を返します.
試験例:[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;
        }
    }
}