选择、冒泡、插入排序——左神数据结构算法Day1学习笔记

时间复杂度：算法的常数操作数量级的数学表达式中，去除常数的最高阶项，比如aN²+bN+c的时间复杂度就是O(N²)。时间复杂度是数据量大到一定程度时，评价算法优劣的指标。当时间复杂度相同时，分析不同数据样本下的实际运行时间来比较算法的优劣。

额外空间复杂度：在执行代码过程中申请的额外存储空间。

选择排序：时间复杂度O(N²)

void selection_sort(int* a, int num)
{
    for (int i = 0; i < num - 1; ++i)
    {
        for (int j = i + 1; j < num; ++j)
        {
            if (a[i] > a[j])
            {
                a[i] = a[i] ^ a[j];
                a[j] = a[i] ^ a[j];
                a[i] = a[i] ^ a[j];
            }
        }
    }
}

冒泡排序：时间复杂度O(N²)

void bubble_sort(int* a, int num)
{
    for (int i = 0; i < num - 1; ++i)
    {
        for (int j = 0; j < num - i - 1; ++j)
        {
            if (a[j] > a[j + 1])
            {
                std::swap(a[j], a[j + 1]);
            }
        }
    }
}

冒泡排序中也可以用这种异或的交换数值方法：

//异或交换前提，&a[i] != &a[j]
a[i] = a[i] ^ a[j];
a[j] = a[i] ^ a[j];
a[i] = a[i] ^ a[j];

两道关于异或的题目：

1. 许多数中只有一种出现了奇数词，其它数都出现了偶数次，找到这个数。

   #include<iostream>
   int main()
   {
       int eor = 0;
       int num[] = {1,2,2,2,2,3,3};
       for (int i = 0; i < sizeof(num) / sizeof(num[0]); ++i)
       {
           eor ^= num[i];
       }
       std::cout << "这个奇数是：" << eor << std::endl;
   }

2. 许多数中只有两种数出现了奇数词，其他都出现了偶数次，找到这个数。

   #include<iostream>
   int main()
   {
       int AxorB = 0;//A、B异或的结果
       int A_or_B = 0;//A、B其中的一个
       int A_or_B_otherone = 0;//A、B中的另外一个
       
       int num[] = {1,2,2,2,2,3,3,3};
   
       for (int i = 0; i < sizeof(num) / sizeof(num[0]); ++i)
       {
           AxorB ^= num[i];
       }
   
       //rightOne是AxorB化为二进制数后，只保留最右侧的1，其它位为0
       int rightOne = AxorB & (~AxorB + 1);
       for (int i = 0; i < sizeof(num) / sizeof(num[0]); ++i)
       {
           if((rightOne & num[i]) == 0)
               A_or_B ^= num[i];
       }
       A_or_B_otherone = AxorB ^ A_or_B;
       std::cout << "这两个奇数是" << A_or_B_otherone << "和" << A_or_B << std::endl;
   }

插入排序：打扑克时往手牌里插牌。数据的状况会影响时间复杂度，按最差情况估计，插入排序的时间复杂度为O(N²)。

​void insertion_sort(int* a, int num)
{
    for (int i = 1; i < num; ++i)
    {
        int key = a[i];
        int j = i - 1;

        while (j >= 0 && a[j] > key)
        {
            a[j + 1] = a[j];
            j--;
        }

        a[j + 1] = key;
    }
}

二分法：时间复杂度O(logN)。数据状况特殊或问题特殊时可采用二分法，比如以下三个问题。

1. 在一个有序数组中找一个数。
2. 在一个有序数组中找大于等于某个值的最左侧位置。
3. 局部最小值问题：无序数组中，相邻两个数不相等。 找到一个局部最小位置，要求时间复杂度好于O(N)。拉格朗日中值定理。

对数器：暴力尝试（不追求时间复杂度、好实现的方法）和自己的想测试的方法做比较。生成一个随机样本产生器，比对两个方法的结果是否相同，经过很多很多组测试，测试自己的方法的正确性。