( M3 e# e, d' n C ^6 _// 接收参数为数组nums,当前调整节点下标i,当前堆的大小sz $ u7 {1 K# c; pvoid adjust_from_buttom(vector<int> &nums, int i, int sz) 1 d- Y3 d5 }1 b: s( z{ X3 |5 n0 M0 Q2 Z; Q // lpos和rpos分别代表左孩子和右孩子,largest用来存储左右孩子中较大的那个的下标 6 _: ?7 S6 D6 C1 Z, H1 w1 c8 M // 建小顶堆需将largest改为minest,此时这个变量用于存储较小的元素 , _1 @ r0 e2 M* G! C0 r" A! L. z int lpos = 2*i+1, rpos = 2*i+2, largest = i; 0 j& V+ L) L0 Y/ y; K // 若有左孩子(下标小于sz)而且左孩子数值大于当前节点数值,就记录下左孩子下标 # L) d' A( O0 o9 J' X4 P // 建小顶堆需将 '>' 改为 '<' % [* [" R- p; w8 F. B if (lpos < sz && nums[lpos] > nums)) U: N- E3 ^4 K+ T5 N1 h9 W$ @
largest = lpos;3 v8 W1 A# |7 a0 H0 k; r; A7 j. i
// 若有右孩子(下标小于sz)而且右孩子数值大于最大的节点值,就记录下右孩子下标 # D# a0 D" ?4 K' A // 建小顶堆需将 '>' 改为 '<' * t/ S1 d* i! O1 R' J2 G if (rpos < sz && nums[rpos] > nums[largest]) , ~, k7 I9 H: f1 h' A largest = rpos; : E' D( ?# o% @4 d6 u+ F // 若存在某个孩子的值比当前值大5 W4 v, ~8 ^% r( \& y0 E
if (largest != i)) g( L' r/ G7 ]3 a
{) l. C' I! ]+ P2 I$ \& `2 J
// 交换当前节点和较大的那个孩子的值8 [- ~4 r$ k6 e7 C& z2 d
swap(nums[largest], nums); # A% R! G- A' K7 e+ P' P3 M0 N // 交换完之后继续往上调整树 , q5 ]5 Y) E4 M( N2 ` adjust_from_buttom(nums, largest, sz); 4 w2 O5 N' `( E- C, Z9 R } 8 q" q3 K! @% \! ^+ _} , f# ?7 E& Q# N- q* J. F" \ : C& F; V. M, {3 X5 J4 xvoid build_heap_from_buttom(vector<int> &nums)! }9 J f* d) B2 |& [, P
{ t& g& z3 n( C+ Y" D
// 若数组只有一个元素则无需建立堆 # J( h1 \$ [. B: Y: G if (nums.size() != 1) 8 l0 }' ]2 l- q/ v7 | // 从最后一个父节点开始循环,一直到根节点 5 {9 r; I9 [( n ?$ U- k% g t for (int i = nums.size()/2 -1; i >= 0; --i) 4 x) R& L; h2 {! o6 g' ?, Y$ \ // 不断对堆进行调整- B% a' @9 r: M3 @0 X" ~
adjust(nums, i, nums.size());4 ?3 _/ S+ }* K! z# ?/ p( x
}; v! Q$ A, o; ]! h9 L6 J
; X9 y/ K1 x' X2 l. T下面是从上往下建大/小顶堆的代码: 2 i( \, i5 c+ {! _) ] 1 }* P& _4 o6 k, Z! Fvoid adjust_from_top(vector<int> &nums, int i, int sz) 1 G: e8 t& }& {{5 k9 D$ D! A: F( B( w
// 如果i不等于09 |' M; o% d$ H# \( x
if (i) ! g) f6 a" }6 k* \( r& j5 @ { & U0 ?! }+ ?1 f7 Y // 若i为偶数,其父节点下标为i/2-1。若满足当前节点的值比父节点的值大+ |' l/ l$ ]2 e* M3 X( K
// 建小顶堆需将 '>' 改为 '<'6 Q7 K( T5 j# l3 m" b& a7 ]2 j
if (!(i%2) && nums > nums[i/2-1]); j1 X3 k% I D* q
{ + l- T/ Q4 \/ v8 [ // 交换当前节点与其父节点,再检查父节点需不需要调整! G; P; s; i5 f
swap(nums, nums[i/2-1]); ; k9 v1 }- h3 X4 W% G adjust_from_top(nums, i/2-1, sz); r- _, U% T5 }4 O7 P
} - X0 ~5 g3 I8 u) P( `* S4 M9 i // 若i为奇数,其父节点下标为i/2,则当前节点比父节点的值大& ^! V- c0 @4 j) e5 B- Y
// 建小顶堆需将 '>' 改为 '<'$ F# c1 O& m8 x- Y" h3 c
if (i%2 && nums > nums[i/2]) + i/ \. t8 e8 z! N6 m { " M8 f9 f! ^- R! q' k // 交换当前节点与其父节点,再检查父节点需不需要调整 9 U3 Q3 C6 D- v6 m1 w, a swap(nums, nums[i/2]); 8 o$ f# { j% Q' V: W. N7 N' } adjust_from_top(nums, i/2, sz); - p6 d6 X- }! e# G5 U0 ^ }# ^& T# x: n1 e3 V4 ~
} : I; p- ~* `3 g9 w+ ]7 ^} 7 X ~- ?: O# s# ?8 C # {* w# h' y. ^' x) ]# Jvoid build_heap_from_top(vector<int> &nums)2 q) K9 R/ D- F T3 V
{ // 从第一个元素开始到最后一个元素结束3 o- q, x) K/ `7 w- S2 z; E
for (int i = 0; i < nums.size(); ++i)" u" O2 c( Z$ ]/ d* J3 t
// 插入新的元素并调整) f) F! O7 q0 i/ ~+ D3 V
adjust_from_top(nums, i, i+1);+ r7 |5 V0 q& p9 n
} 2 ~" t" x9 W! m& }' _6 G0 c( m% y( `* A7 V
建立好的堆之后就可以通过取出堆的根节点,再不断调整堆来进行堆排序,我们可以把取出的节点与堆的最后一个节点进行交换,然后把堆的大小减一,这样就可以利用堆原有的空间来存储排序的结果,而无需额外开辟空间来存储。堆排序代码如下:' s3 s5 f5 S l( K
6 D$ Z. Y3 J7 y+ Ivoid heap_sort(vector<int> &nums) $ @7 |0 m# n6 L: f{/ H' t! R1 w2 [3 \) W0 z7 g! F
build_heap_from_buttom(nums); // 或者是build_heap_from_buttom(nums);9 |% a; L* G: t$ U# s$ Y# t
// 从最后一个节点开始往上走 p9 D( X8 d' J& |- q for(int i = nums.size()-1; i > 0; --i)- [; W4 J, q; A# z9 S4 q
{ : S- N+ h5 X" ^ // 将最后一个节点与堆的根节点交换 ; `! R0 N- b" A) n2 O. B, z0 x3 t swap(nums, nums[0]); m/ B H8 X7 s5 R! F2 }% F // 调整堆,堆的大小为原大小减一6 P( A0 a; w2 j+ k4 j2 ]1 ^
adjust_from_buttom(nums, 0, i); T% s/ X/ R) }: ]' @% k }1 f l- \0 V1 \ A7 j# G' Z
} 9 Q8 T; M. } v" d! j) y我们可以注意到堆排序的过程交换了节点之后,只有根节点发生了改变,因此只有可能是根节点不满足堆的性质,所以在调整的时候我们调用了adjust_from_buttom()方法来堆根节点进行调整。 ' u# a: p7 d5 ^" ^) Z! r9 c* ?6 W, f8 @, `0 e) H4 M6 H
分析:堆排序的时间复杂度包括建堆和调整,从下往上建堆时间复杂度为O(n),调整堆的时间复杂度为(logn),因此堆排序最好、最坏和平均情况的时间复杂度为O(nlogn)。堆排序不需要额外的空间因此其空间复杂度为O(1),但是由于建堆的过程中可能出现位置调整,因此堆排序是一种不稳定的排序方法。 6 [. h X9 j5 c- _& r/ k' `& W+ ^$ d @5 ?1 ~
八、计数排序 # O6 O! c5 Y: Z* w/ w思路:计数排序主要是针对一定范围内的整数来进行了,先确定序列中的最大值和最小值,从而开辟max-min+1大小的空间,空间的每一个位置代表一个数,若遍历到了某个数就将该空间的计数值自增,那么遍历完原数组。排序结果可以通过遍历这个空间来得到。在实现上C++中可以通过map来实现这个操作,因为map本身是保证有序的。当然因为map内部要进去排序,所以如果要实现极致的空间换时间的话,需要自己手动来实现这样的map。 - ~! N: X( U8 O0 A ! @- Z& A' u0 G! T4 hvoid count_sort(vector<int> &nums) * D( o1 v& y6 z a2 m2 m5 M2 T{ / P2 b0 @, |/ }+ Q' i, q4 S // 用于存储数与出现次数的对应关系" ?2 N/ ~% i B! f8 k
map<int, int> cnt_map; $ G2 S1 T$ b0 J // 遍历数组以将元素及出现次数添加进map' p g9 }- L4 g( @ X k
for (auto i : nums). q" O/ b4 A1 Z$ K" S
{ ) y3 H; {) b/ k% c% v, _ // 9 d+ @; r" y8 n8 F7 K7 S; P+ H if (cnt_map.find(i) == cnt_map.end())' P/ t* M( C% t! q3 j
cnt_map = 1; $ C# b# o6 @# F! z }4 n else3 a/ L6 ^, D6 M3 |; z, ]* `- U- E
++cnt_map; ! q& R$ e- K6 s! f1 W" X% f }6 P) N9 b% r6 G$ K0 l; H
// idx代表原数组下标5 u8 s& }" Y: @5 L; S. n) L1 R
int idx = 0; : C' N7 h% M! r9 Z8 F // 遍历map以将map中的元素放回原数组 1 O( k6 B \& ^& ^8 F+ Y) t/ w for (auto it = cnt_map.begin(); it != cnt_map.end(); ++it)) \5 X1 J }; h/ L6 T. w, x* Q0 y+ Q
{7 G, G0 y/ U( T a, @9 }* U# i, }
while (it->second != 0) % F& f J1 v* y5 e {' x2 U' Z8 ~5 H3 L% q4 C+ Z2 C
nums[idx++] = it->first;- X# {7 B. h6 ?, l6 B
--it->second; $ w" V1 {6 j) v0 y9 f, L. ~ }6 i* U1 z% a4 B
} 6 p5 r3 X u+ [0 l* Z9 s} " n; _* f8 ^2 P" l. m5 t4 Q+ w6 T, x7 w* s3 o+ u5 X! `. u
分析:计数排序最好、最坏和平均情况下的时间复杂度都是O(n+k),n是表示遍历原数组的时间,k(数据范围)是表示遍历辅助空间的时间,其空间复杂度为O(k)。计数排序可以看做是一种稳定的排序,比如我们把计数排序存储每个元素的位置看成队列,那么就符合先进先出,所以是稳定的。 1 s) H ]9 U& c. f% }7 S, D, }4 Z* w4 f# L
九、基数排序 $ i7 h, q' x6 o$ ?/ a
基数排序通常可以用在整数或字符串上,比如整数上就可以分0-9十个桶,通过比较个位,十位一直到最高位,分别把数装进相应的桶中,再依次取出,比较更高位再装进桶中,再取出,直到所有的数都在0这个桶中说明所有的数都排好序了。 & s! m. T5 v6 f. D$ y ) a% X. K" T* t; [8 m1 V% s但是需要注意的是,一般的基数排序无法处理有负数的情况。针对负数,一般有两种解决方法:7 ~9 M& a( A/ _- r, m
! U e- }8 J. b8 V' z T; C1、另外开辟10个桶用来存储负数的情况(需要占用更多的空间) p8 X2 g6 @% u7 l/ c
& g" M, h: Q& c; r7 H3 Z; D
2、将所有元素变为正数再处理(可以将所有元素都加上最小负数的绝对值,但存在溢出风险),下面代码实现这种方式) n) y. f; s% K) k0 a
3 c/ k6 W+ d8 A- Bvoid radix_sort(vector<int> &nums) 3 u3 W1 s+ V; w* {, x! }{ 7 Z5 ]) j6 u. \ // 开辟二维数组,第一维10代表十个桶,第二维当前为空7 R8 V1 }" w0 @( {6 B; W. O7 ^& T
vector<vector<int>> ivec(10, vector<int>(0)); 7 z9 C5 ]. ~. h* T9 Y) s // 用于取出最小元素,将所有元素都变为正数 # X! h! S: f6 P, ~8 n' m$ Y int min_num = *min_element(nums.begin(), nums.end());/ D9 u2 U! B' b* ?6 T" H8 m3 g+ {
if (min_num < 0) + @8 o9 p L# n) z3 m0 G( i" X for (auto &i : nums) 4 \3 z4 e/ t5 R: M% `8 \ i -= min_num; & c* z2 n5 F1 J. ~: Q \2 F // 用来控制比较的位数,初始为1代表比较个位数$ z# g8 W- y4 n2 O1 Y6 e
int digit = 1; ' k4 j6 X2 p* D% T3 A // 循环一直进行 ' _8 p7 G& f! F! n while (true)- `# ^! \( T3 O9 z
{ ' I$ _3 Y0 I% \7 Z2 F1 A% X // 对nums中所有元素遍历,将每个元素放入对应桶中 , A/ P0 g) V. c" I for(auto i : nums) ; n1 [8 H6 ?& @7 W8 N2 z- P2 [4 t { ivec[i%(digit*10)/digit].push_back(i);3 G ?1 y( r3 k; s
& j4 F) c* E/ [6 {3 z# k
// 这是循环终止条件,即所有元素都在0号桶中 ) m+ Z$ ~6 n( D% ]) p& b if (ivec[0].size() == nums.size())% W9 e$ b: V" O) |2 n8 U6 [' P
break; ' G' i8 W" T! q$ X // 记录nums中的下标用于放回nums中$ X9 n ?! n* C% k5 S, n$ v
int idx = 0;: J4 k8 ~8 @1 x. r9 n1 ~; c1 U
// 依次从每个桶中拿出元素放回nums,取完之后清空桶 M1 n# n8 L; }2 n1 R+ z% W
for (int i = 0; i < 10; ++i)+ A0 o C0 J/ d, Q
{ . v$ ~8 f: Z3 ]+ \4 s ` for(int j = 0; j < ivec.size(); ++j) 6 @7 w d. h( _2 @4 V+ l1 h nums[idx++] = ivec[j]; 3 D' b$ e* l$ Y/ G ivec.clear(); + w: Y/ N7 H! W) t* G# C j! x0 C } ; b0 q0 F& Y3 M" w- F // 下一次循环比较更高位 z) ~ @. \) B+ R% e
digit *= 10; : S' o& A/ v! L* M' c. Q }/ J% H- X& j6 v; O3 ?
// 排序完毕后将元素恢复为初始值9 V3 R2 ^) L9 m
if (min_num < 0) / D! E- u5 G0 t( m0 b1 ? for (auto &i : nums) l1 i0 m# ^3 t: v2 _8 l b' G i += min_num; . }( l/ p- Z4 }, g: |9 }' \% F8 ~} 3 q2 N8 l) t; o+ q+ d$ E L+ L2 }# ^2 L f; U5 {
分析:基数排序的时间复杂度取决于待排序的元素中的最大位数k,如最大元素为1023,那么最大位数k=4。对于每一位我们需要遍历两遍数组,但是这里的两遍可以省略,因此最好、最坏和平均的时间复杂度都是O(k*n)。由于我们需要开辟一个额外的空间来把每个数放入桶中,因此空间复杂度为O(n)。又因为我们放入桶和从桶中拿出的操作都保证了先进先出,因此基数排序是一种稳定的排序方法。 % H: M# F3 T5 e2 ^0 L$ ]( j+ m 5 D0 [! x& a7 p十、桶排序 ) j3 j5 s! e8 s" j0 K$ `1 M! i7 \
前面计数排序和基数排序都是桶排序的一种特例。桶排序是这样一种排序,它将原来的数组分到不同的桶里,再分别对每个桶内部采用排序算法进行排序(可以用快排、可以用选择、冒泡等都没问题),最后将每个桶里的元素依次取出就得到了排好序的结果。因此桶排序如何分桶是一个关键的问题,如果分的好的话,每个桶都能均匀地承载一部分数据,最后时间复杂度就会比较理想。若果分的不好,很多数据都集中在一个桶里,那么最后的时间复杂度就很差(最差情况下会略大于桶内排序算法的效率),此外桶排序还需要额外的空间。. P. Z' h8 s' l) i
2 G0 c2 o) S8 K3 g: v7 \ O* Ovoid bucket_sort(vector<int> &nums, int bucket_cnt) G8 s0 P! T1 q' n0 m0 p3 X, ]{1 S" W" a( e. c/ h- U; ^1 O& {! ~
// 建立bucket_cnt个桶,每个桶初始为空 * z, ^* ?/ b/ X2 [- u( s vector<vector<int>> ivec(bucket_cnt, vector<int>(0));3 P/ F( G$ [# U* a) I7 S
// 拿出数组中最大和最小的元素来确定每个桶之间的间隔 ) O$ h' f4 \7 G: w) F int min_ele = *min_element(nums.begin(), nums.end()); X% t9 w. R2 G9 l3 c4 S$ e0 q& ] int max_ele = *max_element(nums.begin(), nums.end()); 9 v+ v O, s e6 t int gap = (max_ele - min_ele) / bucket_cnt; 2 X# c; w) y: S+ d+ w+ W // 如果间隔比桶个数都小,那么直接排序可能更快 2 u& {) I: E: c% G+ V1 m if (gap > bucket_cnt) . I E z1 l' `! T. x { 1 i7 J& l/ q. w/ s // 遍历数组中每个元素 $ `7 Z6 F6 }$ y' p$ K for (auto i : nums) 8 [- F+ _% E+ `1 V3 r {2 ` _5 j& R/ ?6 j2 m
// 确定元素所在的桶序号" A; x9 x( U' G3 D1 k
int bucket_num = (i-min_ele)/gap; ) _& R# f1 v4 l4 d& p% l$ o // 若算出的序号等于桶个数,那么说明越界了(比如数组中最大元素就会出现这样的情况) s3 z. n9 C) \ if (bucket_num == bucket_cnt) ) } a4 y9 w8 s4 X2 J/ e* { --bucket_num; . n- F2 G9 W F* ? // 将该元素装入桶中 " f7 H1 r# U8 E ivec[bucket_num].push_back(i); j' j3 ?4 Z% Y% f
}8 ^0 O9 }, R- S5 O4 r% k. O+ K8 {
// idx记录原数组nums中的下标用于装回元素, i$ S5 r- W; Y: p; F9 L% _, I
int idx = 0; " l3 d' K. m7 Z9 r // 对每个桶先排序再往nums中装入元素,最后清空桶. w9 K! k! X, V% ^- v% s
for (auto &vec : ivec) & y% w5 b5 Y, b4 A# X I {3 @% h8 l) z/ q% l5 `0 t8 a3 ~
quick_sort(vec); \6 q+ h% } w; J) j h for (const auto ele : vec) 4 P- E/ f& y* I1 H" k nums[idx++] = ele;/ E' @8 M/ L+ X. c1 l) I4 ]* e8 O
vec.clear();& q& p H3 E6 h4 j" d e
} 3 h2 ?# p+ [. w' \ } ) |1 W: O* c0 o
// 直接排序 4 Z2 V& s) Z6 d else; S: Q' G7 N6 }& a. u
quick_sort(nums); + ?3 o o& H6 B# i1 _} & c5 F! m, F1 P! l# U4 F; G 0 h. [6 C2 Y/ b0 C分析:桶排序将原数组分为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个桶系统会默认分配内存。桶排序是否稳定依赖于其内部的排序算法,若内部使用快排则不稳定,若内部使用归并则是稳定的。 / e( d! I$ T& Y# K———————————————— ! T0 Z Z: v6 L( O6 s版权声明:本文为CSDN博主「Xaiver_97」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 ( \7 B* B; l2 @$ [% S- w原文链接:https://blog.csdn.net/Xavier_97/article/details/126722423 $ k4 ?% F; N" D+ w; T" z0 k. U, S3 @" l9 p3 H" F8 k' _
# _2 Q, x5 F6 Y0 U! Q8 S