#include <iostream>
#include <stdlib.h> #include <time.h> using namespace std;// 交换数组两个元素
void swap(int *arr, int p, int e) { int tmp = arr[p]; arr[p] = arr[e]; arr[e] = tmp; }// 冒泡排序
// arr - 数组 // p - 开始下标 // e - 结束下标 void bubble_sort(int *arr, int p, int e) { int i, j; for (i = p; i < e-1; i++) { for (j = e-1; j >i; j--) if (arr[j] < arr[j-1]) { swap(arr, j, j-1); } } }// 插入排序
// arr - 数组 // p - 开始下标 // e - 结束下标 void insert_sort(int *arr, int p, int e) { int i, j, k, tmp; for (i =p+1; i < e; i++) { for (j = 0; j < i; j++) { if (arr[i] < arr[j]) { tmp = arr[i]; for (k = i; k > j; k--) { arr[k] = arr[k-1]; } arr[j] = tmp; break; } } } }// 快速排序 // arr - 数组 // p - 开始下标 // e - 结束下标 void quick_sort(int *arr, int p, int e) { int i; if (p >= e) return; int m = p; for (i = m+1; i < e; i++) { if (arr[i] < arr[p]) swap(arr, ++m, i); } swap(arr, m, p); quick_sort(arr, m+1, e); quick_sort(arr, p, m); }
// 归并排序
// arr - 数组 // p - 开始下标 // e - 结束下标 int tmp[100000]; void merge_sort(int *arr, int p, int e) { if (p >= e-1) return ; int m = (p+e) / 2; merge_sort(arr, p, m); merge_sort(arr, m, e); int i = p; int j = m; int k = 0; while(i < m && j < e) { if (arr[i] <= arr[j]) { tmp[k++] = arr[i++]; } else { tmp[k++] = arr[j++]; } } while (i < m) tmp[k++] = arr[i++]; while (j < e) tmp[k++] = arr[j++]; for (i = 0; i < k; i++) { arr[p+i] = tmp[i]; } } // 选择排序 // arr - 数组 // p - 开始下标 // e - 结束下标 void select_sort(int *arr, int p, int e) { int i, j, k; for (i = p; i < e-1; i++) { k = i; for (j = i+1; j < e; j++) { if (arr[j] < arr[k]) k = j; } if (k != i) swap(arr, k, i); } }// 堆排序
// arr - 数组 // p - 开始下标 // e - 结束下标 void heap_sort(int *arr, int p, int e) { int i; int * heap = new int[5001]; int size = 0; // 建堆 for (i = p; i < e; i++) { int hole = ++size; for (;heap[hole/2] > arr[i] && hole > 1; hole/=2) heap[hole] = heap[hole/2]; heap[hole] = arr[i]; } // 出堆 int head, hole, child, tmp; i = 0; while(size > 0) { head = heap[1]; hole = 1; tmp = heap[size--]; for (; hole * 2 <= size; hole = child) { child = hole * 2; if (heap[child+1] < heap[child]) child++; if (heap[child] > tmp) break; else heap[hole] = heap[child]; } heap[hole] = tmp; arr[i++] = head; } }// 复制数组
void copy(int *dst, int *src) { for (int i = 0; i < 5000; i++) dst[i] = src[i]; }// 测试各种排序算法时间
void test() { int arr[5000]; // 产生随机数 int i; time_t t; srand((unsigned)time(&t)); for (i = 0; i < 5000; i++) arr[i] = rand()%(1000000+1); // 测试时间 int a[5000]; long beginTime; long endTime; // 冒泡排序 copy(a,arr); beginTime = clock(); bubble_sort(a, 0, 5000); endTime = clock(); cout<<"冒泡排序: "<<endTime-beginTime<<"ms"<<endl; // 插入排序 copy(a, arr); beginTime = clock(); insert_sort(a, 0, 5000); endTime = clock(); cout<<"插入排序: "<<endTime-beginTime<<"ms"<<endl;// 快速排序
copy(a, arr); beginTime = clock(); quick_sort(a, 0, 5000); endTime = clock(); cout<<"快速排序: "<<endTime-beginTime<<"ms"<<endl;// 归并排序
copy(a, arr); beginTime = clock(); merge_sort(arr, 0, 5000); endTime = clock(); cout<<"归并排序: "<<endTime-beginTime<<"ms"<<endl;// 选择排序
copy(a, arr); beginTime = clock(); select_sort(arr, 0, 5000); endTime = clock(); cout<<"选择排序: "<<endTime-beginTime<<"ms"<<endl;// 堆排序
copy(a, arr); beginTime = clock(); heap_sort(arr, 0, 5000); endTime = clock(); cout<<"堆排序: "<<endTime-beginTime<<"ms"<<endl; }int main()
{ cout<<"从小到大排序5000个随机数据，各类排序算法时间: "<<endl; test(); }