c++版：
SortTestHelper.h
#ifndef ALGORITHM_SORTTESTHELPER_H
#define ALGORITHM_SORTTESTHELPER_H
#include <iostream>
#include <ctime>
#include <cassert>
using namespace std;
namespace SortTestHelper {
//生成有n个元素的随机数数组，每个元素的随机范围为[randomL, randomR]
int* generateRandomArray( int n, int randomL, int randomR ){
assert(randomL <= randomR);
int *arr = new int[n];
srand(time(NULL)); //以时间来生成随机种子
//为n个元素赋值
for( int i=0; i<n; i++ ){
int random = rand() % (randomR-randomL+1); //求余数，得到[0, randomR-randomL+1)的随机数
arr[i] = random + randomL; //得到[randomL, randomR]范围内的随机数。
}
return arr;
}
//打印数组
template<typename T>
void printArr( T arr[] , int n ){
for(int i=0; i<n; i++){
cout << " " << arr[i];
}
cout << endl;
}
//测试数组是否有序
template <typename T>
bool isSorted(T arr[], int n){
for (int i=0; i<n-1; i++) {
if(arr[i] > arr[i+1]){
return false;
}
}
return true;
}
//测试算法的有效性和运算时间
template <typename T>
void testSort(string sortName, void(*sort)(T[], int), T arr[], int n){
clock_t startTime = clock();
sort(arr, n);
clock_t endTime = clock();
assert( isSorted(arr, n) );
//CLOCKS_PER_SEC是1秒走过的时钟周期
cout << sortName << ": " << (double)(endTime-startTime) / CLOCKS_PER_SEC << " s" << endl;
}
//拷贝一个一模一样的数组（换成模版函数，类对象有一个深拷贝的问题）
int* copyIntArray(int ori[], int n){
int *des = new int[n];
copy(ori, ori+n, des);
return des;
}
//生成一个元素个数是n的有序数组，并随机进行swapTimes次将其中任意两个元素进行对调。
int* generateNearlyOrderedArray(int n, int swapTimes){
int* arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = i;
}
srand(time(NULL)); //随机种子
for(int i=0; i<swapTimes; i++){
int a = rand() % n;
int b = rand() % n;
swap(arr[a], arr[b]);
}
return arr;
}
};
#endif //ALGORITHM_SORTTESTHELPER_H
main.cpp
#include <iostream>
#include "SortTestHelper.h"
#include "SelectionSort.h"
#include "InsertionSort.h"
#include "MergeSort.h"
using namespace std;
// 选择 VS 插入
void SelectionSort_VS_InsertionSort(){
//Random Array
int n = 10000;
cout << "Test for random array, size = " << n << ", random range [1, " << n << "]" << endl;
int *arr = SortTestHelper::generateRandomArray(n, 1, n);
int *copy = SortTestHelper::copyIntArray(arr, n);
SortTestHelper::testSort("selectionSort", selectionSort, arr, n);
SortTestHelper::testSort("insertionSort", insertionSort, copy, n);
int n2 = 100000;
cout << "Test for random array, size = " << n2 << ", random range [1, " << n2 << "]" << endl;
int *arr2 = SortTestHelper::generateRandomArray(n2, 1, n2);
int *copy2 = SortTestHelper::copyIntArray(arr2, n2);
SortTestHelper::testSort("selectionSort", selectionSort, arr2, n2);
SortTestHelper::testSort("insertionSort", insertionSort, copy2, n2);
}
// 插入 VS 归并
void InsertionSort_VS_MergeSort(){
// Merge Sort是我们学习的第一个O(nlogn)复杂度的算法
// 可以在1秒之内轻松处理100万数量级的数据
// 注意：不要轻易尝试使用SelectionSort, InsertionSort或者BubbleSort处理100万级的数据
// 否则，你就见识了O(n^2)的算法和O(nlogn)算法的本质差异：）
int n = 50000;
// random array Test
cout << "Test for random array, size = " << n << ", random range [1, " << n << "]" << endl;
int *arr = SortTestHelper::generateRandomArray(n, 1, n);
int *copy = SortTestHelper::copyIntArray(arr, n);
SortTestHelper::testSort("insertionSort", insertionSort, arr, n);
SortTestHelper::testSort("mergeSort", mergeSort, copy, n);
delete[] arr;
delete[] copy;
cout<<endl;
// nearly ordered array Test
// 对于近乎有序的数组, 数组越有序, InsertionSort的时间性能越趋近于O(n)
// 所以可以尝试, 当swapTimes比较大时, MergeSort更快
// 但是当swapTimes小到一定程度, InsertionSort变得比MergeSort快
int swapTimes = 15;
assert( swapTimes >= 0 );
cout << "Test for nearly ordered array, size = " << n << ", swap time = " << swapTimes << endl;
int *arr1 = SortTestHelper::generateNearlyOrderedArray(n, swapTimes);
int *copy1 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("insertionSort", insertionSort, arr1, n);
SortTestHelper::testSort("mergeSort", mergeSort, copy1, n);
delete[] arr1;
delete[] copy1;
cout<<endl;
}
// 自顶向下归并 VS 自底向上归并
void MergeSort_VS_MergeSort_BU(){
int n = 50000;
// random array Test
cout << "Test for random array, size = " << n << ", random range [1, " << n << "]" << endl;
int *arr = SortTestHelper::generateRandomArray(n, 1, n);
int *copy = SortTestHelper::copyIntArray(arr, n);
SortTestHelper::testSort("mergeSort", mergeSort, arr, n);
SortTestHelper::testSort("mergeSort_BU", mergeSort_BU, copy, n);
delete[] arr;
delete[] copy;
cout<<endl;
}
int main(){
SelectionSort_VS_InsertionSort();
InsertionSort_VS_MergeSort();
MergeSort_VS_MergeSort_BU();
return 0;
}
运行结果示例：
Test for random array, size = 10000, random range [1, 10000]
selectionSort: 0.117685 s
insertionSort: 0.061454 s
Test for random array, size = 100000, random range [1, 100000]
selectionSort: 11.025 s
insertionSort: 6.19232 s
Test for random array, size = 50000, random range [1, 50000]
insertionSort: 1.61498 s
mergeSort: 0.01237 s
Test for nearly ordered array, size = 50000, swap time = 15
insertionSort: 0.001154 s
mergeSort: 0.00216 s
Test for random array, size = 50000, random range [1, 50000]
mergeSort: 0.011673 s
mergeSort_BU: 0.009817 s
Java版：
SortTestHelper.java
package util;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.Random;
public class SortTestHelper {
//生成有n个元素的随机数数组，每个元素的随机范围为[randomL, randomR]
public static Integer[] genarateRandomArray(int n, int randomL, int randomR) {
//assert randomL <= randomR;
if (randomL > randomR) {
throw new RuntimeException("Class->SortTestHelper, Method->genarateRandomArray's params must be [randomL <= randomR]");
}
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++) {
//方法一：
//new Random().nextInt(10); //得到一个 [0, 10) 范围内的整数
//方法二：
//Math.random(); //得到一个 [0.0, 1.0) 范围内的double值，例如：0.2874378341644207
//利用方法一：
/*
int random = new Random().nextInt(randomR-randomL+1); //得到一个 [0, randomR-randomL+1) 范围内的整数
arr[i] = random + randomL; //得到一个 [randomL, randomR] 范围内的随机数
*/
//利用方法二：
double random = Math.random() * (randomR - randomL + 1); //得到一个 [0.0, randomR-randomL+1) 范围内的随机数
arr[i] = (int) (random + randomL); //得到一个 [randomL, randomR] 范围内的随机数
}
return arr;
}
//交换数组中的两个数
public static void swap(Object[] arr, int i, int j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//打印数组
public static void printArray(Object[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(" " + arr[i]);
}
System.out.println();
}
//测试数组是否有序
public static boolean isSorted(Comparable[] arr) {
for (int i = 0; i < arr.length-1; i++) {
if (arr[i].compareTo(arr[i + 1]) > 0) {
return false;
}
}
return true;
}
//测试算法的有效性和运算时间
public static void testSort(String sortClassName, Comparable[] arr) {
try {
Class sortClass = Class.forName(sortClassName);
Method sortMethod = sortClass.getMethod("sort", new Class[] { Comparable[].class });
long startTimeMillis = System.currentTimeMillis();
sortMethod.invoke( null , new Object[]{ arr } );
long endTimeMillis = System.currentTimeMillis();
//assert isSorted(arr);
if(!isSorted(arr)){
throw new RuntimeException(sortClassName + "is not valid !");
}
// 打印时间
System.out.println(sortClassName + ": " + (endTimeMillis - startTimeMillis) + " ms");
} catch (ClassNotFoundException e) {
e.printStackTrace();
} catch (NoSuchMethodException e) {
e.printStackTrace();
} catch (SecurityException e) {
e.printStackTrace();
} catch (IllegalAccessException e) {
e.printStackTrace();
} catch (IllegalArgumentException e) {
e.printStackTrace();
} catch (InvocationTargetException e) {
e.printStackTrace();
}
}
//生成一个接近有序的数组
public static Integer[] generateNearlyOrderedArray(int n, int swapTimes){
Integer[] arr = new Integer[n];
for(int i=0; i<n; i++){
arr[i] = i;
}
for(int i=0; i<swapTimes; i++){
int a = new Random().nextInt(n);
int b = new Random().nextInt(n);
swap(arr, a, b);
}
return arr;
}
}
Main.java
package top.mengmei219;
import java.util.Arrays;
import util.SortTestHelper;
public class Main {
//选择排序 VS 插入排序
static void SelectionSort_VS_InsertionSort(){
System.out.println("1万数据级别:");
int n = 10000;
//Integer[] arr = SortTestHelper.genarateRandomArray(n, 1, n);
Integer[] arr = SortTestHelper.generateNearlyOrderedArray(n, 15);
Integer[] copy = Arrays.copyOf(arr, n);
SortTestHelper.testSort("top.mengmei219.SelectionSort", arr);
SortTestHelper.testSort("top.mengmei219.InsertionSort", copy);
System.out.println("10万数据级别:");
int n2 = 100000;
//Integer[] arr2 = SortTestHelper.genarateRandomArray(n2, 1, n2);
Integer[] arr2 = SortTestHelper.generateNearlyOrderedArray(n2, 15);
Integer[] copy2 = Arrays.copyOf(arr2, n2);
SortTestHelper.testSort("top.mengmei219.SelectionSort", arr2);
SortTestHelper.testSort("top.mengmei219.InsertionSort", copy2);
}
//插入排序 VS 归并排序
static void InsertionSort_VS_MergeSort(){
// Merge Sort是我们学习的第一个O(nlogn)复杂度的算法
// 可以在1秒之内轻松处理100万数量级的数据
// 注意：不要轻易尝试使用SelectionSort, InsertionSort或者BubbleSort处理100万级的数据
// 否则，你就见识了O(n^2)的算法和O(nlogn)算法的本质差异：）
System.out.println("5万完全随机:");
int n = 50000;
Integer[] arr = SortTestHelper.genarateRandomArray(n, 1, n);
Integer[] copy = Arrays.copyOfRange(arr, 0, n);
SortTestHelper.testSort("top.mengmei219.InsertionSort", arr);
SortTestHelper.testSort("top.mengmei219.MergeSort", copy);
System.out.println("5万近乎有序：");
Integer[] arr2 = SortTestHelper.generateNearlyOrderedArray(n, 15);
Integer[] copy2 = Arrays.copyOfRange(arr2, 0, n);
SortTestHelper.testSort("top.mengmei219.InsertionSort", copy2);
SortTestHelper.testSort("top.mengmei219.MergeSort", arr2);
}
// 自顶向下归并 VS 自底向上归并
static void MergeSort_VS_MergeSort_BU() {
System.out.println("5万完全随机:");
int n = 50000;
Integer[] arr = SortTestHelper.genarateRandomArray(n, 1, n);
Integer[] copy = Arrays.copyOfRange(arr, 0, n);
SortTestHelper.testSort("top.mengmei219.MergeSort", arr);
SortTestHelper.testSort("top.mengmei219.MergeSort_BU", copy);
}
public static void main(String[] args) {
SelectionSort_VS_InsertionSort();
InsertionSort_VS_MergeSort();
MergeSort_VS_MergeSort_BU();
}
}
运行结果示例：
1万数据级别:
top.mengmei219.SelectionSort: 73 ms
top.mengmei219.InsertionSort: 3 ms
10万数据级别:
top.mengmei219.SelectionSort: 6745 ms
top.mengmei219.InsertionSort: 27 ms
5万完全随机:
top.mengmei219.InsertionSort: 2767 ms
top.mengmei219.MergeSort: 42 ms
5万近乎有序：
top.mengmei219.InsertionSort: 1 ms
top.mengmei219.MergeSort: 17 ms
5万完全随机:
top.mengmei219.MergeSort: 29 ms
top.mengmei219.MergeSort_BU: 23 ms
