[排序算法]直接插入排序

1.基本思想

        直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

实际中我们玩扑克牌时，就用了插入排序的思想

2.直接插入排序

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

3.代码实现

// 直接插入排序函数​
// 参数a是待排序数组的指针，n是数组的元素个数​
void InsertSort(int* a, int n)​
{​
    // 外层循环：遍历从0到n - 2的元素，因为最后一个元素不需要再插入​
    for (int i = 0; i < n - 1; i++)​
    {​
        // end指向当前已排好序部分的最后一个元素​
        int end = i;​
        // 暂存当前待插入的元素，即end + 1位置的元素​
        int tmp = a[end + 1];​
        // 内层循环：从end位置开始向前比较，将大于tmp的元素向后移动​
        while (end >= 0)​
        {​
            // 如果当前end位置的元素大于tmp​
            if (a[end] > tmp)​
            {​
                // 将a[end]向后移动一个位置​
                a[end + 1] = a[end];​
                // end向前移动一个位置，继续向前比较​
                end--;​
            }​
            else​
            //end < 0时，意味着在已排序序列中，当前待插入元素tmp的值是最小的
            {​
                // 当遇到不大于tmp的元素时，说明找到了tmp的插入位置，跳出循环​
                break;​
            }​
        }​
        // 将tmp插入到正确的位置​
        a[end + 1] = tmp;​
    }​
}

4.小试牛刀

        题目链接：P1223 排队接水 - 洛谷

   4.1解题思路

        这道题的核心思路是让接水时间短的人先接水，从而使总的等待时间最短，平均等待时间也最小。

   4.2代码

        本题可使用多种排序方法，这里我使用的是插入排序：

#include<stdio.h>
//定义个人结构体
typedef struct 
{
	int number;//编号
	int time;//接水时间
}Person;
void InsertSort(Person* arr,int n)
{
	for(int i=0;i<n-1;i++)
	{
		int end=i;
		//数组中的第二个元素为待排序的对象，默认第一个元素已排序
		Person tmp=arr[end+1];
		while(end>=0)
		{
			if(arr[end].time>tmp.time)
			{
				arr[end+1]=arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end+1]=tmp;
	}
}
main()
{
	int n;//排队人数
	Person people[1001]={0};
	double total;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&people[i].time);
		//实际编号为数组编号加1
		people[i].number=i+1;
	}
	InsertSort(people,n);
	//输出队列序号
	for (int i = 0; i < n; i++)
	{
		printf("%d ",people[i].number);
	}
	//计算排队时间并输出
	for(int i=1;i<n;i++)
	{
		for(int j=0;j<i;j++)
		{
			total+=people[j].time;
		}
	}
	printf("\n%lf",total/(n));
}

5.疑难解答

     5.1为什么第一层循环结束条件为i<n-2

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

        初始时，我们可以把数组的第一个元素看作是一个已经排好序的单元素序列。从第二个元素开始，依次将每个元素插入到前面已排好序的序列中的合适位置。

        当我们处理到数组的倒数第二个元素（即索引为 `n - 2` 的元素）时，经过这一轮插入操作后，前面 `n - 1` 个元素已经是有序的了。此时，数组中只剩下最后一个元素（索引为 `n - 1` 的元素）还未插入到有序序列中。

        由于前面 `n - 1` 个元素已经有序，那么对于最后一个元素，我们只需要将它与前面 `n - 1` 个有序元素进行比较并插入到合适位置即可，不需要再进行一轮新的外层循环来处理它。所以，外层循环只需要遍历到索引为 `n - 2` 的元素，即 `for (int i = 0; i < n - 1; i++)`，这样就能保证整个数组最终被排序。

        举个例子，对于数组 `[4, 2, 1, 3]`：

        1. 初始时，把 `4` 看作已排好序的序列。

        2. 外层循环第一次，`i = 0`，将 `2` 插入到 `[4]` 中，得到 `[2, 4]`。

        3. 外层循环第二次，`i = 1`，将 `1` 插入到 `[2, 4]` 中，得到 `[1, 2, 4]`。

        4. 外层循环第三次，`i = 2`，将 `3` 插入到 `[1, 2, 4]` 中，得到 `[1, 2, 3, 4]`，此时数组已经有序，不需要再处理最后一个元素的插入了。

-------有问题欢迎私信和评论------