面試筆試必用-必須掌握的Java排序算法

Java排序算法
）分類
）插入排序（直接插入排序希爾排序）
）交換排序（冒泡排序快速排序）
）選擇排序（直接選擇排序堆排序）
）歸並排序
）分配排序（箱排序基數排序）
所需輔助空間最多歸並排序
所需輔助空間最少堆排序
平均速度最快快速排序
不穩定快速排序希爾排序堆排序
）選擇排序算法的時候
數據的規模 數據的類型 數據已有的順序
一般來說當數據規模較小時應選擇直接插入排序或冒泡排序任何排序算法在數據量小時基本體現不出來差距考慮數據的類型比如如果全部是正整數那麼考慮使用桶排序為最優 考慮數據已有順序快排是一種不穩定的排序（當然可以改進）對於大部分排好的數據快排會浪費大量不必要的步驟數據量極小而起已經基本排好序冒泡是最佳選擇我們說快排好是指大量隨機數據下快排效果最理想而不是所有情況
）總結
――按平均的時間性能來分
）時間復雜度為O(nlogn)的方法有快速排序堆排序和歸並排序其中以快速排序為最好
）時間復雜度為O(n)的有直接插入排序起泡排序和簡單選擇排序其中以直接插入為最好特 別是對那些對關鍵字近似有序的記錄序列尤為如此
）時間復雜度為O(n)的排序方法只有基數排序
當待排記錄序列按關鍵字順序有序時直接插入排序和起泡排序能達到O(n)的時間復雜度;而對於快速排序而言這是最不好的情況此時的時間性能蛻化為O(n)因此是應該盡量避免的情況簡單選擇排序堆排序和歸並排序的時間性能不隨記錄序列中關鍵字的分布而改變
――按平均的空間性能來分（指的是排序過程中所需的輔助空間大小）
） 所有的簡單排序方法(包括直接插入起泡和簡單選擇)和堆排序的空間復雜度為O()
） 快速排序為O(logn )為棧所需的輔助空間;
） 歸並排序所需輔助空間最多其空間復雜度為O(n );
）鏈式基數排序需附設隊列首尾指針則空間復雜度為O(rd )
――排序方法的穩定性能
） 穩定的排序方法指的是對於兩個關鍵字相等的記錄它們在序列中的相對位置在排序之前和 經過排序之後沒有改變
） 當對多關鍵字的記錄序列進行LSD方法排序時必須采用穩定的排序方法
） 對於不穩定的排序方法只要能舉出一個實例說明即可
） 快速排序希爾排序和堆排序是不穩定的排序方法
）插入排序
包括直接插入排序希爾插入排序
直接插入排序 將一個記錄插入到已經排序好的有序表中
sorted數組的第個位置沒有放數據
從sorted第二個數據開始處理
如果該數據比它前面的數據要小說明該數據要往前面移動
首先將該數據備份放到 sorted的第位置當哨兵
然後將該數據前面那個數據後移
然後往前搜索找插入位置
找到插入位置之後講 第位置的那個數據插入對應位置
O(n*n) 當待排記錄序列為正序時時間復雜度提高至O(n)
希爾排序（縮小增量排序 diminishing increment sort）先將整個待排記錄序列分割成若干個子序列分別進行直接插入排序待整個序列中的記錄基本有序時再對全體記錄進行一次直接插入排序

插入排序Java代碼
public class InsertionSort {
// 插入排序直接插入排序希爾排序
public void straightInsertionSort(double [] sorted){
int sortedLen= sortedlength;
for(int j=;j if(sorted[j] sorted[0]= sorted[j];//先保存一下後面的那個
sorted[j]=sorted[j-1];// 前面的那個後移。TW.WInGwiT.cOM
int insertPos=0;
for(int k=j-2;k>=0;k–){
if(sorted[k]>sorted[]){
sorted[k+]=sorted[k];
}else{
insertPos=k+;
break;
}
}
sorted[insertPos]=sorted[];
}
}
}
public void shellInertionSort(double [] sorted int inc){
int sortedLen= sortedlength;
for(int j=inc+;j if(sorted[j] sorted[0]= sorted[j];//先保存一下後面的那個

int insertPos=j;
for(int k=j-inc;k>=0;k-=inc){
if(sorted[k]>sorted[]){
sorted[k+inc]=sorted[k];
//數據結構課本上這個地方沒有給出判讀出錯
if(kinc<=0){
insertPos = k;
}
}else{
insertPos=k+inc;
break;
}
}
sorted[insertPos]=sorted[0];
}
}
}
public void shellInsertionSort(double [] sorted){
int[] incs={7,5,3,1};
int num= incs.length;

int inc=0;
for(int j=0;j inc= incs[j];
shellInertionSort(sorted,inc);
}
}
public static void main(String[] args) {
Random random= new Random(6);

int arraysize= 21;
double [] sorted=new double[arraysize];
System.out.print("Before Sort:");
for(int j=1;j sorted[j]= (int)(random.nextDouble()* 100);
System.out.print((int)sorted[j]+" ");
}
System.out.println();

InsertionSort sorter=new InsertionSort();
// sorter.straightInsertionSort(sorted);
sorter.shellInsertionSort(sorted);

System.out.print("After Sort:");
for(int j=1;j System.out.print((int)sorted[j]+" ");
}
System.out.println();
}
}
5）交換排序：
包括冒泡排序，快速排序。
冒泡排序法：該算法是專門針對已部分排序的數據進行排序的一種排序算法。如果在你的數據清單中只有一兩個數據是亂序的話，用這種算法就是最快的排序算法。如果你的數據清單中的數據是隨機排列的，那麼這種方法就成了最慢的算法了。因此在使用這種算法之前一定要慎重。這種算法的核心思想是掃描數據清單，尋找出現亂序的兩個相鄰的項目。當找到這兩個項目後，交換項目的位置然後繼續掃描。重復上面的操作直到所有的項目都按順序排好。
快速排序：通過一趟排序，將待排序記錄分割成獨立的兩個部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。具體做法是：使用兩個指針low,high, 初值分別設置為序列的頭，和序列的尾，設置pivotkey為第一個記錄，首先從high開始向前搜索第一個小於pivotkey的記錄和pivotkey所在位置進行交換，然後從low開始向後搜索第一個大於pivotkey的記錄和此時pivotkey所在位置進行交換，重復知道low=high了為止。
交換排序Java代碼：
public class ExchangeSort {
public void BubbleExchangeSort(double [] sorted){
int sortedLen= sorted.length;
for(int j=sortedLen;j>0;j–){
int end= j;
for(int k=1;k double tempB= sorted[k];
sorted[k]= sorted[k] sorted[k]:sorted[k+1];
if(Math.abs(sorted[k]-tempB)>10e-6){
sorted[k+1]=tempB;
}
}
}
}
public void QuickExchangeSortBackTrack(double [] sorted,
int low,int high){
if(low int pivot= findPivot(sorted,low,high);
QuickExchangeSortBackTrack(sorted,low,pivot-1);
QuickExchangeSortBackTrack(sorted,pivot+1,high);
}
}
public int findPivot(double [] sorted, int low, int high){
sorted[0]= sorted[low];
while(low while(low= sorted[0])–high;
sorted[low]= sorted[high];
while(low sorted[high]= sorted[low];
}
sorted[low]=sorted[0];
return low;
}
public static void main(String[] args) {
Random random= new Random(6);

int arraysize= 21;
double [] sorted=new double[arraysize];
System.out.print("Before Sort:");
for(int j=1;j sorted[j]= (int)(random.nextDouble()* 100);
System.out.print((int)sorted[j]+" ");
}
System.out.println();

ExchangeSort sorter=new ExchangeSort();
// sorter.BubbleExchangeSort(sorted);
sorter.QuickExchangeSortBackTrack(sorted, 1, arraysize-1);
System.out.print("After Sort:");
for(int j=1;j System.out.print((int)sorted[j]+" ");
}
System.out.println();
}
}
6）選擇排序：
分為直接選擇排序，堆排序
直接選擇排序：第i次選取 i到array.Length-1中間最小的值放在i位置。
堆排序：首先，數組裡面用層次遍歷的順序放一棵完全二叉樹。從最後一個非終端結點往前面調整，直到到達根結點，這個時候除根節點以外的所有非終端節點都已經滿足堆得條件了，於是需要調整根節點使得整個樹滿足堆得條件，於是從根節點開始，沿著它的兒子們往下面走（最大堆沿著最大的兒子走，最小堆沿著最小的兒子走）。主程序裡面，首先從最後一個非終端節點開始調整到根也調整完，形成一個heap， 然後將heap的根放到後面去（即：每次的樹大小會變化，但是 root都是在1的位置，以方便計算兒子們的index，所以如果需要升序排列，則要逐步大頂堆。因為根節點被一個個放在後面去了。降序排列則要建立小頂堆）
代碼中的問題：有時候第2個和第3個順序不對（原因還沒搞明白到底代碼哪裡有錯）
選擇排序Java代碼：
public class SelectionSort {
public void straitSelectionSort(double [] sorted){
int sortedLen= sorted.length;
for(int j=1;j int jMin= getMinIndex(sorted,j);
exchange(sorted,j,jMin);
}
}
public void exchange(double [] sorted,int i,int j){
int sortedLen= sorted.length;
if(i=0 && j>=0){
double temp= sorted[i];
sorted[i]=sorted[j];
sorted[j]=temp;
}
}
public int getMinIndex(double [] sorted, int i){
int sortedLen= sorted.length;

int minJ=1;
double min= Double.MAX_VALUE;
for(int j=i;j if(sorted[j] min= sorted[j];
minJ= j;
}
}
return minJ;
}

public void heapAdjust(double [] sorted,int start,int end){
if(start double temp= sorted[start];
// 這個地方j for(int j=2*start;j if(j+110e-6){
++j;
}
if(temp<=sorted[j]){
break;
}
sorted[start]=sorted[j];
start=j;
}
sorted[start]=temp;
}
}
public void heapSelectionSort(double [] sorted){
int sortedLen = sorted.length;

for(int i=sortedLen/2;i>0;i–){
heapAdjust(sorted,i,sortedLen);
}
for(int i=sortedLen;i>1;–i){
exchange(sorted,1,i);
heapAdjust(sorted,1,i-1);
}
}
public static void main(String [] args){
Random random= new Random(6);

int arraysize=9;
double [] sorted=new double[arraysize];
System.out.print(“Before Sort:”);
for(int j=1;j sorted[j]= (int)(random.nextDouble()* 100);
System.out.print((int)sorted[j]+" ");
}
System.out.println();

SelectionSort sorter=new SelectionSort();
// sorter.straitSelectionSort(sorted);
sorter.heapSelectionSort(sorted);

System.out.print("After Sort:");
for(int j=1;j System.out.print((int)sorted[j]+" ");
}
System.out.println();
}
}
7）歸並排序：
將兩個或兩個以上的有序表組合成一個新的有序表。歸並排序要使用一個輔助數組，大小跟原數組相同，遞歸做法。每次將目標序列分解成兩個序列，分別排序兩個子序列之後，再將兩個排序好的子序列merge到一起。
歸並排序Java代碼：
public class MergeSort {
private double[] bridge;//輔助數組
public void sort(double[] obj){
if (obj == null){
throw new NullPointerException("
The param can not be null!");
}
bridge = new double[obj.length]; // 初始化中間數組
mergeSort(obj, 0, obj.length - 1); // 歸並排序
bridge = null;
}
private void mergeSort(double[] obj, int left, int right){
if (left < right){
int center = (left + right) / 2;
mergeSort(obj, left, center);
mergeSort(obj, center + 1, right);
merge(obj, left, center, right);
}
}
private void merge(double[] obj, int left,
int center, int right){
int mid = center + 1;
int third = left;
int tmp = left;
while (left <= center && mid <= right){
// 從兩個數組中取出小的放入中間數組
if (obj[left]-obj[mid]<=10e-6){
bridge[third++] = obj[left++];
} else{
bridge[third++] = obj[mid++];
}
}

// 剩余部分依次置入中間數組
while (mid <= right){
bridge[third++] = obj[mid++];
}
while (left <= center){
bridge[third++] = obj[left++];
}
// 將中間數組的內容拷貝回原數組
copy(obj, tmp, right);
}
private void copy(double[] obj, int left, int right)
{
while (left <= right){
obj[left] = bridge[left];
left++;
}
}
public static void main(String[] args) {
Random random = new Random(6);

int arraysize = 10;
double[] sorted = new double[arraysize];
System.out.print("Before Sort:");
for (int j = 0; j < arraysize; j++) {
sorted[j] = (int) (random.nextDouble() * 100);
System.out.print((int) sorted[j] + " ");
}
System.out.println();

MergeSort sorter = new MergeSort();
sorter.sort(sorted);

System.out.print("After Sort:");
for (int j = 0; j < sorted.length; j++) {
System.out.print((int) sorted[j] + " ");
}
System.out.println();
}
}

8）基數排序：
使用10個輔助隊列，假設最大數的數字位數為 x， 則一共做 x次，從個位數開始往前，以第i位數字的大小為依據，將數據放進輔助隊列，搞定之後回收。下次再以高一位開始的數字位為依據。
以Vector作輔助隊列，基數排序的Java代碼：
public class RadixSort {
private int keyNum=-1;
private Vector> util;

public void distribute(double [] sorted, int nth){
if(nth<=keyNum && nth>0){
util=new Vector>();
for(int j=0;j<10;j++){
Vector temp= new Vector ();
util.add(temp);
}
for(int j=0;j int index= getNthDigit(sorted[j],nth);
util.get(index).add(sorted[j]);
}
}
}
public int getNthDigit(double num,int nth){
String nn= Integer.toString((int)num);
int len= nn.length();
if(len>=nth){
return Character.getNumericValue(nn.charAt(len-nth));
}else{
return 0;
}
}
public void collect(double [] sorted){
int k=0;
for(int j=0;j<10;j++){
int len= util.get(j).size();
if(len>0){
for(int i=0;i sorted[k++]= util.get(j).get(i);
}
}
}
util=null;
}
public int getKeyNum(double [] sorted){
double max= Double.MIN_VALUE;
for(int j=0;j if(sorted[j]>max){
max= sorted[j];
}
}
return Integer.toString((int)max).length();
}
public void radixSort(double [] sorted){
if(keyNum==-1){
keyNum= getKeyNum(sorted);
}
for(int i=1;i<=keyNum;i++){
distribute(sorted,i);
collect(sorted);
}
}
public static void main(String[] args) {
Random random = new Random(6);

int arraysize = 21;
double[] sorted = new double[arraysize];
System.out.print(“Before Sort:”);
for (int j = 0; j < arraysize; j++) {
sorted[j] = (int) (random.nextDouble() * 100);
System.out.print((int) sorted[j] + ” “);
}
System.out.println();

RadixSort sorter = new RadixSort();
sorter.radixSort(sorted);

System.out.print(“After Sort:”);
for (int j = 0; j < sorted.length; j++) {
System.out.print((int) sorted[j] + ” “);
}
System.out.println();
}
}
=====》總結：上述Java代碼中，基本上用的都是double數組，如果想要應用其他的數組，只需要將double數組改成 Comparable接口數組，凡是實現了Comparable接口的都可以用。而在C++中，是用模板類來解決這個問題。

From:http://tw.wingwit.com/Article/program/sjjg/201405/30741.html