整理了常用的一些算法：
一，冒泡排序
冒泡排序（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);
}
