插入排序

//插入排序，平均情况O(n^2),最好O(n)，最坏O(n^2),，空间复杂度O(1)，稳定

/*
插入排序思想
a[5] = {2,1,3,4,5}
外层循环：a[0]不用管，默认有序，从a[1]开始往后循环
内层循环：将需要移动的元素a[1]存入临时变量
        遍历a[1]前面的元素，与当前a[1]进行比较，若遍历的当前元素大于a[1]，元素后移a[j] = a[j - 1]
        直到数据元素小于等于临时变量
        移动完后，将当前位置赋值为临时变量
*/
#include <iostream>
using namespace std;

//频繁交换
void insertSortBad(int *a, int n){
    int i, j;
    for (i = 1; i < n; ++i){
        for (j = i; a[j - 1] > a[j] && j > 0; --j){
            swap(a[j - 1], a[j]);
        }
    }
}
//将频繁交换转换为赋值
void insertSort(int *a, int n){
    //临时变量,存放需要移动的元素
    int temp = 0;
    int i, j;
    for (i = 1; i < n; ++i){
            temp = a[i];
            for (j = i; a[j - 1] > temp && j > 0; --j){
                a[j] = a[j - 1];
            }
        a[j] = temp;
    }
}

int main(){
    int a[7] = { 2, 1, 3, 4, 5, 9, 8 };
    insertSortBad(a, 7);
    for (int i = 0; i < 7; ++i)
        cout << a[i] << endl;

    system("pause");
    return 0;
}

二分查找

/**************************************************************************
**  二分查找法
**  在有序数组中查找target，查找到返回index，否则返回-1
*************************************************************************/
#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int target){

    //在[l,r]中查找target
    //包含右边界
    int l = 0, r = n - 1;
    int res;
    while (l <= r){
        //int mid = (l + r) / 2;
        //防止溢出
        int mid = l + (r - l) / 2;
        if (arr[mid] == target){
            res = mid;
            break;
        }
        //在[l,mid-1]中查找target
        else if (arr[mid] > target)
            r = mid - 1;
        //在[mid+1,r]中查找target
        else
            l = mid + 1;
    }
    return res;
}


int main(){
    int a[6] = { 0, 1, 2, 3, 4, 5 };
    int res = binarySearch(a, 6, 4);
    cout << res << endl;
    system("pause");
    return 0;
}

快速排序

//快速排序思想：
//选出一个哨兵，通过一趟排序将待排序列分割成两部分
//其中一部分小于哨兵值，另外一部分大于哨兵值
//然后再对两部分分别进行上述操作，直到排序完成


//解释时间复杂度为nlogn
//分治算法，每次选出哨兵，将待排序列分成两部分，一直分下去，直到只有一个元素，平均分开，相当于n个结点的二叉树，共有logn层，递归深度为logn
//每一层都需要对当前分组的元素排序，问题规模大概为n，第一层遍历n个元素，第二层遍历n-1个...直到最后一层为一个
//nlogn

//解释空间复杂度O(logn)~O(n)
//主要是递归造成的栈空间的使用
//最好情况递归树深度为logn，最坏情况为n

//快排的最差情况什么时候发生？
//1. 已排序
//2. 数值全部相等（1的特殊情况）
//在上面的情况下选择的标定元素一直为第一个，则时间复杂度变为O(n^2)

//快速排序，平均情况O(nlogn),最好O(nlogn)，最坏O(n^2)（选择标定元素有关），空间复杂度O(logn)~O(n)，不稳定

/**************************************************************************
**  要取得[a,b)的随机整数，使用(rand() % (b-a))+ a;
**  要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a;
**  要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1;
**  通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。
**  要取得a到b之间的随机整数，另一种表示：a + (int)b * rand() / (RAND_MAX + 1)。
**  要取得0～1之间的浮点数，可以使用rand() / double(RAND_MAX)。
*************************************************************************/


#include <iostream>
using namespace std;

//双路快排，尽量写这种
//begin,begin+1...i...j...end
int partition2(int *data, int start, int end){
    //产生start和end之间的随机数
    int index = (rand() % (end - start + 1)) + start;

    //将选中的数字交换到start位置
    swap(data[index], data[start]);

    int pivot = data[start];

    //选择的pivot为start位置
    //data[start+1, i) <= pivot   i-1 为小于v的最后一个元素，i为当前左边访问的元素
    //data(j, end] >= pivot  j+1 为大于v的第一个元素，j为当前右边访问的元素
    int i = start + 1, j = end;
    while (true){
        while (i <= end && data[i] <= pivot)
            i++;
        while (j >= start + 1 && data[j] >= pivot)
            j--;
        if (i > j)
            break;
        swap(data[i], data[j]);

        //下面这两行，swap交换之后，双方需要移动，否则会增加一次无用的比较
        i++;
        j--;
    }
    //最后j停止在<= v的最后一个位置， i停止在>=pivot的第一个位置，pivot与j进行交换
    swap(data[start], data[j]);
    return j;
}

void swapOffer(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

//单路随机快排
//begin,begin+1...small,small+1...end
int partition(int *data, int start, int end){
    //产生start和end之间的随机数
    int index = (rand() % (end - start + 1)) + start;

    //将选中的数字交换到start位置
    swap(data[index], data[start]);

    //选择的pivot为start位置
    int pivot = data[start];

    //我们要达到这样的效果
    //data[start+1, small] < v   small为小于pivot的最后一个元素
    //data[small+1, i - 1] >= v   small+1为大于等于pivot的第一个元素

    //注意small的取值,small是为了标识小于
    int small = start;
    for (int i = start + 1; i <= end; ++i){
        if (data[i] < pivot){
            //若当前的元素小于pivot，需要将该元素放到data[start+1, small]中紧挨着small位置
            //将small+1和i进行交换，并将small的长度加长
            swap(data[small + 1], data[i]);
            ++small;
        }
    }
    //最后将start放在应该的位置，即small和small+1之间，因为左侧全是小于pivot的，因此将small和pivot交换
    swap(data[small], data[start]);
    return small;
}

void quickSortOffer(int *data,int start, int end){
    if (start == end)
        return;
    if (start < end){
        int index = partition2(data,  start, end);
        quickSortOffer(data,  start, index - 1);
        quickSortOffer(data, index + 1, end);
    }
}

int main(){
    int arr[8] = { 2, 1, 3, 78, 78,53, 13, 20 };
    quickSortOffer(arr, 0, 7);  //0表示从数组0位置开始，到4位置排序 
    int i;
    for (i = 0; i<8; ++i){
        printf("%d ", arr[i]);
    }
    system("pause");
    return 0;
}

归并排序

//两个序列从相同位置往右遍历比较，根据大小重新排列在新数组中的前提是，左右两个序列都是从小到大排列的

//归并排序思想：先递归再归并
//先递归，将左右归并为有序序列，再将左右进行归并
//将左右有序归并时，两个序列从相同位置往右遍历比较，根据大小重新排列在新数组中
//核心函数是merge，Msort函数是递归分治调用merge的过程

//归并排序，平均情况O(nlogn),最好O(nlogn)，最坏O(nlogn)，空间复杂度O(n + logn)，稳定

//解释时间复杂度为nlogn
//一趟归并要将整个序列所有元素遍历一遍，复杂度为O(n)
//递归树的高度为logn，每次递归都要一趟归并
//nlogn

//解释空间复杂度O(n + logn)
//主要是递归造成的栈空间的使用logn，和每次归并都需要将原数组归并到新数组，再拷贝回原数组，和每次归并都需要将原数组归并到新数组，再拷贝回原数组O(n)
//O(n + logn)
#include <iostream>
#include <vector>
using namespace std;

//函数是将sr两侧归并的数据，重新排列进tr中
//sr[s...m, m+1...t]
//int num = 0;
void merge(int sr[], int s, int m, int t){
    int length = t - s + 1;
    int *tr = new int[length];

    int i = s, j = m + 1, k = 0;

    while(i <= m && j <= t){
        if (sr[i] < sr[j])
            tr[k++] = sr[i++];
        else{
            //num += m - i + 1;
            tr[k++] = sr[j++];
        }
    }
    //当两侧数据长度并非完全相等时，只需要将左、右侧两侧剩余数据拷贝即可
    while (i <= m)
        tr[k++] = sr[i++];
    while (j <= t)
        tr[k++] = sr[j++];

    //将辅助数组的元素拷贝到原数组中
    for (k = 0; k < length; k++)
        sr[s + k] = tr[k];
}

//sr[s, t]原数组
void msort(int sr[], int s, int t){
    if (s >= t)
        return;

    //创建平分中点
    int m = s + (t - s) / 2;
    msort(sr, s, m);
    msort(sr, m+1, t);
    //优化，因为左右两侧都是排序好的数组，只有当左侧最大大于右侧最小时才合并，因为合并意味着比较，会浪费时间
    if (sr[m] > sr[m+1])
        merge(sr, s, m, t);
}

int main(){
    int sr[10] = { 2, 1, 3, 78, 87, 53, 13, 20, 0, 10};
    msort(sr, 0, 9);
    //std::cout << num << endl;
    for (int i = 0; i < 10; i++){
        std::cout << sr[i] << endl;
    }
    std::system("pause");
    return 0;
}

堆排序

//堆排序思想：将待排序列先构造一个最大堆，堆顶元素即为最大值，然后移走堆顶元素，调整剩余元素为最大堆，如此反复执行，便得到有序序列
//若从小到大排列，建立最大堆
//若从大到小排列，建立最小堆

//堆排序，平均情况O(nlogn),最好O(nlogn)，最坏O(nlogn),空间复杂度O(1)，不稳定

//解释时间复杂度O(nlogn)
//建立堆的过程是nlogn,遍历所有非叶子结点，将其和子树调整为最大堆
//调整堆的过程是logn，整体是nlogn

//由数组变为最大堆有两种方式，一种是逐个插入（O(n)），一种是heapify(从第一个非叶子结点开始调整，bottom to up)（O(1)）
//大话数据结构书上的排序基本都是数组的0位置不放元素，从1开始
//这里从0位置开始
#include <iostream>
#include <vector>
using namespace std;

void build_max_heap(vector<int> &a, int len);
void heapadjust(vector<int> &a, int i, int len);

void heap_sort(vector<int> &a) {
    int len = a.size();
    build_max_heap(a, len);
    for (int i = len - 1; i >= 1; i--) {
        //将堆顶的元素和最后一个元素交换位置
        swap(a[0], a[i]);

        //每次将数组前面的部分再调整为最大堆，后续调整的时候传进去的就是当前数组能取到的最大下标了，因为i赋初值时已经解决
        heapadjust(a, 0, i - 1);    
    }
}
//建堆的意思是将数组转换成最大堆
//本质：从下往上，从右往左，将每个非叶子结点当做根节点，将其和子树调整成最大堆，首先找到最后一个叶子结点的父节点len / 2 - 1
//最大堆，每个结点都大于等于左右孩子结点的值
void build_max_heap(vector<int> &a, int len) {  //建堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        heapadjust(a, i, len - 1);              //建堆的时候应该传进去len-1，即当前数组能取到的最大下标，即保证堆调整过程中左右孩子不会数组越界
    }
}

//以i当做根节点，调整其和其子树为最大堆
void heapadjust(vector<int> &a, int i, int len){
    int temp, j;
    temp = a[i];

    //当前结点为j，左孩子序号是2*i，右孩子序号是2*i+1
    //这里的结点从0开始，不是从1开始，因此左孩子序号是2*i + 1，右孩子序号是2*i+2
    for (j = 2*i+1; j <= len; j *= 2){
        //先比较左右孩子,找到左右孩子中较大的那个
        if (j < len && a[j] < a[j+1])
            ++j;

        //如果左右孩子中最大值小于当前值，则不需要移动
        if (a[j] <= temp)
            break;
        //若最大值大于当前值，需要将最大值往前移动，赋给i位置
        //此时不要动j，直到找到j所在位置再赋值
        a[i] = a[j];

        //将当前值和左右孩子比较后，若移动了，则继续往下比较，将j向下移动到刚才较大的孩子处
        i = j;
    }
    //直到找到temp的合适位置
    a[i] = temp;
}

int main(){
    vector<int>a;
    a.push_back(7);
    a.push_back(6);
    a.push_back(5);
    a.push_back(4);
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    heap_sort(a);

    for (int i = 0; i<7; ++i){
        printf("%d ", a[i]);
    }

    system("pause");
    return 0;
}

二叉树非递归遍历

//二叉树的前序，中序和后序遍历是根据根结点的位置来判断
//前序：根左右
//中序：左根右
//后序：左右根
//叶子结点也需要判断左右节点，只不过左右节点都是空


//非递归前序遍历，根左右
//(1) 从根结点开始，向左遍历压栈并输出
//(2) 一直找到二叉树最左边的结点，将最左侧的叶子结点压入栈
//(3) 出栈，指向该结点的右孩子
//(4) 将右孩子作为根节点重复(1)(2)(3)
void Pretravel(BiNode* root)
{
    if (!root)
    {
        return;
    }

    stack<BiNode*> st;
    BiNode* p = root;

    while (p || !st.empty())
    {
        while (p){
            cout << p->data;
            st.push(p);
            p = p->lchild;
        }


        if (!st.empty())
        {
            p = st.top();
            st.pop();
            p = p->rchild;
        }
    }
}

//非递归中序遍历，左根右
//先输出最左侧叶子结点
//(1) 从根结点开始，往左遍历压栈
//(2) 找到最左侧的叶子结点,也将其压栈
//(3) 出栈，输出结点值，并指向该结点的右孩子
//(4) 将右孩子作为根结点继续(1)(2)(3)
void Intravel(BiNode* root){
    if (root == NULL)
        return;
    stack<BiNode*>st;
    BiNode *p = root;

    while (!st.empty() || p){
        while (p){
            st.push(p);
            p = p->lchild;
        }

        if (!st.empty()){
            p = st.top();
            st.pop();
            cout << p->data;
            p = p->rchild;
        }
    }
}

//非递归后序遍历，左右根
// 维护一个pre结点
//(1) 从根结点开始，往左遍历压栈
//(2) 找到最左侧的叶子结点,也将其压栈
//(3) 出栈，判断当前的结点是不是叶子结点或是不是根结点(上一次访问的是右孩子)
//(4) 若是，输出结点值，更新pre指针
//(5) 若不是，指向右孩子，重复(1)(2)(3)(4)
void behtravel(BiNode* root){
    if (NULL == root)
        return;
    stack<BiNode *> st;
    BiNode * p = root;
    BiNode * pre = NULL;
    while (!st.empty || p){
        while (p){
            st.push(p);
            p = p->lchild;
        }
        if (!st.empty()){
            p = st.top();
            st.pop();

            //右孩子为空(左叶子结点和右叶子结点) 或 刚刚访问的是该结点的右孩子(根结点)
            if (!p->rchild || pre == p->rchild){
                cout << p->data;
                pre = p;
            }
            //右孩子不为空，则将刚刚出栈的结点重新压入，指向结点的右孩子
            else{
                st.push(p);
                p = p->rchild;
            }
        }
    }
}

单例模式

//单例思路：静态成员建议在类外进行初始化，但在类内也可以初始化，只是通过类名访问静态成员的属性时，访问不到
//构造函数声明为private或protect防止被外部函数实例化
//内部保存一个private static的类指针保存唯一的实例
//实例的动作由一个public的类方法代劳

//懒汉模式：在getinstance中实例化
//饿汉模式：在单例类定义时实例化

//**********************
//懒汉模式最初实现
//**********************
//#include <iostream>
//
//using namespace std;
//
//class single{
//private:
//  static single *p;
//  single(){}
//  ~single(){}
//
//public:
//  static single* getinstance();
//};
//
//single* single::p = NULL;
//single* single::getinstance(){
//  if (NULL == p)
//      p = new single;
//
//  return p;
//}


//**********************
//懒汉模式线程安全经典实现
//**********************
//#include <iostream>
//#include <unistd.h>
//#include <pthread.h>
//
//using namespace std;
//
//
//class single{
//private:
//  static single *p;
//  static pthread_mutex_t lock;
//  single(){
//      pthread_mutex_init(&lock, NULL);
//  }
//  ~single(){}
//
//public:
//  static single* getinstance();
//
//};
//pthread_mutex_t single::lock;
//single* single::p = NULL;
//single* single::getinstance(){
//  if (NULL == p){
//      pthread_mutex_lock(&lock);
//      if (NULL == p)
//          p = new single;
//  }
//  pthread_mutex_unlock(&lock);
//  return p;
//}

//**************************************************
//懒汉模式线程安全内部静态变量实现
//将经典实现中的私有唯一实例删掉
//改为在instance函数里定义一个静态的实例
//也可以保证拥有唯一实例，在返回时只需要返回其指针就可以
//**************************************************
//#include <iostream>
//#include <unistd.h>
//#include <pthread.h>
//
//using namespace std;
//
//
//class single{
//private:
//  static pthread_mutex_t lock;
//  single(){
//      pthread_mutex_init(&lock, NULL);
//  }
//  ~single(){}
//
//public:
//  static single* getinstance();
//
//};
//pthread_mutex_t single::lock;
//single* single::getinstance(){
//  pthread_mutex_lock(&lock);
//  static single obj;
//  pthread_mutex_unlock(&lock);
//  return &obj;
//}

//************************************************************
//饿汉模式，在定义单例类最初就实例化，此后返回的就一个，感觉相当于全局变量
//在饿汉模式下，在单例类定义的时候就已经定义了一个对象，对类进行了初始化。
//后面不管哪个线程调用成员函数getinstance()，都只不过是返回一个对象的指针而已。
//所以是线程安全的，不需要在成员函数getinstance中加锁。
//************************************************************
#include <iostream>

using namespace std;

class single{
private:
    static single* p;
    single(){}
    ~single(){}

public:
    static single* getinstance();

};
single* single::p = new single();
single* single::getinstance(){
    return p;
}

int main(){

    single *p1 = single::getinstance();
    single *p2 = single::getinstance();

    if (p1 == p2)
        cout << "same" << endl;

    system("pause");
    return 0;
}

智能指针

//智能指针的设计与实现
//智能指针类将一个计数器与类指向的对象相关联，引用计数跟踪该类有多少个对象共享同一指针。
//每次创建类的新对象时，初始化指针并将引用计数置为1；
//当对象作为另一对象的副本而创建时，拷贝构造函数拷贝指针并增加与之相应的引用计数；
//对一个对象进行赋值时，赋值操作符减少左操作数所指对象的引用计数（如果引用计数为减至0，则删除对象），并增加右操作数所指对象的引用计数；
//调用析构函数时，构造函数减少引用计数（如果引用计数减至0，则删除基础对象）。
//所有的智能指针都会重载 -> 和 * 操作符。智能指针还有许多其他功能，比较有用的是自动销毁。

#include <iostream>
#include <memory>

template<typename T>
class SmartPointer {
private:
    T* _ptr;
    //在赋值时，需要修改赋值后指针的引用计数
    size_t* _count;
public:
    //初始化
    SmartPointer(T* ptr = NULL) :
        _ptr(ptr) {
        if (_ptr) {
            _count = new size_t(1);
        }
        else {
            _count = new size_t(0);
        }
    }

    //拷贝构造
    SmartPointer(const SmartPointer& ptr) {
        if (this != &ptr) {
            this->_ptr = ptr._ptr;
            this->_count = ptr._count;
            (*this->_count)++;
        }
    }

    //重载=运算符
    SmartPointer& operator=(const SmartPointer& ptr) {
        if (this->_ptr == ptr._ptr) {
            return *this;
        }

        if (this->_ptr) {
            (*this->_count)--;
            if (this->_count == 0) {
                delete this->_ptr;
                delete this->_count;
            }
        }

        this->_ptr = ptr._ptr;
        this->_count = ptr._count;
        (*this->_count)++;
        return *this;
    }

    //重载*
    T& operator*() {
        assert(this->_ptr == nullptr);
        return *(this->_ptr);

    }

    //重载->
    T* operator->() {
        assert(this->_ptr == nullptr);
        return this->_ptr;
    }

    ~SmartPointer() {
        //因为引用计数是指针，当智能指针声明为空时，仍需释放
        if (*this->_count == 0) {
            delete this->_ptr;
            delete this->_count;
            std::cout << "释放" << std::endl;
        }
        else
            (*this->_count)--;
        if (*this->_count == 0) {
            delete this->_ptr;
            delete this->_count;
            std::cout << "释放" << std::endl;
        }
    }

    size_t use_count(){
        return *this->_count;
    }
};

int main() {
    {
        //只初始化了两次
        SmartPointer<int> sp(new int(10));
        SmartPointer<int> sp2(sp);
        SmartPointer<int> sp3(new int(20));
        sp2 = sp3;
        std::cout << sp.use_count() << std::endl;
        std::cout << sp3.use_count() << std::endl;

        //SmartPointer<int> sp(NULL);
        //std::cout << sp.use_count() << std::endl;
    }

    system("pause");
    return 0;
}

类的默认函数

#include <string.h>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;
class String
{
public:
    String()
    : _pstr(new char[1]())
    {}

    String(const char * pstr) 
    : _pstr(new char[strlen(pstr) + 1]())
    {
        strcpy(_pstr, pstr);
        cout << "String(const char *)" << endl;
    }

    //
    //复制控制函数
    String(const String & rhs)
    : _pstr(new char[strlen(rhs._pstr) + 1]())
    {
        strcpy(_pstr, rhs._pstr);   
        cout << "String(const String &)" << endl;
    }

    String & operator=(const String & rhs)
    {
        cout << "String& operator=(const String &)" << endl;
        if(this != & rhs) {
            delete [] _pstr;
            _pstr = new char[strlen(rhs._pstr) + 1]();
            strcpy(_pstr, rhs._pstr);
        }
        return *this;
    }

    //如果传递右值时，具有移动语义的函数会优先执行
    //移动构造函数
    String(String && rhs)
    : _pstr(rhs._pstr)
    {
        rhs._pstr = NULL;//将临时对象的指针设为空
        cout << "String(String &&)" << endl;
    }
    //移动赋值运算符函数
    String & operator=(String && rhs)
    {
        cout << "String & operator=(String &&)" << endl;
        if(this != & rhs) {
            delete [] _pstr;

            _pstr = rhs._pstr;
            rhs._pstr = NULL;
        }
        return *this;
    }


    ~String()
    {
        delete [] _pstr;
        cout << "~String()" << endl;
    }

    friend std::ostream & operator<<(std::ostream & os, const String & rhs);

private:
    char * _pstr;
};

String str("hello");

//右值引用本身是左值还是右值，取决于其有没有名字

//右值引用作为函数的返回值， 此时是右值
String && func()
{
    return std::move(str);
}

std::ostream & operator<<(std::ostream & os, const String & rhs)
{
    os << rhs._pstr;
    return os;
}