这个我也不知道能写多少，只是最近快放假了实在懒得看DSP了,而且卡在一个地方了，什么都不干又感觉心慌的很，所以又回头看看算法的东西。一些测试程序放在这里
1.排序
正好看到分治法关于归并排序的这块，所以想把排序做一个总结。主要包括冒泡，计数，插入，选择，归并排序，堆排序和插入排序。写的时候可能没有什么顺序。
排序算法是最常用的一种算法，给定一个数组，把这个数组排序是最基本的需求，所以排序算法有很多种，性能也不移，比较快的堆排序，归并排序和快速排序，其他的都很慢。下面这个表可以看一下：
| 排序算法 | 最坏情况下的性能 | 平均性能 |
|---|---|---|
| 冒泡排序 | n^2 | n^2 |
| 计数排序 | n^2 | n^2 |
| 插入排序 | n^2 | n^2 |
| 选择排序 | n^2 | n^2 |
| 堆排序 | nlog(n) | nlog(n) |
| 归并排序 | nlog(n) | nlog(n) |
| 快速排序 | n^2 | nlog(n) |
这个是在《数据结构算法与应用-c++描述》的书上的p462，sartaj sahni著。
1.1 归并排序
因为这次我先看的归并排序，就来先写这个了，归并排序是分治法的一个典型应用，其主要思想是把数据分组排序，然后两两一组进行归并（归并的同时对这两组进行排序），直到合并成一个大的数组。
维基百科图片
这个是递归的实现，思路就是分解成单个元素，然后两两归并，无法分组的直接复制下来，直到归并成一个数组，这个时候就是一个排好序的数组了。
为了程序下标简单，我们数组下标从1开始，也就是说0位置空下来，不把数据放进去
先来写一个归并函数，就是把两个排序数组合并成一个排序数组，这个是在归并排序中要经常用到的：
l是表示第一个数组的下标起点，m表示第一个数组的最后一个数据下标，n表示第二个数组的最后一个下标。如图，要合并的是绿色和棕色的数组。
void Merge(T *initList, T *mergeList, const int l, const int m, const int n)
{
//这个是归并两个排序数组，双指针归并
int i1, i2; //双指针
int index = l; //这个是新数组的序号
for (i1 = l, i2 = m + 1; i1 <= m&&i2 <=n; index++)
{
if (initList[i1] < initList[i2])
{
mergeList[index] = initList[i1];
i1++;
}
else
{
mergeList[index] = initList[i2];
i2++;
}
}
//这两个copy最多只有一个起作用
copy(initList + i1, initList + m + 1, mergeList + index);
copy(initList + i2, initList + n + 1, mergeList + index);
}
整体也比较简单，是一个双指针合并数组的标准写法，最后用copy把没有遍历的copy过来就可以了。
上面这个只能实现对一对组合的归并，我们在进行归并的时候可能要对多组数据（这些还是存放在一个大的数组里的）进行归并，所以我们还需要写另外一个函数进行这样的归并。
template<class T>
void MergePass(T *initlist, T *result, int n, int s) //n是数据个数，s是每段个数
{
int i;
for (i = 1; i <=n-2*s+1; i += 2 * s) //这里一定是n-2*s+1，每两个一对，不成对的话就不能遍历了。
{
Merge(initlist, result, i, i + s - 1,i+2*s-1);
}
if ((i + s - 1) < n) //这是最后一次merge才会进入这个循环，也就是i=1下来的
{
Merge(initlist, result, i, i + s - 1, n);
}
else
copy(initlist + i, initlist + n + 1, result + i);
}
n是总数据的个数，s是每一段数据的个数，所以里面的for循环是一组一组进行归并，i每次增加2s,因为是两两归并，i的循环条件是<=n-2s+1这个保证i如果等于n-2s+1的时候后面还有2s个数据可以归并。
下面判断i+s-1和n的大小，如果进行了遍历，i+s-1是第一组数据最后的一个数，如果这个数小于n的话，说明已经进行到最后一次归并了，直接对大数组进行两段归并就可以了，这个时候i是等于1的（也就是说并没有进行上面的for循环，n-2s+1已经小于1了，无法分成两组等量的来进行归并）。
如果已经进行了归并，就只把后面的没有分组的复制下来就好了，注意复制的时候是左闭右开区间。
最后就是汇总的程序了，首先是以1为长度归并，然后是2，再是4，以此类推。
template<class T>
void MergeSort(T *initlist, int n)
{
T *tempList = new T[n + 1];
for (int l = 1; l < n; l *= 2)
{
MergePass(initlist, tempList, n, l);
/*copy(tempList, tempList + n + 1, initlist); */ //每次都拷贝一遍，可以重复利用
//一种更好的写法是下面这个，归并一次变换到原来的数组，而不是简单的拷贝，效率要高一些
l *= 2;
MergePass(tempList, initlist, n, l);
}
delete[] tempList;
}
因为不是原位归并，所以需要借助辅助的一个数组，可以每次归并完把数据拷贝回去，一种更好的方式是一次循环里做两次归并。不用担心万一只需要做奇数次归并怎么办，如果如此，最后一次归并实际上是做了一次复制。
归并排序就到这里了。
1.2冒泡排序
这个大概是本科上c++的课程的时候学的第一个算法，算法很简单，每次循环把最大的一个数放到最后面，就相当于冒泡一样，这样循环n次就可以对一组数进行排序：
这里有一个动图可以看一看。
int main(void) {
int a[]={7,4,9,3,1},temp;
for(int i=0;i<5;i++)
for(int j=i;j<5;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
for(int i=0;i<5;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
我从维基上直接复制过来的代码，很简单，不用多说。
1.3插入排序
插入排序也是比较简单的，每次拿出一个数，插入到已经排序好的数组中，插入的过程是一个找位置的过程，具体的过程看这个动图，我们认为数组的第一个数是已经排好序的，然后从第二个数开始验证，为这个数找一个位置。举个简单的例子。
a=[1,3,5,2,1];
对于这个数组，我们现在遍历到a[3]这个位置。
先用tmp=a[3]把a[3]存储起来，然后tmp依次和a[2],a[1],a[0]，比较，如果tmp<a[2],则把a[2]后移（a[3]=a[2]）。这个时候数组变成:
a=[1,3,5,5,1];
然后tmp再和a[1]比较,tmp依然小于a[1],则把a[1]后移，则变为：
a=[1,3,3,5,1];
然后tmp和a[0]比较，tmp>=a[0],说明这个位置就是要找的，则把a[1]这个位置赋值为tmp，则变为：
a=[1,2,3,5,1];
这样一次遍历就结束了，其他的都是这样的，注意写对遍历的序号和边界条件就行了。
template<class T>
void InsertSort(T *a, int n)
{
int i, j;
for (j = 1; j < n; j++)
{
int tmp = a[j];
cout << "tmp:" << tmp << endl; //test
i = j-1; //已排序的
while (i >= 0)
{
if (tmp < a[i])
{
a[i + 1] = a[i]; //后移
i--;
}
else
{
a[i+1] = tmp; //找到位置，赋值
break;
}
}
}
}
二分查找及其变种
-
基本二分查找
参考：你真的会写二分查找么
二分查找是一种“猜价格”的最好策略，也很好理解，每一次查找，都把范围缩小一半，直到找到要查找的元素为止，是一种非常高效的查找方式，条件是查找的目标必须是排序的。
基本的二分查找比较简单：
int Binary_Search1(vector<int> &v, int key)
{
int res=-1;
int left = 0;
int right = v.size() - 1;
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (key > v[mid])
left = mid + 1;
else if (key < v[mid])
right = mid - 1;
else
{
return mid; //找到的话返回下标
}
}
return -1; //表示没有找到
}
两点注意：
①终止条件是<=，如果不加等于，有些数据遍历不到，比如当数据是第一个数时。{1,2,3}查找1的话就会查找不到。
②left和right的更新是mid+1或者mid-1，这是因为mid已经查找过，而且不这样做的话容易引起死循环。比如当left=right时，mid等于left，这时候无论key的值如何，都会进入left=right的死循环。
如果能够保证key一定存在，查找到就可以返回，这是二分查找最简单的一种写法。
-
二分查找的变形
另外，二分查找还存在着一些变形：
比如，当存在多个值时，要求查找最后一个或者第一个，如何处理？
如果找到mid不结束循环，最终的left和right应该是满足这样的关系：left+1=right
示意图
那么，可以找到
①最后一个小于key的元素，1，
②第一个大于等于key的元素，2，
③最后一个小于等于key的元素，2，
④第一个大于key的元素，5，
另外，如果存在多个key时，稍加判断，就可以找到
⑤ 第一个与key相等的元素
⑥最后一个与key相等的元素
首先来看①--④，解决问题的关键在于上面这一张图，如果是左边的话，要求最后指向这么一种状态，那么找到的时候就不能停止查找，而是要把right=mid-1，这样可以让mid继续减少，最后达到左边的图的这一种状态，这时候选择返回left或者right就能达到不同的结果。如果是右边的话就刚好相反，我把代码直接贴到下面:
int Binary_Search2(vector<int> &v, int key); //查找最后一个小于目标的数
int Binary_Search3(vector<int> &v, int key); //查找第一个大于等于目标的数
int Binary_Search4(vector<int> &v, int key); //第一个大于目标的数
int Binary_Search5(vector<int> &v, int key); //最后一个小于等于目标的数
int Binary_Search2(vector<int> &v, int key)
{
int left = 0;
int right = v.size() - 1;
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (key > v[mid])
left = mid + 1;
else if (key <=v[mid])
right = mid - 1;
}
return right;
}
int Binary_Search3(vector<int> &v, int key)
{
int left = 0;
int right = v.size() - 1;
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (key > v[mid])
left = mid + 1;
else if (key <= v[mid])
right = mid - 1;
}
return left;
}
int Binary_Search4(vector<int> &v, int key)
{
int left = 0;
int right = v.size() - 1;
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (key >= v[mid])
left = mid + 1;
else if (key < v[mid])
right = mid - 1;
}
return left;
}
int Binary_Search5(vector<int> &v, int key)
{
int left = 0;
int right = v.size() - 1;
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (key >= v[mid])
left = mid + 1;
else if (key < v[mid])
right = mid - 1;
}
return right;
}
⑤⑥的问题其实就已经在上面了包括了，如果存在多个key值，第一个大于等于key值的元素就是第一个key值，最后一个小于等于key值得元素就是最后一个key值。
另外，如果key值本身就不存在，我们想找一个可以插入key值得位置，那么我们既可以找最后一个小于等于key值的索引，插到其后，也可以找第一个大于key值得索引，插到它前面。
理解了这些再去看二分插入简直不要太简单，看这个题：最长上升子序列
未完待续
网友评论