& s# G9 g. R6 I" _9 O$ T7 q分析:快速排序算法的时间复杂度分是O(logn),治是O(n),因此其最好和平均的复杂度是O(nlogn)。考虑一种情况,当数组有序而且我们选取pivot的方法是选最左边的或者最右边的元素时复杂度退化为O()。原地排序因此不需要额外空间,但是由于是递归函数,因此需要栈来保存状态,最好和平均情况下需要O(logn),最坏的情况下需要O(n)。由于快速排序涉及到随机位置值的交换,因此快速排序是一种不稳定的排序方法。 w+ A' J- Q9 Z$ N- i! a
8 O; W8 J. X B. v; S) X# a, P七、堆排序 5 e! s* b3 s8 {, N [思路:堆排序顾名思义需要一个堆,堆是一个完全二叉树,可以分为大顶堆和小顶堆,其中大顶堆是满足子节点的值小于父节点的堆,小顶堆是满足子节点的值大于父节点的堆。建好了堆之后我们就可以通过取堆顶元素再不断调整堆的方法来得到排序结果。因为堆是完全二叉树,因此其父节点和子节点的关系容易得到,所以我们可以用数组来模拟一棵树(一个堆),下面这个视频将堆排序讲的很清晰。, _8 T- Y: y1 V" y9 _3 o
! c" F6 J w+ J1 I8 q |& E【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆_哔哩哔哩_bilibili! A9 K" u+ T3 y! a5 {% v
1 i- e! p' g7 ^% I# t$ W' y" U
建堆:建立堆的方式可以分为从下往上和从上往下。以大顶堆为例,从下往上的话,对于每个父节点,判断其子节点值是否存在大于父节点的情况,是的话就交换这父节点和子节点的值,然后继续调整子节点(若子节点也存在节点的话则继续往下调整)。如果是从上往下建堆,就相当于是堆从从空的开始,不断插入元素再进行调整,判断当前插入的选择值是否大于其父节点的值,若是的话则交换当前节点与父节点,并继续向上调整直到无需调整或者到根节点。可以判断,从下往上的方式其时间复杂度为O(n),而从上往下调整的方式其时间复杂度为O(nlogn)。同时需要注意的是,对于同一个数组,采用从下往上和从上往下的方式建立可能会导致节点的排列方式不一样,但是都满足大顶堆/小顶堆的性质。 o9 O, u& J) u4 b+ W
( Q- [. Q$ P% K* [8 E8 R下面是从下往上建大/小顶堆的代码: ' D* l3 p; ?% t# g, m; s* u, _ ! f' m$ D6 X9 Q/ h* P( G: {// 接收参数为数组nums,当前调整节点下标i,当前堆的大小sz ) i# E, L' x+ }9 Mvoid adjust_from_buttom(vector<int> &nums, int i, int sz) & ]& i2 C7 _: W0 [' C{( Z$ z: A" h3 l1 q' _
// lpos和rpos分别代表左孩子和右孩子,largest用来存储左右孩子中较大的那个的下标 - `; o: p0 m& D' Y, r // 建小顶堆需将largest改为minest,此时这个变量用于存储较小的元素 ( d8 X3 l: ], @ int lpos = 2*i+1, rpos = 2*i+2, largest = i;$ d* l4 Q" b, q6 K
// 若有左孩子(下标小于sz)而且左孩子数值大于当前节点数值,就记录下左孩子下标 ! x5 L( {0 V8 @; }# N3 d // 建小顶堆需将 '>' 改为 '<' + h& p0 i8 ?: ?7 A7 m/ G if (lpos < sz && nums[lpos] > nums) " K2 j" F% K8 ] largest = lpos; & X' r' q5 B: c5 H$ R // 若有右孩子(下标小于sz)而且右孩子数值大于最大的节点值,就记录下右孩子下标 J, Y- Y( t% }
// 建小顶堆需将 '>' 改为 '<' - M$ {2 k5 j8 E if (rpos < sz && nums[rpos] > nums[largest]) 2 |# o5 R& L0 V( W3 F largest = rpos; . `- u) Z% Y# ^- U // 若存在某个孩子的值比当前值大 ! `' B! c$ ^3 \, L if (largest != i)3 E$ E% B0 G" j$ F7 d2 |
{9 E! P9 S. h: O3 {% D
// 交换当前节点和较大的那个孩子的值 ; r7 i4 R9 ]) V swap(nums[largest], nums); # w0 M, s8 r3 X4 O- x* D' ^2 j' f // 交换完之后继续往上调整树9 l: C7 F2 \2 v$ y* k6 C3 ?
adjust_from_buttom(nums, largest, sz); 2 x1 K* M/ v. S% A- x# K3 T } - {" W7 a5 d% u}/ W6 K: N p# A, _
4 S1 r+ m3 P3 f
void build_heap_from_buttom(vector<int> &nums)5 x. C3 {! t: B! ^
{ ; C) f8 ]+ F- h% m! | // 若数组只有一个元素则无需建立堆/ E k- ~( R+ H: @ k
if (nums.size() != 1): K- ?& K* D4 |' }
// 从最后一个父节点开始循环,一直到根节点 6 ]/ s7 }- X3 Q% S/ Q for (int i = nums.size()/2 -1; i >= 0; --i) & W1 P4 j0 @4 ?4 P* [* N // 不断对堆进行调整7 R# a0 p# {. f
adjust(nums, i, nums.size());5 F X: D0 W4 B# y, ?& p! A
}& w! _- E7 q7 W) a# q5 T
0 X2 J8 `7 Y9 }$ T3 U% y下面是从上往下建大/小顶堆的代码:* r5 T3 g9 }1 F" H5 `
+ X* s3 ~$ `: q* j
void adjust_from_top(vector<int> &nums, int i, int sz) 8 o3 h, A" [9 X3 H9 \) e. O+ _{ 5 Q% Q) B2 v4 } // 如果i不等于0 t/ Z5 k! u ]" ^ if (i)! J. U# J7 q0 Y. z: c
{6 G# ]& V* S* v; b' y; q
// 若i为偶数,其父节点下标为i/2-1。若满足当前节点的值比父节点的值大 + w3 o: q" U2 }, `2 ~# B& A1 r // 建小顶堆需将 '>' 改为 '<'/ O& b! g6 g( r% D
if (!(i%2) && nums > nums[i/2-1])% _/ m; w6 U$ l7 Q, C* d9 U4 t5 i
{ 9 o4 E0 u7 G1 a, v8 m, e
// 交换当前节点与其父节点,再检查父节点需不需要调整 2 |9 n: o! i. s) g/ k7 O; x swap(nums, nums[i/2-1]); 4 z; q4 c6 z" Y7 G! g+ ]& q% { adjust_from_top(nums, i/2-1, sz); 9 u# ?" w2 O; H5 ~# M6 w7 [ } , c( w w8 E* t9 h/ t( R // 若i为奇数,其父节点下标为i/2,则当前节点比父节点的值大, L5 K- d, i/ a& Q" k; L1 R* ]; `
// 建小顶堆需将 '>' 改为 '<' ! u! }: c+ }, e7 v" ? if (i%2 && nums > nums[i/2])- Y6 V# M, d1 B* F- C q
{7 `! R; Q6 a1 U. E
// 交换当前节点与其父节点,再检查父节点需不需要调整 9 v. G# ~/ `' U$ Q swap(nums, nums[i/2]); + D7 K2 U" G' }+ K8 x adjust_from_top(nums, i/2, sz); / B- l/ G* X5 D/ j2 |0 G/ q }- u* s6 w% T3 n( M
} 1 o+ }: \. T |}4 ]1 c: T* J; ^& [+ X
+ i; w' p( B; O
void build_heap_from_top(vector<int> &nums) G9 W$ T7 k, W: I) e' K' Z{ // 从第一个元素开始到最后一个元素结束 9 w2 x( e$ p+ s9 | u5 T- M for (int i = 0; i < nums.size(); ++i) ; d( y# D/ h$ Q" v // 插入新的元素并调整 4 a5 ^7 N& Y) h' s# i: o' y3 V5 C adjust_from_top(nums, i, i+1);/ X j7 U, W0 ~& j2 K2 ~! M
} ' f; Z+ {! P% ] Y7 B $ p" E# Q" k# |- I9 _建立好的堆之后就可以通过取出堆的根节点,再不断调整堆来进行堆排序,我们可以把取出的节点与堆的最后一个节点进行交换,然后把堆的大小减一,这样就可以利用堆原有的空间来存储排序的结果,而无需额外开辟空间来存储。堆排序代码如下:/ J5 V! F" ?9 I1 X, O6 H8 W5 l
/ \8 z8 B6 L: A) Y
void heap_sort(vector<int> &nums) ! L" g; ?2 l2 n# V7 B9 ~& Y# O{9 y# I. I1 Z; a* y0 L
build_heap_from_buttom(nums); // 或者是build_heap_from_buttom(nums);* z6 R3 b N: `, v2 }2 z- O. [# H9 _
// 从最后一个节点开始往上走 . l) E* o- m4 V! Z @ for(int i = nums.size()-1; i > 0; --i) ; b8 e1 J9 G- F$ g1 ] { m$ x6 A3 }6 E6 Y3 ?" ?& H J: R$ Z
// 将最后一个节点与堆的根节点交换+ R- Y0 D$ |$ [6 Q
swap(nums, nums[0]);6 Q/ W/ G4 E8 A- ]% z9 z" N: V
// 调整堆,堆的大小为原大小减一 ( z; s+ F0 q6 X. H" y( C" v% G adjust_from_buttom(nums, 0, i); % W; u' Z: a& p% @3 j }) g1 ^+ {* y. `
} / A$ N2 S. B$ D$ q, r' u9 d4 h我们可以注意到堆排序的过程交换了节点之后,只有根节点发生了改变,因此只有可能是根节点不满足堆的性质,所以在调整的时候我们调用了adjust_from_buttom()方法来堆根节点进行调整。 4 \( b; O# G9 W! y: B( B0 S3 d# X' { " z `3 y3 A5 h; [* B分析:堆排序的时间复杂度包括建堆和调整,从下往上建堆时间复杂度为O(n),调整堆的时间复杂度为(logn),因此堆排序最好、最坏和平均情况的时间复杂度为O(nlogn)。堆排序不需要额外的空间因此其空间复杂度为O(1),但是由于建堆的过程中可能出现位置调整,因此堆排序是一种不稳定的排序方法。 6 N% d% H: q- d* Y3 L8 v % R5 R E0 b1 J& m八、计数排序 + n/ q7 \$ _$ K7 r/ t$ H/ O" g6 _思路:计数排序主要是针对一定范围内的整数来进行了,先确定序列中的最大值和最小值,从而开辟max-min+1大小的空间,空间的每一个位置代表一个数,若遍历到了某个数就将该空间的计数值自增,那么遍历完原数组。排序结果可以通过遍历这个空间来得到。在实现上C++中可以通过map来实现这个操作,因为map本身是保证有序的。当然因为map内部要进去排序,所以如果要实现极致的空间换时间的话,需要自己手动来实现这样的map。* e* n. [- g8 `1 u _
3 @* ^/ ?2 S3 ovoid count_sort(vector<int> &nums) # f( ]" @' N- p7 b0 @{ % E# R' F' L( L# m
// 用于存储数与出现次数的对应关系! {7 W# G( F8 S! ?0 P3 B; O
map<int, int> cnt_map; 2 I' Z7 a: F8 K" c8 c // 遍历数组以将元素及出现次数添加进map. H8 L, G, [) w' K8 E B
for (auto i : nums)7 U3 v1 t& r9 M' @$ {$ a
{ 0 W' ^) s" ^3 P) g; e //5 M/ K* l' }* n. v, {3 C
if (cnt_map.find(i) == cnt_map.end()) / x- s. H5 }7 w$ d* }/ Y cnt_map = 1; * c* H# B- p; U+ P& ^ ~9 Y9 h" L else ^* |: t( z1 X# G, t
++cnt_map;1 v3 V% V j/ R6 K
} ( N7 o$ L7 @. ?0 f4 f // idx代表原数组下标 ! A, B8 r, e4 Q+ _6 M7 j* j( |/ T int idx = 0;) ]9 j, ]( R9 h
// 遍历map以将map中的元素放回原数组- r S8 V/ N# t1 K* S
for (auto it = cnt_map.begin(); it != cnt_map.end(); ++it) 5 _$ M4 l' t% p v# l {+ Q ?# w* j; h) t. k: O4 q, [0 E9 H
while (it->second != 0) # r3 s% o6 o# a% s# ~5 Z { 8 a) }( H" F" {3 ? nums[idx++] = it->first; ( v3 Y6 q$ p2 Q: M' I --it->second;& e& K2 i2 y- T6 X
} 7 H/ k. _- i- y+ o } . ?8 ?( U1 B/ G* }} 8 }2 ~; ?) }( L. p0 `+ C8 \9 v2 \& u5 c8 J- m+ F
分析:计数排序最好、最坏和平均情况下的时间复杂度都是O(n+k),n是表示遍历原数组的时间,k(数据范围)是表示遍历辅助空间的时间,其空间复杂度为O(k)。计数排序可以看做是一种稳定的排序,比如我们把计数排序存储每个元素的位置看成队列,那么就符合先进先出,所以是稳定的。 ! }. l* F' }( m" z $ c- \+ J$ I. p* n' `$ E九、基数排序 # n, C6 Y1 I. ?* Q
基数排序通常可以用在整数或字符串上,比如整数上就可以分0-9十个桶,通过比较个位,十位一直到最高位,分别把数装进相应的桶中,再依次取出,比较更高位再装进桶中,再取出,直到所有的数都在0这个桶中说明所有的数都排好序了。 : i/ [$ U7 j3 H+ x8 e" R' u* W6 i% b# s- {$ w) G% e: ^
但是需要注意的是,一般的基数排序无法处理有负数的情况。针对负数,一般有两种解决方法: ; ?$ I5 {* s( J- G 2 s" _4 D: Y( ` P1、另外开辟10个桶用来存储负数的情况(需要占用更多的空间) 9 |6 W; k; Q6 m+ G1 h/ P5 e, M% a0 `/ r" C' g
2、将所有元素变为正数再处理(可以将所有元素都加上最小负数的绝对值,但存在溢出风险),下面代码实现这种方式1 z1 B- N, J' O! k2 o
& g" _, ]+ w& x6 s
void radix_sort(vector<int> &nums)# \ _$ J+ E& n, j
{! `2 H$ f" t8 K8 g6 @
// 开辟二维数组,第一维10代表十个桶,第二维当前为空/ B9 q9 M: n, C1 x- _, }
vector<vector<int>> ivec(10, vector<int>(0));/ T6 z) e6 e9 l. E6 I0 u) O. Z6 ]0 B
// 用于取出最小元素,将所有元素都变为正数 . E2 \! n) m, w+ }" D5 G int min_num = *min_element(nums.begin(), nums.end());% d2 U' G. E* h5 ?
if (min_num < 0). S/ D: y& q4 Y# m: p
for (auto &i : nums)1 S d" r) T5 l" ~( M' P
i -= min_num;1 S& M# D4 B) F
// 用来控制比较的位数,初始为1代表比较个位数$ z- i# x% V& Z6 |8 y. e4 A3 v
int digit = 1; 0 f/ x2 v8 `/ p& Z, C' W6 g, O( i // 循环一直进行 ! w+ d; J |7 z3 X, m1 o& P7 F while (true) $ ~1 |+ P4 f( A' R' L) t { 8 A8 z8 o B3 V8 A3 q# f6 u* r1 e7 v0 p // 对nums中所有元素遍历,将每个元素放入对应桶中0 d5 @: N# Q; A, \
for(auto i : nums) " M8 ?; {% ^6 o ivec[i%(digit*10)/digit].push_back(i); + C: `) W' H1 D3 a5 k6 e3 _$ z6 r7 C$ g1 _0 u9 d P9 n
// 这是循环终止条件,即所有元素都在0号桶中 - w8 _* }/ h2 X( U. A if (ivec[0].size() == nums.size()) 8 `% @5 u# K1 F+ Q break;. v* \- t1 i# a2 |2 p
// 记录nums中的下标用于放回nums中+ N0 B" K0 |6 _6 p$ ]
int idx = 0; 2 z3 j4 y/ \( P h# ~0 } // 依次从每个桶中拿出元素放回nums,取完之后清空桶: l$ O' u7 n5 ^, @. D
for (int i = 0; i < 10; ++i) / q# s; J8 x, r {2 `2 T7 f9 y) [8 n; G) Z5 ~
for(int j = 0; j < ivec.size(); ++j)% i, H; C0 J V4 h3 i, F) ~
nums[idx++] = ivec[j];6 P1 o4 P* @6 \5 A! t
ivec.clear();5 X8 O& I+ _, w& L8 {7 M$ k/ V; W
}* D# a$ e- `3 x0 P- z$ [
// 下一次循环比较更高位 # P" k7 N3 k& R( z* [ digit *= 10;7 u, ]- ^8 P: N7 T+ R
}( b4 {5 I2 Z# s$ `& T+ V
// 排序完毕后将元素恢复为初始值 R5 ]& z {" N4 r
if (min_num < 0)% R7 c: u; j w, _" H$ \
for (auto &i : nums) * o" L. d7 p/ A q i += min_num;8 ?- o, \+ F P% A
} & o- F- n7 m- q4 P& y$ ~0 T/ y p% o/ _; n) {8 K$ y; d分析:基数排序的时间复杂度取决于待排序的元素中的最大位数k,如最大元素为1023,那么最大位数k=4。对于每一位我们需要遍历两遍数组,但是这里的两遍可以省略,因此最好、最坏和平均的时间复杂度都是O(k*n)。由于我们需要开辟一个额外的空间来把每个数放入桶中,因此空间复杂度为O(n)。又因为我们放入桶和从桶中拿出的操作都保证了先进先出,因此基数排序是一种稳定的排序方法。& m$ S$ Y+ z* e
6 J% M6 u" d2 U, u
十、桶排序 & t: } n9 I" X# e' J! ?. `0 o5 }前面计数排序和基数排序都是桶排序的一种特例。桶排序是这样一种排序,它将原来的数组分到不同的桶里,再分别对每个桶内部采用排序算法进行排序(可以用快排、可以用选择、冒泡等都没问题),最后将每个桶里的元素依次取出就得到了排好序的结果。因此桶排序如何分桶是一个关键的问题,如果分的好的话,每个桶都能均匀地承载一部分数据,最后时间复杂度就会比较理想。若果分的不好,很多数据都集中在一个桶里,那么最后的时间复杂度就很差(最差情况下会略大于桶内排序算法的效率),此外桶排序还需要额外的空间。 . S/ e4 P/ a) v- y9 O) q7 @, X% K/ @' |8 s! U
void bucket_sort(vector<int> &nums, int bucket_cnt) ) y$ V% V F% g8 A* q; ^4 }% R; t{ ( P; D5 _" q! D& H$ y // 建立bucket_cnt个桶,每个桶初始为空. O7 C& D4 B" A5 w: t& i% Z! ~% B e
vector<vector<int>> ivec(bucket_cnt, vector<int>(0));' L- \/ ^. Y9 I# H6 d
// 拿出数组中最大和最小的元素来确定每个桶之间的间隔 & X$ c2 e# W$ \3 X int min_ele = *min_element(nums.begin(), nums.end()); ' S: E+ m5 [7 [* }+ L) m int max_ele = *max_element(nums.begin(), nums.end());4 v' A9 {+ E- I& x& I% S, Z; b
int gap = (max_ele - min_ele) / bucket_cnt;7 H3 C( ]- Q! }% V. }$ d. B; C$ {
// 如果间隔比桶个数都小,那么直接排序可能更快& H! s' o) [" z7 Y
if (gap > bucket_cnt) * v' w( O6 T5 y { $ ^' R; {- M" C% w( i& A // 遍历数组中每个元素( l* |! ]+ \: z
for (auto i : nums) - F1 X* x. b' r" z$ y% S { 6 c0 y A: d+ y x0 L; X // 确定元素所在的桶序号 2 v) A6 C# G/ ^ int bucket_num = (i-min_ele)/gap;, T8 h0 R) C Z4 ~ k1 a
// 若算出的序号等于桶个数,那么说明越界了(比如数组中最大元素就会出现这样的情况)4 A9 I/ k- j4 y B
if (bucket_num == bucket_cnt)0 j1 \5 J% m! P' I! ^& S
--bucket_num; w$ y7 U' V, R6 F% { // 将该元素装入桶中- t8 ~2 ?. T, L; g: ~3 c4 Q
ivec[bucket_num].push_back(i); 8 f4 A) Y2 A) \, z9 k! k5 w }4 L; @0 K. o9 S. y1 e
// idx记录原数组nums中的下标用于装回元素 0 a. Y! S3 s; n( I* } int idx = 0; * x! ?2 }' ~( w8 S3 Y; a& u- A // 对每个桶先排序再往nums中装入元素,最后清空桶/ F6 v4 L8 u: Y9 B
for (auto &vec : ivec) " N' I" e1 \' N5 K {# s9 X7 w( T: k) j: f
quick_sort(vec);2 k9 o* N W/ \. k
for (const auto ele : vec) 1 a/ Z; I1 ^& h, }9 @9 J- _" `$ F% Y nums[idx++] = ele;& M1 M3 ~- w' w. z' P1 P* A2 z
vec.clear(); + ?+ c& u$ g* H } # { R, b; F4 r# k2 Y3 \ } 3 `6 z/ W: h n {8 S
// 直接排序# z) h* d3 w" H: w- P
else+ v9 d, P$ o* A( v6 N: g) _
quick_sort(nums); ' z4 o. C: }0 ?- F} 3 B9 O5 U' Z" o2 E% i7 P 0 G. n) r; q7 |5 A( E7 {8 G分析:桶排序将原数组分为k个桶来处理,假设数组总数为n,那么每个桶装了n/k个数据,假设我们在桶的内部使用快速排序,其时间复杂度为O(klogk),那么对于所有桶来说,总的时间复杂度就是k*O((n/k)*log(n/k)) = O(n*log(n/k))。最好的情况是每个数据都装进一个桶,这样就无需排序了,因此最好的时间复杂度是O(n),平均情况的时间复杂度是O(n*log(n/k)),最坏的情况的可以接近O(nlogn),但是比O(nlogn)要更差(因为存在分桶等操作)。桶排序的空间复杂度是O(n+k),因为桶排序除了要装下原始数组长度的元素,还需要额外的k个桶,这k个桶系统会默认分配内存。桶排序是否稳定依赖于其内部的排序算法,若内部使用快排则不稳定,若内部使用归并则是稳定的。. l: q+ c% ]* o
———————————————— $ [$ h# r3 u- y! S/ K版权声明:本文为CSDN博主「Xaiver_97」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。* H, k, E4 b4 \) l( E
原文链接:https://blog.csdn.net/Xavier_97/article/details/126722423 & D8 ?* w; J; V7 { : a! d% p& {0 S/ o( Z ?: L( f) N