用冒泡排序、選擇排序帽衙、插入排序叁鉴、歸并排序、快速排序佛寿、堆排序幌墓、希爾排序但壮、計(jì)數(shù)排序?qū)懗鱿旅孢@一題的代碼
給定一個(gè)int數(shù)組A及數(shù)組的大小n，請返回排序后的數(shù)組常侣。
測試樣例：
排序前[1,2,3,5,2,3],6
排序后[1,2,2,3,3,5]
1.冒泡排序
<code>
import java.util.*;
public class BubbleSort {
public int[] bubbleSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
for(int i=0;i<n;i++){
for(int j=0;j<n-i-1;j++){
if(A[j]>A[j+1]){
int temp =A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
}
}
return A;
}
}
</code>
2.選擇排序
<code>
import java.util.*;
public class SelectSort {
public int[] selectionSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(A[i]<A[j]){
int temp =A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
return A;
}
}
</code>
3.插入排序
<code>
import java.util.*;
public class InsertionSort {
public int[] insertionSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
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;
}
}
</code>
4.歸并排序
<code>
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];//歸并排序需要一個(gè)輔助數(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++];
}
}
</code>
5.快速排序
<code>
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];//選擇一個(gè)劃分值
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);
}
}
</code>
6.堆排序
<code>
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é)點(diǎn)的父節(jié)點(diǎn)開始建堆
int k = i;//記錄當(dāng)前節(jié)點(diǎn)
while((2k+1)<=lastIndex){//為每個(gè)節(jié)點(diǎn)建立大根堆,只要這個(gè)根節(jié)點(diǎn)還有子節(jié)點(diǎn)
int bigIndex = 2*k+1;//假設(shè)左節(jié)點(diǎn)的值最大
if(bigIndex<lastIndex){//有右節(jié)點(diǎn)存在
//子節(jié)點(diǎn)中的最大值
if(A[bigIndex]<A[bigIndex+1])
bigIndex++;
}
//根節(jié)點(diǎn)跟子節(jié)點(diǎn)比較
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;
}
}
</code>
7.希爾排序
<code>
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;
}
}
</code>
8.計(jì)數(shù)排序
<code>
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;
}
}
</code>
說明：前三個(gè)排序是時(shí)間復(fù)雜度為O(n2)溯祸，歸并排序+快速排序+堆排序+希爾排序的時(shí)間復(fù)雜度是O(NlogN)，計(jì)數(shù)排序的時(shí)間復(fù)雜度為O(N)
問題是對于以上的這個(gè)題目舞肆，如何用java語言寫出基數(shù)排序的代碼焦辅？(計(jì)數(shù)排序和基數(shù)排序都不是基于比較的排序算法，二者的思想來自通排序)基數(shù)排序是先準(zhǔn)備10個(gè)桶(隊(duì)列)根據(jù)個(gè)位十位百位進(jìn)入相對應(yīng)的0號到9號桶椿胯，然后倒出來就有序了筷登，代碼怎么實(shí)現(xiàn)？
