SortAlgorithms/quick_sort.cpp at master · zzzhpzhp/SortAlgorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include "quick_sort.h"

namespace algorithm_ns
{
    void QuickSort::sort()
    {
        _sort(0, (int)nums_.size()-1);
    }

    void QuickSort::_sort(int l, int h)
    {
        if (l >= h)
        {
            return;
        }
        else
        {
            int pivot_idx = l;
            auto pivot = nums_[l];

            for (int i = l+1; i <= h; i++)
            {
                if (nums_[i] < pivot)
                {
                    if (i - pivot_idx == 1)
                    {
                        std::swap(nums_[i], nums_[pivot_idx]);
                        pivot_idx = i;
                    }
                    else
                    {
                        std::swap(nums_[i], nums_[pivot_idx+1]);
                        std::swap(nums_[pivot_idx], nums_[pivot_idx+1]);
                        pivot_idx = pivot_idx+1;
                    }
                }
            }

            _sort(l, pivot_idx);
            _sort(pivot_idx+1, h);
        }
    }
}