MT5(C++)软件编程-插入排序算法

1. MT5(C++)软件编程十大排序算法 - 冒泡排序算法 (bubble Sort)
2. MT5(C++)软件编程十大排序算法 - 选择排序算法 (select Sort)
3. MT5(C++)软件编程十大排序算法 - 插入排序算法 (insert Sort)
4. MT5(C++)软件编程十大排序算法 - 快速排序算法 (quick Sort)
5. MT5(C++)软件编程十大排序算法 - 希尔排序算法 (shell Sort)
6. MT5(C++)软件编程十大排序算法 - 堆排序算法 (heap Sort)
7. MT5(C++)软件编程十大排序算法 - 归并排序算法 (merge Sort)
8. MT5(C++)软件编程十大排序算法 - 计数排序算法 (counting Sort)
9. MT5(C++)软件编程十大排序算法 - 桶排序算法 (bucket Sort)
10. MT5(C++)软件编程十大排序算法 - 基数排序算法 (radix Sort)

1 插入排序算法
每产生一个新的无序元素就和前面排序好的元素进行重新排序
arr: 需要排序的数组
seq: 排序的方向, true 为升序, false为降序

template <typename T>
void insertSort(T & arr[],const bool seq=true)
{
  if(typename(arr) == "int" || typename(arr) == "double")
  {
    int size = ArraySize(arr);
    int insertIndex = 0;
    if(seq)
    {
      for(int i=0; i<size;i++)
      {
        insertIndex = i;
        while(insertIndex >= 1)
        {
          if(arr[insertIndex - 1] > arr[insertIndex])
          swap(arr[insertIndex - 1], arr[insertIndex]);
          insertIndex--;
        }
      }
    }
    else
    {
      for(int i=0; i<size;i++)
      {
        insertIndex = i;
        while(insertIndex >= 1)
        {
          if(arr[insertIndex - 1] < arr[insertIndex])
          swap(arr[insertIndex - 1], arr[insertIndex]);
          insertIndex--;
        }
      }
    }
    
  }
  
}

2折半插入排序算法
每产生一个新的无序元素就和前面排序好的元素进行重新排序
arr: 需要排序的数组
seq: 排序的方向, true 为升序, false为降序

template <typename T>
void insertSortBS(T & arr[],const bool seq=true)
{
  if(typename(arr) == "int" || typename(arr) == "double")
  {
    int size = ArraySize(arr);
    int insertIndex = 0;
    if(seq)
    {
      for(int i = 1; i < size ; i++)
      {
        int left = 0;
        int right = i;
        int temp = arr[i];
        while(left < right)
        {
         int mid = left + ((right - left) >> 1);
         if(arr[mid] > temp) right = mid;
         else left = mid + 1;
        }
        for(int j = i; j > left; j--) arr[j] = arr[j - 1];
        arr[left] = temp;
      }
    }
    else
    {
      for(int i = 1; i < size ; i++)
      {
        int left = 0;
        int right = i;
        int temp = arr[i];
        while(left < right)
        {
         int mid = left + ((right - left) >> 1);
         if(arr[mid] < temp) right = mid;
         else left = mid + 1;
        }
        for(int j = i; j > left; j--) arr[j] = arr[j - 1];
        arr[left] = temp;
      }
    }
    
  }
  
}