lurenaa的博客

🐶冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * <冒泡排序>
 * 时间复杂度: 最好O(n) 最坏O(n^2) 平均O(n^2) 稳定
 * 空间复杂度: O(1)
  (5)   2   3   4   2   1   0
   2   (5)   3   4   2   1   0
   2   3   (5)   4   2   1   0
   2   3   4   (5)   2   1   0
   2   2   3   4   (5)   1   0
   1   2   2   3   4   (5)   0
   0   1   2   2   3   4   (5)
  */
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for(int i = 0; i < nums.size(); ++i) 
            for(int j = i + 1; j < nums.size(); ++j) {
                if(nums[i] > nums[j])
                    swap(nums[i], nums[j]);
            }
        return nums;
    }
};

🙈选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * <选择排序>
 * 时间复杂度: 最好O(n^2) 最坏O(n^2) 平均O(n^2) 稳定
 * 空间复杂度: O(1)
 */
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for(int i = 0; i < nums.size(); ++i) {
            int _min = i;
            for(int j = i + 1; j < nums.size(); ++j) 
                if(nums[j] < nums[_min]) _min = j;
            swap(nums[_min], nums[i]);
        }
        return nums;
    }
};

👺插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * <插入排序>
 * 时间复杂度: 最好O(n) 最坏O(n^2) 平均O(n^2) 稳定
 * 空间复杂度: O(1)
 */
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for(int i = 1; i < nums.size(); ++i)
            for(int j = i; j > 0 && nums[j] < nums[j-1]; --j) 
                swap(nums[j-1], nums[j]);
        return nums;
    }
};

🎃希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * <希尔排序> / <缩小增量排序>
 * 时间复杂度: 平均O(n^1.3) 不稳定
 * 空间复杂度: O(1)
 * 特点: 缩小增量的插入排序
 */
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int h = 1;
        while(h < nums.size() / 3) h = h * 3 + 1;
        while(h >= 1) {
            for(int i = h; i < nums.size(); i+= h)  {
                for(int j = i; j >= h && nums[j] < nums[j - h]; j -= h) 
                    swap(nums[j], nums[j - h]);
            }
            h = h / 3;
        }
        return nums;
    }
};

👩‍🚒归并排序

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * <归并排序>
 * 时间复杂度: 最好O(n*log(n)) 最坏O(n*log(n)) 平均O(n*log(n)) 稳定
 * 空间复杂度: O(n)
 */
class Solution {
public:
    vector<int> aux;
    vector<int> sortArray(vector<int>& nums) {
        aux.resize(nums.size());
        _sortArray(nums, 0, nums.size() - 1);
        return nums;
    }
    void _sortArray(vector<int>& nums, int lo, int hi) {
        if(hi <= lo)
            return ;
        int mid = lo + (hi - lo) / 2;
        _sortArray(nums,lo ,mid);
        _sortArray(nums, mid + 1, hi);
        merge(nums, lo, mid, hi);
    }
    void merge(vector<int>& nums, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        for(int k = lo; k <= hi; ++k) 
            aux[k] = nums[k];
        for(int k = lo; k <= hi; ++k) {
            if(i > mid) nums[k] = aux[j++];
            else if (j > hi) nums[k] = aux[i++];
            else if (aux[i] < aux[j]) nums[k] = aux[i++];
            else nums[k] = aux[j++]; 
        }
    }
};

//自底向上
class Solution {
public:
    vector<int> aux;
    vector<int> sortArray(vector<int>& nums) {
        aux.resize(nums.size());
        for(int sz = 1; sz < nums.size(); sz = 2 * sz)
            for(int lo = 0; lo < nums.size(); lo += sz + sz) 
                merge(nums, lo, lo + sz - 1, min(lo + sz + sz - 1, (int)nums.size() - 1));
        return nums;
    }
    void merge(vector<int>& nums, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        for(int k = lo; k <= hi; ++k) 
            aux[k] = nums[k];
        for(int k = lo; k <= hi; ++k) {
            if(i > mid) nums[k] = aux[j++];
            else if (j > hi) nums[k] = aux[i++];
            else if (aux[i] < aux[j]) nums[k] = aux[i++];
            else nums[k] = aux[j++]; 
        }
    }
};

🧑‍快速排序

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
/**
 * <快速排序>
 * 时间复杂度: 最好O(n*log(n)) 最坏O(n^2) 平均O(n*log(n)) 不稳定
 * 空间复杂度: O(log(n))
 * 特点: 本质是给基准数找其正确位置的过程.
 */
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        sort(nums, 0, nums.size() - 1);
        return nums;
    }
    void sort(vector<int>& nums, int lo, int hi) {
        if(lo >= hi)
            return ;
        int k = parti(nums, lo, hi);
        sort(nums, lo, k - 1);
        sort(nums, k + 1, hi);
    }
    int parti(vector<int>& nums, int lo, int hi) {
        int lf = lo, rt = hi + 1;
        int v = nums[lo];
        while(true) {
            while(nums[++lf] <= v) if(lf == hi) break;
            while(nums[--rt] >= v) if(rt == lo) break;
            if(lf >= rt)
                break;
            swap(nums[lf], nums[rt]);
        }
        swap(nums[lo], nums[rt]);
        return rt;
    }
};

🐸堆排序

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
/**
 * <堆排序>
 * 时间复杂度: 最好O(n*log(n)) 最坏O(n*log(n)) 平均O(n*log(n)) 不稳定
 * 空间复杂度: O(1)
 */
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int N = nums.size();
        nums.insert(nums.begin(), 0);
        // for(int i = N / 2; i >= 1; --i)
        //     sink(nums, i, N);
        for(int i = 1; i <= N; ++i) 
            swim(nums, i ,N);
        while(N > 1) {
            swap(nums[1], nums[N--]);
            sink(nums, 1, N);
        }
        nums.erase(nums.begin());
        return nums;
    }
    void sink(vector<int>& nums, int i, int N) {
        while(i <= N / 2) {
            int k = i * 2;
            if(k + 1 <= N && nums[k] < nums[k + 1]) k = k + 1;
            if(nums[i] >= nums[k]) break;
            swap(nums[k], nums[i]);
            i = k;
        }
    }
    void swim(vector<int>& nums, int i, int N) {
        while(i > 1 && nums[i] >= nums[i / 2]) {
            swap(nums[i], nums[i / 2]);
            i /= 2;
        }
    }
};

 上一页

算法