一、複雜度估計和排序演算法（上）
1。 時間複雜度和空間複雜度
時間複雜度：演算法的時間複雜度，也就是演算法的時間量度，記作：T（n）=O（f（n））。
它表示隨問題規模n的增大，演算法執行時間的增長率和f（n）的增長率相同，稱作算
法的漸近時間複雜度，簡稱為時間複雜度。其中f（n）是問題規模n的某個函式。 這
樣用大寫O（ ）來體現演算法時間複雜度的記法，我們稱之為大O記法。 一般情況下，
隨n的增大，T（n）增長最慢的演算法為最優演算法。
空間複雜度：是對一個演算法在執行過程中臨時佔用儲存空間大小的量度記做
S（n）=O（f（n））。一個演算法在計算機儲存器上所佔用的儲存空間，包括儲存演算法本身
所佔用的儲存空間，演算法的輸入輸出資料所佔用的儲存空間和演算法在執行過程中臨
時佔用的儲存空間這三個方面。
在我們學習資料結構的過程中。可能會遇到這樣的一個問題：在進行測試排序演算法
時，在資料小的情況下，程式可以正常執行，但是當有大量資料時，就會出現各種
報錯，或者出現排序錯誤的情況，這種問題很常見，這並不一定說明實現的演算法是
錯誤的。基於這樣的一個問題，對數器可以幫助我們解決。所謂的對數器就是幫助
我們隨機生成一個不定長和不定值的陣列。
下面以氣泡排序來實現：
package com。ceshi；
import java。util。Arrays；
public class duishuqi {
/**
* 氣泡排序
* @param arr
*/
public static void bubbleSort（int［］ arr） {
if （arr == null || arr。length < 2） {
return；
}
for （int e = arr。length - 1； e > 0； e——） {
for （int i = 0； i < e； i++） {
if （arr［i］ > arr［i + 1］） {
swap（arr， i， i + 1）；
}
}
}
}
/**
* 交換陣列的兩個值
* @param arr 運算元組
* @param i 陣列下標
* @param j 陣列下標
*/
public static void swap（int［］ arr， int i， int j） {
int temp；
temp = arr［i］；
arr［i］ = arr［j］；
arr［j］ = temp；
}
/**
* 對陣列進行排序， 這個排序一定正確，用於驗證我們編寫的演算法是否正確
* @param arr
*/
public static void comparator（int［］ arr） {
Arrays。sort（arr）；
}
/**
* 隨機生成不定長、不定值的陣列
* @param maxSize 陣列最大長度
* @param maxValue 陣列最大值
* @return
*/
public static int［］ generateRandomArray（int maxSize， int maxValue） {
int［］ arr = new int［（int） （（maxSize + 1） * Math。random（））］；
for （int i = 0； i < arr。length； i++） {
arr［i］ = （int） （（maxValue + 1） * Math。random（）） - （int） （maxValue * Math。random（））；
}
return arr；
}
/**
* 複製陣列
* @param arr 需要複製的陣列
* @return
*/
public static int［］ copyArray（int［］ arr） {
if （arr == null） {
return null；
}
int［］ res = new int［arr。length］；
for （int i = 0； i < arr。length； i++） {
res［i］ = arr［i］；
}
return res；
}
/**
* 判斷兩個陣列是否相等
* @param arr1 源陣列
* @param arr2 目標陣列
* @return
*/
public static boolean isEqual（int［］ arr1， int［］ arr2） {
if （（arr1 == null && arr2 ！= null） || （arr1 ！= null && arr2 == null）） {
return false；
}
if （arr1 == null && arr2 == null） {
return true；
}
if （arr1。length ！= arr2。length） {
return false；
}
for （int i = 0； i < arr1。length； i++） {
if （arr1［i］ ！= arr2［i］） {
return false；
}
}
return true；
}
/**
* 輸出陣列結果
* @param arr 需要列印的陣列
*/
public static void printArray（int［］ arr） {
if （arr == null） {
return；
}
for （int i = 0； i < arr。length； i++） {
System。out。print（arr［i］ + “ ”）；
}
System。out。println（）；
}
public static void main（String［］ args） {
int testTime = 500000；
int maxSize = 100；
int maxValue = 100；
boolean succeed = true；
for （int i = 0； i < testTime； i++） {
int［］ arr1 = generateRandomArray（maxSize， maxValue）；
int［］ arr2 = copyArray（arr1）；
bubbleSort（arr1）；
comparator（arr2）；
// 判斷兩個排序後的陣列是否相等
if （！isEqual（arr1， arr2）） {
succeed = false；
break；
}
}
System。out。println（succeed ？ “Nice！” ： “Fucking fucked！”）；
int［］ arr = generateRandomArray（maxSize， maxValue）；
//printArray（arr）；
bubbleSort（arr）；
printArray（arr）；
}
}
輸出結果：
3。氣泡排序
3。1 原理
比較兩個相鄰的元素，將值大的元素交換到右邊，遇到相同的兩個數，不進行交換
3。2 思路
依次比較相鄰的兩個數，將比較小的數放在前面，比較大的數放在後面。
（1）第一次比較：首先比較第一和第二個數，將小數放在前面，將大數放在後面。
（2）比較第2和第3個數，將小數 放在前面，大數放在後面。
……
（3）如此繼續，知道比較到最後的兩個數，將小數放在前面，大數放在後面，重複步
驟，直至全部排序完成
（4）在上面一趟比較完成後，最後一個數一定是陣列中最大的一個數，所以在比較第
二趟的時候，最後一個數是不參加比較的。
（5）在第二趟比較完成後，倒數第二個數也一定是陣列中倒數第二大數，所以在第三
趟的比較中，最後兩個數是不參與比較的。
（6）依次類推，每一趟比較次數減少依次。
3。3 實現程式碼
javapackage com。ceshi；
import java。util。Arrays；
public class maopao {
public static void main（String［］ args） {
int［］ arr = { 1， 3， 4， 2， 6， 7， 8， 0， 5 }；
int i = 0；
int tmp = 0；
long startTime = System。nanoTime（）； // 獲取開始時間
for （i = 0； i < arr。length - 1； i++） {
// 確定排序趟數
int j = 0；
for （j = 0； j < arr。length - 1 - i； j++） {
// 確定比較次數
if （arr［j］ > arr［j + 1］） {
// 交換
tmp = arr［j］；
arr［j］ = arr［j + 1］；
arr［j + 1］ = tmp；
}
}
}
long endTime = System。nanoTime（）； // 獲取結束時間
System。out。println（“排序結果：” + Arrays。toString（arr））；
System。out。println（“程式執行時間： ” + （endTime - startTime） + “ns”）；
}
}
執行結果：
4。1 原理
每次排序都是尋找最小的一個。
1。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2。再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。
3。重複第二步，直到所有元素均排序完畢。
package com。ceshi；
public class xuanzepaixu {
public static void selectionSort（int［］ arr） {
for （int i = 0； i < arr。length - 1； i++） {
int index = i；
for （int j = i + 1； j < arr。length； j++） {
if （arr［j］ < arr［index］） {
index = j；// searching for lowest index
}
}
int smallerNumber = arr［index］；
arr［index］ = arr［i］；
arr［i］ = smallerNumber；
}
}
public static void main（String a［］） {
int［］ arr1 = { 9， 14， 3， 2， 43， 11， 58， 22 }；
System。out。println（“Before Selection Sort”）；
for （int i ： arr1） {
System。out。print（i + “ ”）；
}
System。out。println（）；
selectionSort（arr1）；// sorting array using selection sort
System。out。println（“After Selection Sort”）；
for （int i ： arr1） {
System。out。print（i + “ ”）；
}
}
}
執行結果：
5。插入排序
5。1 主要思想
插入排序演算法是所有排序方法中最簡單的一種演算法，其主要的實現思想是將資料按照一定的順序一個一個的插入到有序的表中，最終得到的序列就是已經排序好的資料。
5。2 方法
直接插入排序是插入排序演算法中的一種，採用的方法是：在新增新的記錄時，使用順序查詢的方式找到其要插入的位置，然後將新記錄插入。很多初學者所說的插入排序，實際上指的就是直接插入排序演算法，插入排序演算法還包括折半插入排序、2-路插入排序，表插入排序和希爾排序等。
package com。ceshi；
public class zhijiecharu {
public static void main（String［］ args） {
int［］ values = { 5， 2， 4， 1， 3 }；
sort（values）；
for （int i = 0； i < values。length； ++i） {
System。out。println（values［i］）；
}
}
public static void sort（int［］ values） {
int temp；
int j = 0；
for （int i = 1； i < values。length； i++） {
if（values［i］ { temp = values［i］； //資料往後移動 for （j=i-1； j>=0 && temp { values［j+1］ =values［j］； } //將資料插入到j+1位置 values［j+1］ =temp； System。out。print（“第” + （i + 1） + “次：”）； for （int k = 0； k < values。length； k++） { System。out。print（values［k］+“，”）； } System。out。println（“”）； } } } } 執行結果： 6。歸併排序 6。1 主要思想 歸併排序的主要思想是分治法。主要過程是： 1。將n個元素從中間切開，分成兩部分。（左邊可能比右邊多1個數）。 2。將步驟1分成的兩部分，再分別進行遞迴分解。直到所有部分的元素個數都為1。 3。從最底層開始逐步合併兩個排好序的數列。 package com。ceshi； public class guibing { public static void main（String［］ args） { //需要進行排序的陣列 int［］ array=new int［］{8，3，2，1，7，4，6，5}； //輸出原陣列的內容 printResult（array）； //歸併排序操作 sort（array，0，array。length-1）； //輸出排序後的相關結果 printResult（array）； } /** * 歸併排序 * @param array */ private static void sort（int［］ array，int i，int j） { if（i { int middle=（i+j）/2； //遞迴處理相關的合併事項 sort（array，i，middle）； sort（array，middle+1，j）； merge（array，i，middle，j）； } } /** * 合併相關的陣列內容 * 同時使合併後的陣列仍然有序 * @param array * @param i * @param middle * @param j * 4 5 6 9 10 11 * */ private static void merge（int［］ array， int i， int middle， int j） { //建立一個臨時陣列用來儲存合併後的資料 int［］ temp=new int［array。length］； int m=i； int n=middle+1； int k=i； while（m<=middle&&n<=j） { if（array［m］ temp［k++］=array［m++］； else temp［k++］=array［n++］； } //處理剩餘未合併的部分 while（m<=middle） { temp［k++］=array［m++］； } while（n<=j） { temp［k++］=array［n++］； } //將臨時陣列中的內容儲存到原陣列中 while（i<=j） { array［i］=temp［i++］； } } /** * * 輸出相應陣列的結果 * @param array */ private static void printResult（int［］ array） { for（int value：array） System。out。print（“ ”+value+“ ”）； System。out。println（）； } /** * 交換陣列中兩個變數的值 * @param array * @param i * @param j */ private static void swap（int［］ array，int i，int j）{ int temp=array［i］； array［i］=array［j］； array［j］=temp； } } 執行結果： 7。小和問題 7。1 什麼是小和 在一個數組中，每一個元素左邊比當前元素值小的元素值累加起來，叫做這個陣列的小和。 7。2 解決思路 1。將當前序列分為兩個子序列，分別求其小和。 2。對a劃分得到的兩個子序列進行merge操作，得到合併過程產生的小和，再加上a得到的兩個子序列的小和之和。 3。遞迴地執行1和2。 package com。ceshi； public class xiaohe { public static int smallsum（int［］ arr） { if （arr==null || arr。length<2） { return 0； } return mergeSort（arr，0，arr。length-1）； } public static int mergeSort（int［］ arr， int l， int r） { if （l == r） { return 0； } // int mid = l + （（r-l） >> 1）； //防止溢位 int mid = （l+r）/2； return mergeSort（arr， l， mid） + mergeSort（arr， mid+1， r） + merge（arr，l，mid，r）； } public static int merge（int［］ arr， int l， int mid， int r） { int res = 0； int［］ help = new int［r - l + 1］； //help的長度不是一個大的N 而是每次分治 的長度 int i=0； int p1 = l； int p2 = mid+1； while（p1 <= mid && p2 <= r） { res += arr［p1］ < arr［p2］ ？ （r-p2+1）*arr［p1］ ： 0 ； //核心 help［i++］ = arr［p1］ < arr［p2］ ？ arr［p1++］ ： arr［p2++］ ； } while（p1<=mid） { help［i++］ = arr［p1++］； } while （p2<=r） { help［i++］ = arr［p2++］； } //複製到 arr陣列 for （int j = 0； j < help。length； j++） { arr［l+j］ = help［j］； //這裡寫錯了 掉了 l } return res； } //對數器 生成隨機長度 隨機值的陣列 public static int［］ generateRamdomArray（int maxSize， int maxValue） { int［］ array = new int［（int） （（maxSize+1）* Math。random（））］； for （int i = 0； i < array。length； i++） { array［i］ = （int） （（maxValue+1）* Math。random（）） - （int） （（maxValue+1）* Math。random（））； } return array； } //一個複雜度高但是正確的方法 for 測試另一種方法 public static int comparator（int［］ arr） { int res = 0； if （arr == null || arr。length < 2 ） { return 0； } for （int i = 1； i < arr。length； i++） { for （int j = 0； j < i； j++） { res += （arr［j］ < arr［i］ ？ arr［j］ ： 0 ）； } } System。out。println（“res：”+res）； return res； } //判斷兩個陣列是否相等 public static boolean isEqual（int［］ arr1， int［］ arr2） { if （（arr1 == null && arr2 ！= null） || （arr1 ！= null && arr2 == null）） { return false； } if （arr1 == null && arr2 == null） { return true； } if （arr1。length ！= arr2。length） { return false； } for （int i = 0； i < arr2。length； i++） { if （arr1［i］！=arr2［i］） { return false； } } return true； } //複製陣列 public static int［］ copyArrar（int［］ arr） { if （arr == null） { return null； } int［］ res = new int［arr。length］； for （int i = 0； i < arr。length； i++） { res［i］ = arr［i］； } return res； } public static void printArray（int［］ arr） { if （arr == null） { return； } for （int i = 0； i < arr。length； i++） { System。out。print（arr［i］ + “ ”）； } System。out。println（）； } public static void main（String［］ args） { int testTime = 5000； int maxSize = 10； int maxValue = 50； boolean flag = true； int［］ arr1 = generateRamdomArray（maxSize， maxValue）； int［］ arr2 = copyArrar（arr1）； printArray（arr1）； printArray（arr2）； for （int i = 0； i < testTime； i++） { if （smallsum（arr1）！= comparator（arr2）） { flag = false； printArray（arr1）； printArray（arr2）； break； } } System。out。println（flag ？ “Nice！” ： “Fucking fucked！”）； } } 執行結果：
