四種排序算法的時間比較
#include<iostream>
#include<time.h>
using namespace std;
template<class T>
inline void Swap(T& a, T& b);
template<class T>
void BubbleSort(T a[], int n);
template<class T>
void InsertionSort(T a[], int n);
template<class T>
void SelectionSort(T a[], int n);
template<class T>
void Rank(T a[], int n);
int main()
{
int n,*a1,*a2,*a3,*a4;
cout<<"please input a number(1000~60000)"<<endl;
cin>>n;
a1=new int[n];
a2=new int[n];
a3=new int[n];
a4=new int[n];
double start, finish;
for (int i = 0; i < n; i++)
{ a1[i] = n -i; // initialize
a2[i]=a1[i];
a3[i]=a2[i];
a4[i]=a3[i];
}
start = clock( );
InsertionSort(a1, n);
finish = clock( );
cout << n << ' ' << (double)(finish -start) / (CLOCKS_PER_SEC)<< endl;
start = clock( );
SelectionSort(a2, n);
finish = clock( );
cout << n << ' ' << (double)(finish -start) / (CLOCKS_PER_SEC)<< endl;
start = clock( );
Rank(a3, n);
finish = clock( );
cout << n << ' ' << (double)(finish -start) / (CLOCKS_PER_SEC)<< endl;
start = clock( );
BubbleSort(a4, n);
finish = clock( );
cout << n << ' ' << (double)(finish -start) / (CLOCKS_PER_SEC)<< endl;
delete []a1;
delete []a2;
delete []a3;
delete []a4;
system("pause");
}
template<class T>
inline void Swap(T& a, T& b)
{// Swap a and b.
T temp = a;
a = b;
b = temp;
}
/*********************Bubble Sort*************************/
/*進行n- 1次遍歷，每次鄰位比較，是最大數冒到最後面 */
template<class T>
void BubbleSort(T a[], int n)
{// Sort a[0:n -1] using bubble sort.
for (int i = n; i > 1; i--)
for (int i = 0; i < n -1; i++)
if (a[i] > a[i+1])
Swap(a[i], a[i + 1]);
}
/**********************Insertion Sort***********************/
/*每一步都將一個待排數據按其大小插入到已經排序的數據中的適當位置,直到全部插入完畢*/
template<class T>
void InsertionSort(T a[], int n)
{// Sort a[0:n-1].
for (int i = 1; i < n; i++) {
// insert a[i] into 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;
}
}
/********************Selection sort************************/
/*將最大的數選擇出來，並與每次的最後一個數進行交換 */
template<class T>
void SelectionSort(T a[], int n)
{
bool sorted = false;
for (int size = n; !sorted && (size > 1); size--)
{
int pos = 0;
sorted = true;
for (int i = 1; i < size; i++)
if (a[pos] <= a[i]) pos = i;
else sorted = false; // out of order
Swap(a[pos], a[size -1]);
}
}
/*******************Rank sort*****************************/
/*先將數組中的元素按大小給它標號，並存在另外一個相應的數組裡面，
然後新建個數組按照標號讀取原來數組的值，之後再把排好後的值依次賦給原來數組
*/
template<class T>
void Rank(T a[], int n) {
int *r = new int[n+1];
for(int i = 0; i < n; i++)
r[i] = 0; //initialize
for(int i = 1; i < n; i++) {
for(int j = 0; j < i; j++) {
if(a[j] <= a[i])
r[i]++;
else r[j]++;
}
} //end for
T *u = new T[n+1];
for (int i = 0; i < n; i++) {
u[r[i]] = a[i];
}
for (int i = 0; i < n; i++) {
a[i] = u[i];
}
delete []u;
} //end function
