3.31日：排序數組
給定一個整數數組
nums
，将該數組升序排列。
我感覺有必要總結一下了！
1、直接插入排序(Insertion Sort)
直接插入排序是一種簡單直覺的排序方法。思想：對于未排序的元素，在已排序的元素中從後向前掃描，找到合适的位置後插入。
直接插入排序是穩定的。因為未排序的元素在向前掃描的過程中遇到相同的元素就不會繼續向前掃描了，更不會插在它的前面。
平均和最差情況T(n) = O(n2)，最佳情況T(n) = O(n)。如果這個數組原來就是有序的，那麼隻需要比較 n-1 次，不需要移動，是以最好情況下的時間複雜度是 n。
2、希爾排序(Shell Sort)
希爾排序是直接插入排序的更新版。主要思想是把一組數組分成了不同的“組”，隻有同組元素才能比較和排序。随着排序的進行，“組”會慢慢減少，“組”中的元素也會慢慢增多，數組整體也會慢慢有序。
希爾排序是不穩定的。雖然是否穩定是由該算法代碼的具體實作決定的，但這種元素間遠距離的交換一般都很難保證相同元素的相對位置。
最差情況 T(n) = O(n2)，平均情況 T(n) = O(n1.3)，最佳情況 T(n) = O(n)。
3、簡單選擇排序(Selection Sort)
簡單選擇排序是時間複雜度上最穩定的排序算法之一。排序方法很簡單，每次都從未排序的數組中找到最小的元素，然後放在最前端。
簡單選擇排序是不穩定的。畢竟它每趟隻是選擇最小的元素，選哪個可不一定，沒辦法保證兩個相同元素的相對位置。
任何情況下 T(n) = O(n2)，是以說它在時間複雜度上穩定嘛。因為無論數組有序或是無序，簡單選擇排序都會周遊 n 遍這個數組。
4、堆排序(Heap Sort)
堆排序是利用了最大堆這種資料結構的排序方法。因為每次将堆調整為最大堆後，堆的根結點一定是堆中最大的元素。我們通過不停的取出最大堆的根節點和重新調整為最大堆，就可以一直得到未排序數組的最大值。
堆排序是不穩定的。畢竟遠距離元素交換，不好保證相同元素的相對位置。
任何情況下 T(n) = O(nlogn)
5、冒泡排序(Bubble Sort)
冒泡排序是很簡答的一種排序方法。顧名思義，數組中最大的元素會像泡泡一樣“浮”到隊列的末端。主要的思想是通過元素的兩兩交換，将隊列中最大的元素移動到隊列的末尾。
冒泡排序是穩定的。因為它是元素兩兩交換，如果兩個元素相等，就不會交換。這樣就保證了相同元素的相對位置不變。
平均和最差情況 T(n) = O(n2)，最佳情況 T(n) = O(n)。因為平均和最差情況下每次周遊這個長度為 n 數組都隻能确定一個元素，是以想要确定全部 n 個元素的位置，時間複雜度就為 n×n。但最佳情況下，如果數組是有序的，那麼隻要周遊一次就夠了，是以時間複雜度是 n。
6、快速排序(Quick Sort)
快速排序是十大排序算法中最經典的一個。主要思想是通過一趟排序将待排序的數組分為獨立的兩個部分，前半部分都比中間的關鍵元素小，後半部分都比中間的關鍵元素大，進而确定了中間的關鍵元素的位置。
快速排序是不穩定的，畢竟要遠距離的調換元素。
最佳和平均情況下 T(n) = O(nlogn)，最差情況下 T(n) = O(n2)。快速排序的實作依賴的是遞歸加二分法，但這個二分法并不是完美的二分法。如果二分法每次正好隻分到一邊，那麼一共就有 n-1 層，是以時間複雜度是 n2；其他情況下一共有logn 層，是以時間複雜度是 n*logn。
7、歸并排序(Merge Sort)
歸并排序以需要額外空間作為代價，表現比簡單選擇排序好得多。二路歸并排序就是兩兩排序，然後兩個區域一起排序，以此類推。
歸并排序是穩定的。因為在使用額外空間的時候，靠前區域的元素隻要小于等于靠後區域的元素就能被放進額外空間。
任何情況下 T(n) = O(nlogn)。歸并排序主要是靠遞歸加二分法，每一層的時間代價都是 n 相關，一共有 logn 層，是以時間複雜度是 n*logn。是以無論數組是不是有序的，都會被二分法分為前後兩個部分，然後遞歸下去。
8、基數排序(Radix Sort)
基數排序是非比較排序。主要思想是對數組中所有元素先根據其個位進行排序，再根據其十位進行排序，之後是百位、千位，以此類推，直到最高位。
基數排序是穩定的。因為它是非比較排序，元素之間的順序不依賴元素之間的比較。
任何情況下 T(n) = O(n * k)，其中 k 是桶的個數。
9、計數排序(Counting Sort)
計數排序是非比較排序。它的核心是将數組中的元素值轉換為鍵存儲在額外空間中。主要思想是額外建立一個數組，額外數組中元素下标是待排序數組中元素的值，而額外數組中的值是其下标的值在待排序數組中作為元素的值出現的次數。
計數排序是穩定的。因為它是非比較排序，元素之間的順序不依賴元素之間的比較。
任何情況下 T(n) = O(n+k)，其中 k 是桶的個數。
10、桶排序(Bucket Sort)
桶排序是計數排序的更新版，也是非比較排序。主要思想是對數組中數值範圍進行劃分，數組中的每個元素根據其數值的所在範圍，進入不同的“桶”。然後在不同的桶中分别對這些元素進行排序（直接插入排序），再依次輸出。
桶排序是穩定的。因為它是非比較排序，元素之間的順序不依賴元素之間的比較。
最好和平均情況下 T(n) = O(n+k)，最差情況下 T(n) = O(n2)，其中 k 是桶的個數。
Java代碼
import java.util.ArrayList;
import java.util.Arrays;
public class Sort {
public static void main(String[] args) {
int[] arr = new int[20];
int index = 0;
for(int i = 20;i > 0;i--)
arr[index++] = i;
System.out.println("原數組：");
System.out.println(Arrays.toString(arr));
System.out.println("開始排序");
arr = MergeSort(arr);
System.out.println("排序後為：");
System.out.println(Arrays.toString(arr));
}
// 工具：交換數組中元素的位置
public static int[] swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// ****** 1.直接插入排序 ******
public static int[] InsertionSort(int[] arr){
if(arr.length == 0 || arr.length == 1)
return arr;
for(int i = 0;i < arr.length - 1;i++){
// 将 i+1 位置的數插入 0 到 i 之間的數組，從後往前周遊
// current 指 i+1 的位置元素，pre 指 0 到 i 中依次向前周遊的指針
int current = arr[i+1];
int pre = i;
while(pre >= 0 && current < arr[pre]){
arr[pre+1] = arr[pre];
pre--;
}
// 最後将原來 i+1 位置的元素放入現在 0 到 i+1 之間數組中正确的位置上
// pre+1 是因為剛才循環結束時又自減了一次
arr[pre+1] = current;
// 列印這一輪的排序結果
System.out.println(Arrays.toString(arr));
}
return arr;
}
// ****** 2.希爾排序 ******
// 希爾排序最重要的變量就是 gap，所有需要+1或者自加1的地方都要注意
public static int[] ShellSort(int[] arr){
if(arr.length == 0 || arr.length == 1)
return arr;
int current, gap = arr.length / 2;
while(gap > 0){
for(int i = gap;i < arr.length;i++){
// 将 pre+gap 位置的數插入 0 到 pre 之間“同組”的數組，從後往前周遊
// current 指 pre+gap 的位置元素
current = arr[i];
int pre = i - gap;
while(pre >= 0 && arr[pre] > current){
arr[pre+gap] = arr[pre];
pre -= gap;
}
arr[pre+gap] = current;
// 列印這一輪的排序結果
System.out.println(Arrays.toString(arr));
}
gap /= 2;
}
return arr;
}
// ****** 3.簡單選擇排序 ******
public static int[] SelectionSort(int[] arr){
if(arr.length == 0 || arr.length == 1)
return arr;
for(int i = 0;i < arr.length - 1;i++){
// 每一輪挑出一個最小的元素，依次與不斷增長的 i 位置的元素交換
int MinIndex = i;
for(int j = i;j < arr.length;j++){
if(arr[j] < arr[MinIndex])
MinIndex = j;
}
arr = swap(arr,MinIndex,i);
// 列印這一輪的排序結果
System.out.println(Arrays.toString(arr));
}
return arr;
}
// ****** 4.堆排序 ******
// 主函數
public static int[] HeapSort(int[] arr){
if(arr.length == 0 || arr.length == 1)
return arr;
int len = arr.length;
// 堆排序第一步是先把目前數組變成一個最大堆
arr = AdjustMaxHeap(arr, len-1);
while(len > 0){
// 取出堆頂的元素（最大元素）與末尾還沒有确定位置的元素交換
arr = swap(arr,0,len - 1);
// 列印這一輪的排序結果
System.out.println(Arrays.toString(arr));
len--;
arr = AdjustMaxHeap(arr,len - 1);
}
return arr;
}
// 調整為最大堆
public static int[] AdjustMaxHeap(int[] arr, int lastIndex){
for(int i = (lastIndex - 1) / 2;i>=0;i--){
arr = AdjustLocalHeap(arr,lastIndex,i);
}
return arr;
}
//調整局部堆使其成為局部最大堆
/*
注意事項：堆中結點是從 1 開始的，但把數組看作堆的話，數組的下标是從 0 開始的
那麼父結點與子結點的關系就會發生變化：
父結點 = （子結點-1）/2
左子結點 = 父結點*2+1
右子結點 = 父結點*2+2
*/
public static int[] AdjustLocalHeap(int[] arr,int lastIndex,int i){
// 找出目前結點和左右子結點（如果有左右子結點的話）中最大的元素，讓這個最大的元素成為父結點
int maxIndex = i;
if(i*2+1 <= lastIndex && arr[i] < arr[i*2+1])
maxIndex = i*2+1;
// 這裡要多一個右子結點是否大于左子結點的判定
if(i*2+2 <= lastIndex && arr[i] < arr[i*2+2] && arr[i*2+1] < arr[i*2+2])
maxIndex = i*2+2;
// 如果父結點不是三個結點中的最大結點，那麼将最大結點變成父結點
// 再通過遞歸看看這個比較小的父結點能不能再“往下沉”
if(maxIndex != i){
arr = swap(arr,maxIndex,i);
arr = AdjustLocalHeap(arr,lastIndex,maxIndex);
}
return arr;
}
// ****** 5.冒泡排序 ******
public static int[] BubbleSort(int[] arr){
if(arr.length == 0 || arr.length ==1)
return arr;
for(int i = arr.length-1;i > 0;i--){
for(int j = 1;j <= i;j++){
if(arr[j] < arr[j-1])
arr = swap(arr,j,j-1);
}
// 列印這一輪的排序結果
System.out.println(Arrays.toString(arr));
}
return arr;
}
// ****** 6.快速排序 ******
//主函數
public static int[] QuickSort(int[] arr){
if(arr.length == 0 || arr.length ==1)
return arr;
arr = LocalQuickSort(arr,0,arr.length -1 );
return arr;
}
// 快速排序
public static int[] LocalQuickSort(int[] arr, int start, int last){
if(start >= last)
return arr;
// benchmark 指基準數，也就是這一輪将要确定位置的數
int benchmark = arr[start];
int left = start;
int right = last;
while(left < right){
// 必須右指針先走
while(arr[right] > benchmark && left < right) right--;
if(arr[right] <= benchmark && left < right) arr[left++] = arr[right];
while(arr[left] < benchmark && left < right) left++;
if(arr[right] >= benchmark && left < right) arr[right--] = arr[left];
}
arr[left] = benchmark;
// 列印這一輪的排序結果
System.out.println(Arrays.toString(arr));
// 通過遞歸，分别對已确定位置的數的兩邊區域進行快速排序
arr = LocalQuickSort(arr,start,left-1);
arr = LocalQuickSort(arr,left+1,last);
return arr;
}
// ****** 7.歸并排序 ******
// 主函數
public static int[] MergeSort(int[] arr){
if(arr.length == 0 || arr.length ==1)
return arr;
arr = Merge(arr,0,arr.length-1);
return arr;
}
// 歸并排序
public static int[] Merge(int[] arr,int start,int last){
// start < last 的判斷意味着 arr 指定的範圍内必須至少有兩個元素
if(start < last){
int mid = (start + last) / 2;
// 左右部分分别遞歸
arr = Merge(arr,start,mid);
arr = Merge(arr,mid+1,last);
// 遞歸層面：從裡往外依次将左半部分和右半部分整合成一個部分
arr = merge(arr,start,mid,last);
}
return arr;
}
public static int[] merge(int[] arr,int start,int mid,int last){
// tempArr 指一個額外數組，用來臨時給 arr 中同一區域的元素排序
int[] tempArr = new int[arr.length];
// p1 指 arr 指定區域的左半部分的指針，p2 指 arr 指定區域的右半部分的指針，p 指額外數組 tempArr 的指針
int p1 = start, p2 = mid+1, p = start;
// 從指定區域的左右半部分中取出最小元素放入額外數組，完成指定區域内的排序
while(p1 <= mid && p2 <= last){
if(arr[p1] <= arr[p2])
tempArr[p++] = arr[p1++];
else
tempArr[p++] = arr[p2++];
}
while(p1 <= mid) tempArr[p++] = arr[p1++];
while(p2 <= last) tempArr[p++] = arr[p2++];
// 将額外數組中的資料覆寫到原 arr 數組中
for(int i = start;i <= last;i++)
arr[i] = tempArr[i];
System.out.println(Arrays.toString(arr));
return arr;
}
// ****** 8.基數排序 ******
public static int[] RadixSort(int[] arr){
if(arr.length == 0 || arr.length ==1)
return arr;
// max 指數組中最大的數，maxDigit 指這個最大的數是幾位數
int max = arr[0];
for(int x:arr)
max = Math.max(x,max);
int maxDigit = 0;
while(max != 0){
max /= 10;
maxDigit++;
}
// mod 用于為數組中的數取餘數，div 用于把通過 mod 取的餘數變成個位數
int mod = 10;
int div = 1;
ArrayList<ArrayList<Integer>> bucket = new ArrayList<ArrayList<Integer>>();
for(int j = 0;j < 10;j++){
bucket.add(new ArrayList<Integer>());
}
for(int i = 0;i<maxDigit;i++,mod *= 10,div *= 10){
// 列印這一輪的排序結果
System.out.println(Arrays.toString(arr));
for(int j = 0;j < arr.length;j++){
// num 指目前元素 arr[j] 的個/十/百/千位是幾
int num = (arr[j] % mod) / div;
bucket.get(num).add(arr[j]);
}
int index = 0;
for(int j = 0;j < 10;j++){
if(bucket.get(j).size() != 0){
for(int x:bucket.get(j))
arr[index++] = x;
// 将桶中所有的動态數組清空，否則第二次循環開始再用到這些動态數組時裡面還會有資料
bucket.get(j).clear();
}
}
}
return arr;
}
// ****** 9.計數排序 ******
public static int[] CountingSort(int[] arr){
if(arr.length ==0 || arr.length == 1)
return arr;
int min, max;
min = max = arr[0];
for(int x: arr){
if(x > max)
max = x;
if(x < min)
min = x;
}
// bucket 指用來存儲每個元素出現次數的桶，長度為元素的範圍
int[] bucket = new int[max - min +1];
// 把 bucket 用 0 填滿，因為之後要累加
Arrays.fill(bucket,0);
// 在 bucket 中相應的位置記錄每個元素出現的次數
for(int x:arr){
bucket[x - min]++;
}
int index = 0;
// 依次從 bucket 中提取元素覆寫到原來的 arr 上
for(int i =0;i<bucket.length;i++){
while(bucket[i] != 0){
arr[index++] = i + min;
bucket[i]--;
}
}
return arr;
}
// ****** 10.桶排序 ******
// 主函數
public static int[] BucketSort(int[] arr){
if(arr.length == 0 || arr.length == 1)
return arr;
arr = Bucket(arr,5);
return arr;
}
// 桶排序
// bucketSize 指每個桶的容量，bucketCount 指桶的個數
public static int[] Bucket(int[] arr,int bucketSize){
int min,max;
min = max = arr[0];
for(int x:arr){
if(x > max)
max = x;
if(x > min)
min = x;
}
int bucketCount = (max - min) / bucketSize +1;
ArrayList<ArrayList<Integer>> bucket = new ArrayList<ArrayList<Integer>>();
for(int i = 0;i < bucketCount;i++)
bucket.add(new ArrayList<Integer>());
for(int x: arr){
// 周遊每個桶
for(int bucketIndex = 0;bucketIndex < bucketCount;bucketIndex++){
// 如果 arr 目前元素在該桶的範圍内，則将該元素放入該桶内，并結束周遊每個桶的循環
if(x >= min + bucketIndex*bucketSize && x < min + (bucketIndex+1)*bucketSize){
bucket.get(bucketIndex).add(x);
break;
}
}
}
int index = 0;
for(int i = 0;i < bucketCount;i++){
// 對每個桶使用直接插入排序，調整桶内元素的順序
bucket.set(i,InsertionSortOfArrayList(bucket.get(i)));
for(int x:bucket.get(i))
arr[index++] = x;
}
return arr;
}
// 針對動态數組的直接插入排序
public static ArrayList<Integer> InsertionSortOfArrayList(ArrayList<Integer> arr){
if(arr.size() == 0 || arr.size() ==1)
return arr;
int current;
int pre;
for(int i = 0;i < arr.size() - 1;i++){
pre = i;
current = arr.get(i+1);
while(arr.get(pre) > current && pre >= 0){
arr.set(pre+1,arr.get(pre));
pre--;
}
arr.set(pre+1,current);
}
return arr;
}
}