算法小记（一）

冷不防 2024-01-20 07:46 6阅读 0赞

1、生成指定个数的随机数组  
C++实现：

#include <iostream>
    #include <ctime>
    #include <cassert>
    using namespace std;
    namespace RandomArray
     {
        
    	//生成有n个元素的随机数组，每个元素的随机范围为[rangeL,rangeR]
    	int* generateRandomArray(int n, int rangeL, int rangeR)
    	 {
        
    		assert(rangeL <= rangeR);
    		int *arr = new int[n];
    		srand(time(NULL));
    		for (int i = 0; i < n; i++) 
    		{
        
    			arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
    		}
    		return arr;
    	}
    }

2、C++实现选择排序（模板化）

//默认从小到大排序
    template<typename T>
    void selectionSort(T arr[], int n)
    {
        
    	for (int i = 0; i < n; i++)
    	{
        
    		//寻找[i,n)区间里的最小值
    		int minIndex = i;
    		for (int j = i + 1; j < n; j++)
    		{
        
    			if (arr[i] < arr[minIndex])
    			{
        
    				minIndex = j;
    			}
    		}
    		swap(arr[i], arr[minIndex]);
    	}
    }

碰到类似这种循环：

for (int j = i; j > 0; j--)
    {
        
    	if (arr[i] < arr[j - 1])
    	{
        
    		swap(arr[j], arr[j - 1]);
    	}
    	else
    	{
        
    		break;
    	}
    }

可以简化为：

for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--)
    {
        
    	swap(arr[j], arr[j - 1]);
    }

3、数组拷贝：  
C++实现：

template<typename T>//T限定为八大基本数据类型
    T* copyIntArray(T a[], int n)//第一个参数是要拷贝的数组名称，第二个参数是数组的大小
    {
        
    	T* arr = new T[n];
    	copy(a, a + n, arr);//使用std中的copy函数。第一个参数是原数组的头指针，第二个参数是原数组的尾指针，第三个参数是拷贝到的目的地址的头指针。
    	return arr;
    }

4、C++实现插入排序：

template<typename T>
    void insertionSort(T arr[], int n)
    {
        
    	for (int i = 1; i < n; i++)
    	{
        
    
    		//寻找元素arr[i]合适的插入位置
    		for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--)
    		{
        
    			swap(arr[j], arr[j - 1]);
    		}
    	}
    }

优化后（对于一个将近有序的数组，时间明显减少）：

template<typename T>
    void insertionSort(T arr[], int n)
    {
        
    	for (int i = 1; i < n; i++)
    	{
        
    		//寻找元素arr[i]合适的插入位置
    		T e = arr[i];
    		int j;//j保存元素e应该插入的位置
    		for (int j = i; j > 0 && arr[j - 1] > e; j--)
    		{
        
    			arr[j] = arr[j - 1];
    		}
    		arr[j] = e;
    	}
    }