用一個測試類簡化排序算法時間複雜度的研究
目錄
一、背景
在學習算法的過程中，除了熟練掌握各種算法的程序邏輯外，還經常需要用到一些測試案例對算法的時間複雜度做具體的測試。本文將通過打造一個測試類工具包，讓我們可以更簡便地研究排序算法的時間複雜度。
二、概念
2.1、時間複雜度的定義
即從序列的初始狀態到經過排序算法後形成的最終排序狀態這個過程所花費的時間度量
2.2、時間複雜度的比較
| 排序算法 | 時間複雜度（平均） | 時間複雜度（最好） | 時間複雜度（最壞） |
|---|---|---|---|
| 冒泡排序 | O（n2） | O（n） | O（n2） |
| 選擇排序 | O（n2） | O（n2） | O（n2） |
| 插入排序 | O（n2） | O（n） | O（n2） |
| 希爾排序 | O（n logn） | O（n log2n） | O（n log2n） |
| 歸併排序 | O（n logn） | O（n logn） | O（n logn） |
| 快速排序 | O（n logn） | O（n logn） | O（n2） |
| 堆排序 | O（n logn） | O（n logn） | O（n logn） |
- 時間複雜度曲線
三、測試類
3.1、程序結構
- 為便於文章書寫，該測試類只實現了插入排序與快速排序，讀者可根據接口定義自行加入其他排序算法。
3.2、測試工具類
- 生成一個亂序的數組
- 生成一個從0開始的近乎順序的整型數組
- 對整型數組做完全拷貝
- 判斷整型數組是否已經升序排列
- 遍歷打印數組
- 通過排序接口，調用各種排序算法進行測試
/**
* 整數排序測試工具類
*
* @author zhuhuix
* @date 2020-06-06
*/
public class SortUtils {
/**
* 生成一個亂序的數組
*
* @param count 數組的數量
* @param startRanger 數字範圍起始值
* @param endRanger 數字範圍終止值
* @return 亂序的整數數組
*/
public static int[] generateRandomArray(int count, int startRanger, int endRanger) {
if (startRanger <= endRanger) {
int[] arr = new int[count];
Random random = new Random();
for (int i = 0; i < count; i++) {
arr[i] = startRanger + random.nextInt(endRanger - startRanger );
}
return arr;
} else {
return null;
}
}
/**
* 生成一個從0開始的近乎順序的整型數組
*
* @param count 數組的數量
* @param swapCount 數字範圍起始值
* @return 近乎順序的整型數組
*/
public static int[] generateNearlyOrderedArray(int count, int swapCount) {
int[] arr = new int[count];
for (int i = 0; i < count; i++) {
arr[i] = i;
}
Random random = new Random();
for (int i = 0; i < swapCount; i++) {
int x = random.nextInt(count);
int y = random.nextInt(count);
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
return arr;
}
/**
* 對整型數組做完全拷貝
*
* @param source 源數組
* @return 數組拷貝
*/
public static int[] copyArray(int[] source) {
if (source != null) {
int dest[] = new int[source.length];
for (int i = 0; i < source.length; i++) {
dest[i] = source[i];
}
return dest;
} else {
return null;
}
}
/**
* 判斷整型數組是否已經升序排列
*
* @param arr 整型數組
* @return 已經升序排列為true否則為false
*/
public static boolean isSorted(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
return false;
}
}
return true;
}
/**
* 遍歷打印數組
* @param arr 整型數組
*/
public static void printArray(int[] arr) {
if (arr!=null) {
System.out.print("[");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i != arr.length - 1) {
System.out.print(",");
} else {
System.out.println("]");
}
}
}else{
System.out.println("數組為空!");
}
}
/**
* 通過排序接口，調用各種排序算法進行測試
* @param sortName 排序算法名稱
* @param sort 排序統一接口
* @param arr 整型數組
*/
public static void testSort(final String sortName,Sort sort,int[] arr){
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
Long start = System.currentTimeMillis();
System.out.println(sortName+"排序開始時間：" + sdf.format(start));
sort.sort(arr);
Long end = System.currentTimeMillis();
System.out.println(sortName+"排序結束時間：" + sdf.format(end));
System.out.println(sortName+"排序耗用了" + (end - start) + "毫秒");
//斷言判斷該數組是否已實現升序排序
assert(isSorted(arr));
}
}
3.3、 排序算法接口定義
- 在測試工具類SortUtils testSort方法中調用該接口定義
–public static void testSort(final String sortName,Sort sort,int[] arr)
/**
* 整型數組排序統一接口定義
*
* @author zhuhuix
* @date 2020-06-06
*/
public interface Sort {
/**
* 整型排序
* @param arr 待排序數組
*/
void sort(int[] arr);
}
3.4、 各種排序算法的實現
- 我們可以通過實現排序接口加入各種排序算法，本文章僅演示插入排序及快速排序
- 插入排序
/**
* 插入排序
*
* @author zhuhuix
* @date 2020-06-06
*/
public class InsertSort implements Sort {
@Override
public void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j;
for (j = i; j > 0 && (arr[j - 1] > temp); j--) {
arr[j] = arr[j - 1];
}
arr[j] = temp;
}
}
}
- 快速排序
/**
* 快速排序
*
* @author zhuhuix
* @date 2020-06-06
*/
public class QuickSort implements Sort {
@Override
public void sort(int[] arr) {
quick(arr, 0, arr.length - 1);
}
private void quick(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quick(arr, left, partitionIndex - 1);
quick(arr, partitionIndex + 1, right);
}
}
private int partition(int[] arr, int left, int right) {
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
private void swap(int arr[], int x, int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}
- 其他排序
public class othersSort implements Sort {
@Override
public void sort(int[] arr) {
// 自行實現其他各種排序算法
....
}
}
}
3.5、 測試主程序
- 文中僅對以上實現的兩種排序算法進行比較，讀者實現其他排序算法後可自行擴充。
/**
* 整數排序測試類
* * @author zhuhuix
* @date 2020-06-06
*/
public class SortTest {
public static void main(String[] args) {
int count=100000;
// 產生一個隨機數組
int[] arr1 = SortUtils.generateRandomArray(count, 0, count);
// 對隨機數組產生一個拷貝
int[] arr2 = SortUtils.copyArray(arr1);
// 進行插入排序
SortUtils.testSort("隨機亂序的插入排序",new InsertSort(),arr1);
// 進行快速排序
SortUtils.testSort("隨機亂序的快速排序",new QuickSort(),arr2);
// 產生一個隨機數組
int[] arr3 = SortUtils.generateNearlyOrderedArray(count, 100);
// 對隨機數組產生一個拷貝
int[] arr4 = SortUtils.copyArray(arr3);
// 進行插入排序
SortUtils.testSort("相對順序的插入排序",new InsertSort(),arr3);
// 進行快速排序
SortUtils.testSort("相對順序的快速排序",new QuickSort(),arr4);
}
}
3.6、 測試分析
- 通過以上測試主程序及測試工具包的運行，我們清晰地看到了以下結論：
— 在對數量較大且亂序的數組進行排序時，快速排序的性能明顯要好於插入排序。
— 但即使數量較大，如果數組相對有序時，插入排序的性能不比快速排序差。
— 我們還發現排序數量相同的情況下，數組越亂序，快速排序性能越好。
四、寫在最後
在日常學習上，邏輯思維非常重要，特別是在數據結構和算法的學習過程中，建立邏輯+套路的結構思維化，具備結構化思維，才能將問題分析地更全面、更深刻。
