看這篇前請(qǐng)先把我上一篇了解一下：深入理解數(shù)據(jù)結(jié)構(gòu)第一彈——二叉樹(shù)（1）——堆-CSDN博客

前言：

相信很多學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人，都會(huì)遇到一種情況，就是明明最一開(kāi)始學(xué)習(xí)就學(xué)習(xí)了時(shí)間復(fù)雜度，但是在后期自己寫(xiě)的程序或者是做到哪個(gè)需要判斷時(shí)間復(fù)雜度的題時(shí)，仍然判斷不出來(lái)時(shí)間復(fù)雜度是多少，今天，我們結(jié)合我們上期學(xué)習(xí)的堆，給大家深入剖析一下時(shí)間復(fù)雜度這個(gè)概念，同時(shí)更深入的理解堆的概念，方便我們后期應(yīng)用堆進(jìn)行排序等。

目錄

一、堆排序

1、堆排序的大體思路

2、堆排序的實(shí)例講解

二、堆排序的時(shí)間復(fù)雜度

向下排序的時(shí)間復(fù)雜度

向上排序的時(shí)間復(fù)雜度

堆排序整體的時(shí)間復(fù)雜度

總結(jié)

---

一、堆排序

1、堆排序的大體思路

在上一篇我們已經(jīng)講過(guò)了堆是什么東西，我們已經(jīng)知道堆有大堆和小堆兩種形式，堆排序的想法正是借助它的這個(gè)特點(diǎn)誕生的，例如：

數(shù)組 { 7，8 ，3 ，5 ，1 ，9 ，5 ，4}在堆中分布為：

如圖展示的是小堆，首先我們先強(qiáng)調(diào)一點(diǎn)，降序是需要小堆來(lái)解決，升序是需要大堆來(lái)解決

比如說(shuō)圖上這個(gè)數(shù)組，我們要求它的降序序列時(shí)，因?yàn)槎秧斣匾欢ㄊ嵌阎凶钚〉?#xff0c;所以我們就可以把堆頂元素與堆尾元素進(jìn)行交換，然后把堆尾元素刨除在外再進(jìn)行降序排列

2、堆排序的實(shí)例講解

堆排序與堆相比并沒(méi)有什么新東西，把我前面那章看明白，這里直接把代碼呈上

（除了test.c）其他的是直接從上一章搬過(guò)來(lái)的

Seqlist.h

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int sz;int capacity;
}HP;//初始化
void HeapInit(HP* php);
//銷(xiāo)毀
void HeapDestory(HP* php);
//插入
void HeapPush(HP* php, HPDataType x);
//刪除
void HeapPop(HP* php);
//找堆頂元素
HPDataType HeapTop(HP* php);
//判斷是否為空
bool HeapEmpty(HP* php);
//算個(gè)數(shù)
int HeapSize(HP* php);

test.c

//堆排序
void HeapSort(int* a, int n)
{//建堆——向下調(diào)整建堆O(N-log(n))for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);//再調(diào)整，選出次小數(shù)AdjustDown(a, end, 0);end--;}
}
int main()
{int a[] = { 7,8,3,5,1,9,5,4 };HeapSort(a, sizeof(a) / sizeof(int));return 0;
}

Seqlist.c

//堆
//初始化
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->capacity = 0;php->sz = 0;
}
//銷(xiāo)毀
void HeapDestory(HP* php)
{free(php->a);free(php);
}
//交換
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//刪除//向上調(diào)整(小堆)
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
//向下調(diào)整
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child<n){if (child+1<n&&a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//插入
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->sz == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);php->a = tmp;php->capacity = newcapacity;}php->a[php->sz] = x;php->sz++;//向上調(diào)整AdjustUp(php->a, php->sz - 1);
}
//刪除
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->sz - 1]);php->sz--;//向下調(diào)整AdjustDown(php->a, php->sz,0);
}
//判斷是否為空
bool HeapEmpty(HP* php)
{assert(php);return php->sz == 0;
}
//找堆頂元素
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php->a[0];
}
//算個(gè)數(shù)
int HeapSize(HP* php)
{assert(php);return php->sz;
}

實(shí)現(xiàn)上述代碼，我們就可以實(shí)現(xiàn)堆排序了

二、堆排序的時(shí)間復(fù)雜度

我們都知道在實(shí)現(xiàn)堆時(shí)有向上排序和向下排序兩種，細(xì)心的人可能已經(jīng)注意到，我在實(shí)現(xiàn)上面那個(gè)堆排序用例時(shí)，用的是向下排序，原因就是向下排序的時(shí)間復(fù)雜度更低，接下來(lái)，我們就來(lái)分析一下這兩種排序各自的時(shí)間復(fù)雜度

向下排序的時(shí)間復(fù)雜度

向上排序的時(shí)間復(fù)雜度

堆排序整體的時(shí)間復(fù)雜度

計(jì)算堆排序整體的時(shí)間復(fù)雜度就是計(jì)算上面這兩步的時(shí)間復(fù)雜度

第一步：

因?yàn)檫@一步實(shí)際上就是多次向下調(diào)整建堆，所以這一步時(shí)間復(fù)雜度就是向下調(diào)整法時(shí)間復(fù)雜度的倍數(shù)，那根據(jù)漸進(jìn)表示法就可以表示為O(N-log(N)),因?yàn)楫?dāng)N很大時(shí)，log(N)比N小很多,所以可以忽略表示為O（N）

第二步:

第二步外循環(huán)需要N次，內(nèi)循環(huán)看似每次都是一個(gè)完整的向下排序法，但其實(shí)隨著循環(huán)次數(shù)的增加，里面向下排序的時(shí)間復(fù)雜度在不斷減小，因?yàn)槎盐才胚^(guò)去的數(shù)字實(shí)際上就不用再參與堆排序的，所以這一步時(shí)間復(fù)雜度實(shí)際上是O(N*log)

因此，堆排序的時(shí)間復(fù)雜度為O（N+N*log（N））

總結(jié)

堆排序及其時(shí)間復(fù)雜度的講解就到此為止了，如果有不理解的地方歡迎在評(píng)論區(qū)中指出或者與我私信交流，歡迎各位大佬來(lái)訪(fǎng)！！！

創(chuàng)作不易，還請(qǐng)各位大佬點(diǎn)贊支持！！！