并简述排序算法原理，分析这三种排序算法的时间复杂度、空间复杂

/*
    直接插入排序
    时间复杂度：O(n^2)
        空间复杂度：1
        稳定性：稳定
*/
template<class T>
T* straightInsertion(T* array,int n){
    int i,j;
    T temp;
    for(i = 1; i < n; i++){
        j = i;
        temp = array[i];
        while(j > 0 && temp < array[j-1]){
            array[j] = array[j-1];//每比较一个数，比temp大的就后移一位
            j--;//移动已经排好部分的下标
        }
        array[j] = temp;
    }
    return array;
}

//
// Created by John on 2021/02/20.
  快速排序
    时间复杂度：平均O(nlog2n) 最坏O(n^2)
        空间复杂度：平均O(log2n) 最坏O(n)
        稳定性：不稳定
//  //
template<class T>
int getIndex(T* array,int low,int high){
    T data = array[low];//取第一个元素作为枢轴，对表进行划分
    while (low < high){
        while (low < high && array[high] >= data) --high;//不断移动下标直到找到一个比枢轴小的值
        array[low] = array[high];//把找到的值移动到左端
        while (low < high && array[low] <= data) ++low;//不断移动下标直到找到一个比枢轴大的值
        array[high] = array[low];//把找到的值移动到右端
    }
    array[low] = data;//枢轴值最终存放的位置
    return low;
}
template<class T>
T* quickSort(T* array,int low,int high){
    if (low < high){
        int index = getIndex(array,low,high);//以第一个元素为枢轴进行快排并且返回排序后枢轴元素的下标
        //依次对枢轴元素左右的子表进行递归快排
        quickSort(array,low,index-1);
        quickSort(array,index+1,high);
    }
    return array;
}