0x01 介绍

C++类中有两种方式可以用来初始化成员变量,一种最常见的是在构造函数内部直接对成员函数赋值:

class CTest{
    int m_a, m_b;
    CTest(int a, int b){
        m_a = a;
        m_b = b;
    }
}

另外一种方式就是通过构造函数的初始值列表来完成初始化:

class CTest{
    int m_a, m_b;
    CTest(int a, int b) : m_a(a), m_b(b){}
}

这种在构造函数后加一个冒号然后初始化的方式叫做构造函数初始值列表,它更优于第一种初始化方式。

0x02 初始值列表的必要性

在以下情况下,必需使用初始值列表方式来初始化:

  • 类成员包含const对象时。
  • 在类A没有提供默认构造函数且被类B包含或者继承时,类B必需使用默认初始化方式初始化A。

对于第一个条件比较好理解,因为const本身在初始化后是无法再赋值的,所以必须使用初始化列表来对其初始化。

对于第二种情况,因为根据构造函数的执行顺序,在构造类B时必须先构造类A的构造函数,但类A并没有提供默认的构造函数,此时导致编译器找不到合适的构造函数,所以对象构造失败。因此这里必须在初始值列表中初始化。

#pragma once
#include <iostream>
class CAnimal
{
public:
    CAnimal(int weight) :m_weight(weight) {
    }
    int m_weight;
};

class CDog {
public:
    CAnimal m_a;
    const int m_b;
    CDog(int a, int b) : m_b(b), m_a(a){
    }
};

0x02 初始值列表的效率

使用普通方式初始化时编译器会先执行一次对象的默认构造函数,然后才会对其赋值,初始化时执行了两个步骤。

#include <iostream>
class CAnimal
{
public:
    CAnimal() { std::cout << "default" << std::endl; }  // 添加默认初始化函数
    CAnimal(int weight) :m_weight(weight) {
    }
    int m_weight;
};

class CDog : public CAnimal {
public:
    CDog(int weight) {
        m_weight = weight;
    }
    // 初始值列表,和上面的构造函数不可共存
    CDog(int weight): CAnimal(weight) {
    }
};

执行CDog构造函数时会先执行CAnimal的默认构造函数,输出defualt 然后后才会执行m_weight = weight。但是对于初始值列表方式来说并不会执行两步,直接通过相应的构造函数初始化就完成了,相对来说简化了一个过程,效率肯定也会高一些。

0x03 初始化顺序

使用初始值列表初始化时,初始化的顺序是根据成员变量定义的顺序来的,并不是初始值列表的顺序。

class CAnimal
{
public:
    CAnimal(int weight) :m_weight(weight) {
        std::cout << weight << std::endl;
    }
    int m_weight;
};

class CDog {
public:
    CAnimal m_a, m_b;
    CDog(int a, int b) : m_b(b), m_a(a){
    }
};

实例一个对象CDog d(1, 2) ,结果会输出:

1
2

并不是根据初始值列表先用2初始化m_b,可见初始顺序是根据定义顺序来的。

一、原理

原理很简单, 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从从Z到A)错误就把他们交换过来。 冒泡排序是一种稳定的排序算法。

冒泡排序不管在什么情况下,时间复杂度都是O($n^2$)。

对比插入排序来说,在平均的情况下,插入排序性能是冒泡排序的两倍。

图例:

以数组[54, 15, 34, 82, 15, 46, 85, 43]为例:

bubble_sort_1

第一次循环先比较54和15,54大于15,交换两个元素:

bubble_sort_2

比较54和34,54大于34,交换两个元素:

bubble_sort_3

比较54和82,54不大于82,不交换:

bubble_sort_4

比较82和15,82大于15,交换两个元素:

bubble_sort_5

按照相同的方式一直对比,直到最后,85被移动到最后:

bubble_sort_6

此时完成一轮冒泡排序,接下来将剩下的元素再次执行同样的操作即可完成对整个数组的遍历。

二、代码实现

2.1 C++实现

template<typename T>
void bubble_sort(vector<T> &data) {
    int i, j;

    // i的作用是控制遍历次数,n个元素的数组一共要执行n-1轮冒泡
    for (i = 0; i < data.size() - 1; i++) {
        // j从第二个元素开始,每次和前面的元素对比
        for (j = 1; j < data.size() - i; j++) {
            if (data[j] < data[j - 1]) {
                // 如果当前元素小于前一个元素,交换两个元素
                swap(data[j - 1], data[j]);
            }
        }
    }
}

2.2 python实现

def bubble_sort(data):
    size = len(data)
    for i in range(0, size - 1):
        for j in range(size - 1, i, -1):
            if data[j] < data[j - 1]:
                data[j - 1], data[j] = data[j], data[j - 1]

三、冒泡排序的优化

当对第x个数据排序时,冒泡排序每次都会遍历剩下的n-x个元素,即使整个序列已经有序。

因此可以在这一个层面进行优化,如果序列已经有序了,则后面的排序就无需进行了,可以添加一个标记字段来处理这个问题。

template<typename T>
void bubble_sort(vector<T> &data) {
    int i, j;
    bool again = true;
    
    for (i = 0; again && i < data.size() - 1; i++) {
        // 每开始新一轮冒泡,把标记置为false。
        again = false;
        for (j = 1; j < data.size() - i; j++) {
            if (data[j] < data[j - 1]) {
                swap(data[j - 1], data[j]);
                // 只有出现了逆序,才把标记置为true
                again = true;
            }
        }
    }
}

一、原理

选择排序的原理是分治,把排序序列切分成若干个小组后分别排序。每次排序都以随机的一个元素作为哨兵(一般都以排序区间的中间元素或者首元素作为哨兵),比他大的元素都放到右边,比它小的都放到左边。然后分别对该元素左边和右边的元素再法排序,直到所有的元素都是有序状态。

具体的排序过程描述为:

  1. 选取一个哨兵元素temp,设置两个指针low和high分别从数组的两端开始遍历。
  2. high指针从右到左遍历,当遇到A[high] < temp的时候,设置A[low]的值为A[high]。
  3. low指针从左到右遍历,当遇到A[low] > temp的时候,设置A[high]的值为A[low]。
  4. 重复执行2、3步,直到low和high相遇,设置low元素的值为temp。此时low左边的元素都小于temp,low右边的元素都大于temp。再分别对左右子区间的元素分别排序。

图例:

以数组[54, 15, 34, 82, 15, 46, 85, 43]为例,初始状态时设置low指针指向第一个元素,high指针指向最后一个元素,temp为第一个元素的值54:

quick_sort_1

遍历high指针,从右到左找到第一个小于54的元素43,赋值给low:

quick_sort_2

遍历low指针,从左到右找到第一个大于54的元素82,赋值给high:

quick_sort_3

遍历high指针,从右到左找到一个小于54的元素46,赋值给low:

quick_sort_4

遍历low指针,继续寻找第一个大于54的元素。但是直到遇见high指针,都没有找到再比54大的元素,把temp值赋值给low:

quick_sort_5

此时第一轮排序完成,54左边的元素都比它小,右边的元素都比它大。因此按照这个操作,继续对左边和右边的区间再执行相同的操作,多次排序即可完成整个数组的排序。

复杂度分析:

最坏的情况下,数组无序,快速排序和冒泡排序差不多。
  • 时间复杂度:最坏情况下,时间复杂度为O($n^2$);最好的情况和平均情况下算法复杂度为O($n\log(n)$)​。
  • 空间复杂度:最坏情况下,空间复杂度为O($n$);平均情况下空间复杂度为O($\log(n)$)。

二、代码实现

快排的写法多样,以下实现了C++和Python两种语言的快速排序算法实现。

其中C++选取的哨兵是数组第一个元素,python选取的哨兵是数组中间元素。

2.1 C++实现

以区间中点作为排序标杆:

/*
 * 快速排序算法实现,对[left, right)部分的数组排序。
 * @data 待排序数组
 * @left 左区间,包含该下标元素
 * @right 右区间,不包含该下标元素
 */
template<typename T>
void quick_sort(vector<T> &data, int left, int right) {
    int i = left, j = right - 1;
    T temp;

    if (right <= left) {
        return;
    }

    temp = data[i];

    while (i < j) {
        // 从右到左遍历找到一个比temp大的
        while (i < j && data[j] >= temp) {
            j--;
        }
        if (i < j && data[j] < temp) {
            data[i] = data[j];
        }

        // 从左到右遍历找到一个比temp小的
        while (i < j && data[i] <= temp) {
            i++;
        }
        if (i < j && data[i] > temp) {
            data[j] = data[i];
        }
    }

    data[i] = temp;

    // 排序的区间是左闭右开
    quick_sort(data, left, i);
    quick_sort(data, i + 1, right);
}

2.2 python

以区间中点元素作为标杆:

import math


def quick_sort(data, left, right):
    """
    快速排序算法,对[left, right)区间的元素排序
    :param data: 待排序数组
    :param left: 待排序数组的左区间,包含对对该下标元素排序
    :param right: 待排序数组的右区间,不包含对该下标元素排序
    :return:
    """
    i, j = left, right - 1

    if i >= j:
        return

    # 选择区间中点元素作为哨兵
    mid = math.floor((i + j) / 2)
    temp = data[mid]
    data[i], data[mid] = data[mid], data[i]

    while i < j:
        while i < j and data[j] >= temp:
            j -= 1
        if i < j and data[j] < temp:
            data[i] = data[j]

        while i < j and data[i] <= temp:
            i += 1
        if i < j and data[i] > temp:
            data[j] = data[i]

    data[i] = temp

    quick_sort(data, left, i)
    quick_sort(data, i + 1, right)

2.3 golang实现快速排序

2020-02-29刷leetcode添加,使用数组中间元素作为哨兵。排序边界是[left, right]
/*
 * 快速排序,对[left, right]区间内的元素排序
 * @nums 排序数组
 * @left 左边界
 * @right 右边界,包含该下标元素
 */
func doQuickSort(nums []int, left, right int) {
    i, j := left, right
    if left >= right {
        return
    }

    // 取中间元素作为哨兵
    mid := (i + j) / 2
    x := nums[mid]
    nums[mid], nums[i] = nums[i], nums[mid]

    for i < j {
        for nums[j] >= x && i < j {
            j -= 1
        }
        if i < j && nums[j] < x {
            nums[i] = nums[j]
        }
        for nums[i] <= x && i < j {
            i += 1
        }
        if i < j && nums[i] > x {
            nums[j] = nums[i]
        }
    }
    nums[i] = x
    doQuickSort(nums, left, i-1)
    doQuickSort(nums, i+1, right)
}

func quickSort(nums []int) []int {
    doQuickSort(nums, 0, len(nums)-1)
    return nums
}

一、原理

选择排序(Selection sort)是一种简单直观的排序算法,它的工作原理是:从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

选择排序无论在最坏或是最好的情况,时间复杂度都是O($n^2$)

排序逻辑:

for i in (i, n-1)
    min = data[i]
    for j in (j, n)
        如果min>data[j],标记当前位置,重新设置min,继续循环
    把最小的元素min和data[i]替换

图解

以序列[3, 1, 5, 4, 7]为例,执行第一趟排序时,找到的最小元素是1,把它放到最前面和3对换:

第二趟排序,未排序数组为[3, 5, 4, 7],此时数组内最小的元素是3,刚好就是当前数组最开头的位置,因此无需替换,继续下一趟排序。

第三趟排序,未排序数组为[5, 4, 7],此时数组内最小的元素是4,放到最前面和5对换:

执行完第三趟排序后,数组就已经有序了。但是对计算机而言却并不知情,它还会继续判断后面的[5, 7],但是刚好每次排序的时候,他们就处于应该在的位置。

二、代码实现

2.1 C++实现

template <typename T>
void select_sort(vector<T> &v) {
    size_t i, j;
    // 记录最小的下标
    T min_idx;

    if (v.size() < 2)
        return;

    // 只用执行n-1趟排序
    for (i = 0; i < v.size() - 1; i++) {
        min_idx = i;

        // 找到最小的下标
        for (j = i + 1; j < v.size(); j++) {
            if (v[j] < v[min_idx])
                min_idx = j;
        }

        // 替换最小的
        if (min_idx != i) {
            my_swap(v[i], v[min_idx]);
        }
    }
}

2.2 python实现

def select_sort(data):
    size = len(data)
    for i in range(size - 1):
        k = i
        for j in range(i + 1, size):
            if data[j] < data[k]:
                k = j
        if k != i:
            data[k], data[i] = data[i], data[k]

2.3 c语言实现

int select_sort(int* data, unsigned int len) {
    unsigned int i, j, min;

    for (i = 0; i < len - 2; i++) {
        min = i;
        for (j = i + 1; j < len - 2; j++) {
            if (data[j] < data[i])
                min = j;
        }
        if (min != i)
            swap(data[min], data[i]);
    }
}

一、原理

从排序序列的第二个元素开始,依次往前面查询,直到找到一个合适的位置就把它插进去。

每个元素在交换完成之后[0, n]都是一个有序序列,它的时间复杂度为O(n^2)

最好的情况下,序列有序,时间复杂度为O(n)。

最坏的情况下,序列逆序,时间复杂度为O(n^2)。随机的情况下平均时间复杂度接近于最坏的情况。

排序逻辑:

for i in (1, n-1)
    使用data[i]前向查找,找到一个合适的位置插入

- 阅读剩余部分 -

很久没有用C++,今天用C++写链表,结果因为一个小问题卡了好半天。

浪费了大半天才找到问题的原因,这里记录一下,生疏了。。。

创建一个类CTest ,代码如下:

#pragma once
class CTest
{
public:
    CTest() { i = 10; };
    ~CTest() { i = 0; };
    int i;
};

主函数中创建一个CTest 指针并打印i 值:

#include <iostream>
#include "Test.h"

int main() {
    CTest *t = &CTest();
    std::cout << t->i << std::endl;
    return 0;
}

最后的结果是0 不是10 ,断点调试发现t 的地址和CTest() 构造的时候一致:

// CTest.h
CTest() {
    i = 10;
    std::cout << (void*)this << " " << i <<  std::endl;
};

// main.cpp
CTest *t = &CTest();
cout << (void*)t << endl;

打印结果:

00FBFA8C 10
00FBFA8C
0

t.i 在构造的时候确实赋值了,并且t 的地址在返回前后没有变,这也说明构造t 在初始化时并没是拷贝之后再返回的。那为什么t.i 在初始化之后变成了0 ???

1. 错误原因

研究一番发现,使用CTest *t = &CTest() 形式创建的变量,虽然没有拷贝到其他副本再返回,但在返回赋值到t 前会执行一次析构,这就导致了t.i 又重新被赋值成了0 。这里可以修改修改~CTest() 方法验证这个观点:

~CTest() { 
    std::cout << "~CTest()" << std::endl;
    i = 0;
};

运行结果:

004FFCDC
~CTest()
004FFCDC
0

可见析构确实是被运行了,所以结果也确实应该是0!

2. 改进方法

创建指针时,使用new 创建而不要用上面的方式创建,使用new 创建不会出现上面的问题。

3. 吐槽

go 写久了,c 都忘得差不多了,都忘了还有new 这个东西了。。。

本安装教程及程序来源于网络,软件下载地址:密码:t5oz

目前最高支持vs2017,安装后可以在vs内部更新。

安装步骤:

  • 删除原有VA_X并重新安装软件包中携带的安装程序
  • 复制Crack目录下的破解补丁到相应的目录下覆盖即可

各版本破解补丁目录:

  • 2008:安装目录,默认位于c:\Program Files (x86)\Visual Assist X\
  • 2010:%USERPROFILE%\AppData\Local\Microsoft\VisualStudio\10.0\Extensions\Whole Tomato Software\Visual Assist\__version__\
  • 2011-2012:%USERPROFILE%\AppData\Local\Microsoft\VisualStudio\11.0\Extensions\__random_dir__\
  • 2013:%USERPROFILE%\AppData\Local\Microsoft\VisualStudio\12.0\Extensions\__second_random_dir__\
  • 2015:%USERPROFILE%\AppData\Local\Microsoft\VisualStudio\14.0\Extensions\__random_dir__\
  • 2017:%USERPROFILE%\AppData\Local\Microsoft\VisualStudio\15.0\Extensions\__random_dir__\

__random_dir____second_random_dir__是随机的文件夹,形如v3tpxirz.5pr