选择冒泡插入排序 异或 二分 对数器

算法

时间复杂度O(x)

空间复杂度O(x)

数据状况是否影响时间复杂度表现

选择排序

n²

1

否

冒泡排序

n²

1

否

插入排序

n²

1

是(最好情况下O(N))

1.选择排序：

遍历找出0~n-1最小的数放在0位置，遍历找出1~n-1最小的数放在1位置

时间复杂度O(n²)  空间复杂度O(1)

void swap(vector<int>& nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
void selectSort(vector<int>& nums){
    if(nums.empty() || nums.size() < 2){
        return;
    }
    for(int i = 0; i < nums.size() - 1; i++){
        int minIndex = i;
        for(int j = i + 1; j < nums.size(); j++){
            minIndex = nums[j] < nums[minIndex] ? j : minIndex;
        }
        swap(nums, i, minIndex);
    }
}

2.冒泡排序

0~n-1遍历每一对数，大的数放右边；0~n-2遍历每一对数，大的数放右边

时间复杂度O(n²)  空间复杂度O(1)

void swap(vector<int>& nums, int i, int j){
    nums[i] = nums[i] ^ nums[j];
    nums[j] = nums[i] ^ nums[j];
    nums[i] = nums[i] ^ nums[j];
}
void bubbleSort(vector<int>& nums){
    if(nums.empty() || nums.size() < 2){
        return;
    }
    for(int e = nums.size() - 1; e > 0; e--){
        for(int i = 0 ; i < e; i++){
            if(nums[i] > nums[i+1]){
                swap(nums, i, i+1);
            }
        }
    }
}

3.异或

0^N=N    N^N=0

交换律和结合律：  a^b=ba     (a^b)c=a^(bc)

// a = 甲
// b = 乙
a = a ^ b; // a=甲^乙  b=乙 
b = a ^ b; // a=甲^乙  b=甲^乙^乙=甲
a = a ^ b; // a=甲^乙^甲=甲^甲^乙=乙 b=甲
// 注意：a和b可以值相同，执行完后a和b值不变
// 但a和b不能是同一块内存，否则执行完a b均为0

给定一个数组，数组中除a，b两个数出现了奇数次外，其他数都出现了偶数次，找出这两个数a，b，要求时间复杂度为O(n)

对数组中所有数取异或，得到的结果肯定为a^b

又因为a，b是两个不同的数，所以a^b肯定不为0，肯定有某一位为1

假设a^b的第8位为1，说明a和b的第8位是不一样的

对数组中第8位为1的所有数取异或，得到的结果肯定为a和b中的一个

再用这个结果与a^b做异或，得到a和b中的另一个

vector<int> getOddTimesNum2(vector<int>& arr){
    int eor = 0;
    for(auto a : arr){
        eor ^= a;
    }
    int rightOne = eor & (~eor + 1); //提取出最右的1
    int ans1 = 0;
    for(auto a : arr){
        if(a & rightOne){
            ans1 ^= a;
        }
    }
    vector<int> ans;
    ans.push_back(ans1);
    ans.push_back(ans1 ^ eor);
    return ans;
}

4.插入排序

先使0~1范围有序，再使0~2范围有序，一直到0~n范围有序，类似斗地主摸牌

void swap(vector<int>& nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
void insertionSort(vector<int>& nums){
    if(nums.empty() || nums.size() < 2){
        return;
    }
    for(int i = 1; i < nums.size(); i++){
        for(int j = i-1; j >= 0 && nums[j] > nums[j+1]; j--){
            swap(nums,j,j+1);
        }
    }
}

5.二分法

在一个有序数组中，找>=k的最左侧的位置

使用二分法找到值为k的位置时不会立即返回，而是看左侧是否还有数，如果有则继续二分，直到左侧没有数

int getLargerLeft(vector<int>& nums, int k){
    int l = 0, r = nums.size() - 1;
    int m;
    while(l <= r){
        m = l + (r - l)/2;
        if(nums[m] < k){
            l = m;
        }
        else{
            if(l == m || nums[m-1] < k){
                return m;
            }
            else{
                m = r;
            }
        }
    }
}

在一个无序数组arr中，相邻两个数一定不相等，求数组中的一个局部最小值

先检查0位置和n-1位置是不是局部最小，是则返回其中一个

如果0和n-1位置都不是局部最小，则在中间必存在局部最小

对中间二分，如果arr[mid]是局部最小，则直接返回

否则在其左边或右边必存在局部最小，继续二分

int getLocalMin(vector<int>& nums){
    if(nums.empty() || nums.size() == 1){
        return -1;
    }
    if(nums[0] < nums[1]){
        return nums[0];
    }
    if(nums[nums.size() - 1] < nums[nums.size() - 2]){
        return nums[nums.size() - 1];
    }
    int l = 0,r = nums.size() -1;
    int m;
    while(l<=r){
        int m = l + (r - l)/2;
        if (nums[m] < nums[m+1] && nums[m] < nums[m-1]){
            return nums[m];
        }
        else if(nums[m] < nums[m+1] && nums[m-1] < nums[m]){
            r = m;
        }
        else{
            l = m;
        } 
    }
}

6.对数器

需要两个函数，被测函数和标准函数

生成随机测试用例，比较两个函数的测试结果

vector<int> generateRandomArray(int maxSize, int maxValue){
    vector<int> ans;
    // 生成 0 ~ maxSize 随机整数
    int length = rand() % (maxSize + 1); // rand()生成随机整数
    for(int i = 0; i < maxSize; i++){
        // 生成 0 ~ maxValue 随机整数
        ans.push_back(rand() % (maxValue + 1));
    }
    return ans;
}
int main(){
    int testTime = 5000;
    int maxSize = 100;
    int maxValue = 100;
    bool succeed = true;
    for (int i = 0; i < testTime; i++){
        vector<int> arr1 = generateRandomArray(maxSize, maxValue);
        vector<int> arr2(arr1);
        selectSort(arr1);
        insertionSort(arr2);
        if(arr1 != arr2){
            // 打印arr1，arr2
            succeed = false;
            break;
        }
    }
    if(succeed){
        cout << "succeed";
    }
}