1. 插入排序
思想： 假設左邊的已經(jīng)排好序惦费，要加入的數(shù)值需要從右邊開始逐個比較哮塞。如果小于下一個要比較的值
arr[j-1]南蹂，那么交換arr[j-1]到后面一個位置。如果大于或等于（即不小于）下一個要比較的值arr[j-1]囱井，那么要插入的值位置應該在arr[j]驹尼。java實現(xiàn)
package Sort;
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
int[] arr= {5,3,8,6,4};
ToInsertSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void ToInsertSort(int[] arr) {
if(arr==null || arr.length==0)
return;
for(int i=1;i<arr.length;i++) { //假設最左邊的已經(jīng)排序好
int temp=arr[i]; //這個位置可能被占用
int j=i;
while(j>0&&arr[j-1]>temp) {
arr[j]=arr[j-1];
j--;
}
arr[j]=temp;
}
}
}
- 復雜度
- 時間上，最壞庞呕，1+2+ ... +(n-1)=n*(n-1)/2新翎；最好，n
- 空間上住练，n
2. 選擇排序
- 思想：插入排序的改進地啰。考慮到插入排序在序列基本有序的條件下讲逛，效率更高亏吝。選擇增量序列，進行k趟排序盏混。
package Sort;
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] arr= {5,3,8,6,4,9,10,5,6};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void shellSort(int[] arr) {
if(arr==null || arr.length==0)
return;
int d=arr.length/2;
for(;d>=1;d=d/2) {
shellInsert(arr,d);
}
}
private static void shellInsert(int[] arr,int d) {
//進行插入排序
for(int i=d;i<arr.length;i++) { //假設d位置之前的已經(jīng)排好序
int temp=arr[i];
int j=i;
while(j>d-1&&arr[j-d]>temp) {
arr[j]=arr[j-d];
j-=d; //競爭j-d -->j-d位置
}
arr[j]=temp;
}
}
}
- 復雜度
- 時間上蔚鸥，最壞惜论，不好算，是o(n^2 )止喷；最好馆类，log(n)*n；平均弹谁，n^1.3
- 空間上乾巧，n
3. 選擇排序
- 思想：選擇出最小值的下標，進行交換预愤。
package Sort;
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int[] arr= {5,3,8,6,4,9,10,5,6};
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void selectSort(int[] arr) {
if(arr==null || arr.length==0)
return;
for(int i=0;i<arr.length-1;i++) {
int minindex=i;
for(int j=i+1;j<arr.length;j++) {
if(arr[minindex]>arr[j])
minindex=j;
}
if(minindex!=i)
swap(arr,minindex,i);
}
}
private static void swap(int[] arr,int i,int j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
- 復雜度
- 時間上沟于，最壞和最好都是1+2+3+ ... +n-1=n(n-1)/2
- 空間上，n鳖粟。輔助空間o(1)
4. 冒泡排序
- 思想：比較相鄰的兩個元素社裆，仍后根據(jù)結果決定是否交換位置。比選擇排序要差向图，交換次數(shù)太多。不過有一點優(yōu)于選擇排序：可以根據(jù)某個指標判斷是否提前完成排序标沪。
package Sort;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr= {5,3,8,6,4,9,10,5,6};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bubbleSort(int[] arr) {
if(arr==null || arr.length==0)
return;
int flag=0;
for(int i=0;i<arr.length-1;i++) {
if(flag==1)
break;
flag=1;
for(int j=arr.length-1;j>i;j--) {
if(arr[j]<arr[j-1]) {
swap(arr,j,j-1);
flag=0;
}
}
}
}
private static void swap(int[] arr,int i,int j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
- 復雜度
- 時間上榄攀，最壞o(n^2) ，最好o(n)金句。
- 空間上檩赢，n。輔助空間o(1)
5. 歸并排序
- 思想：分而治之违寞，后合并贞瞒。分到只有一個數(shù)為止，然后合并趁曼。
package Sort;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] arr= {5,3,8,6,4,9,10,5,6};
mergeSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr,int left,int right) {
if(arr==null || arr.length==0)
return;
if(left>=right)
return;
int mid=(left+right)/2;
mergeSort(arr,left,mid);
mergeSort(arr,mid+1,right);
merge(arr,left,mid,right);
}
private static void merge(int[] arr,int left,int mid,int right) {
int[] temp=new int[right-left+1];
int i=left;
int j=mid+1;
int k=0;
while(i<=mid&&j<=right) {
if(arr[i]<arr[j])
temp[k++]=arr[i++];
else
temp[k++]=arr[j++];
}
while(i<=mid)
temp[k++]=arr[i++];
while(j<=right)
temp[k++]=arr[j++];
for(int p=0;p<temp.length;p++)
arr[left+p]=temp[p];
}
}
- 復雜度
- 時間上军浆，nlog(n)。
- 空間上挡闰，n+n乒融。輔助空間o(n)
6. 快速排序
- 思想：分而治之。每次確定出來一個pivot（基準）摄悯。它左邊的數(shù)都比pivot小赞季，右邊都大。這樣pivot的位置就確定了奢驯。遞歸下去申钩。有歸并的味道。不過瘪阁，歸并是后期發(fā)力撒遣《鲜ⅲ快速一開始就會確定一個位置。
package Sort;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr= {5,3,8,6,4,9,10,5,6};
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr,int left,int right) {
if(arr==null || arr.length==0)
return;
if(left>=right)
return;
int pivot=partition(arr,left,right);
quickSort(arr,left,pivot-1);
quickSort(arr,pivot+1,right);
}
private static int partition(int[] arr,int left,int right) {
int pivot=left;
int pivotKey=arr[left];
while(left<right) {
while(left<right&&arr[right]>=pivotKey)
right--;
while(left<right&&arr[left]<=pivotKey)
left++;
swap(arr,left,right);
}
if(left!=pivot)
swap(arr,left,pivot);
return left;
}
private static void swap(int[] arr,int i,int j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
- 復雜度
- 時間上愉舔，平均nlog(n)钢猛。
- 空間上，n轩缤。輔助空間o(1)
7. 堆排序
- 思想：首先命迈，調(diào)整數(shù)組到滿足堆性質(zhì)。大頂堆火的，即數(shù)組第1個數(shù)最大壶愤。然后交換首末數(shù)。這樣最后面的數(shù)最大馏鹤。調(diào)整堆征椒。
package Sort;
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] arr= {5,3,8,6,4,9,10,5,6};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
for(int i=arr.length/2-1;i>=0;i--) { //下標為arr.length/2-1，才開始有子葉
heapAdjust(arr,i,arr.length-1);
}
for(int i=arr.length-1;i>0;i--) {
int temp=arr[0];
arr[0]=arr[i];
arr[i]=temp;
heapAdjust(arr,0,i-1);
}
}
private static void heapAdjust(int[] arr,int start,int end) {
int temp=arr[start];
int i=2*start+1;
while(i<=end) { //子節(jié)點是2*i+1 2*i+1
if(i<end&&arr[i]<arr[i+1])
i++;
if(temp>=arr[i]) //滿足堆性質(zhì)
break;
arr[start]=arr[i];
start=i; //開啟下一輪,確定下標i位置是否滿足性質(zhì)
i=2*start+1;
}
arr[start]=temp;
}
}
- 復雜度
- 時間上湃累，o(nlog(n))勃救。
- 空間上，n治力。輔助空間o(1)
8. 基數(shù)排序
- 思想：借助多關鍵字排序思想對單邏輯關鍵字進行排序的方法蒙秒。如果對數(shù)字進行排序，那么個位宵统、十位晕讲、百位就是不同優(yōu)先級的關鍵字，如果要進行升序排序马澈，那么個位瓢省、十位、百位優(yōu)先級一次增加痊班∏诨椋基數(shù)排序是通過多次的收分配和收集來實現(xiàn)的，關鍵字優(yōu)先級低的先進行分配和收集辩块。
package Sort;
import java.util.*;
public class RadixSort {
public static void main(String[] args) {
int max=100;
int min=1;
int[] arr = new int[10];
Random random = new Random(47);
for (int i=0; i<10; i++) {
int s = random.nextInt(max)%(max-min+1) + min;
arr[i]=s;
//System.out.println(s);
}
//int[] arr= {5,3,8,6,4,9,10,5,6,12,123};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr) {
if(arr==null || arr.length==0)
return;
int arrMax=getMax(arr);
int maxBit = (arrMax+"").length();
for(int i=1;i<=maxBit;i++) {
List<List<Integer>> buf=distribute(arr,i,maxBit);
collect(arr,buf);
}
}
public static void collect(int[] arr,List<List<Integer>> buf) {
int k=0;
for(List<Integer> bucket:buf) {
for(int ele:bucket) {
arr[k++]=ele;
}
}
}
public static List<List<Integer>> distribute(int[] arr,int bit,int maxBit){
List<List<Integer>> buf = new ArrayList<List<Integer>>();
for(int i=1;i<=10;i++)
buf.add(new LinkedList<Integer>());
for(int i=0; i<arr.length; i++) {
buf.get(getNBit(arr[i], bit)).add(arr[i]);
}
return buf;
}
public static int getNBit(int x, int n) {
String sx = x + "";
if(sx.length() < n)
return 0;
else{
return sx.charAt(sx.length()-n)-'0';
}
}
public static int getMax(int[] arr) {
int max=arr[0];
for(int i=1;i<arr.length;i++){
if(arr[i]>max){
max=arr[i];
}
}
return max;
}
}
- 復雜度
- 時間上蛔六，o(d(n+rd))
- 空間上，n+rd废亭。輔助空間o(rd)
總結（來源“算法愛好者”）
在前面的介紹和分析中我們提到了冒泡排序国章、選擇排序、插入排序三種簡單的排序及其變種快速排序豆村、堆排序液兽、希爾排序三種比較高效的排序。后面我們又分析了基于分治遞歸思想的歸并排序還有計數(shù)排序、桶排序四啰、基數(shù)排序三種線性排序宁玫。我們可以知道排序算法要么簡單有效，要么是利用簡單排序的特點加以改進柑晒，要么是以空間換取時間在特定情況下的高效排序欧瘪。但是這些排序方法都不是固定不變的，需要結合具體的需求和場景來選擇甚至組合使用匙赞。才能達到高效穩(wěn)定的目的佛掖。沒有最好的排序，只有最適合的排序涌庭。
下面就總結一下排序算法的各自的使用場景和適用場合芥被。
從平均時間來看，快速排序是效率最高的坐榆，但快速排序在最壞情況下的時間性能不如堆排序和歸并排序拴魄。而后者相比較的結果是，在n較大時歸并排序使用時間較少席镀，但使用輔助空間較多匹中。
上面說的簡單排序包括除希爾排序之外的所有冒泡排序、插入排序愉昆、簡單選擇排序职员。其中直接插入排序最簡單，但序列基本有序或者n較小時跛溉，直接插入排序是好的方法，因此常將它和其他的排序方法扮授，如快速排序芳室、歸并排序等結合在一起使用。
基數(shù)排序的時間復雜度也可以寫成O(d*n)刹勃。因此它最使用于n值很大而關鍵字較小的的序列堪侯。若關鍵字也很大，而序列中大多數(shù)記錄的最高關鍵字均不同荔仁，則亦可先按最高關鍵字不同伍宦，將序列分成若干小的子序列，而后進行直接插入排序乏梁。
從方法的穩(wěn)定性來比較次洼，基數(shù)排序是穩(wěn)定的內(nèi)排方法，所有時間復雜度為O(n^2)的簡單排序也是穩(wěn)定的遇骑。但是快速排序卖毁、堆排序、希爾排序等時間性能較好的排序方法都是不穩(wěn)定的落萎。穩(wěn)定性需要根據(jù)具體需求選擇亥啦。
上面的算法實現(xiàn)大多數(shù)是使用線性存儲結構炭剪，像插入排序這種算法用鏈表實現(xiàn)更好，省去了移動元素的時間翔脱。具體的存儲結構在具體的實現(xiàn)版本中也是不同的奴拦。
