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.快速排序：
