数学建模社区-数学中国

标题: 常见的十种排序算法C++实现（附时空复杂度，稳定性分析） [打印本页]

---

作者: 杨利霞    时间: 2022-9-8 09:57
标题: 常见的十种排序算法C++实现（附时空复杂度，稳定性分析）
常见的十种排序算法C++实现（附时空复杂度，稳定性分析）
, u! I3 m) g. `- D3 g* P
一、冒泡排序
8 E' N" n. `/ C7 Y& V3 o8 v思路：每一轮排序使得当前无序的部分的最大值冒到当前无序数组的末尾，下一轮中无序部分的长度等于上一轮减一，原数组的末端不断的变成有序的部分。
' N" U1 Q9 Y! U- P( f4 V) Q
  Z" J6 s* [% K# C. Uvoid bubble_sort(vector<int> &nums)
/ z% M8 ^# }  w( W+ P8 z, L7 ~{
    // 用于标记当前轮是否有交换发生
  l. h3 G; R  `5 V! s7 t    bool swaped;
8 Z8 \* K7 T, H# |6 ?. {    // 从第一个数到倒数第二个数（n个数需要冒泡n-1次）
3 A- D7 C5 ?0 h! D3 d6 S3 ~    for(int i = 0; i < nums.size() - 1; ++i)
    {
        swaped = false;
, O# G4 X, r) Y: N" f3 N- s        // 因为是当前的和后面的比，所以结束条件是一直到冒泡完毕的元素的前一个
        for (int j = 0; j < nums.size()-1-i; ++j)
        {   
$ c; o! r& O# C# g            // 通过交换两个元素，使得最大的冒到数组的末尾去，并且标记交换过
            // 若要从大到小排序，只需要把这个 '>' 改成 '<' 即可
            if (nums[j] > nums[j+1])
            {
                int tmp = nums[j];
& r$ G2 G7 A" ^, _& t                nums[j] = nums[j+1];
                nums[j+1] = tmp;
                swaped = true;
, W' D" _0 F& k5 W+ I- k  E            }
: |1 U, t: p  N( r        }
6 y* A' q4 M3 p, h        // 若该轮没有交换发生，说明数组已经有序，跳出循环
        if (!swaped)
            break;
- v0 \& _: K: p( U    }
3 L( O3 ^% b0 C3 O9 K0 A; K* C  b0 T}
0 Z. N5 P! X9 o# _8 Q! @
6 u+ n5 V& b, h4 R分析：时间复杂度最坏和平均情况是O()，最好的情况是已经有序所以是O(n)，空间复杂度O(1)，且因为两个相同的元素是不会交换位置的，因此是一种稳定的排序。

二、选择排序
6 o% ~' h# N' ?6 O  f6 F. D- ^思路：每一轮都将未排序数组中最小的/最大的选择出来，然后与未排序数组的第一个交换。接着未排序数组的长度就应该减一，然后继续做这个操作，直到未排序数组的长度为1
. }4 b0 q% M1 W" E
void select_sort(vector<int> &nums)
( E% C* R) q2 I, g! J1 p7 j) i$ j; V& v{   
6 V! w$ t$ g( p: v    // 用于存储每一轮中最小的数的下标
, k4 S# ]! m9 ^0 K. R3 r    int min_idx;
    // 循环从第一个数开始到倒数第二个数
    for(int i = 0; i < nums.size() - 1; ++i)
) h" V! r5 J. G  m' e+ S    {
        min_idx = i;
6 S) p+ B2 {% n. O        // 在未排序部分寻找最小的数
        for (int j = i+1; j < nums.size(); ++j)
        {
: _9 W* g/ \4 W; s9 z3 ]            // 这里将 '<' 换成 '>' 就可以从大到小排序
            if (nums[j] < nums[min_idx])
                min_idx = j;
$ @4 h: C! j. g2 I8 x7 \( t        }
        // 将未排序部分最小的数与未排序部分的第一数交换位置
        int tmp = nums[min_idx];
        nums[min_idx] = nums;
& J1 T# o( V& d# j) ^- v5 o" E        nums = tmp;
2 h& r- q( u# e- L1 V+ T    }
4 L  D8 `- C; S- A9 a& i}

分析：时间复杂度最坏、最好和平均情况都是O()，空间复杂度O(1)。因为每次选择最小元素要与未排序部分的第一个元素进行交换，因此可能会出现两个相同元素相对位置发生改变的情况，因此者是一种不稳定的排序。

0 o2 ~7 M5 }; n. N+ Z1 ]三、插入排序
# u- C6 u! |; Q思路：从第二个元素作为当前位置，往前看，判断前面的元素是否大于当前位置，是的话就把前面的元素往后移动一个，依次类推，直到到了数组头或者碰到一个元素比当前元素小则循环终止，此时的位置就应该是当前位置元素的排序合适的位置。接着向后移动，把第三个元素作为当前位置，一直到最后一个元素。

3 I" g4 b1 C6 bvoid insert_sort(vector<int> &nums)
{
    // 从第二个元素到最后一个元素
    for(int i = 1; i < nums.size(); ++i)
    {
        // tmp存下当前元素的值，将i赋给j
) M8 Y9 A1 V2 g        int tmp = nums;
        int j = i;
        // j从当前元素往前找，一直找到第二个元素位置
5 N! S# I' |9 m0 c6 Q* Y        for (; j > 0; j--)
2 k# ^. Q% r! |2 r! I- Q        {
4 B7 `8 o( i: m; D            // 判断tmp是否小于j-1位置的元素，是的话j-1的元素往后移动
* [* W  [  ^1 \2 ?. \+ r  }            // 要从大到小排序，只需要把 '<' 改为 '>' 即可
( Z. h2 J- D, {: s/ C- K5 _            if (tmp < nums[j-1])
                nums[j] = nums[j-1];
            // 否的话，j位置就应该是tmp的最终合适的位置
/ Y7 \. b, A% z5 S  q, G( s6 `            else
                break;
% r& y- R0 C" U: f4 A        }
        // 将tmp赋给j位置的元素
0 h1 i  D" [- @1 g) {' r        nums[j] = tmp;
    }
}

5 r% h" Z& D/ E! Q* x% j; y分析： 时间复杂度最坏和平均情况都是O()，最好的情况是O(n)（最好情况就是已经有序，因此内层循环只需要判断一次就可以break），空间复杂度O(1)。因为是依次往前找的，元素移动也是相邻位置的移动，因此这个方法是稳定的。
' t% R3 s* x8 @- {, A
3 @: F9 r% ?, D- z/ A四、希尔排序
思路：希尔排序是插入排序的一种扩展，它不是一个的找然后插入。而是将与原数组根据间隔分成不同的组，比如十个数{1，2，3，4，5，6，7，8，9，10}可以设置gap为2，这样就分成了{1, 3, 5, 7, 9}和{2, 4, 6, 8, 10}两个组，分的组数就等于gap的数量，每组的包含的元素数量就等于数组的长度除以gap。通过这样操作，再最后gap为1的时候，数组就是基本有序的了，因此这时只需要很少的操作就可以将整个数组变为有序的。希尔排序gap的设置很关键，设置一组好的gap序列往往可以很大程度上提高希尔排序的效率

void shell_sort(vector<int> &nums)
0 w+ ~( e: P2 C3 V! b8 v5 D{
) I9 M& {# D, _    // 初始将gap设置为数组长度的一半，每次gap等于上次gap的一半，一直循环一直到gap等于1
    for(int gap = nums.size()/2; gap > 0; gap/=2)
    {
! v* u. p! ~& i. O* E' r9 {        // 每一组的元素数量
2 Y; E9 M$ g$ C- h: l        int ele_sz = nums.size() / gap;
7 B9 Z, L2 g2 E- w! P5 J7 \  S        // 遍历每一组
        for (int i = 0; i < gap; ++i)
& E5 s% F7 v, t3 F' R- o4 y+ `2 f        {
1 p* l" G8 ?, }$ m9 k            // 对每一个组进行插入排序，下面的代码和插入排序那基本一样
8 a0 [2 x- ]: f. o1 G            for (int j = 1; j < ele_sz; ++j)
7 k$ V1 N: k8 T6 I. w) F/ G            {
                int tmp = nums[j*gap];
3 v' }8 I7 ~0 n& g8 ?  X" Z                int k = j;
                for (; k > 0; --k)
  ]. f: ~% E1 l                {
9 \4 N* F" I1 O1 H5 E                    // 注意这里的下标要符合希尔排序间隔\
/ l0 i9 I! w! X                    // 要从大到小排序，只需要把 '<' 改为 '>' 即可
                    if (tmp < nums[(k-1)*gap])
                        nums[k*gap] = nums[(k-1)*gap];
                    else
4 d; d7 K% W/ Y  d- @                        break;
                }
0 D- s; W; z; Q% x& K/ v5 n/ n                // 找到了最终插入的位置
- Q: R! ?  z- |1 b- r                nums[k*gap] = tmp;
. V9 B6 O0 i, U  @            }
2 s- `! i  q3 V- w: G4 E        }
+ [( Q( `0 a% `) E2 n" k9 x: K4 }        // 因为每次gap等于上次一半，当gap为1的时候就陷入死循环，所以这里设置一个判断用于跳出
1 b7 ^4 X3 R/ z* y# _        if (gap == 1)
- i+ |( h2 q! A2 u& M            break;
8 E0 x1 [+ w. o3 b" V" d. [  t3 G    }
}

7 w$ `: c2 h5 N3 p! C分析：希尔排序最好情况的时间复杂度为O(nlogn)，而最坏情况和平均情况要根据它的增量序列来确定，好的增量序列可以把最坏情况的时间复杂度控制为O()。希尔排序是原地排序因此空间复杂度为O(1)。由于增量序列的存在，使得比较的元素存在间隔，因此就可能导致相同元素的相对位置发生改变，因此希尔排序是不稳定的。

+ U' U; V6 e5 o: r五、归并排序
思路：归并排序是分治法的典型应用之一。首先先把大的数组拆分成两半，再继续拆，直到只剩一个数位置，拆完之后要合并，合并的时候就需要对两边的数进行排序，合并完成的时候就变成了有序的数组。以此类推，对左边的已经有序和右边已经有序的数组进行合并，最终得到了整体有序的数组。
% C, r$ z5 F6 D3 Q
// 合的过程
& u) V- h9 Y$ k1 t7 \vector<int> merge_vec(vector<int> ivec1, vector<int> ivec2)
$ {* o" J2 f- ]! w{
    // 定义结果数组res, i和j分别用于遍历ivec1和ivec2
3 Z" U6 k2 G4 r& X% |& m2 D+ U    vector<int> res;
8 p5 B* s2 d& E" A# }    int i = 0, j = 0;
    // 当两个数组都没遍历到底
( S6 ]( r8 u4 S/ q2 j. {    while(i < ivec1.size() && j < ivec2.size())
    {
2 Q: m& P0 L; |0 c: v        // 谁的当前数字小，谁就加入结果数组，并且下标后移
        // 这里将 '<' 改为 '>' 就可以从大到小排序
. I! P4 T6 a0 T( I/ k4 m        if (ivec1 < ivec2[j])
- A. W' V1 w0 q: d: o  M            res.push_back(ivec1[i++]);
# _, a; H- |  ^/ Z1 ~& o        else
            res.push_back(ivec2[j++]);
) }' k, @# q0 {) U) {: }; F" U8 m8 E* _    }
    // 处理未遍历完的数组，直接全部加入最后面
( U+ T8 @3 Y/ l9 n    while (j < ivec2.size())
        res.push_back(ivec2[j++]);
    while (i < ivec1.size())
/ f' ]8 W- r% e8 m        res.push_back(ivec1[i++]);
    // 返回合并好的数组
( a( n( f: x4 I: K% a    return res;
}
6 ?9 M) @% ~7 x- `
3 @. N3 d( N* b: h  D// 分的过程
& a; s; m" u. B1 N, L% qvector<int> merge_sort(vector<int> nums)
; v% }! }: X' b; o{
0 `0 g* d: s2 Y# l7 R* ^4 b    // 递归结束条件是只剩一个元素，则无序再分，直接返回
5 ]9 C% w/ ~' U% c$ z# s    if (nums.size() == 1)
        return nums;
6 N2 u1 K7 d4 y! z; T
    // 将大数组分治为左边的和右边的
: o4 J. n6 u2 N    vector<int> ivec1 = merge_sort(vector<int> (nums.begin(), nums.begin()+nums.size()/2));
    vector<int> ivec2 = merge_sort(vector<int> (nums.begin()+nums.size()/2, nums.end()));
: B) g% p5 Y+ b; e    // 返回合并后的大数组
) g2 }: f1 N5 M+ Z1 h" g  Y    return merge_vec(ivec1, ivec2);
  u7 ^: C1 U# Q2 g) Q' t8 N}

分析：拆的过程时间复杂度是O(logn)，合的过程时间复杂度是O(n)，因此总的最好、最坏和平均时间复杂度是O(nlogn)。这种排序方法并非是原地排序，所以其空间复杂度是O(n)。这种方法并不会破坏相等元素之间的相对位置因此这是一种稳定的排序算法。
8 B5 u6 q$ W8 w( o# Y+ c* K2 M
六、快速排序
思路：快速排序同样也是利用分治法的思想，但是快速排序可以实现原地排序因此无序额外的空间。快速排序和归并排序的分的过程不同，快速排序分是根据小于和大于某个元素来分成两部分，而归并排序总是以中间的地方来划分。

注意：算法中每一轮quicksort会确定一个元素的最终位置，我们递归处理这个元素左边的剩余数组和右边的剩余数组。lp和rp在走的时候，需要注意的只要rp指向的元素大于等于pivot就一直往左，lp指向的元素小于等于pivot就一直往右，若不加入等于这个判断条件可能就会在中途停下来而陷入死循环。而且pivot的选取也很关键，我们是以pivot大小来划分左右的，常见的方法可以以最左边或者最右边的元素作为pivot（但是这样在已经有序的数组中效率很差），或者随机选择pivot。

1 _( f5 ]5 t8 V( |; Evoid quicksort(vector<int> &nums, vector<int>::iterator lp, vector<int>::iterator rp)
{
# V3 Q$ a& ?7 }% t    // 若左右相等，说明只有一个元素，就不需要排序
    if (rp - lp > 0)
5 F& X9 y) c: z; m    {
7 w. l7 `8 u7 o/ N        // old和orp存取起始位置和结束为止
7 S4 U4 ?- b+ c* O        auto olp = lp, orp = rp;
% o* X- U, o% R9 j  d; Q4 d3 l
% @) i( ^4 ?  [3 w: O7 O, n& [        // 下面两行代码可以要也可以去掉，其作用是随机选定一个范围在lp和rp之间的数作为pivot
        // 将这个数与最左边的数调换位置就可以通过*lp得到这个数
: S0 G& b# F0 f% {" R        int random = rand() % (rp - lp + 1);
        swap(*lp, *(lp + random));

, n) X  C% i7 x5 P! }, r* l7 t        int pivot = *lp;

        // 当lp和rp没遇到的时候
        while (lp != rp)
        {
            // 只要rp指向的元素大于等于pivot而且lp和rp没遇到，rp自减
( C# ], K( I  y            // 将这里的 '>=' 换成 '<=' 并且把下面的 '<=' 换成 '>=' 就是从大到小
/ S1 `; ?6 Z; m4 E9 s2 I8 w            while (*rp >= pivot && lp != rp)
1 Y2 m# X& E- y" y1 t' i                --rp;
1 A+ S+ N, T& l% H1 v4 ?% U& e            // 只要lp指向的元素小于等于pivot而且lp和rp没遇到，lp自增
            while (*lp <= pivot && lp != rp)
                ++lp;
8 r. G5 i4 F- S2 I; H# f            // 停下来的时候交换值
7 Y% v6 P' X  j$ r9 L! n            swap(*lp, *rp);
        }
4 c- K+ V7 o& |  D
: `" Y" }3 e: g- e3 Y        // lp遇到rp说明比pivot小的已经放在左边，比pivot大的已经放在右边了
        // 因为while循环中rp先走，说明rp所指的元素一定是小于pivot或者正好是pivot
# B% _$ D4 M: f3 H# M4 F        // 因此需要交换二者的值，同时pivot就被放在了正确的排序位置上
* O' P9 }  R% @2 \9 y        swap(*olp, *rp);
5 v( x- K* P7 e) x/ n        // 递归处理pivot的左边和右边
6 `3 H! \0 z% V  s0 v& B3 L        quicksort(nums, olp, lp-1);
        quicksort(nums, rp+1, orp);
    }
  m5 h$ G/ c% T}
* c5 e4 |$ h  t' r- {1 C# [& q

void quick_sort(vector<int> &nums)
{
7 u* E0 X$ R2 A$ o# ]9 Y; y    quicksort(nums, nums.begin(), nums.end()-1);
}

# r0 k7 d& ]- E分析：快速排序算法的时间复杂度分是O(logn)，治是O(n)，因此其最好和平均的复杂度是O(nlogn)。考虑一种情况，当数组有序而且我们选取pivot的方法是选最左边的或者最右边的元素时复杂度退化为O()。原地排序因此不需要额外空间，但是由于是递归函数，因此需要栈来保存状态，最好和平均情况下需要O(logn)，最坏的情况下需要O(n)。由于快速排序涉及到随机位置值的交换，因此快速排序是一种不稳定的排序方法。
- w; t6 F, s9 I8 e. I
七、堆排序
思路：堆排序顾名思义需要一个堆，堆是一个完全二叉树，可以分为大顶堆和小顶堆，其中大顶堆是满足子节点的值小于父节点的堆，小顶堆是满足子节点的值大于父节点的堆。建好了堆之后我们就可以通过取堆顶元素再不断调整堆的方法来得到排序结果。因为堆是完全二叉树，因此其父节点和子节点的关系容易得到，所以我们可以用数组来模拟一棵树（一个堆），下面这个视频将堆排序讲的很清晰。

6 [* o& \4 H) u5 \【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆_哔哩哔哩_bilibili
. B& a1 }7 S0 J/ l3 ]! U
建堆：建立堆的方式可以分为从下往上和从上往下。以大顶堆为例，从下往上的话，对于每个父节点，判断其子节点值是否存在大于父节点的情况，是的话就交换这父节点和子节点的值，然后继续调整子节点（若子节点也存在节点的话则继续往下调整）。如果是从上往下建堆，就相当于是堆从从空的开始，不断插入元素再进行调整，判断当前插入的选择值是否大于其父节点的值，若是的话则交换当前节点与父节点，并继续向上调整直到无需调整或者到根节点。可以判断，从下往上的方式其时间复杂度为O(n)，而从上往下调整的方式其时间复杂度为O(nlogn)。同时需要注意的是，对于同一个数组，采用从下往上和从上往下的方式建立可能会导致节点的排列方式不一样，但是都满足大顶堆/小顶堆的性质。

2 x7 [% v- G6 Z6 r: I下面是从下往上建大/小顶堆的代码：

) W+ B" d, _) G2 i& ]: |6 g3 G// 接收参数为数组nums，当前调整节点下标i，当前堆的大小sz
% a8 W* U& H" w' wvoid adjust_from_buttom(vector<int> &nums, int i, int sz)
) X0 t4 e: A6 q9 g; I{
    // lpos和rpos分别代表左孩子和右孩子，largest用来存储左右孩子中较大的那个的下标
9 X8 P2 S, R: t0 n9 h    // 建小顶堆需将largest改为minest，此时这个变量用于存储较小的元素
8 S6 e# [, n+ S0 `( x% W. ^    int lpos = 2*i+1, rpos = 2*i+2, largest = i;
% o# V" S7 c! O6 ^$ G5 b5 M    // 若有左孩子（下标小于sz）而且左孩子数值大于当前节点数值，就记录下左孩子下标
4 A. U3 T  S9 [    // 建小顶堆需将 '>' 改为 '<'
3 l9 J" x' X" G$ g5 Z: Q: q+ `3 T8 W    if (lpos < sz && nums[lpos] > nums)
        largest = lpos;
( }% Z5 p5 p) G2 _- D$ w; k    // 若有右孩子（下标小于sz）而且右孩子数值大于最大的节点值，就记录下右孩子下标
    // 建小顶堆需将 '>' 改为 '<'
    if (rpos < sz && nums[rpos] > nums[largest])
        largest = rpos;
    // 若存在某个孩子的值比当前值大
# a! w# ?' h8 I    if (largest != i)
    {
( A/ E- |! s3 k; V        // 交换当前节点和较大的那个孩子的值
5 y+ t) P7 p$ b/ ^9 X        swap(nums[largest], nums);
        // 交换完之后继续往上调整树
# A* i: Q. \9 h* f1 \* |        adjust_from_buttom(nums, largest, sz);
4 b) [  s, c* P" d3 m    }
}

void build_heap_from_buttom(vector<int> &nums)
3 N3 s" \/ V6 v! w* [# S) s5 U, H{
    // 若数组只有一个元素则无需建立堆
    if (nums.size() != 1)
        // 从最后一个父节点开始循环，一直到根节点
        for (int i = nums.size()/2 -1; i >= 0; --i)
            // 不断对堆进行调整
            adjust(nums, i, nums.size());
}
" J2 J! D" t4 w7 P$ k' r$ l
下面是从上往下建大/小顶堆的代码：

void adjust_from_top(vector<int> &nums, int i, int sz)
{
/ q, n$ m! ~; f0 L# y    // 如果i不等于0
' }* a0 }8 w; X/ u+ Q- K$ B  C  D. Q    if (i)
1 j9 z' N( i% v* \) j    {
: j- |8 Y0 l) r! R5 _: q        // 若i为偶数，其父节点下标为i/2-1。若满足当前节点的值比父节点的值大
9 i7 f' K7 p% p        // 建小顶堆需将 '>' 改为 '<'
        if (!(i%2) && nums > nums[i/2-1])
  d6 i; A2 U9 u0 S2 B$ R- O        {   
            // 交换当前节点与其父节点，再检查父节点需不需要调整
            swap(nums, nums[i/2-1]);
) v) Z9 M' I0 U0 P            adjust_from_top(nums, i/2-1, sz);
2 K3 J2 h$ X* D* c/ b        }
        // 若i为奇数，其父节点下标为i/2，则当前节点比父节点的值大
        // 建小顶堆需将 '>' 改为 '<'
0 `" w3 e* P) _6 u. e1 t        if (i%2 && nums > nums[i/2])
        {
$ `8 S4 \, t1 X$ c) p1 _+ F; Z5 M; r            // 交换当前节点与其父节点，再检查父节点需不需要调整
' J8 ~5 p# @8 H, L' k: B            swap(nums, nums[i/2]);
9 I& B! S1 n6 O            adjust_from_top(nums, i/2, sz);
        }
% }7 y4 \" E+ ^7 R; |5 @& n# H    }
% g( r* a# E: I% ^& t% K8 K" s}
- F# j) e- P. |2 m* ~) X+ Z! Z3 `( M
void build_heap_from_top(vector<int> &nums)
{   // 从第一个元素开始到最后一个元素结束
    for (int i = 0; i < nums.size(); ++i)
0 T. Y8 w2 a1 k        // 插入新的元素并调整
+ k$ c# ]6 z$ \8 D' T! G        adjust_from_top(nums, i, i+1);
}

建立好的堆之后就可以通过取出堆的根节点，再不断调整堆来进行堆排序，我们可以把取出的节点与堆的最后一个节点进行交换，然后把堆的大小减一，这样就可以利用堆原有的空间来存储排序的结果，而无需额外开辟空间来存储。堆排序代码如下：
/ I4 e3 K1 U: T1 [1 @* O4 F9 q. z
! I7 x8 }1 T, z. z. i) M3 v( nvoid heap_sort(vector<int> &nums)
$ O6 y' Q5 E; u* d- ]2 U{
    build_heap_from_buttom(nums); // 或者是build_heap_from_buttom(nums);
    // 从最后一个节点开始往上走
    for(int i = nums.size()-1; i > 0; --i)
  s4 [/ g. f9 O% _/ a9 Z; D    {
/ s" c' m: U- N2 {8 Y: D        // 将最后一个节点与堆的根节点交换
        swap(nums, nums[0]);
9 D/ r  W# Z& E  O        // 调整堆，堆的大小为原大小减一
9 Y& A0 W* [$ h        adjust_from_buttom(nums, 0, i);
    }
}
3 w' ]$ M# l+ Q. S1 P, R我们可以注意到堆排序的过程交换了节点之后，只有根节点发生了改变，因此只有可能是根节点不满足堆的性质，所以在调整的时候我们调用了adjust_from_buttom()方法来堆根节点进行调整。
4 D2 Q: n( r  O. A! r0 N
& q* |( \4 ^( \) [' Q6 S+ ^9 R分析：堆排序的时间复杂度包括建堆和调整，从下往上建堆时间复杂度为O(n)，调整堆的时间复杂度为(logn)，因此堆排序最好、最坏和平均情况的时间复杂度为O(nlogn)。堆排序不需要额外的空间因此其空间复杂度为O(1)，但是由于建堆的过程中可能出现位置调整，因此堆排序是一种不稳定的排序方法。

; z2 ~8 x& G, j! Y八、计数排序
4 [( }& H1 J3 f6 G9 u6 f思路：计数排序主要是针对一定范围内的整数来进行了，先确定序列中的最大值和最小值，从而开辟max-min+1大小的空间，空间的每一个位置代表一个数，若遍历到了某个数就将该空间的计数值自增，那么遍历完原数组。排序结果可以通过遍历这个空间来得到。在实现上C++中可以通过map来实现这个操作，因为map本身是保证有序的。当然因为map内部要进去排序，所以如果要实现极致的空间换时间的话，需要自己手动来实现这样的map。

4 ^+ }" F( B3 [- [4 q+ ]9 X, Vvoid count_sort(vector<int> &nums)
{   
9 y2 k! u" `1 \/ W: H! w/ }% I    // 用于存储数与出现次数的对应关系
6 w$ K2 e1 i6 b2 X( p* E4 F    map<int, int> cnt_map;
; G  ?# D0 Y7 S7 k% w/ i# w    // 遍历数组以将元素及出现次数添加进map
    for (auto i : nums)
7 Y" A  }+ n% G6 U    {
9 K9 G  u' ]4 N4 N0 T+ C        //
5 s5 {/ a/ v! n0 W3 M+ p% f        if (cnt_map.find(i) == cnt_map.end())
            cnt_map = 1;
/ R2 b4 N" ^- f9 P  g6 u        else
            ++cnt_map;
    }
# t  r. R1 _& a6 h. e    // idx代表原数组下标
$ Q% F9 @8 @6 H: p! ]5 k6 L    int idx = 0;
    // 遍历map以将map中的元素放回原数组
    for (auto it = cnt_map.begin(); it != cnt_map.end(); ++it)
4 v) A; d! Y( S$ V& n  u    {
& H4 z0 L; ]+ G        while (it->second != 0)
, n  O0 j" \, Z2 W4 ^! p. L        {
            nums[idx++] = it->first;
            --it->second;
        }
    }
; e1 c' Z- H  Z8 j; b' O}

$ c0 d& \  s) C2 Z# J分析：计数排序最好、最坏和平均情况下的时间复杂度都是O(n+k)，n是表示遍历原数组的时间，k（数据范围）是表示遍历辅助空间的时间，其空间复杂度为O(k)。计数排序可以看做是一种稳定的排序，比如我们把计数排序存储每个元素的位置看成队列，那么就符合先进先出，所以是稳定的。

九、基数排序
/ P/ V2 I; X+ w4 d基数排序通常可以用在整数或字符串上，比如整数上就可以分0-9十个桶，通过比较个位，十位一直到最高位，分别把数装进相应的桶中，再依次取出，比较更高位再装进桶中，再取出，直到所有的数都在0这个桶中说明所有的数都排好序了。
2 E" E* L" \% F! h0 `
但是需要注意的是，一般的基数排序无法处理有负数的情况。针对负数，一般有两种解决方法：

* h1 e- v- A6 `5 k4 f8 N7 A1、另外开辟10个桶用来存储负数的情况（需要占用更多的空间）

9 D; j9 J5 F1 O( m. H0 ^  O8 n" _2、将所有元素变为正数再处理（可以将所有元素都加上最小负数的绝对值，但存在溢出风险），下面代码实现这种方式
7 P/ l7 h2 M+ M% Z* w
! E/ ?$ [& g; X* M, s$ {5 Nvoid radix_sort(vector<int> &nums)
$ @. J" Q* ?3 G) N% a{
" {5 P# W. z4 A5 M# Q4 g$ N9 w* B' x& ^    // 开辟二维数组，第一维10代表十个桶，第二维当前为空
    vector<vector<int>> ivec(10, vector<int>(0));
) q% g- V5 H  |    // 用于取出最小元素，将所有元素都变为正数
; |0 O" _5 ?. c( z* ~    int min_num = *min_element(nums.begin(), nums.end());
1 q; r- c; N. ^5 I    if (min_num < 0)
        for (auto &i : nums)
! }4 Y* I5 A+ @) M7 H  C7 T8 ?' d( I            i -= min_num;
3 I4 {5 A. S- q7 r, x( x' U    // 用来控制比较的位数，初始为1代表比较个位数
    int digit = 1;
; R8 `; b$ Q- C# J    // 循环一直进行
    while (true)
    {
        // 对nums中所有元素遍历，将每个元素放入对应桶中
        for(auto i : nums)
            ivec[i%(digit*10)/digit].push_back(i);
8 [, g5 B/ W- }& o  _7 Z5 N2 i& A4 K
        // 这是循环终止条件，即所有元素都在0号桶中
        if (ivec[0].size() == nums.size())
            break;
        // 记录nums中的下标用于放回nums中
3 Q' B* t4 X1 {6 i9 O8 X) s- v        int idx = 0;
, d: |6 h3 [! x2 T" M8 }) T! U: S6 i        // 依次从每个桶中拿出元素放回nums，取完之后清空桶
8 }; m- B# U0 d$ m  }6 Y        for (int i = 0; i < 10; ++i)
        {
: k5 L. B! ]; C, U            for(int j = 0; j < ivec.size(); ++j)
3 U" p, v* ]$ _  S& j0 K                nums[idx++] = ivec[j];
            ivec.clear();
7 o8 Z% }; ?0 f: D7 x        }
0 f0 J1 f8 V# i+ y! M        // 下一次循环比较更高位
        digit *= 10;
% v) ~/ o5 P" O" B, K% N: ?' _    }
" n6 t' I9 ^0 L! E    // 排序完毕后将元素恢复为初始值
1 O+ w/ f# P: w; E    if (min_num < 0)
        for (auto &i : nums)
            i += min_num;
}
1 ^- r& S+ g, o9 S4 w, r
分析：基数排序的时间复杂度取决于待排序的元素中的最大位数k，如最大元素为1023，那么最大位数k=4。对于每一位我们需要遍历两遍数组，但是这里的两遍可以省略，因此最好、最坏和平均的时间复杂度都是O(k*n)。由于我们需要开辟一个额外的空间来把每个数放入桶中，因此空间复杂度为O(n)。又因为我们放入桶和从桶中拿出的操作都保证了先进先出，因此基数排序是一种稳定的排序方法。
0 N* b' v! I( Z2 e- T
( Y) Y* f  E& \十、桶排序
! j% L  v% I' ~# S% y+ I8 R前面计数排序和基数排序都是桶排序的一种特例。桶排序是这样一种排序，它将原来的数组分到不同的桶里，再分别对每个桶内部采用排序算法进行排序（可以用快排、可以用选择、冒泡等都没问题），最后将每个桶里的元素依次取出就得到了排好序的结果。因此桶排序如何分桶是一个关键的问题，如果分的好的话，每个桶都能均匀地承载一部分数据，最后时间复杂度就会比较理想。若果分的不好，很多数据都集中在一个桶里，那么最后的时间复杂度就很差（最差情况下会略大于桶内排序算法的效率），此外桶排序还需要额外的空间。

( x# {( K. Y9 l3 ^6 H9 I0 }" qvoid bucket_sort(vector<int> &nums, int bucket_cnt)
1 S: z. I9 I+ Y( x! }- A{
3 a, X* Z: L4 D1 s' ~8 M* ?9 e    // 建立bucket_cnt个桶，每个桶初始为空
4 G: S' E- m! m) T    vector<vector<int>> ivec(bucket_cnt, vector<int>(0));
    // 拿出数组中最大和最小的元素来确定每个桶之间的间隔
    int min_ele = *min_element(nums.begin(), nums.end());
# ^5 ~* h+ l9 S  L4 _8 G    int max_ele = *max_element(nums.begin(), nums.end());
) W5 G6 J" z  X5 O* ~; q    int gap = (max_ele - min_ele) / bucket_cnt;
4 _7 n' A9 s5 [. Z' G, E    // 如果间隔比桶个数都小，那么直接排序可能更快
    if (gap > bucket_cnt)
    {
        // 遍历数组中每个元素
        for (auto i : nums)
        {
            // 确定元素所在的桶序号
            int bucket_num = (i-min_ele)/gap;
            // 若算出的序号等于桶个数，那么说明越界了（比如数组中最大元素就会出现这样的情况）
            if (bucket_num == bucket_cnt)
2 S  t' x  p4 k* w  j; r                --bucket_num;
            // 将该元素装入桶中
- f6 ?& Y! |2 |( L6 ~" ~& q$ U            ivec[bucket_num].push_back(i);
        }
        // idx记录原数组nums中的下标用于装回元素
2 O$ v) p) X" b        int idx = 0;
        // 对每个桶先排序再往nums中装入元素，最后清空桶
        for (auto &vec : ivec)
: N5 C# M& z$ i        {
( \5 T+ T. `( b  Z4 C6 ]! c% G* t            quick_sort(vec);
            for (const auto ele : vec)
                nums[idx++] = ele;
9 D5 o+ P4 C  C' [3 u/ y, o            vec.clear();
& C% \; @$ n  S' E( s  Z9 j        }
  `9 E5 N& M# D2 Y# o7 C    }
3 b9 S0 o  ^4 ~7 j    // 直接排序
    else
: Q+ [4 Z# K* s* U6 e        quick_sort(nums);
}

分析：桶排序将原数组分为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个桶系统会默认分配内存。桶排序是否稳定依赖于其内部的排序算法，若内部使用快排则不稳定，若内部使用归并则是稳定的。
. w4 G" W1 w0 \) I1 S+ [* I————————————————
4 @, ?# @+ Z% D9 J. L# p' ~4 v版权声明：本文为CSDN博主「Xaiver_97」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* J( h# @( ~! r# |! P6 W原文链接：https://blog.csdn.net/Xavier_97/article/details/126722423
  m) r6 y& G+ I- C$ L0 E
1 W: X+ c6 q9 {( c$ c

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5