C++ 的一些常用函数

顺序查找

int sequentialSearch(T a[], int n, const T& x)

template<class T>
int sequentialSearch(T a[], int n, const T& x)
{
	//如果找到，返回下标，否则返回 -1
    int i;
    for(i = 0; i < n && a[i] != x; i++)
    	if(i == n)
    		return -1;
    	else
    		return i;
}

//递归方法
template<class T>
int sequentialSearch(T a[], int n, const T& x)
{
	//如果找到，返回下标，否则返回 -1
   if(n < 1)
   		return -1;
   if(a[n - 1] == x)
   		return n - 1;
   	return sequentialSearch(a[], n - 1, x);
}

indexOfMax(T a[], int n) 找最大值的下标

template<class T>
int indexOfMax(T a[], int n)
{//查找数组a[0:n-1]中的最大值的
    if(n <= 0)
    	throw illegalParameterValue("n 必须大于 0");
    int indexOfMax = 0;
    for(int i = 1; i < n; i++)
    {
        if(a[indexOfMax] < a[i])
        	indexOfMax = i;
        return indexOfMax;
    }
}

---

排序

swap(T& x, T& y ) 交换

template<class T>
void Swap(T& x, T& y)
{
    T temp;
    temp = x;
    x = y;
    y = temp;
}

selectionSort(T a[], int n) 选择排序

template<class T>
void selectionSort(T a[], int n)
{//排序数组 a[0:n-1]
    for(int size = n; size > 1; size--)
    {
        int i = indexOfMax(a, size);
        Swap(a[i], a[size - 1]);
    }
}

selectionSortPlus(T a[], int n) 及时终止选择排序

template<class T>
void selectionSortPlus(T a[], int n)
{
    boole sort = false;
    for(int i = n; !sort && (i > 1); i--)
    {
        int indexOfMax = 0;
        sotr = true;
        for(int j = 1; j < i; j++)
        {
            if(a[indexOfMax] <= a[j])
            	indexOfMax = j;
            else
            	sort = false;//无序
        }
        Swap(a[indexOfMax], a[j - 1]);
    }
}

　　及时终止选择排序，最好情况下外部 for 循环只走一次，比较次数为 n-1。最坏情况下，比较次 数为(n-1)n/2，并且速度比选择排序要慢一些。

bubbleSort(T a[], int n)冒泡排序

template<class T>
void bubbleSort(T a[], int n)
{
    for(int i = n; i > 1; i--)
        for(int j = 0; j < n - 1; j ++)
        {
            if(a[j] > a[j + 1])
            	Swap(a[j], a[j + 1]);
        }
}

bubbleSort(T a[], int n) 及时终止冒泡排序

template<class T>
bool bubble(T a[], int n)
{
    bool swap = false;
    for(int i = 0; i < n - 1; i++)
    {
        if(a[i] > a[i + 1])
        {
            Swap(a[i], a[i + 1]);
            swap = true;//发生交换
        }
    }
    return swap;
}

template<class T>
void bubbleSort(T a[], int n)
{
    for(int i = n; i > 1 && bubble(a, i); i--)
    {
        
    }
}

　　最坏情况比较次数：n(n-1)/2；最好情况比较次数：n-1。

insertionSort(T a[], int n) 插入排序

template<class T>
void insertionSort(T a[], int n)
{
    for(int i = 1; i < n; i++)
    {//把 a[i] 插入 a[0:i-1]
        T t = a[i];
        int j;
        for(j = i - 1; j >= 0 && t < a[j]; j--)
        {
            a[j + 1] = a[j];
        }
        a[j + 1] = t;
    }
}

　　最坏情况比较次数：n(n-1)/2；最好情况比较次数：n-1。 　　

---

矩阵转置

transpose(T **a, int rows) 矩阵转置

template<class T>
void transpose(T **a, int rows)
{//矩阵a[n][n] 转置
	for(int i = 0; i < rows; i++)
	{
        for(int j = i + 1; j < rows; j++)
        {
            Swap(a[i][j], a[j][i]);
        }
	}
}

matrixAdd(T **a, T **b, T **c, int rows, int cols) 矩阵加法

template<class T>
void matrixAdd(T **a, T **b, T **c, int rows, int cols)
{
    for(int i = 0; i < rows; i++)
    {
        for(int j =0; j <cols; j++)
        {
            c[i][j] = a[i][j] + b[i][j];
        }
    }
}

---

持续更新。。。。。。