#include <iostream>
#include<algorithm>
#include <string>
#include "SortTestHelper.h"
#include "SelectionSort.h"
#include "BubbleSort.h"
using namespace std;
//插入排序
template<typename T>
void insertSort(T arr[], int n){
    for (int i = 1; i < n; i++){    
        
        for (int j = i; j >= 1; j--){            
            if (arr[j] < arr[j-1])
                swap(arr[j-1], arr[j]);
            else
                break;   //提前终止循环，减少不必要的运算。当执行到此步骤时，说明前者小于后者，而前面也已经排好序。
            
        }        
    }
}
//理论上插入排序要比选择排序快，因为中间就break，但实际上耗时更长。因为频繁的swap（）操作更耗时。
//改进后
template<typename T>
void insertSortImprove(T arr[], int n){
    for (int i = 1; i < n; i++){
        T tempValue = arr[i];
        int j;  //保存要存放的位置
        for (j = i; j >0 && arr[j - 1] > tempValue; j--){            
            arr[j] = arr[j - 1];            
        }
        arr[j] = tempValue;
    }
}


int main(){

    int n = 10000;
    int *arr = SortTestHelper::generateRandomArray(n, 0, n);    
    int *arr2 = SortTestHelper::copyIntArray(arr,n);
    int *arr3 = SortTestHelper::copyIntArray(arr, n);
    int *arr4 = SortTestHelper::copyIntArray(arr, n);
    SortTestHelper::testSort("Selection Sort", selectionSort, arr, n);
    SortTestHelper::testSort("Insert Sort", insertSort, arr2, n);
    SortTestHelper::testSort("Insert Sort Improve", insertSortImprove, arr3, n);
    SortTestHelper::testSort("Bubble Sort", bubbleSort, arr4, n);
    //四种算法耗时长短比较  优化的插入排序<选择排序<冒泡排序<插入排序 
    //这四种算法都是O(n2)级别的运算量
    delete[] arr;
    delete[] arr2;
    delete[] arr3;
    delete[] arr4;
    system("pause");
    return 0;
}

#ifndef SELECTIONSORT_SORTTESTHELPER_H
#define SELECTIONSORT_SORTTESTHELPER_H

#include <iostream>
#include <ctime>
#include <cassert>

using namespace std;

namespace SortTestHelper{
	//generateRandomArray 产生n个范围[rangeL,rangeR]的随机数
	int* generateRandomArray(int n, int rangeL, int rangeR){
		assert(rangeL <= rangeR);
		int *arr = new int[n];
		srand(time(NULL));
		for (int i = 0; i < n; i++){
			arr[i] = rand() % (rangeL - rangeR + 1) + rangeL;
		}
		return arr;
	}
	template<typename T>
	void printArray(T arr[], int n){
		for (int i = 0; i < n; i++)
			cout << arr[i] << " ";
		cout << endl;

		return;
	}

	//isSorted 判断是否排序成功
	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;		
	}

	//testSort 测试排序时间
	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));
		cout << sortName << ":" << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
		return;
	}

	//copyIntArray 拷贝数组
	int* copyIntArray(int a[], int n){
		int* copyA = new int[n];
		copy(a, a + n, copyA);
		return copyA;
	}
}

#endif

template<typename T>
void selectionSort(T arr[], int n){

    for (int i = 0; i < n; i++){
        int minIndex = i;
        for (int j = i + 1; j < n; j++){
            if (arr[j] < arr[minIndex]){
                minIndex = j;
            }

        }
        swap(arr[i], arr[minIndex]);
    }
}

template<typename T>
void bubbleSort(T arr[], int n){
    for (int i = 0; i < n - 1; i++){
        for (int j = i + 1; j < n; j++){
            if (arr[i]>arr[j]){
                swap(arr[i], arr[j]);
            }
        }
    }
}