一、前言
本篇以学生信息管理系统为背景，主要学习简单的查找与排序功能。
高级查找与排序会在接下来的文章中再做介绍，欢迎大家关注并留意博主动态。
查找主要涉及顺序查找、二分查找。
排序主要涉及直接插入排序、直接选择排序、冒泡排序。
二、查找讲解
1、顺序查找
（1）普通的顺序查找
顺序查找就是依托顺序表的存储特点：顺序存储，利用其相邻的存储位置进行查找操作。
void SqSearch(SqList L) { int i = 0; int flag = 0; cout << "请输入你要查找的学生姓名>:"; char arr[10] = "\0"; scanf("%s", arr); for (i = 0; i < L.length; i++) { if (strcmp(L.elem[i].name, arr) == 0) { flag = 1; cout << "该学生信息如下>:" << endl; OutList(L, i); break; } } if (flag == 0) cout << "未找到该学生！" << endl; }
根据函数我们可以清晰地了解到，这种普通的顺序查找方式每次循环都需要进入判断i<L.length。即这一算法需要进行两次判断，一是查找位置是否合法：i<L.length，二是该位置的元素是否是我们要查找的元素：strcmp(L.elem[i].name, arr) == 0，那么我们是否可以每次进行一次判断就得到我们想要的结果呢，答案是肯定的，请看下文“监视哨”顺序查找的介绍。
（2）“监视哨”顺序查找
“监视哨”就是在顺序表中留出一个位置，不管是头部还是尾部，每次只需要将待比较的元素与“监视哨”位置的元素比较即可，这样每次都能节省一次判断，算法如下：
int SqSearch(SqList L) { int i = 0; cout << "请输入你要查找的学生姓名>:"; char arr[10] = "\0"; scanf("%s", arr); strcpy(L.elem[0].name,arr); for (i = L.length; strcmp(L.elem[i].name, arr) != 0; i--) { ;//空语句 } return i; }
当返回值为0时，证明查找失败。
利用监视哨的方式进行查找，只需要留出一个顺序表中的位置，所带来的效率提升还是比较明显的，尤其是在数据庞大的时候。
2、二分查找
二分查找适用的是有序表，即原始数据必须有序，他的思想就是从表的中间记录开始，用给定值与中间值比较，如果相等，则查找成功，如果给定值大于或小于中间值，则在表中大于或小于的那一半中继续查找。
//二分查找 void binaryFld(SqList L) { cout << "请输入你要查找的学生学号>:"; int id = 0; cin >> id; int low = 0; int high = L.length - 1; int flag = 0; while (low <= high) { int mid = (low + high) / 2;//mid的赋值位置尤为重要 if (L.elem[mid].stu_id < id) { low = mid + 1; } else if (L.elem[mid].stu_id > id) { high = mid - 1; } else { flag = 1; cout << "你要查找的学生信息如下>:" << endl; OutList(L, mid); break; } } if (flag == 0) cout << "未找到该学生！" << endl; }
需要尤其注意的是，mid赋值的位置尤为重要，如果你不小心将mid的复制位置放在了循环外，就会引起程序错误，进入死循环。
三、排序讲解
1、直接插入排序
直接插入排序的思想是将数据分为两部分，一部分为已排序部分，另一部分为待排序部分，每次从待排序部分的第一个元素插入到已排序部分中。
//直接插入排序 void Insert_sorting(SqList &L) { int i = 0; for (i = 1; i < L.length; i++)//默认单个元素为有序，所以从第二个元素开始 { Stu t={0}; if (strcmp(L.elem[i].name,L.elem[i - 1].name)<0)比较元素大小 { t= L.elem[i]; L.elem[i]= L.elem[i - 1]; //寻找插入位置 int j = 0; for (j = i - 1; strcmp(L.elem[j].name,t.name)>0 ; j--) { L.elem[j + 1]= L.elem[j];//元素后移 } L.elem[j + 1]= t;插入元素 } } }
思想滤清后，我们得到以下步骤 ：
分析直接插入排序思想，我们需要解决的问题为三个，一是将待排序元素与已排序元素比较大小，二是寻找合适的插入位置，三是元素后移并插入。
2、直接选择排序
直接选择排序的思想就是每次从待排序数据中找到最小值，并从头开始替换。
//直接选择排序 void Choose_sorting(SqList& L) { int i = 0; int k = 0; int j = 0; Stu tmp = {0}; for (i = 0; i < L.length; i++) { k = i; for (j = i + 1; j < L.length; j++)//寻找最小值 { if (L.elem[k].stru_score > L.elem[j].stru_score) { k = j; } } if (k != i)//替换数据 { tmp = L.elem[i]; L.elem[i] = L.elem[k]; L.elem[k] = tmp; } } }
分析直接选择排序思想，我们需要解决的问题为两个，一是将寻找最小值，二是逐个替换。
3、冒泡排序
冒泡排序的思想是交换，即待排序数据依次两两比较，将较大者保持在每轮的最后一个。
这样每一轮的最大值就交换到了尾部，再进行新一轮的比较，将次大值交换到最大值的钱一个位置，依次循环进行。
void Bubbling_sorting(SqList& L) { int i = 0; int m = L.length - 1; int flag = 1; Stu tmp = { 0 }; while (m > 0 && flag == 1) { flag = 0; for (i = 0; i < m; i++) { if (L.elem[i].cpp_score > L.elem[i + 1].cpp_score) { flag = 1; tmp = L.elem[i + 1]; L.elem[i + 1] = L.elem[i]; L.elem[i] = tmp; } } --m; } }
