数据结构之常见排序算法的实现

常见排序算法的实现

插入排序基本思想：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列

直接插入排序

    当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
代码实现：

void InsertSort(int* a, int n) {
    // [0,end]有序，把end+1位置的插入到前序序列
    // 控制[0,end+1]有序
    for (int i = 0; i < n - 1; i++)
    {
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            if (tmp < a[end])//如果小于则将a[end]复制覆盖到后一位，tmp保存被覆盖的值
            {
                a[end + 1] = a[end];
            }
            else
            {
                break;
            }

            --end;//每次都往前比较
        }

        a[end + 1] = tmp;//将tmp保存值插入比它小的值的前面一位
    }
}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
5. 代码实现

6. void ShellSort(int* a, int n) {
       int gap = n;
       while (gap > 1)//当gap<=1则说明已经进行了最后的插入排序
       {
           gap = gap / 3 + 1;//gap每次缩小相应倍数，使得排序越来越接近有序，
           //+1使得gap最后一次排序为直接插入排序

           for (int i = 0; i < n - gap; ++i)
           {
               int end = i;//end为该次排序起始位置下标
               int tmp = a[end + gap];//每次间隔gap个位置进行比较
               
               while (end >= 0)//此处为直接插入思想
               {
                   if (tmp < a[end])
                   {
                       a[end + gap] = a[end];
                       end -= gap;
                   }
                   else
                   {
                       break;
                   }
               }
               //
               a[end + gap] = tmp;
           }
       }
   }希尔排序的特性总结：
   稳定性：不稳定
   希尔排序是对直接插入排序的优化。
   当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。*
   希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定