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;
}
}
// 2-->插入法insert sort
template <class T> void Swap(T A[], int i, int j)
{
T tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
//插入法insert sort
template<class T> void InsSort(T A[], int n)
{
for (int i=1; i<n; ++i) //i为什么要初始化为1？因为在i的前面至少有一个元素，才能比较。
{
for (int j=i; (j>0) && (A[j]>A[j-1]); --j)//总是与它的前一个元素比较，j>0是为了保证j-1不会溢出
{
Swap<T>(A, j, j-1);
}
}
} 4.快速排序：
