十大排序算法詳解
點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號(hào)”
優(yōu)質(zhì)文章，第一時(shí)間送達(dá)
作者 | MPolaris
來(lái)源 | urlify.cn/nI3MRn
76套java從入門到精通實(shí)戰(zhàn)課程分享
1. 十大排序算法
其中 冒泡，選擇，歸并，快速，希爾，堆排序?qū)儆?/span>比較排序
穩(wěn)定性理解
如果相等的兩個(gè)元素，在排序前后的相對(duì)位置保持不變，那么這是穩(wěn)定的排序算法。
排序前：5，1，3(a)，4，7，3(b)
穩(wěn)定的排序：1，3(a)，3(b)，4，5，7
不穩(wěn)定的排序：1，3(b)，3(a)，4，5，7
原地算法（In-place Algorithm）理解
定義：不依賴額外的資源或依賴少數(shù)的額外資源（空間復(fù)雜度較低），僅依靠輸出覆蓋輸入（例如直接對(duì)輸入的數(shù)組進(jìn)行操作）
2. 工具類
用于提供測(cè)試數(shù)據(jù)與測(cè)試代碼正確性
2.1 斷言工具類
public class Asserts {
public static void test(boolean value) {
try {
if (!value) throw new Exception("測(cè)試未通過(guò)");
} catch (Exception e) {
e.printStackTrace();
}
}
}2.2 Integers工具類
public class Integers {
/** 生成隨機(jī)數(shù) */
public static Integer[] random(int count, int min, int max) {
if (count <= 0 || min > max) return null;
Integer[] array = new Integer[count];
int delta = max - min + 1;
for (int i = 0; i < count; i++) {
array[i] = min + (int)(Math.random() * delta);
}
return array;
}
/** 合并兩個(gè)數(shù)組 */
public static Integer[] combine(Integer[] array1, Integer[] array2) {
if (array1 == null || array2 == null) return null;
Integer[] array = new Integer[array1.length + array2.length];
for (int i = 0; i < array1.length; i++) {
array[i] = array1[i];
}
for (int i = 0; i < array2.length; i++) {
array[i + array1.length] = array2[i];
}
return array;
}
public static Integer[] same(int count, int unsameCount) {
if (count <= 0 || unsameCount > count) return null;
Integer[] array = new Integer[count];
for (int i = 0; i < unsameCount; i++) {
array[i] = unsameCount - i;
}
for (int i = unsameCount; i < count; i++) {
array[i] = unsameCount + 1;
}
return array;
}
/**
* 生成頭部和尾部是升序的數(shù)組
* disorderCount：希望多少個(gè)數(shù)據(jù)是無(wú)序的
*/
public static Integer[] headTailAscOrder(int min, int max, int disorderCount) {
Integer[] array = ascOrder(min, max);
if (disorderCount > array.length) return array;
int begin = (array.length - disorderCount) >> 1;
reverse(array, begin, begin + disorderCount);
return array;
}
/**
* 生成中間是升序的數(shù)組
* disorderCount：希望多少個(gè)數(shù)據(jù)是無(wú)序的
*/
public static Integer[] centerAscOrder(int min, int max, int disorderCount) {
Integer[] array = ascOrder(min, max);
if (disorderCount > array.length) return array;
int left = disorderCount >> 1;
reverse(array, 0, left);
int right = disorderCount - left;
reverse(array, array.length - right, array.length);
return array;
}
/**
* 生成頭部是升序的數(shù)組
* disorderCount：希望多少個(gè)數(shù)據(jù)是無(wú)序的
*/
public static Integer[] headAscOrder(int min, int max, int disorderCount) {
Integer[] array = ascOrder(min, max);
if (disorderCount > array.length) return array;
reverse(array, array.length - disorderCount, array.length);
return array;
}
/**
* 生成尾部是升序的數(shù)組
* disorderCount：希望多少個(gè)數(shù)據(jù)是無(wú)序的
*/
public static Integer[] tailAscOrder(int min, int max, int disorderCount) {
Integer[] array = ascOrder(min, max);
if (disorderCount > array.length) return array;
reverse(array, 0, disorderCount);
return array;
}
/** 升序生成數(shù)組 */
public static Integer[] ascOrder(int min, int max) {
if (min > max) return null;
Integer[] array = new Integer[max - min + 1];
for (int i = 0; i < array.length; i++) {
array[i] = min++;
}
return array;
}
/** 降序生成數(shù)組 */
public static Integer[] descOrder(int min, int max) {
if (min > max) return null;
Integer[] array = new Integer[max - min + 1];
for (int i = 0; i < array.length; i++) {
array[i] = max--;
}
return array;
}
/** 反轉(zhuǎn)數(shù)組 */
private static void reverse(Integer[] array, int begin, int end) {
int count = (end - begin) >> 1;
int sum = begin + end - 1;
for (int i = begin; i < begin + count; i++) {
int j = sum - i;
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
/** 復(fù)制數(shù)組 */
public static Integer[] copy(Integer[] array) {
return Arrays.copyOf(array, array.length);
}
/** 判斷數(shù)組是否升序 */
public static boolean isAscOrder(Integer[] array) {
if (array == null || array.length == 0) return false;
for (int i = 1; i < array.length; i++) {
if (array[i - 1] > array[i]) return false;
}
return true;
}
/** 打印數(shù)組 */
public static void println(Integer[] array) {
if (array == null) return;
StringBuilder string = new StringBuilder();
for (int i = 0; i < array.length; i++) {
if (i != 0) string.append("_");
string.append(array[i]);
}
System.out.println(string);
}
}2.3 時(shí)間測(cè)試工具類
public class Times {
private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");
public interface Task {
void execute();
}
public static void test(String title, Task task) {
if (task == null) return;
title = (title == null) ? "" : ("【" + title + "】");
System.out.println(title);
System.out.println("開(kāi)始：" + fmt.format(new Date()));
long begin = System.currentTimeMillis();
task.execute();
long end = System.currentTimeMillis();
System.out.println("結(jié)束：" + fmt.format(new Date()));
double delta = (end - begin) / 1000.0;
System.out.println("耗時(shí)：" + delta + "秒");
System.out.println("-------------------------------------");
}
}2.4 Sort抽象父類
public abstract class Sort<T extends Comparable<T>> implements Comparable<Sort<T>> {
/** 目標(biāo)數(shù)組 */
protected T[] array;
/** 比較次數(shù) */
private int cmpCount;
/** 交換次數(shù) */
private int swapCount;
/** 執(zhí)行時(shí)間 */
private long time;
/** 小數(shù)格式化 */
private DecimalFormat fmt = new DecimalFormat("#.00");
/** 預(yù)處理 */
public void sort(T[] array) {
if (array == null || array.length < 2) return;
this.array = array;
long begin = System.currentTimeMillis();
sort();
time = System.currentTimeMillis() - begin;
}
/** 目標(biāo)方法 */
protected abstract void sort();
/**
* 比較數(shù)組下標(biāo)對(duì)應(yīng)的值
*
* 返回值等于0，代表 array[index1] == array[index2]
* 返回值小于0，代表 array[index1] < array[index2]
* 返回值大于0，代表 array[index1] > array[index2]
*/
protected int cmp(int index1, int index2) {
cmpCount++;
return array[index1].compareTo(array[index2]);
}
/** 比較值 */
protected int cmp(T value1, T value2) {
cmpCount++;
return value1.compareTo(value2);
}
/** 交換值 */
protected void swap(int index1, int index2) {
swapCount++;
T tmp = array[index1];
array[index1] = array[index2];
array[index2] = tmp;
}
/** 穩(wěn)定性測(cè)試 */
@SuppressWarnings("unchecked")
private boolean isStable() {
Student[] students = new Sort.Student[20];
for (int i = 0; i < students.length; i++) {
//（0，10） （10，10） （20，10） （30，10）
students[i] = new Student(i * 10, 10);
}
sort((T[]) students);//只會(huì)對(duì)年齡進(jìn)行排序
for (int i = 1; i < students.length; i++) {
int score = students[i].score;
int prevScore = students[i - 1].score;
if (score != prevScore + 10) return false;
}
return true;
}
private static class Student implements Comparable<Student>{
Integer score;
Integer age;
public Student(Integer score, Integer age) {
this.score = score;
this.age = age;
}
@Override
public int compareTo(Student o) {
return age - o.age;
}
}
/** 排序方式 */
@Override
public int compareTo(Sort o) {
int result = (int)(time - o.time);
if(result != 0) return result;
result = cmpCount - o.cmpCount;
if(result != 0) return result;
return swapCount - o.swapCount;
}
@Override
public String toString() {
return "【" + getClass().getSimpleName() + "】\n"
+ "交換次數(shù) ==> " + numberString(swapCount) + "\n"
+ "比較次數(shù) ==> " + numberString(cmpCount) + "\n"
+ "執(zhí)行時(shí)間 ==> " + time * 0.001 + "s" + "\n"
+ "穩(wěn)定性 ==> " + isStable() + "\n"
+ "=================================";
}
/** 數(shù)字格式化 */
private String numberString(int number) {
if (number < 10000) return "" + number;
if (number < 100000000) {
return fmt.format(number / 10000.0) + "萬(wàn)";
}
return fmt.format(number / 100000000.0) + "億";
}
}
3. 冒泡排序（Bubble Sort）
3.1 執(zhí)行流程
從頭開(kāi)始比較每一對(duì)相鄰元素，如果第一個(gè)比第二個(gè)大就交換它們的位置。執(zhí)行完一輪后最末尾哪個(gè)元素就是最大的元素
忽略第一步找到的最大元素，重復(fù)執(zhí)行第一步，直到全部元素有序
3.2 基本實(shí)現(xiàn)
public void sort() {
for (int eIndex = array.length - 1; eIndex > 0; eIndex--) {
for (int i = 1; i <= eIndex; i++) {
if (cmp(i, i - 1) < 0) {
swap(i, i - 1);
}
}
}
}3.4 優(yōu)化一
優(yōu)化方案：如果序列已經(jīng)完全有序，可以提前終止冒泡排序
缺點(diǎn)：只有當(dāng)完全有序時(shí)才會(huì)提前終止冒泡排序，概率很低
public void sort() {
for (int eIndex = array.length - 1; eIndex > 0; eIndex--) {
boolean sorted = true;
for (int i = 1; i <= eIndex; i++) {
if (cmp(i,i - 1) < 0) {
swap(i, i - 1);
sorted = false;
}
}
if (sorted) break;
}
}3.5 優(yōu)化二
優(yōu)化方案：如果序列尾部已經(jīng)局部有序，可以記錄最后一次交換的位置，減少比較次數(shù)
public class BubbleSort<T extends Comparable<T>> extends Sort<T> {
/**
* 優(yōu)化方式二：如果序列尾部已經(jīng)局部有序，可以記錄最后依次交換的位置，減少比較次數(shù)
* 為什么這里sortedIndex為1（只要保證 eIndex-- > 0 即可）？
* => 如果sortedIndex為eIndex，當(dāng)數(shù)組第一次就完全有序時(shí)，就退回到最初的版本了
* => 如果sortedIndex為1，當(dāng)數(shù)組第一次就完全有序時(shí)，一輪掃描就結(jié)束了！
*
*/
@Override
public void sort() {
for (int eIndex = array.length - 1; eIndex > 0; eIndex--) {
int sortedIndex = 1; //記錄最后一次交換的下標(biāo)位置
for (int i = 1; i <= eIndex; i++) {
if (cmp(i, i - 1) < 0) {
swap(i, i - 1);
sortedIndex = i;
}
}
eIndex = sortedIndex;
}
}
}
3.6 算法優(yōu)劣
最壞，平均時(shí)間復(fù)雜度：O(n^2），最好時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)
屬于穩(wěn)定排序
注意：稍有不慎，穩(wěn)定的排序算法也能被寫(xiě)成不穩(wěn)定的排序算法，如下冒泡排序是不穩(wěn)定的
public void sort() {
for (int eIndex = array.length - 1; eIndex > 0; eIndex--) {
for (int i = 1; i <= eIndex; i++) {
if (cmp(i, i - 1) <= 0) {
swap(i, i - 1);
}
}
}
}屬于原地算法
4. 選擇排序（Selection Sort）
4.1 執(zhí)行流程
從序列中找出最大的哪個(gè)元素，然后與最末尾的元素交換位置。執(zhí)行完一輪后最末尾那個(gè)元素就是最大的元素
忽略第一步找到的最大元素，重復(fù)執(zhí)行第一步
這里以選最小元素為例
4.2 基本實(shí)現(xiàn)
public class SelectionSort<T extends Comparable<T>> extends Sort<T> {
@Override
public void sort() {
for (int eIndex = array.length - 1; eIndex > 0; eIndex--) {
int maxIndex = 0;
for (int i = 1; i <= eIndex; i++) {
//注意：為了穩(wěn)定性，這里要寫(xiě) <=
if (cmp(maxIndex, i) <= 0) {
maxIndex = i;
}
}
if(maxIndex != eIndex) swap(maxIndex, eIndex);
}
}
}4.3 算法優(yōu)劣
選擇排序的交換次數(shù)要遠(yuǎn)少于冒泡排序，平均性能優(yōu)于冒泡排序
最好，最壞，平均時(shí)間復(fù)雜度均為O(n^2)，空間復(fù)雜度為O(1)，屬于不穩(wěn)定排序
選擇排序是否還有優(yōu)化的空間？=> 使用堆來(lái)選擇最大值
5. 堆排序（Heap Sort）
堆排序可以認(rèn)為是對(duì)選擇排序的一種優(yōu)化
5.1 執(zhí)行流程
對(duì)序列進(jìn)行原地建堆（heapify）
重復(fù)執(zhí)行以下操作，直到堆的元素?cái)?shù)量為1
交換堆頂元素與尾元素
堆的元素?cái)?shù)量減1
對(duì)0位置進(jìn)行一次siftDown操作
5.2 基本實(shí)現(xiàn)
public class HeapSort<T extends Comparable<T>> extends Sort<T> {
/** 記錄堆數(shù)據(jù) */
private int heapSize;
@Override
protected void sort() {
// 原地建堆（直接使用數(shù)組建堆）
heapSize = array.length;
for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
while (heapSize > 1) {
// 交換堆頂元素和尾部元素
swap(0, --heapSize);
// 對(duì)0位置進(jìn)行siftDown（恢復(fù)堆的性質(zhì)）
siftDown(0);
}
}
/** 堆化 */
private void siftDown(int index) {
T element = array[index];
int half = heapSize >> 1;
while (index < half) { // index必須是非葉子節(jié)點(diǎn)
// 默認(rèn)是左邊跟父節(jié)點(diǎn)比
int childIndex = (index << 1) + 1;
T child = array[childIndex];
int rightIndex = childIndex + 1;
// 右子節(jié)點(diǎn)比左子節(jié)點(diǎn)大
if (rightIndex < heapSize &&
cmp(array[rightIndex], child) > 0) {
child = array[childIndex = rightIndex];
}
// 大于等于子節(jié)點(diǎn)
if (cmp(element, child) >= 0) break;
array[index] = child;
index = childIndex;
}
array[index] = element;
}
}5.2 算法優(yōu)劣
最好，最壞，平均時(shí)間復(fù)雜度：O(nlog^n)
空間復(fù)雜度：O(1)
屬于不穩(wěn)定排序
5.3. 冒泡，選擇，堆排序比較
@SuppressWarnings({"rawtypes","unchecked"})
public class SortTest {
public static void main(String[] args) {
Integer[] arr1 = Integers.random(10000, 1, 20000);
testSort(arr1,
new SelectionSort(),
new HeapSort(),
new BubbleSort());
}
static void testSort(Integer[] arr,Sort... sorts) {
for (Sort sort: sorts) {
Integer[] newArr = Integers.copy(arr);
sort.sort(newArr);
//檢查排序正確性
Asserts.test(Integers.isAscOrder(newArr));
}
Arrays.sort(sorts);
for (Sort sort: sorts) {
System.out.println(sort);
}
}
}
6. 插入排序（Insertion Sort）
6.1 執(zhí)行流程
在執(zhí)行過(guò)程中，插入排序會(huì)將序列分為兩部分（頭部是已經(jīng)排好序的，尾部是待排序的）
從頭開(kāi)始掃描每一個(gè)元素，每當(dāng)掃描到一個(gè)元素，就將它插入到頭部適合的位置，使得頭部數(shù)據(jù)依然保持有序
6.2 基本實(shí)現(xiàn)
public class InsertionSort<T extends Comparable<T>> extends Sort<T> {
@Override
protected void sort() {
for (int i = 1; i < array.length; i++) {
int cur = i;
while(cur > 0 && cmp(cur,cur - 1) < 0) {
swap(cur,cur - 1);
cur--;
}
}
}
}6.3 逆序?qū)Γ↖nversion）
什么是逆序?qū)Γ?/strong> => 數(shù)組 [2,3,8,6,1] 的逆序?qū)椋?lt;2,1> < 3,1> <8,1> <8,6> <6,1>
插入排序的時(shí)間復(fù)雜度與逆序?qū)Φ臄?shù)量成正比關(guān)系
時(shí)間復(fù)雜度最高如下：O(n^2)
6.4 優(yōu)化一
優(yōu)化思路 => 將交換改為挪動(dòng)
先將待插入元素備份
頭部有序數(shù)據(jù)中比待插入元素大的，都朝尾部方向挪動(dòng)1個(gè)位置
將待插入元素放到最終合適位置
注意：逆序?qū)υ蕉啵搩?yōu)化越明顯
public class InsertionSort<T extends Comparable<T>> extends Sort<T> {
@Override
protected void sort() {
for (int i = 1; i < array.length; i++) {
int cur = i;
T val = array[cur];
while(cur > 0 && cmp(val,array[cur - 1]) < 0) {
array[cur] = array[cur - 1];//優(yōu)化重點(diǎn)在這里
cur--;
}
array[cur] = val;
}
}
}
6.5 優(yōu)化二
優(yōu)化思路 => 將交換改為二分搜索（較少比較次數(shù)）
二分搜索理解
如何確定一個(gè)元素在數(shù)組中的位置？（假設(shè)數(shù)組里全是整數(shù)）
如果是無(wú)序數(shù)組，從第 0 個(gè)位置開(kāi)始遍歷搜索，平均時(shí)間復(fù)雜度：O(n)
如果是有序數(shù)組，可以使用二分搜索，最壞時(shí)間復(fù)雜度：O(log^n)
思路
如下，假設(shè)在 [begin, end) 范圍內(nèi)搜索某個(gè)元素 v，mid == (begin + end) / 2
如果 v < mid，去 [begin,mid) 范圍內(nèi)二分搜索
如果 v > mid，去 [mid + 1,end) 范圍內(nèi)二分搜索
如果 v == mid，直接返回 mid
實(shí)例
/** 二分搜索-基本實(shí)現(xiàn)
* 查找val在有序數(shù)組arr中的位置，找不到就返回-1
*/
private static int indexOf(Integer[] arr,int val) {
if(arr == null || arr.length == 0) return -1;
int begin = 0;
//注意這里end設(shè)計(jì)為arr.length便于求數(shù)量（end - begin）
int end = arr.length;
while (begin < end) {
int mid = (begin + end) >> 1;
if(val < arr[mid]) {
end = mid;
} else if(val > arr[mid]) {
begin = mid + 1;
} else {
return mid;
}
}
return -1;
}
二分搜索(Binary Search)優(yōu)化實(shí)現(xiàn)
之前的插入排序代碼，在元素 val 的插入過(guò)程中，可以先二分搜索出合適的插入位置，然后將元素 val 插入
適合于插入排序的二分搜索必須滿足：要求二分搜索返回的插入位置是第1個(gè)大于 val 的元素位置
如果 val 是 5 ，返回 2
如果 val 是 1，返回 0
如果 val 是15，返回 7
如果 val 是 8，返回 5
實(shí)現(xiàn)思路
假設(shè)在 [begin,end) 范圍內(nèi)搜索某個(gè)元素 val，mid == (begin + end) / 2
如果val < mid，去 [begin,mid) 范圍內(nèi)二分搜索
如果val >= mid，去 [mid + 1,end) 范圍內(nèi)二分搜索
當(dāng) begin == end == x，x 就是待插入位置
實(shí)例
/**
* 二分搜索-適用于插入排序
* 查找val在有序數(shù)組arr中可以插入的位置
* 規(guī)定：要求二分搜索返回的插入位置是第1個(gè)大于 val 的元素位置
*/
private static int search(Integer[] arr,int val) {
if(arr == null || arr.length == 0) return -1;
int begin = 0;
int end = arr.length;
while (begin < end) {
int mid = (begin + end) >> 1;
if(val < arr[mid]) {
end = mid;
} else {
begin = mid + 1;
}
}
return begin;
}
插入排序最終實(shí)現(xiàn)
注意：使用了二分搜索后，只是減少了比較次數(shù)，但插入排序的平均時(shí)間復(fù)雜度依然是O(n^2)
public class InsertionSort<T extends Comparable<T>> extends Sort<T> {
/** 優(yōu)化 => 二分搜索 */
@Override
protected void sort() {
for (int begin = 1; begin < array.length; begin++) {
//這里為什么傳索引而不是傳值？
// => 傳索引還可以知道前面已經(jīng)排好序的數(shù)組區(qū)間：[0,i)
insert(begin,search(begin));
}
}
/** 將source位置的元素插入到dest位置 */
private void insert(int source,int dest) {
//將[dest,source)范圍內(nèi)的元素往右邊挪動(dòng)一位
T val = array[source];
for (int i = source; i > dest; i--) {
array[i] = array[i - 1];
}
//插入
array[dest] = val;
}
private int search(int index) {
T val = array[index];
int begin = 0;
int end = index;
while (begin < end) {
int mid = (begin + end) >> 1;
if(cmp(val,array[mid]) < 0) {
end = mid;
} else {
begin = mid + 1;
}
}
return begin;
}
}
6.6 算法優(yōu)劣
最壞，平均時(shí)間復(fù)雜度為 O(n^2)，最好時(shí)間復(fù)雜度為 O(n)
空間復(fù)雜度為 O(1)
屬于穩(wěn)定排序
7. 歸并排序（Merge Sort）
7.1 執(zhí)行流程
不斷的將當(dāng)前序列平均分割成 2 個(gè)子序列，直到不能再分割（序列中只剩一個(gè)元素）
不斷的將 2 個(gè)子序列合并成一個(gè)有序序列，直到最終只剩下 1 個(gè)有序序列
7.2 思路
merge
大致想法
細(xì)節(jié)
需要 merge 的 2 組序列存在于同一個(gè)數(shù)組中，并且是挨在一起的
為了更好的完成 merge 操作，最好將其中 1 組序列備份出來(lái)，比如 [begin,mid)
基本實(shí)現(xiàn)
情況一：左邊先結(jié)束 => 左邊一結(jié)束整個(gè)歸并就結(jié)束
情況二：右邊先結(jié)束 => 右邊一結(jié)束就直接將左邊按順序挪到右邊去
7.3 基本實(shí)現(xiàn)
@SuppressWarnings("unchecked")
public class MergeSort<T extends Comparable<T>> extends Sort<T> {
private T[] leftArr;
@Override
protected void sort() {
leftArr = (T[]) new Comparable[array.length >> 1];
sort(0, array.length);
}
/** 對(duì) [begin,end) 位置的元素進(jìn)行歸并排序 */
private void sort(int begin, int end) {
if (end - begin < 2) return;
int mid = (begin + end) >> 1;
sort(begin, mid);
sort(mid, end);
merge(begin, mid, end);
}
/** 將 [begin,mid) 和 [mid,end) 范圍的序列合并成一個(gè)有序序列 */
private void merge(int begin, int mid, int end) {
int li = 0, le = mid - begin;
int ri = mid, re = end;
int ai = begin;
//備份左邊數(shù)組
for (int i = 0; i < le; i++) {
leftArr[i] = array[begin + i];
}
//如果左邊還沒(méi)有結(jié)束（情況一）
while (li < le) {
//當(dāng) ri < re 不成立，就會(huì)一直leftArr挪動(dòng)（情況二）
if (ri < re && cmp(array[ri],leftArr[li]) < 0) {
array[ai++] = array[ri++];
} else { //注意穩(wěn)定性
array[ai++] = leftArr[li++];
}
}
}
}7.4 算法優(yōu)劣
復(fù)雜度分析
T(n) = sort() + sort() + merge()
=> T(n) = T(n/2) + T(n/2) + O(n)
=> T(n) = 2T(n/2) + O(n)
//由于sort()是遞歸調(diào)用，用T表示，由于T(n/2)不好估算，現(xiàn)在要理清T(n)與O(n)之間的關(guān)系
T(1) = O(1)
T(n)/n = T(n/2) / (n/2) + O(1)
//令S(n) = T(n)/n
S(1) = O(1)
S(n) = S(n/2) + O(1)
= S(n/4) + O(2)
= S(n/8) + O(3)
= S( n/(2^k) ) + O(k)
= S(1) + O(log^n)
= O(lon^n)
T(n) = n*S(n) = O(nlog^n)
=> 歸并排序時(shí)間復(fù)雜度：O(nlog^n)
常見(jiàn)遞推式
總結(jié)
由于歸并排序總是平均分割子序列，所以最好，最壞，平均時(shí)間復(fù)雜度都是：O(nlog^n)
空間復(fù)雜度：O(n/2 + log^n) = O(n)，n/2用于臨時(shí)存放左側(cè)數(shù)組，log^n用于遞歸調(diào)用
屬于穩(wěn)定排序
鋒哥最新SpringCloud分布式電商秒殺課程發(fā)布
??????
??長(zhǎng)按上方微信二維碼 2 秒
感謝點(diǎn)贊支持下哈 
評(píng)論
圖片
表情