快速排序 归并排序

 快速排序（重点）

//quick_sort

void quick_sort(int a,int l,int r)
{
    if(l>=r) return;
    
    int i=l-1,j=r+1;            //所谓的 “ 双 指 针 ”
    int x=a[(l+r)/2];

     while(i<j)
{    
do i++;while(a[i]<x);    //不能等于x
do j--;while(a[j]>x);
if(i<j)
{
swap(a[i],a[j]);    //不合法则交换； 
} 
}

quick_sort(a,l,j);
quick_sort(a,j+1,r);

}
//算例： 1 3 2 6 5 
//算例： 4 1 4 2 5 

/*划分一个中间数。双指针向中间移动，最后的结果是将数组划分成两个区间；
然后以j为分界线进行划分。
在图中会表现为i和j “ 擦 肩 而 过 ” 
*/

归并排序

//merge_sort

void merge_sort(int a,int l,int r)
{
    if(l>=r) return;
    
   int m=(l+r)/2;
   merge_sort(a,l,m);
   merge_sort(a,m+1,r);
   
   int t[10],k=0;//存储合并之后的结果 
   int i=l,j=m+1;
 
while(i<=m&&j<=r)
{
if(a[i]<a[j]) t[k++]=a[i++];
else t[k++]=a[j++];
} 

while(j<=r) t[k++]=a[j++];
while(i<=m) t[k++]=a[i++];

for(int i=l,j=0;i<=r;i++,j++)  //将原来的数组粘贴到对应的位置当中去
 
{
a[i]=t[j];
}
}

/*
非常有趣的一个排序：
以m为界限不断的细分（调用自己）
所以在每一次调用的时候都会出现一个新的l和r，
不能再分时：（只有一个元素）先写入数组t[]（“排序”），然后在写入上个数组t。
t是一个中间数组，通过写入的方式实现了“排序“。

*/

原文地址：https://blog.csdn.net/cssdhfks/article/details/144069085

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！