学步园

1.冒泡排序：n*n。  俩个for循环决定其时间复杂度为n^2

template <class T> void Swap(T A[], int i, int j)
{
    T tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

//冒泡法bubble sort
template<class T> void BubSort(T A[], int n)
{
    for (int i=0; i<n; ++i)
    {
        for (int j=i+1; j<n; ++j)
        {
            if (A[i] < A[j])
                Swap(A, i, j);
        }
    }
}

2.选择排序：n*n。  同样，俩个for循环决定其时间复杂度为n^2。

  template <class T> void Swap(T A[], int i, int j)
{
    T tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

template<class T> void SelSort(T A[], int n)
{
    for (int i=0; i<n; ++i)
    {
        int largIndex = i;    //largIndex存储元素值大的下标
        for (int j=i+1; j<n; ++j)
        {
            if (A[largIndex] < A[j])
                largIndex = j;    //发现了较大的元素，记录下它的下标
        }
        Swap<T>(A, i, largIndex);    //只进行最后一次交换
    }
}

3.直接插入排序：n*n。  俩个for循环。

// 1->插入排序
void InsertSort(int array[], int length)
{
　　　 int i, j, key;

　　　 for (i = 1; i < length; i++)
　　　 {
　　　　　　　 key = array[i];
　　　　　　　 // 把i之前所有大于array[i]的数据向后移动
　　　　　　　 for (j = i - 1; j >= 0 && array[j] > key; j--)
　　　　　　　 {
　　　　　　　　　　　 array[j + 1] = array[j];
　　　　　　　 }
　　　　　　　 // 在合适位置安放当前元素
　　　　　　　 array[j + 1] = key;
　　　 }
}

 template <class T> void Swap(T A[], int i, int j)
{
    T tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}