实验四 查找和排序算法实现

开课实验室：计算机科学与工程实验(电子楼)       2020年12月31日

学院	计算机科学与网络工程学院		年级、专业、班	网络工程194	姓名	jwt	学号
实验课程		数据结构实验					成绩
实验项目		实验四 查找和排序算法实现					指导老师

一、实验目的

1、各种排序算法的实现

2、各种查找算法实现

二、使用仪器、器材

微机一台

操作系统：Win10

编程软件：C++

三、实验内容及原理

1、各种排序算法的实现

用随机函数生成 16 个 2 位正整数(10~99)，实现插入排序、希尔排序、冒泡排序、

快速排序、选择排序、堆排序、二路归并排序等多种排序算法，输出排序中间过程、统计关键字的比较次数和记录的移动次数。

思路：

直接插入排序：

假设把数组分为两部分，一部分是初始时是R1[1]，另一部分是R2[2……n-1],每次将R2的第一个元素抽出来与R1中的数进行比较，找到合适的位置插入，然后把这个元素加入R1，依次循环直到R2的数组为空。

折半插入排序：

与直接插入类似，只不过在寻找插入位置时采用了折半方法。

希尔排序：

设置初始增量为n/2（n为数组长度），将数组划分为n/2个小数组,然后对每个小数组进行直接插入排序，一轮结束后，再将增量/2，重复上述步骤，直至增量=0，即排序完成。

冒泡排序：

设置双重循环，相邻元素之间比较大小根据大小进行移动。并添加标志，如果剩下的序列中没有元素发生移动，则表明数组元素已排序完成，可以提前退出。

快速排序：

初始时，将数组的第一个元素作为标记，然后扫描数组，将比标记小的数移到标记左边，比数组大的数移到标记右边，最后返回标记的位置；所以以标记为中心，数组被划分为了两部分，假设为左右子表，接着对左右子表用递归方式重复上述步骤即可完成排序。

选择排序：

设置双重循环，初始时假设第一个元素是最小值，向后扫描找是否有比第一个更小的元素，如果有则记录它的下标，直到找到真正的最小值，然后把最小值和第一个元素交换位置；第二趟排序则设第二个元素是最小值，重复上述步骤，即可完成排序。

堆排序：

将数组看作是一棵完全二叉树的顺序存储结构。初始时，需要构建大根堆。由完全二叉树性质可得，序号大于n/2的结点都是叶子结点，叶子结点满足堆，所以只需要对序号小于n/2的这部分结点进行筛选调整。之后再反复重建堆即可完成排序。

归并排序：

初始时，设数组分为n个 部分，所以每个部分都是有序的；每一趟排序将两两小数组合并（合并时要比较大小进行排序）；最后合并得到一个数组即为有序数组，完成排序。

2、各种查找算法实现

(1) 顺序查找：使用数组或链表结构。用随机函数生成 16 个不重复的字母(’a’~’z’)，

键盘输入待查找的字母，返回查找成功与否，若成功则返回该字母所在的位置(序号)，

并计算比较次数。

(2) 折半查找：用数组实现，查找前元素先排序。计算比较次数。分别用查找成功、

不成功进行测试。

(3) 二叉查找树：手工输入 10 个字母，生成一棵二叉查找树，用递归算法打印树结

构或分别输出先序和中序遍历序列以确认其结构。键盘输入待查找的字母，计算比较次数，并删除该字母。分别用查找成功、不成功进行测试。

思路：

顺序查找：

要获得16个随机不重复的字母，可以先定义一个数组存放26个英文字母（顺序从a-z），然后生成随机下标，再定义一个标记数组，已访问过的元素进行标记，避免产生重复下标，把随机下标得到的字母依次赋予一个新数组，即可得到16个不重复的随机字母。生成数组后，查找即从数组第一个元素开始逐个比较，找到后返回相应下标。

折半查找：

因为上边定义了26个字母的有序数组，所以可以直接用来做折半查找。折半字面意思，对半折，从数组中间开始比较，如果需查找值比中间值大，则在中间值右边继续找，重复上述步骤，直至找到该元素；如果需查找值比中间值小，则在中间值左边继续找，重复上述步骤。

二叉查找树：

利用递归方式构建一棵二叉查找树，使得左子树所有结点都比根节点小，右子树所有结点都比根节点大。再用递归方式先序和中序遍历确认树结构。查找时，通过与根节点比较大小即可分别对应进入左右子树，依次递归，直至找到该元素。删除操作：要判断删除结点的子树情况：若左右子树均不为空，则在被删结点的左子树中找到最右边的结点，把该结点提上来（实际操作中将被删结点赋予新值，删除左子树最右边的结点即可）；若只有左子树，直接把左子树提上来；若只有右子树，直接把右子树提上来（还需要判断被删结点是前驱结点的左孩子还是右孩子，若为根节点则直接挂接子树）然后删除结点。

四、实验过程原始数据记录

直接插入排序

void InsertSort(int arr[], int n)                       //直接插入排序
{
    int i, j;
    compare_count = 0;				//关键字比较次数
    remove_count = 0;					//关键字移动次数
    process = 1;                //中间过程
    for (i = 2; i  
折半插入排序 
void BInsertSort(int arr[],int n)                       //折半插入排序
{
    int i, j, low, high, m;
    compare_count = 0;				//关键字比较次数
    remove_count = 0;					//关键字移动次数
    process = 1;                //中间过程
    for (i = 2; i < n; ++i)
    {
        ++compare_count;
        if (arr[i] < arr[i - 1])
        {
            arr[0] = arr[i];          					//将待插入的记录暂存到监视哨中
            ++remove_count;
            low = 1; high = i;        				    //置查找区间初值
            while (low <= high)
            {											//在r[low..high]中折半查找插入的位置
                m = (low + high) / 2;             		//折半
                ++compare_count;
                if (arr[0] < arr[m])                    //插入点在前一子表
                    high = m - 1;
                else                                    //插入点在后一子表
                    low = m + 1;
            }
            for (j = i - 1; j >= high + 1; --j)         //记录后移
            {
                arr[j + 1] = arr[j];
                ++remove_count;
            }
            arr[high + 1] = arr[0];						//将r[0]即原r[i]，插入到正确位置
            ++remove_count;
        }
        cout << "第" << process++ << "次排序的中间过程： ";
        DisArr(arr);                                    //输出数组元素
        cout << endl;
    }
    cout << "关键字比较次数： " << compare_count << "t" << "记录移动次数： " << remove_count << endl;
}
 
希尔排序 
void ShellSort(int arr[], int n)                    //希尔排序
{
    int i, j, d;
    d = n / 2;                                      //增量初始值
    compare_count = 0;				//关键字比较次数
    remove_count = 0;					//关键字移动次数
    process = 1;                //中间过程
    while (d > 0)
    {
        for (i = d+1; i < n; ++i)                     //对所有组进行直接插入排序
        {
            ++compare_count;
            if (arr[i] < arr[i - d])
            {
                arr[0] = arr[i];                            //将待插入的记录暂存到监视哨中
                ++remove_count;
                j = i - d;                       
                for (j; (arr[0] < arr[j])&&(j>0) ; j = j - d)     //从后向前寻找插入位置，逐个后移，空出插入位置
                {
                    ++compare_count;
                    arr[j + d] = arr[j];
                    ++remove_count;
                }
                ++compare_count;                        //上一个for循环最后一步判断条件不成立后不执行++compare_count，这里补上一次比较
                arr[j + d] = arr[0];                        //插入正确位置
                ++remove_count;
            }
        }
        d = d / 2;                                  //减小增量
        cout << "第" << process++ << "次排序的中间过程： ";
        DisArr(arr);                                //输出数组元素
        cout << endl;
    }
    cout << "关键字比较次数： " << compare_count << "t" << "记录移动次数： " << remove_count << endl;
}
 
冒泡排序 
void BubbleSort(int arr[],int n)     //冒泡排序
{
    //对顺序表L做冒泡排序
    int j,m, flag;
    m = n - 1;
    flag = 1; 				        //flag用来标记某一趟排序是否发生交换
    compare_count = 0;				//关键字比较次数
    remove_count = 0;					//关键字移动次数
    process = 1;                //中间过程
    while(m&&flag)
    {
        flag = 0;           				//flag置为0，如果本趟排序没有发生交换，则不会执行下一趟排序
        for (j = 1; j < m; ++j)
        {
            ++compare_count;
            if (arr[j] > arr[j + 1])
            {
                flag = 1;					//flag置为1，表示本趟排序发生了交换
                arr[0] = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = arr[0];	    //交换前后两个记录
                remove_count += 3;
            }
        }
        --m;
        if (flag == 0)
        {
            cout << "关键字比较次数： " << compare_count << "t" << "记录移动次数： " << remove_count << endl;
            return;
        }
        else
        {
            cout << "第" << process++ << "次排序的中间过程： ";
            DisArr(arr);
            cout << endl;
        }
    }  
}
 
快速排序 
int Partition(int arr[], int low, int high)//划分
{
    //对顺序表L中的子表r[low..high]进行一趟排序，返回枢轴位置
    arr[0] = arr[low];                    	//用子表的第一个记录做标记
    ++remove_count;
    while (low < high)
    {										//从表的两端交替地向中间扫描
        while (low < high && arr[high] >= arr[0])
        {
            ++compare_count;
            --high;
        }
        ++compare_count;                     //上一个while循环最后一次不满足条件时也进行了比较但没有执行++compare_count，这里补上一次
        arr[low] = arr[high];					//将比标记记录小的记录移到左边
        ++remove_count;
        while (low < high && arr[low] <= arr[0])
        {
            ++compare_count;
            ++low;
        }
        ++compare_count;                     //上一个while循环最后一次不满足条件时也进行了比较但没有执行++compare_count，这里补上一次
        arr[high] = arr[low];					//将比标记记录大的记录移到右边
        ++remove_count;
    }
    arr[low] = arr[0];						//标记记录到位
    ++remove_count;
    cout << "第" << process++ << "次排序的中间过程： ";
    DisArr(arr);
    cout << endl;
    return  low;							//返回标记位置
}
void QuickSort(int arr[], int low, int high)        //快速排序
{	
    int i;
    if (low < high)
    {										
        i = Partition(arr, low, high); 		//将arr[low..high]一分为二，i是标记位置
        QuickSort(arr, low, i - 1);				//对左子表递归排序
        QuickSort(arr, i + 1, high);        	//对右子表递归排序
    }
}
 
选择排序 
void SelectSort(int arr[],int n)                  //选择排序
{
    //对顺序表L做简单选择排序
    int i, j, temp;                 //假设arr[temp]为最小
    compare_count = 0;				//关键字比较次数
    remove_count = 0;					//关键字移动次数
    process = 1;                //中间过程
    for (i = 1; i < n-1; ++i)
    {  												//在arr[] 中选择关键字最小的记录
        temp = i;
        for (j = i + 1; j <=n-1; ++j)
        {
            ++compare_count;
            if (arr[j] < arr[temp])
                temp = j;			//temp指向此趟排序中关键字最小的记录
        }
        if (temp != i) 
        { 
            arr[0] = arr[i]; 
            arr[i] = arr[temp]; 
            arr[temp] = arr[0]; 
            remove_count += 3;
        } //交换r[i]与r[k] 
        cout << "第" << process++ << "次排序的中间过程： ";
        DisArr(arr);
        cout << endl;
    }
    cout << "关键字比较次数： " << compare_count << "t" << "记录移动次数： " << remove_count << endl;
}
 
堆排序 
void sift(int arr[], int low, int high)             //筛选
{
    int i = low, j = 2 * i;                         //根据完全二叉树性质，i的孩子为2*i和2*i+1
    arr[0] = arr[i];
    ++remove_count;
    while (j <= high)
    {
        ++compare_count;
        if (j < high && arr[j] < arr[j + 1])         //若右孩子比较大  
            ++j;
        ++compare_count;
        if (arr[0] < arr[j])                          //将arr[j]调整到双亲结点位置上
        {
            arr[i] = arr[j];
            ++remove_count;
            i = j;                                     //修改i和j，以便向下筛选
            j = 2 * i;
        }
        else
            break;
    }
    arr[i] = arr[0];                                    //被筛选结点放入最终位置上
    ++remove_count;
}

void HeapSort(int arr[], int n)             //堆排序
{
    int i;
    compare_count = 0;				//关键字比较次数
    remove_count = 0;					//关键字移动次数
    process = 1;                //中间过程
    for (i = n / 2; i >= 1; --i)       //建立初始堆，调用sift算法（n/2）（向下取整）次
        sift(arr, i, n);
    for (i = n; i >= 2; i--)
    {
        arr[0] = arr[i];
        arr[i] = arr[1];
        arr[1] = arr[0];
        remove_count += 3;
        sift(arr, 1, i - 1);
        cout << "第" << process++ << "次排序的中间过程： ";
        DisArr(arr);
        cout << endl;
    }
    cout << "关键字比较次数： " << compare_count << "t" << "记录移动次数： " << remove_count << endl;
}
 
二分归并排序 
int ct = 0,length=16;//想着用来判断合并次数和长度的关系输出排序过程，结果不行……
void Merge(int arr[], int temp[], int low,int mid, int high)       //合并
{
   int i = low,j=mid+1,k=low;
   while (i <= mid && j <= high)        //将arr中的记录从小到达放入temp中
   {
       ++compare_count;
       if (arr[i] <= arr[j])
       {
           ++remove_count;
           temp[k++] = arr[i++];
       }
       else
       {
           ++remove_count;
           temp[k++] = arr[j++];        
       }
   }
   while (i <= mid)                     //若arr[j……high]已遍历完，则将arr[i,mid]复制到temp中
   {
       ++remove_count;
       temp[k++] = arr[i++];
   }
   while (j <= high)                    //若arr[i,mid]已遍历完，则将arr[j……high]复制到temp中
   {
       ++remove_count;
       temp[k++] = arr[j++];
   }
   ++ct;
}

void MergeSort(int arr[], int temp[], int low, int high)        //二分归并排序
{
    int s[17];
    if (low == high)
        temp[low] = arr[low];
    else
    {
        int mid = (low + high) / 2;             //将当前序列一分为二
        MergeSort(arr, s, low, mid);            //对分裂点的左边序列递归归并排序，结果放入S[low……mid]
        MergeSort(arr, s, mid + 1, high);       //对分裂点的右边序列递归归并排序，结果放入S[mid+1……high]
        Merge(s, temp, low, mid, high);         //合并S[low……mid]和S[mid+1……high]
        if (ct==length/2 )
        {
            cout << "第" << process++ << "次排序的中间过程： ";
            DisArr(temp);
            cout << endl;
            length /= 2;
            ct = 0;
        }
    }
}
 
顺序查找 
int SeqSearch(char str[], int n, char ch)//顺序表查找
{
	int i = 0;//ct统计比较次数
	for (i; i < n; ++i)
	{
		++ct;//次数+1
		if (str[i] == ch)//找到该元素，返回下标
			return i + 1;//设数组元素位置从1开始
	}
	cout << "数组中没有该元素！" << endl;
	return -1;//若没找到则返回-1
}
 
折半查找 
int BinSearch(char str[], int n, char ch)
{
	ct = 0;
	int low = 0, high = n - 1, mid;
	while (low <= high)
	{
		++ct;
		mid = (low + high) / 2;
		if (str[mid] == ch)
			return mid + 1;
		else if (str[mid] > ch)	//如果比中间值小，则在中间值左边查找
			high = mid - 1;		//更新high
		else                    //如果比中间值大，则在中间值右边查找
			low = mid + 1;		//更新low
	}
	cout << "数组中没有该元素！" << endl;
	return -1;//若没找到则返回-1
}
 
二叉查找树 
bool InsertBST(BiTree& bt, char ch)//在二叉查找树中插入新结点
{
	if (bt == NULL)					//创建新结点
	{
		bt = new BiNode;
		bt->c = ch;
		bt->lchild = bt->rchild = NULL;
		return true;
	}
	else if (bt->c == ch)
	{
		cout << "已存在该元素，请重新输入!" << endl;
		return false;
	}
	else if (ch < bt->c)
		return InsertBST(bt->lchild, ch);
	else
		return InsertBST(bt->rchild, ch);
}
BiTree CreateBST(BiTree& bt)
{
	bt = NULL;
	char ch;
	for (int i = 0; i < 10; ++i)
	{
		cout << "请输入第" << i + 1 << "个字母:  ";
		cin >> ch;
		if (!InsertBST(bt, ch))//如果输入的数据重复，--i使得可以重新输出第i个字母；不重复则正常插入
			--i;
	}
	cout << endl;
	return bt;
}
BiTree SearchBST(BiTree bt, char ch)//二叉排序树的查找
{
	++ct;
	if (bt == NULL || bt->c == ch)
		return bt;
	if (ch < bt->c)					//ch比根节点值小
		return SearchBST(bt->lchild, ch);
	else							//ch比根节点大
		return SearchBST(bt->rchild, ch);
}
bool DeleteBST(BiTree& bt, char ch)
{
	//从二叉排序树T中删除关键字等于ch的结点
	BiTree p = bt;
	BiTree f = NULL;                     			//初始化
	BiTree q, s;
	while (p)
	{
		if (p->c == ch) break;  	      	//找到关键字等于ch的结点*p，结束循环
		f = p;                                			//*f为*p的双亲结点
		if (ch < p->c)  p = p->lchild;     	//在*p的左子树中继续查找
		else p = p->rchild;  	                  		//在*p的右子树中继续查找
	}//while
	if (!p)
		return false;                         		//找不到被删结点则返回
	q = p;
	if ((p->lchild) && (p->rchild))
	{     		//被删结点*p左右子树均不空
		s = p->lchild;
		while (s->rchild)                			//在*p的左子树中继续查找其前驱结点，即最右下结点
		{
			q = s;
			s = s->rchild;
		}	         		//向右到尽头
		p->c = s->c;               			//q指向被删结点的“前驱”
		if (q != p)								//如果p的左孩子有右子树
			q->rchild = s->lchild;     	//重接*q的右子树
		else
			q->lchild = s->lchild;        		//重接*q的左子树
		delete s;
		return true;
	}//if
	else if (!p->rchild)                		//被删结点*p无右子树，只需重接其左子树
		p = p->lchild;
	else if (!p->lchild) 					//被删结点*p无左子树，只需重接其右子树
		p = p->rchild;
	if (!f)
		bt = p;                       		//被删结点为根结点
	else if (q == f->lchild)
		f->lchild = p;   					//挂接到*f的左子树位置
	else
		f->rchild = p;                 		//挂接到*f的右子树位置
	delete q;
	return true;
}
 
五、实验结果及分析 
 
定义两个数组，数组1用于固定存储随机值，数组2复制数组1，然后用数组2进行排序测试。
 
先显示随机数组（方便比对），调用直接插入排序函数，每一趟排序都输出一次数组（即中间过程），最后再输出关键字比较次数、记录的移动次数以及排序后的数组。后边几幅图类似（最后一行有显示用了何种排序）
 
每次排序前重新对数组2赋值（复制数组1），为了可以比对各个排序算法的差别以及关键字比较次数、记录移动次数等。测试结果均正确。
 
 
 
 
归并排序用了递归归并的方法，所以中间过程前两趟输出有问题，因为它先对左子序列进行归并，再对右子序列进行归并，然后得到长度各一半的左右有序序列，最后一趟将两序列归并得到有序序列。递归方式的中间过程想不出来如何输出了……但比较次数和记录移动次数都正确，数组也能排出正确的序列。
 
 
先输出生成的16个随机不重复的字母，然后输入要查询的字母，调用顺序查找函数，输出该字母所在位置，并输出比较次数
 
折半查找用的是26个有序的字母表。输入要查询的字母，调用折半查找函数，输出该字母所在位置，并输出比较次数
 
先创建一个二叉查找树，输入10个不同的字母。然后先序遍历、中序遍历二叉树确定二叉树的结构。输入要查找的字母，调用查找函数，成功了，输出比较次数。然后输入要删除的字母，调用删除函数，提示删除成功，再次先序、中序遍历二叉树，确认已删除成功。
 
 
 
总结 
因为我用的是普通数组，所以在循环语句边界时要注意，防止数据溢出导致输出异常。只要调整好循环次数即可。
输出中间过程、统计关键字的比较次数以及记录的移动次数要注意统计语句放到哪里，否则统计不正确。
二叉查找树删除结点要注意判断被删除结点的孩子情况，并且要有指针指向前驱结点和被替换结点的前驱。
遇到的问题：二分归并排序用了递归方式，暂时想不到方法出输出中间排序过程……
Pass：仅作为实验参考，有些地方可能不够完善，见谅一下。转载请注明出处！