對于一個int數(shù)組为居，請編寫一個插入排序算法矾克，對數(shù)組元素排序教寂。給定一個int數(shù)組A及數(shù)組的大小n捏鱼，請返回排序后的數(shù)組。
測試樣例：
[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];//歸并排序需要一個輔助數(shù)組
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++)//先讓輔助數(shù)組跟原數(shù)組一樣
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，如大于或等于劃分值則繼續(xù)循環(huán)
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節(jié)點的父節(jié)點開始建堆
int k = i;//記錄當(dāng)前節(jié)點
while((2*k+1)<=lastIndex){//為每個節(jié)點建立大根堆,只要這個根節(jié)點還有子節(jié)點
int bigIndex = 2*k+1;//假設(shè)左節(jié)點的值最大
if(bigIndex<lastIndex){//有右節(jié)點存在
//子節(jié)點中的最大值
if(A[bigIndex]<A[bigIndex+1])
bigIndex++;
}
//根節(jié)點跟子節(jié)點比較
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++){//分組進(jìn)行插入排序
temp = A[i];
for(j=i-increment;(j>=0)&&(A[j]>temp);j-=increment)
A[j+increment] = A[j];
A[j+increment] = temp;//后面小于待插入元素,設(shè)定待插入元素位置
}
}
return A;
}
}
****6.計數(shù)排序****
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;//先讓數(shù)組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.基數(shù)排序****
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];//臨時數(shù)組
int[] buckets = new int[radix];//radix為10,按10進(jìn)制拆分(10個桶)
//循環(huán)中rate用于保存當(dāng)前計算的位,十位時rate=10
for(int i=0,rate=1;i<d;i++){//
Arrays.fill(buckets,0);//buckets數(shù)組中全部為0
System.arraycopy(A,0,temp,0,n);//將A中元素復(fù)制進(jìn)臨時數(shù)組緩存
for(int j=0;j<n;j++){
//計算數(shù)據(jù)指定位上的子關(guān)鍵字
int subKey = (temp[j]/rate)%radix;
buckets[subKey]++;
}
for(int j=1;j<radix;j++){
buckets[j] = buckets[j]+buckets[j-1];
}
//按子關(guān)鍵字對指定數(shù)據(jù)進(jìn)行排序
for(int m=n-1;m>=0;m--){
int subKey = (temp[m]/rate)%radix;
A[--buckets[subKey]] = temp[m];
}
rate *= radix;
}
}
}
