首页 > 代码库 > 十大基础实用算法之归并排序和二分查找
十大基础实用算法之归并排序和二分查找
归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
算法步骤：
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾
用分治策略解决问题分为三步：分解、解决、合并。也即：将原问题划分成n个规模较小而结构与原问题相似的子问题； 递归地解决这些子问题，然后再合并其结果，得到原问题的解。此处n=2。每次都把原问题划分为两个子问题。
归并排序的伪代码(来自算法导论)
合并排序伪代码(使用哨兵)：
merge(A,p,q,r)://合并算法，[p,q],[q+1,r]
n1 <—— q-p+1
n2 <—— r-q
create array L[0,n1] and R[0,n2]
for i <—— 0 to n1-1
do L[i] <—— A[p+i]
for j <—— 0 to n2-1
do R[j] <—— A[q+j+1]
L[n1] <—— +∞
R[n2] <—— +∞
i <—— 0
j <—— 0
for k i <—— p to r
do if L[i]<=R[j]
then A[k] <—— L[i]
i <—— i+1
else A[k] <—— R[j]
j <—— j+1
//通过调用merge完成排序：
merge_sort(A,p,r)：
if p<r
then q <—— [(p+r)/2] //向下取整
merge_sort(A,p,q) //分治
merge_sort(A,q+1,r)
merge(A,p,q,r) //合并结果归并排序实现
#include <stdio.h>
#include <stdlib.h>
#define MAX_INT ~(1<<31)//最大整数
//arr[p,q] arr[q+1,r]
void merge(int *arr,int p,int q,int r)
{
if(arr==NULL)
return;
int n1=q-p+1;
int n2=r-q;
int *L=(int*)malloc((n1+1)*sizeof(int));//申请新空间用于暂时存储元素
int *R=(int*)malloc((n2+1)*sizeof(int));
int i,j;//这里直接申请一个r-p+1长度的数组，在临时数组中排序后拷贝回原数组
for(i=0;i<n1;++i)
L[i]=arr[p+i];
for(j=0;j<n2;++j)
R[j]=arr[q+j+1];
//哨兵元素赋值
L[n1]=MAX_INT;
R[n2]=MAX_INT;
int k;
i=0,j=0;
for(k=p;k<=r;++k){
if(L[i]<=R[j])
arr[k]=L[i++];
else
arr[k]=R[j++];
}//最后可能有一个数组有元素剩余，这里使用一个哨兵(MAX_INT)可以在一次循环中完成全部复制
free(L);
free(R);
}
void merge_sort(int *arr,int p,int r)
{
if(p<r){
int q=(r+p)/2;
merge_sort(arr,p,q);//分治
merge_sort(arr,q+1,r);
merge(arr,p,q,r);//合并结果
}
}
int main()
{
int arr[8]={32,3,4,5,6,7,9,106};
merge_sort(arr,0,7);
for (int i=0;i<8;i++)
printf("%d ",arr[i]);
system("pause");
}二分查找算法
二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn) 。二分查找可以解决（预排序数组的查找）问题：只要数组中包含T（即要查找的值），那么通过不断缩小包含T的范围，最终就可以找到它。其算法流程如下：
- 1、一开始，范围覆盖整个数组。
- 2、将数组的中间项与T进行比较，如果T比数组的中间项要小，则到数组的前半部分继续查找，反之，则到数组的后半部分继续查找。
- 3、如此，每次查找可以排除一半元素，范围缩小一半。就这样反复比较，反复缩小范围，最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。
对于包含N个元素的表，整个查找过程大约要经过log(2)N次比较。
//首先要把握下面几个要点：
//right = n-1 => while(left <= right) => right = middle-1;
//right = n => while(left < right) => right = middle;
//middle的计算不能写在while循环外，否则无法得到更新。
int BinarySearch(int array[], int n, int value)
{
int left = 0;
int right = n - 1;
//如果这里是int right = n 的话，那么下面有两处地方需要修改，以保证一一对应：
//1、下面循环的条件则是while(left < right)
//2、循环内当 array[middle] > value 的时候，right = mid
while (left <= right) //循环条件，适时而变
{
int middle = left + ((right - left) >> 1); /*防止溢出，移位也更高效。同时，每次循环都需要更新。mid = left + (right-left)/2这样写可以有效避免right + left 溢出。如果写成mid = (left + right)/2可能存在溢出*/
if (array[middle] > value)
{
right = middle - 1; //right赋值，适时而变
}
else if(array[middle] < value)
{
left = middle + 1;
}
else
return middle;
//可能会有读者认为刚开始时就要判断相等，但毕竟数组中不相等的情况更多
//如果每次循环都判断一下是否相等，将耗费时间
}
return -1;
}以上就是本次介绍的归并排序和二分查找。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。