再写排序

对于一个int数组，请编写一个插入排序算法，对数组元素排序。给定一个int数组A及数组的大小n，请返回排序后的数组。

测试样例：
[1,2,3,5,2,3],6
[1,2,2,3,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;i<n;i++){
            for(int j=i;j>0;--j){
                if(A[j]<A[j-1]){
                    int temp = A[j-1];
                    A[j-1] = A[j];
                    A[j] = temp;
                }
            }
        }
        return A;
    }
}

****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]<key){
                int temp = A[j];
                A[j] = A[i+1];
                A[i+1] = temp;
                i++;
            }
        }
        A[start] = A[i];
        A[i] = key;
        quick(A,start,i-1);
        quick(A,i+1,end);
    }
}

****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<n-1;i++){
            buildMaxHeap(A,n-1-i);
            swap(A,0,n-1-i);
        }
        return A;
    }
    private void buildMaxHeap(int[] A, int lastIndex){//建大根堆
       for(int i=(lastIndex-1)/2;i>=0;i--){//从lastIndex节点的父节点开始建堆
           int k = i;//记录当前节点
           while((2*k+1)<=lastIndex){//为每个节点建立大根堆,只要这个根节点还有子节点 
               int bigIndex = 2*k+1;//假设左节点的值最大
               if(bigIndex<lastIndex){//有右节点存在
                   //子节点中的最大值
                   if(A[bigIndex]<A[bigIndex+1])
                       bigIndex++;
               }
               //根节点跟子节点比较
               if(A[k]<A[bigIndex]){
                   swap(A,k,bigIndex);
                   k = bigIndex;
               }
               else
                   break;
           }
       } 
    }
    private void swap(int[] A, int i, int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

****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<n;i++){//分组进行插入排序
                temp = A[i];
                for(j=i-increment;(j>=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;i<NUM;i++)
            B[i] = 0;//先让数组B中的元素全部为0
        for(int i=0;i<n;i++)
            B[A[i]]++;
        int k = -1;
        for(int i=0; i<NUM;i++){
            int j = B[i];
            while(j>0){
                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<d;i++){//
            Arrays.fill(buckets,0);//buckets数组中全部为0
            System.arraycopy(A,0,temp,0,n);//将A中元素复制进临时数组缓存
            for(int j=0;j<n;j++){
                //计算数据指定位上的子关键字
                int subKey = (temp[j]/rate)%radix;
                buckets[subKey]++;
            }
            for(int j=1;j<radix;j++){
                buckets[j] = buckets[j]+buckets[j-1];
            }
            //按子关键字对指定数据进行排序
            for(int m=n-1;m>=0;m--){
                int subKey = (temp[m]/rate)%radix;
                A[--buckets[subKey]] = temp[m];
            }
            rate *= radix;
        }
    }
}

推荐阅读更多精彩内容