搜索顺序搜索//顺序搜索templateclasselemtypeintsqsearch (elemtype elem [ ]，int n，ElemType key ) intI； for(I=0； i n elem[i]！=key； I； //注意这里的循环而什么也不做的if(In ) return i； else返回- 1； )二分搜索(/折半搜索(* )1)搜索区间长度小于1 )1(lowhigh )，表示搜索失败，返回-1； 否则，进入下一步。 (2)将搜索区间的中间位置处的数据元素的下标mid (求出mid=(low high )/2 )3)区间的中间位置处的数据元素的关键字elem[mid]与预定值key进行比较，比较的结果，有以下三种可能性： 1 )如果elem[mid]=key，则表示要搜索的数据元素在mid的右侧，设为low=mid 1，继续折回检索，返回步骤13。 elem[mid]key表示要查找的数据元素位于mid的左侧，设为high=mid-1，继续进行折回搜索。 步骤1*///非递归templateclasselemtypeintbinserch (elemtype elem [ ]，int n，ElemType key ) {int low=0，high=n - 1； int mid； wile(low=high ) {mid=) lowhigh )/2； if(key==elem[mid] )返回mid； elseif(keyelem[mid] ) low=mid 1； elsehigh=mid - 1； }返回- 1； //递归templateclasselemtypeintbinsearch (elemtype elem [ ]，int low，int high，ElemType key ) {int mid； 低高度(if )返回- 1； else{mid=(lowhigh )/2； if(keyElem[mid] ) mid=Binsearch(Elem，mid 1，high，key )； elseif(keyelem[mid] ) mid=Binsearch ) elem，low，mid - 1，key )； }返回mid； //主函数# includeiostreamusingnamespacestd； int main () {int pos； inta [ ]={ 8，11，23，34，46，68，71，86 }； POS=Binserch(a，8，23 )； cout '折半搜索：' a[pos] endl； pos=sq搜索(a，8，68 )； 按cout '顺序排列：' a[pos]； 返回0； } hash搜索代码缩写
排序插入排序直接插入排序templateclasselemtypevoidstraightinsertsort (elemtype elem [ ]，int n ) {int i，j； for(intI=1； i n； I ) {ElemType e=elem[i]； for(j=I-1； j=0 e elem[j]； j--}{Elem[j1]=Elem[j]； 向后移动所有大于//E的记录(}elem[j 1]=e； //j 1是插入位置} (分割插入排序templateclasselemtypevoidbininsertsort (elemtype elem [ ]，int n ) intI，j，low，high，mid； for(I=1； i n； I )//在前面排列的序列中插入elem [1]-elem [ n-1 ] ({ elemtype e=elem [ I ] )； low=0； high=i - 1； wile(low=high ) {mid=) lowhigh )/2； if(eElem[mid] ) high=mid - 1； //查找左半子表中的else low=mid 1； //else包括e=elem[mid]的情况。 这是为了保持排序的稳定性，如果相等，则继续向后搜索。 //如果高级循环的lowhigh搜索结束，且要插入的位置为high 1或low，则low大于high下标1//，并且包含low到i-1之间的元素(包括两个端点)。 j high； j-- ) elem[j 1]=elem[j]； elem[high 1]=e； }将包含希尔排序/*n个数据元素的表拆分为d(dn )子表。 每个子表由间隔为d的数据元素组成，直接插入每个子表对其进行排序，然后将所有数据元素直接插入同一序列中，直到减小间隔d，(向上舍入d/2 ) d=1为止
入排序，由于此时表中数据元素已基本有序，所以直接插入排序的效率很高*/template<class ElemType>void ShellSort(ElemType elem[],int n) {int i, j, d = n / 2;ElemType e;while (d > 0) {for (i = d; i < n; i++) {//步长为d时的直接插入排序e=elem[i];//取下标为i的元素，与同一个表中前面的数据作比较j = i - d;while (j >= 0 && e < elem[j]) {elem[j + d] = elem[j];//将子序列中比e大的元素都后移j = j - d;}elem[j + d] = e;}d = d / 2;//缩短步长}} #include<iostream>using namespace std;int main() {int a[8] = { 8,7,6,5,4,3,2,1 };int b[8] = { 8,7,6,5,4,3,2,1 };int c[8] = { 8,7,6,5,4,3,2,1 };StraightInsertSort(a, 8);cout << "直接插入排序结果";for (int i = 0; i < 8; i++)cout<< a[i] << " ";cout << endl;BinInsertSort(b, 8);cout << "折半插入排序结果";for (int i = 0; i < 8; i++)cout << b[i] << " ";cout << endl;ShellSort(c, 8);cout << "希尔排序结果";for (int i = 0; i < 8; i++)cout << c[i] << " ";return 0;} 交换排序 冒泡排序 template<class ElemType>void Swap(ElemType &a, ElemType &b) {ElemType temp;temp = a;a = b;b = temp;}/*设数据表中有n个元素，首先第第一个元素与第二个元素（elem[1]与elem[2]）两两比较，如果elem[0]>elem[1],即发生了逆序，则交换它们两个元素，然后第二个元素和第三个元素做同样处理，重复此过程直到处理完最后两个相邻的元素，此为一趟冒泡，它将最大的关键字的数据元素移动到最后一个位置。然后进行第二趟冒泡排序，对表中前n-1个元素进行上述同一操作，其结果使整个数据表中第二大的元素移到到elem[n-2]的位置。如此最多进行n-1趟冒泡对于有n个数据元素的数据表进行冒泡排序，最多需要进行n-1次冒泡，但具体到某一个数据表上，可能不需要进行n-1趟冒泡就能完成排序在算法中增加一个标志finish，用以标识本趟冒泡过程是否发生了逆序而进行过交换。如果进行过交换，则finish为false，标识数据元素可能没有完全排好，则需要进行下一趟冒泡；如果没有进行过交换，则finish为TRUE表示全部数据已排好序*/template<class ElemType>void BubbleSort(ElemType elem[],int n) {bool fininsh = false;int i = 1;while (i < n && !fininsh) //最多n-1趟冒泡，即n-1趟循环{fininsh = true;for (int j = 0; j < n - i; j++)if (elem[j] > elem[j + 1]) {Swap(elem[j], elem[j + 1]);fininsh = false;}i++;}}//这个排序也是正确的，不是两两比较。第一次比较n-1次，比较n-1次，第n-1次比较一次//原来这个是选择排序，但是应该记录最小的位置而不是一判断逆序就交换，这样数据元素移到的次数大大增加void testSort(int a[],int n) {int i, j;for (i = 0; i < n-1; i++) {for (j = i + 1; j < n; j++)if (a[i] > a[j])Swap(a[i], a[j]);}} 快速排序 /*任取数据表中某个数据元素（如取第一个数据元素）作为基准，按照该数据元素的关键字大小，将整个数据表划分为左右两个子表；左侧子表中所有数据元素的关键字都小于或等于基准数据元素的关键字，右侧子表所有数据元素关键字都大于基准数据元素的关键字，基准数据元素排在这两个子表的中间（也是该数据元素最终应安放的位置），最后分别对这两个子表重复施行上述方法的快速排序，直到所有子表长度都为1，则排序结束。*/template<class ElemType>void QuickSort(ElemType elem[], int low, int high){ElemType e = elem[low];//第一个元素作为基准int i = low, j = high;while (i < j) {while (i<j && elem[j]>e) j--;//初始基准在左边，检查右边的元素，如果右边的元素大于基准e,不需要移动，将右边的下标左移继续与基准比较，直至右边的元素小于基准，执行下一句交换。if (i < j) elem[i++] = elem[j];//这一步右边的元素小于基准，基准与右边的元素交换，只需将基准位置赋给右边的元素即可，然后左边的元素向右移一位即i++，基准的位置还没有最终确定，假设换到了右边继续比较，此时基准在右侧while (i < j && elem[i] <= e) i++;//基准在右侧，通过i判断左侧的元素，如果左侧的元素小于基准，i++,左侧元素下标右移继续比较，直至左侧元素大于基准，应该交换，同上基准位置还不是最终位置，此时假设基准在左边，执行下一步交换操作if (i < j) elem[j--] = elem[i];//这一步左边元素大于基准，将基准的位置赋给左边i位置的元素，同时右边元素向左移一位即j--}elem[i] = e;//最终位置if (low < i - 1) QuickSort(elem, low, i - 1);//递归部分if (i + 1 < high) QuickSort(elem, i + 1, high);//递归部分} //主函数#include<iostream>using namespace std;int main() {int a[8] = { 8,7,6,5,4,3,2,1 };int b[8] = { 8,7,1,2,3,4,5,6 };int c[8] = { 8,7,6,5,4,3,2,1 };BubbleSort(a, 8);cout << "冒泡排序结果";for (int i = 0; i < 8; i++)cout << a[i] << " ";cout << endl;QuickSort(b,0,7);cout << "快速排序结果";for (int i = 0; i < 8; i++)cout << b[i] << " ";cout << endl;return 0;} 选择排序 简单选择排序 template<class ElemType>void Swap(ElemType& a, ElemType& b) {ElemType temp;temp = a;a = b;b = temp;}template<class ElemType>void SimpleSelecSort(ElemType elem[], int n) {int k;for (int i = 0; i < n - 1; i++) {k = i;for (int j = i + 1; j < n; j++)if (elem[j] < elem[k])k = j;if (k != i)//如果k不是这趟比较数据的首元素的话，则将与其交换。swap(elem[i],elem[k]);}} 堆排序 /*堆排序的思想：1）对数据表中的数据元素，利用堆的调整算法形成初始堆2）输出堆顶元素3）对剩余元素重新调整形成堆4）重复执行第2）、3）步，直到所有数据元素被输出*///堆排序的向下调整函数template<class ElemType>void FilterDown(ElemType elem[], int low, int high) { //low代表调整的起始结点，high代表数组最大下标int f = low, i = 2 * low + 1;ElemType e = elem[low];while (i <= high) { //f的左孩子i存在则执行循环体if (i < high && elem[i] < elem[i + 1])i++; //如果f的右孩子存在，且大于左孩子的值，将i赋给右孩子，保持i是最大的孩子if (elem[i] <= e)break;else {elem[f] = elem[i];f = i;i = 2 * f + 1;}}//当调整到f位叶结点，i为空时结束循环，此时f为插入位置elem[f] = e;}template<class ElemType>void HeapSort(ElemType elem[], int n){//初始建堆，将elem[0..n-1]调整成最大堆,从最后一个非叶结点开始执行FilterDown算法//最后一个非叶结点的下标为（n-2）/2int i;for (i = (n - 2) / 2; i >= 0; --i)FilterDown(elem, i, n - 1);for (i = n - 1; i > 0; i--) { //第i趟堆排序Swap(elem[0],elem[i]); //将堆顶元素和当前未经排序的子序列elem[0...i]中的最后一个元素交换FilterDown(elem,0,i-1); // 将elem[0...i-1]重新调整为最大堆}} #include<iostream>using namespace std;int main() {int a[8] = { 8,7,6,5,4,3,2,1 };int b[8] = { 8,7,1,2,3,4,5,6 };int c[8] = { 8,7,6,5,4,3,2,1 };SimpleSelecSort(a, 8);cout << "选择排序结果";for (int i = 0; i < 8; i++)cout << a[i] << " ";cout << endl;HeapSort(b, 8);cout << "堆排序结果";for (int i = 0; i < 8; i++)cout << b[i] << " ";cout << endl;return 0;}