排序算法1--插入排序

插入排序思想:每一步将一个待排序的元素，按期排序码的大小，插入到前面已经排好序的一组元素的合适位置上去，知道元素插完。
插入排序分为直接插入排序，和优化后的二分插入排序，我们先看第一种；

直接插入排序

1. 基本思想：当我们插入第i（i>=1）个元素时，前面的所有元素已经排好序，此时我们使用当前元素从后向前比较，直到找到一个小于array[i]的节点（若没有，则插在数组下标为0的地方），从下一个节点顺序后移，将array[i]插入进来。
2. 时间复杂度： O(n^2)
3. 空间复杂度： O(1)
4. 稳 定 性 ：稳定
5. 适用场景：1.数据量较小；2.基本接近有序

void InsertSort(int* arr, int _size)
{
 if (arr == NULL || _size <= 0)
   return;
 for (int idx = 1; idx < _size; ++idx)
 {
   int end = idx - 1;
   //end为插入之前最后一个节点的下标
   while (end >= 0 && arr[end] > arr[end + 1])
   {
     int tmp = arr[end + 1];//保存待插入的结点
     arr[end + 1] = arr[end];//将待插入结点之前的元素后移
     arr[end] = tmp;//插入待插入结点
     end--;
   }
 }
}

二分插入排序
基本思想：在直接插入排序的基础上进行优化，因为待插入元素之前的元素已经有序，我们没必要每个都遍历，借助而二分法的思想可以有效降低查找的时间。

void BinaryInsertSort(int *arr, int size)

{
 if (arr == NULL || size <= 0)
 
  return ;
 int index = 0;

 for (int idx = 1; idx < size; ++idx)
 
{
   int tmp = arr[idx];//保存待插入元素
  
 int left = 0;
  
 int right = idx - 1;
 
  int mid = (left&right) + ((left^right) >> 1);
   //二分法查找插入位置
  
 while (left <= right)
  
 {
     if (tmp < arr[mid])
  
   {
       right = mid - 1;
   
    index = mid;//更新插入位置
    
 }    
     
else if (tmp >= arr[mid])
   
 {
       left = mid + 1;
    
   index = mid + 1;//更新插入位置
    
 }  
   
 mid = (left&right) + ((left^right) >> 1);//缩小空间
  
 }
  
 //后移元素
 
  for (int j = idx; j > index; j--)
  
 {
     arr[j] = arr[j - 1];
   }

   //插入新元素
   arr[index] = tmp;

 }

}

下个排序算法—>希尔排序