排序篇(一)----插入排序

1.直接插入排序

插入排序的思想:

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

你可以想像成打牌一样,比如说斗地主,一张一张的摸牌,然后把手上的这些牌变成手续的排列.

具体步骤如下：

1. 将第一个元素视为已排序的序列，将第二个元素与已排序序列进行比较，找到合适的位置插入。
   

1. 将第三个元素与已排序序列进行比较，找到合适的位置插入。
   
2. 以此类推，将后续的元素与已排序序列进行比较并插入。
   
3. 最终得到一个完整的有序序列。
   

假设现在有一组数据需要排序:

初始序列：5 2 4 6 1 3

1. 将第一个元素5视为已排序序列，不需要进行比较，直接插入。
   

已排序序列：5

未排序序列：2 4 6 1 3

1. 将第二个元素2与已排序序列进行比较，找到合适的位置插入。
   

已排序序列：2 5

未排序序列：4 6 1 3

1. 将第三个元素4与已排序序列进行比较，找到合适的位置插入。
   

已排序序列：2 4 5

未排序序列：6 1 3

1. 将第四个元素6与已排序序列进行比较，找到合适的位置插入。
   

已排序序列：2 4 5 6

未排序序列：1 3

1. 将第五个元素1与已排序序列进行比较，找到合适的位置插入。
   

已排序序列：1 2 4 5 6

未排序序列：3

1. 将最后一个元素3与已排序序列进行比较，找到合适的位置插入。
   

已排序序列：1 2 3 4 5 6

未排序序列：空

最终得到有序序列：1 2 3 4 5 6

int arr[] = { 5, 2, 4, 6, 1, 3};
InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
//直接插入排序
void InsertSort(int* a, int n)
{
    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 + 1] = a[end];
                end--;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

1. 外部循环从第一个元素迭代到倒数第二个元素。
   
2. 在每次迭代中，定义一个变量end，它的初始值为当前外部循环的索引i。
   
3. 定义一个变量tmp，用于存储下一个待插入的元素，即a[end+1]。
   
4. 在内部循环中，从end开始向前遍历数组，比较tmp与当前元素a[end]的大小。
   
5. 如果tmp小于a[end]，则将a[end]向后移动一位，即a[end+1] = a[end]，并将end减1。
   
6. 重复步骤4和步骤5，直到找到tmp应该插入的位置，即tmp大于等于a[end]。
   

1. 将tmp插入到正确的位置，即a[end+1] = tmp。
   
2. 重复步骤1到步骤7，直到所有元素都被排序。
   

2.希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：

先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
   
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
   

会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

1. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的
   

4.希尔排序的时间复杂度都不固定：

我们这里的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按 照： O(N^1.3)来算.

简而言之希尔排序就是在上面的直接插入排序上加入了预排序,巧妙的就是当gap为1的时候,其实走的就是直接插入排序,可以说希尔排序是直接插入排序的升级版本.

//希尔排序(便于理解版)
void ShellSort1(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        //gap /= 2;
        gap = gap / 3 + 1;
        for (int j = 0; j < gap; j++)
        {
            for (int i = j; i < n - gap; i += gap)
            {
                int end = i;
                int tmp = a[end + gap];
                while (end >= 0)
                {
                    if (tmp < a[end])
                    {
                        a[end + gap] = a[end];
                        end -= gap;
                    }
                    else
                    {
                        break;
                    }
                }
                a[end + gap] = tmp;
            }
        }
    }
}
//希尔排序(少一层循环版)
void ShellSort2(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        //gap /= 2;
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; i++)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                    break;
            }
            a[end + gap] = tmp;
        }
    }
}

代码详解:

ShellSort1版本的希尔排序算法：

1. 首先，初始化一个间隔值gap为数组的长度n。
   

在一个循环中，当间隔值大于1时，执行以下操作： a. 将间隔值gap除以3并加1，得到新的间隔值gap。 b. 在一个嵌套循环中，从0到gap-1，对每个间隔进行插入排序：

• 从当前间隔值的位置开始，向后遍历数组，每次以间隔值gap递增。
  
• 对于每个位置i，将其作为插入排序的起始位置，将a[i+gap]作为待插入的元素tmp。
  
• 在内部循环中，从当前位置向前遍历，比较tmp与当前元素a[end]的大小。
  
• 如果tmp小于a[end]，则将a[end+gap]的值更新为a[end]，并将end减去间隔值gap。
  
• 如果tmp大于等于a[end]，则跳出内部循环。
  
• 将tmp插入到正确的位置，即a[end+gap] = tmp。
  

1. 重复步骤2，直到间隔值gap为1，完成整个排序过程。
   

ShellSort2版本的希尔排序算法：

1. 首先，初始化一个间隔值gap为数组的长度n。
   

在一个循环中，当间隔值大于1时，执行以下操作： a. 将间隔值gap除以3并加1，得到新的间隔值gap。 b. 在一个嵌套循环中，从0到n-gap-1，对每个间隔进行插入排序：

• 从当前位置i开始，将其作为插入排序的起始位置，将a[i+gap]作为待插入的元素tmp。
  
• 在内部循环中，从当前位置向前遍历，比较tmp与当前元素a[end]的大小。
  
• 如果tmp小于a[end]，则将a[end+gap]的值更新为a[end]，并将end减去间隔值gap。
  
• 如果tmp大于等于a[end]，则跳出内部循环。
  
• 将tmp插入到正确的位置，即a[end+gap] = tmp。
  

1. 重复步骤2，直到间隔值gap为1，完成整个排序过程。
   

这两个版本的希尔排序算法的区别在于内部循环的起始位置不同，ShellSort1从j开始，每次以间隔值gap递增，而ShellSort2从0开始，每次以1递增。