基础算法(二)——归并排序-创新互联
归并排序
介绍
名称栏目:基础算法(二)——归并排序-创新互联
转载注明:http://pwwzsj.com/article/ddhdps.html
归并排序是一种复杂度O( n l o g ( n ) nlog(n) nlog(n))的排序算法,并且在任何情况下都是,但是它不是原地算法,即需要额外存储空间
成都创新互联坚持“要么做到,要么别承诺”的工作理念,服务领域包括:网站设计制作、网站制作、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的洪洞网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!其原理是,先将区间均匀分成左右两半,然后再对左右两半继续二分,直到一个数为一个区间为止。
然后从小区间到大区间进行左右区间合并。合并方式就是将两个有序间合并为一个大区间,并且大区间保持有序,因为最小区间单元是一个数,因此最初的区间一定有序,由下至上就可以保证合并过程中的区间都是有序的。
因此可以发现,归并排序的核心是先递归后排序。
核心思想:合并过程步骤:
- 开辟一个新的内存空间
tmp
用于存放合并后的区间 - 设定两个指针分别指向待合并的两个区间起点
- 比较两个指针的数,取较小值放入
tmp
- 最后将未指向终点的指针所代表那个区间接到
tmp
区间的后面 - 将
tmp
区间的内容覆盖回原区间
即将两个小区间通过双指针算法,合并为一个大区间,最后把大区间的内容覆盖回原来两个小区间。
模板代码:int q[N], tmp[N];
void merge_sort(int q[N], int l, int r)
{
if( l >= r) return;
int mid = l + r >>1;
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
int i = l, j = mid + 1, k = 0; // i 和 j 分别是左右区间的第一个下标
// 区间合并
while( i<= mid && j<= r )
{
if( q[i]< q[j] ) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
}
// 将剩余的区间补上
while(i<= mid) tmp[k++] = q[i++];
while(j<= r) tmp[k++] = q[j++];
// 将排序好的内容重新放回q数组
for(int i=l, k=0; i<=r; i++, k++) q[i] = tmp[k];
}
例题思路:按上述模板进行书写即可
代码:#includeusing namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[N], int l, int r)
{
if(l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >>1];
while(i< j)
{
do i++;while(q[i]< x);
do j--;while(q[j] >x);
if( i< j ) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j+1, r);
}
int main()
{
scanf("%d", &n);
for(int i=0; i
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
名称栏目:基础算法(二)——归并排序-创新互联
转载注明:http://pwwzsj.com/article/ddhdps.html