目錄
- 一、背景
- 二、概念
- 2.1、時間復雜度的定義
- 2.2、時間復雜度的比較
- 三、測驗類
- 3.1、程式結構
- 3.2、測驗工具類
- 3.3、 排序演算法介面定義
- 3.4、 各種排序演算法的實作
- 3.5、 測驗主程式
- 3.6、 測驗分析
- 四、寫在最后
一、背景
在學習演算法的程序中，除了熟練掌握各種演算法的程式邏輯外，還經常需要用到一些測驗案例對演算法的時間復雜度做具體的測驗，本文將通過打造一個測驗類工具包，讓我們可以更簡便地研究排序演算法的時間復雜度，
二、概念
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、 測驗分析
- 通過以上測驗主程式及測驗工具包的運行，我們清晰地看到了以下結論：
-- 在對數量較大且亂序的陣列進行排序時，快速排序的性能明顯要好于插入排序，
-- 但即使數量較大，如果陣列相對有序時，插入排序的性能不比快速排序差，
-- 我們還發現排序數量相同的情況下，陣列越亂序，快速排序性能越好，
四、寫在最后
在日常學習上，邏輯思維非常重要，特別是在資料結構和演算法的學習程序中，建立邏輯+套路的結構思維化，具備結構化思維，才能將問題分析地更全面、更深刻，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/170784.html
標籤：Java