一、 实验目的

（1） 掌握直接插入、简单选择排序算法的思想；
（2） 掌握各排序算法的程序实现。

二、 实验环境

Windows 7以上版本的操作系统，Visual Studio 2010以上版本编程环境。

三、 实验内容和步骤

• 根据直接插入排序和简单选择排序的算法思想，分别写出序列{30,20,50,40,25}的直接插入排序和简单选择排序的变化过程，并标示出每趟排序的有序区范围，然后使用目录sort下的文件sort.cpp验证排序结果。
  直接插入排序：将元素集合分成有序区和无序区两部分。每趟排序取出无序区中第一个元素，对有序区按从后向前的顺序查找其插入位置，直到全部数据元素都插入到有序区中为止。
  直接插入排序：
  
  简单选择排序：将元素集合分成有序区和无序区两部分。每趟排序从无序区中选取出关键字最小的元素同无序区的第一元素交换，直到全部数据元素排序完毕。
  简单选择排序：
  

2. 使用目录sort下的文件sort.cpp，对序列{52, 49, 80, 36, 14, 58, 61, 23, 97, 75}分别用直接插入和简单选择的排序方法进行排序。
   1)在main()函数中调用函数InsertSort(A,10);在InsertSort函数中设置断点①（每趟排序前）和断点②（每趟排序后），按“F5”调试程序，每次暂停后在断点①处观察i和j的值，在断点②处观察j和j+1的值。通过填写第1，5，7次排序过程中的数据回答下列问题。

• 设待排序数据长度为n，第i趟排序过程中，有序区的范围是 0~i-1 （用下标表示），无序区的范围是 i~n-1 （用下标表示）
• 第i趟排序过程中，待插入元素的下标是 i
• 第i趟排序在查找待插入元素的插入位置时，查找的起始位置下标是 i-1 ，待插入元素的最终插入位置下标是 j+1
  

3. 使用目录sort下的文件sort.cpp，对序列{52, 49, 80, 36, 14, 58, 61, 23, 97, 75}分别用直接插入和简单选择的排序方法进行排序。
   2)在main()函数中调用函数SelectSort(A,10);在SelectSort函数中设置断点③（每趟排序前）和断点④（每趟排序后），按“F5”调试程序，每次暂停后在断点③处观察i、 j和min的值，在断点④处观察min的值。通过填写第0，1，5次排序过程中的数据回答下列问题。

• 第i趟排序过程中，无序区第一个元素的下标是 i
• 第i趟排序后，最小值的最终存放位置下标是 i
  

4. 在直接插入排序中，插入位置是通过在有序区从后向前依次比较得出的。考虑到有序区中的元素已经排好序，也可以利用折半查找的方法寻找插入位置。折半查找成功时，插入位置为mid+1，查找失败时，插入位置为low或high+1。这种排序算法称为折半插入排序。
   请参考课本P370的相关内容，实现折半插入排序并在程序中验证：
   void BinInsertSort(int Array[], int length)

void BinInsertSort(int Array[], int length)
{
	int i, j;
	int tmp;
	int low, high, mid, pos;  // pos为插入位置
	for (i = 1; i < length; i++)
	{
		tmp = Array[i];  // 待插入元素暂存到tmp
		low = 0;       // 折半查找区间上界
		high = i - 1;  // 折半查找区间下界
		while (low <= high)
		{
			mid = (low + high) / 2;
			if (Array[mid] == Array[i])
			{
				pos = mid + 1;  // 查找成功，mid+1为插入位置
				break;
			}
			else if (Array[i] < Array[mid])
			{
				high = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
		}
		if (low > high)
		{
			pos = low;  // 查找失败，low为插入位置。 或high+1
		}
		for (j = i - 1; j >= pos; j--)
		{
			Array[j + 1] = Array[j];  // 向后移动元素
		}
		Array[pos] = tmp;  // 插入元素

		Output();
	}
}

4. 利用目录ListInArray下提供的顺序表实现文件listinarray.cpp和listinarray.h建立项目，并对该顺序表添加直接插入排序接口和简单选择排序的接口。
   1)函数原型：//插入排序
   void InsertSort(SqList &L);
   //选择排序
   void SelectSort(SqList &L);
   2)利用下面主函数进行测试：

#include "listinarray.h"

int main()
{
  ElemType A[] = {52, 49, 80, 36, 14, 58, 61, 23, 97, 75};
  SqList my_list;
  InitList(my_list);

  //在my_list的尾部依次插入数组元素
  for (int i = 0; i < 10; i++)
    ListInsert(my_list, i + 1, A[i]);

  cout << "顺序表中元素：";
  TraverseList(my_list);

  //InsertSort(my_list);
  //SelectSort(my_list);

  cout << "顺序表排序后：";
  TraverseList(my_list);
  return 0;
}

四、 小结

1. 排序算法的思想。
   直接插入排序：将元素集合分成有序区和无序区两部分。每趟排序取出无序区中第一个元素，对有序区按从后向前的顺序查找其插入位置，直到全部数据元素都插入到有序区中为止。（初始有序区长度为1）
   简单选择排序：将元素集合分成有序区和无序区两部分。每趟排序从无序区中选取出关键字最小的元素同无序区的第一元素交换，直到全部数据元素排序完毕。（初始有序区空）
2. 排序算法的实现过程。
   掌握实现过程中两个循环的作用，以及有序区和无序区的范围
3. 会用排序算法解决实际问题。