整理了常用的一些算法：
一，冒泡排序
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
以下代码可以直接运行：
#include <iostream> using namespace std; template<typename T> //整数或浮点数皆可使用 void bubble_sort(T arr[], int len) { int i, j; T temp; for (i = 0; i < len - 1; i++) for (j = 0; j < len - 1 - i; j++) if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } int main() { int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 }; int len = (int) sizeof(arr) / sizeof(*arr); bubble_sort(arr, len); for (int i = 0; i < len; i++) cout << arr[i] << ' '; cout << endl; float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 }; len = (int) sizeof(arrf) / sizeof(*arrf); bubble_sort(arrf, len); for (int i = 0; i < len; i++) cout << arrf[i] << ' '; return 0; }
二、快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序的思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此 对这两部分数据分别进行快速排序，整个排序过程可以 递归 进行，以此达到整个数据变成有序序列 。
以下代码可以直接运行：
#include <iostream> using namespace std; void Qsort(int arr[], int low, int high){ if (high <= low) return; int i = low; int j = high + 1; int key = arr[low]; while (true) { /*从左向右找比key大的值*/ while (arr[++i] < key) { if (i == high){ break; } } /*从右向左找比key小的值*/ while (arr[--j] > key) { if (j == low){ break; } } if (i >= j) break; /*交换i,j对应的值*/ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } /*中枢值与j对应值交换*/ int temp = arr[low]; arr[low] = arr[j]; arr[j] = temp; Qsort(arr, low, j - 1); Qsort(arr, j + 1, high); } int main() { int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24}; Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/ for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++) { cout << a[i] << ""; } return 0; }/*参考数据结构p274(清华大学出版社，严蔚敏)*/
三，桶排序
桶排序 (Bucket sort) 或所谓的箱排序 ，是一个排序算法 ，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的 排序算法 或是以递归方式继续使用桶排序进行排序）。桶排序是 鸽巢排序 的一种 归纳 结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（ Θ （ n ））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限 的影响。
以下代码可以直接运行：
#include<iostream> usingnamespace std; int a[]={1,255,8,6,25,47,14,35,58,75,96,158,657}; const int len=sizeof(a)/sizeof(int); int b[10][len+1]={0};//将b全部置0 void bucketSort(int a[]);//桶排序函数 void distribute Elments(int a[],int b[10][len+1],int digits); void collectElments(int a[],int b[10][len+1]); int numOfDigits(int a[]); void zeroBucket(int b[10][len+1]);//将b数组中的全部元素置0 int main() { cout<<"原始数组："; for(int i=0;i<len;i++) cout<<a[i]<<","; cout<<endl; bucketSort(a); cout<<"排序后数组："; for(int i=0;i<len;i++) cout<<a[i]<<","; cout<<endl; return 0; } void bucketSort(int a[]) { int digits=numOfDigits(a); for(int i=1;i<=digits;i++) { distributeElments(a,b,i); collectElments(a,b); if(i!=digits) zeroBucket(b); } } int numOfDigits(int a[]) { int largest=0; for(int i=0;i<len;i++)//获取更大值 if(a[i]>largest) largest=a[i]; int digits=0;//digits为更大值的位数 while(largest) { digits++; largest/=10; } return digits; } void distributeElments(int a[],int b[10][len+1],int digits) { int divisor=10;//除数 for(int i=1;i<digits;i++) divisor*=10; for(int j=0;j<len;j++) { int numOfDigist=(a[j]%divisor-a[j]%(divisor/10))/(divisor/10); //numOfDigits为相应的(divisor/10)位的值,如当divisor=10时,求的是个位数 int num=++b[numOfDigist][0];//用b中之一列的元素来储存每行中元素的个数 b[numOfDigist][num]=a[j]; } } void collectElments(int a[],int b[10][len+1]) { int k=0; for(int i=0;i<10;i++) for(int j=1;j<=b[i][0];j++) a[k++]=b[i][j]; } void zeroBucket(int b[][len+1]) { for(int i=0;i<10;i++) for(int j=0;j<len+1;j++) b[i][j]=0; }
四、合（归）并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
#include<iostream> using namespace std; void merge(int *data, int start, int mid, int end, int *result) { int i, j, k; i = start; j = mid + 1; //避免重复比较data[mid] k = 0; while (i <= mid && j <= end) //数组data[start,mid]与数组(mid,end]均没有全部归入数组result中去 { if (data[i] <= data[j]) //如果data[i]小于等于data[j] result[k++] = data[i++]; //则将data[i]的值赋给result[k]，之后i,k各加一，表示后移一位 else result[k++] = data[j++]; //否则，将data[j]的值赋给result[k]，j,k各加一 } while (i <= mid) //表示数组data(mid,end]已经全部归入result数组中去了，而数组data[start,mid]还有剩余 result[k++] = data[i++]; //将数组data[start,mid]剩下的值，逐一归入数组result while (j <= end) //表示数组data[start,mid]已经全部归入到result数组中去了，而数组(mid,high]还有剩余 result[k++] = data[j++]; //将数组a[mid,high]剩下的值，逐一归入数组result for (i = 0; i < k; i++) //将归并后的数组的值逐一赋给数组data[start,end] data[start + i] = result[i]; //注意，应从data[start+i]开始赋值 } void merge_sort(int *data, int start, int end, int *result) { if (start < end) { int mid = start + (end-start) / 2;//避免溢出int merge_sort(data, start, mid, result); //对左边进行排序 merge_sort(data, mid + 1, end, result); //对右边进行排序 merge(data, start, mid, end, result); //把排序好的数据合并 } } void amalgamation(int *data1, int *data2, int *result) { for (int i = 0; i < 10; i++) result[i] = data1[i]; for (int i = 0; i < 10; i++) result[i + 10] = data2[i]; } int main() { int data1[10] = { 1,7,6,4,9,14,19,100,55,10 }; int data2[10] = { 2,6,8,99,45,63,102,556,10,41 }; int *result = new int[20]; int *result1 = new int[20]; amalgamation(data1, data2, result); for (int i = 0; i < 20; ++i) cout << result[i] << " "; cout << endl; merge_sort(result, 0, 19, result1); for (int i = 0; i < 20; ++i) cout << result[i] << " "; delete[]result; delete[]result1; return 0; }
五、二分查找
int find(int x,int y,int m) //在[x,y]区间查找关键字等于m的元素下标 { int head,tail,mid; head=x;tail=y;mid=((x+y)/2);//取中间元素下标 if(a[mid]==m) return mid;//如果中间元素值为m返回中间元素下标mid if(head>tail) return 0;//如果x>y，查找失败，返回0 if(m>a[mid]) //如果m比中间元素大，在后半区间查找，返回后半区间查找结果 return find(mid+1,tail); else //如果m比中间元素小，在前半区间查找，返回后前区间查找结果 return find(head,mid-1); }
