对于一个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;
}
}
}
