查看: 22|回复: 0

[转载图文] 排序算法小结

[复制链接]
发表于 3 天前 | 显示全部楼层 |阅读模式
  网上关于排序算法的总结太多了,这篇文章就写得不错。
  http://m.blog.csdn.net/blog/likaiwalkman/23713373
  经典就是经典,个人觉得这些经典的算法被反复研究几十遍都不为过。同时也参考了很经典的书籍《数据结构与算法分析——C语言描述》,温故而知新,每次回头看这些算法的时候都为其中博大精深的思想所折服,呵呵,不扯了。这里只贴出一份用代码敲出来的各个排序算法,纯粹是想练一下手。主要关注快排和堆排序。

交换排序

快速排序
  快排的算法思想很精妙,经常在俩指针问题中用到。
  假设待排序的元素个数为n,分别存放在数组a[1,…,n]中,令第一个元素为参考元素(称为枢纽元,pivot),pivot=a[1],初始时,i=1,j=n,按照以下方法操作:
  (1)    从第j个元素开始向前依次将每个元素与枢纽元pivot比较。如果当前元素大于等于pivot,则比较前一个元素与pivot,即比较a[j-1]与pivot;否则,将当前元素移动到第i个位置,并转到步骤(2)。
  (2)    从第i个元素开始向后依次将每个元素与枢纽元pivot比较。如果当前元素小于pivot,则比较后一个元素与pivot,即比较a[i+1]与pivot;否则,将当前元素移动到第j个位置,并转到步骤(3)。
  (3)    重复执行(1)和(2),直到出现i>=j,将元素移动到a中。此时,整个元素序列被划分成两个部分,第i个位置之前的元素都小于a,第i个位置后的元素都大于等于a。至此,完成一趟快速排序。
  按照以上的方法,将每个部分都进行类似的划分操作,直到每个部分都只有一个元素为止,这样整个元素序列就构成了一个有序的序列。
#include<iostream>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
void quicksort(int a[],int start,int end)//对a[start]到a[end]的元素进行排序 
{
int i=start,j=end;
int temp;
if(start<end)
{
temp=a[start];
while(i!=j)
{
while(j>i&&a[j]>=temp)
j--;
a[i]=a[j];
while(i<j&&a[i]<=temp)
i++;
a[j]=a[i];
}
a[i]=temp;
quicksort(a,start,i-1);
quicksort(a,i+1,end);
} 
}
int main()
{
int a[]={17,1,5,6,98,78,79,54,32,11,15,14,13,20,29};
int n=sizeof(a)/sizeof(a[0]);
quicksort(a,0,n-1);
print(a,n);
return 0;
}
冒泡排序
#include<iostream>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
int main()
{
int a[]={1,5,78,94,48,34,32,47,55,96,19,5};
int n=sizeof(a)/sizeof(a[0]);
int i,j,temp,flag=1;
for(i=0;i<n&&flag;i++)
{
flag=0;
for(j=0;j<n-i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp; 
flag=1;
}
}
print(a,n);
}
return 0;
}

选择排序
  选择排序的算法思想很简单,从待排序的元素中选择最小(最大)的元素放在已经排序的序列的最后,直到全部排完为止。

堆排序
  关于堆排序,C++的STL中已经提供了很成熟的函数,像入堆push_heap、创建堆make_heap、出堆pop_heap,判断是否为堆is_heap,堆排序sort_heap等,实际应用中可以直接调用。但是,算法的思想还是要掌握的。
  假设一个大根堆中有n个元素,如果将堆中的根节点元素输出后,再将剩下的n-1个元素重新建立成一个新堆,并将根节点元素输出,然后将剩下的n-2元素重新建立成堆,重复执行以上过程,直到堆中没有元素为止。所以堆排序的关键就是创建堆调整堆
  建立大根堆的算法思想大概过程是这样的。从位于元素序列中的最后一个一个非叶子结点,即第n/2向下取整个元素开始,逐层比较并调整元素的位置,使其满足a>=a[2*i]且a>=a[2*i+1],直到根节点为止。假设当前结点的序号为i,则当前元素为a,其左右孩子结点分别为a[2*1]和a[2*i+1]。将a[2*1]和a[2*i+1]较大者与a比较,如果孩子结点元素值大于当前结点值,则交换两者;否则,不进行交换。逐层向上执行此操作,直到根节点为止,这样就建立了一个大根堆。建立小根堆的算法与此类似。
  调整堆其实也是重新建立堆的过程。除了堆顶元素外,剩下的元素本身就具有a>=a[2*i]且a>=a[2*i+1],(i=1,2,3,…,[n/2]向下取整)的性质,也就是说剩下的元素由大到小逐层排列。所以,将剩下的元素调整成大根堆只需要从上往下逐层比较,找出最大的元素将其放在根节点的位置上就可以构成新的大根堆了。
  调整堆的大概过程是这样的。输出堆顶元素可以将堆顶元素放在堆的最后,也就是将第一个元素与最后一个元素交换,即a[1]与a[n]交换一下,那么,接下来需要调整的元素就是a[1,…,n-1]。从根节点开始,如果其左、右子树结点元素值大于根节点元素值,选择较大的一个与根节点进行交换,否则,不交换。逐层重复执行这个操作,直到叶子结点,就完成了堆的调整,构成了一个新的堆。
#include<iostream>
//#include<algorithm>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
void adjustheap(int a[],int low,int high)//调整a[low,high],使其成为堆
{
int i=low,j=2*i;//j指向i的左孩子结点 
int temp=a[i];//根节点暂存临时变量中
while(j<=high)
{
if(j<high&&a[j]<a[j+1])//右孩子较大
j++;
if(temp<a[j])
{
a[i]=a[j];
i=j;//修改i和j的值,以便继续向下筛选 
j=2*i;
} 
else
break; 
}
a[i]=temp;
}
/*void adjustheap(int a[],int s,int m)
{
int t,j;
t=a[s];
for(j=2*s+1;j<=m;j*=2+1)
{
if(j<m&&a[j]<a[j+1])
j++;
if(t>a[j])
break;
a[s]=a[j];
s=j;
}
a[s]=t;
} */

void heapsort(int a[],int n)
{
int i,temp;
for(i=n/2;i>=1;i--)//创建堆 
adjustheap(a,i,n);
for(i=n;i>1;i--)
{
temp=a[1];
a[1]=a[i];
a[i]=temp;
adjustheap(a,1,i-1);
}
}

int main()
{
int a[]={0,11,12,54,47,86,87,98,75,34,70};
int n=sizeof(a)/sizeof(a[0]);
//make_heap(a,a+n);
//sort_heap(a,a+n);
heapsort(a,n-1);
print(a,n);
return 0;
}

  注:细心的人,会发现上面的程序有个问题,在创建和调整堆的过程中,下标的对应容易出问题,即数据下标是从1开始的。调用C++ STL中的相关函数接口,就没这个问题。上面的程序是对着教材敲的,没仔细看这个问题,纠结了好久,呵呵。
  这个版本就没问题。
#include <stdio.h>
void exch(int& a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

void fixdown(int a[], int k, int N)
{
    while(2*k <= N)
    {
        int j=k*2;
        if(j<N && a[j]<a[j+1]) j++;
        if(!(a[k]<a[j])) break;
        exch(a[k], a[j]);
        k = j;
    }
}
void heapsort(int a[], int l, int r)
{
    int k, N=r-l+1;
    int *pq = a+l-1; //notice!
    for(k = N/2; k>=1; k--)
        fixdown(pq, k, N);
    while(N>1)
    {
        exch(pq[1], pq[N]);
        fixdown(pq, 1, --N);
    }
}
int main()
{
    int a[10] = {11,12,54,47,86,87,98,75,34,70};
    heapsort(a, 0, 9);
    for(int i=0; i<10; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

  注:参考了这篇文章
  http://www.cnblogs.com/wouldguan/archive/2012/11/12/2766070.html
简单选择排序
#include<iostream>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
void selectsort(int a[],int n)
{
int i,j,k;
int temp;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
{
if(a[j]<a[k])
k=j;//k记录最小元素的位置 
}
if(k!=i)
{
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
int main()
{
int a[]={11,12,54,47,86,89,98,75,34,59};
int n=sizeof(a)/sizeof(a[0]);
selectsort(a,n);
print(a,n); 
return 0;
}
插入排序直接插入排序
//直接插入排序,属于稳定的排序算法
#include<iostream>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
int main()
{
int a[]={17,46,32,15,1,10,6,7,9,18};
int n=sizeof(a)/sizeof(a[0]);
int temp,i,j;
for(i=1;i<n;i++)
{
temp=a[i];//取出待排元素放入临时变量 
for(j=i-1;j>=0&&temp<a[j];j--)//寻找插入位置 
{
a[j+1]=a[j];
}
a[j+1]=temp;
print(a,n);
}
return 0;
}

折半插入排序
#include<iostream>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
int main()
{
int a[]={1,48,46,57,98,96,16,13,18,29,30,45,47};
int n=sizeof(a)/sizeof(a[0]);
int temp,i,j,low,high,mid;
for(i=1;i<n;i++)
{
temp=a[i];//待排元素放入临时变量 
for(low=0,high=i-1;high>=low;)//寻找插入位置 
{
mid=(low+high)/2;
if(temp<a[mid])
high=mid-1;
else
low=mid+1;
}
for(j=i-1;j>=low;j--)//元素移动 
a[j+1]=a[j];
a[low]=temp;
print(a,n);
}
return 0;
}

希尔排序
  与直接插入排序、折半插入排序相比,希尔排序将待排序的元素划分为若干个子序列,在每个组内进行直接插入排序。
#include<iostream>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
int main()
{
int a[]={1,5,78,94,48,34,32,47,55,96,19,5};
int n=sizeof(a)/sizeof(a[0]);
int i,j,inc,temp;
for(inc=n/2;inc>0;inc/=2)
{
for(i=inc;i<n;i++)
{
temp=a[i];//取待排元素放入临时变量 
for(j=i;j>=inc;j-=inc)//组内进行插入排序,寻找插入位置 
{
if(temp<a[j-inc])
{
a[j]=a[j-inc];
}
else
    break;
}
a[j]=temp;
print(a,n);
}
}
return 0;
}
归并排序
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
void copy(int source[],int dest[],int len,int start)
{
int i,j=start;
for(i=0;i<len;i++)
{
dest[j]=source[i];
j++;
}
}
void merge(int a[],int left,int right)
{
int begin1,begin2,mid,k=0,len,*b;
begin1=left;
mid=(left+right)/2;
begin2=mid+1;
len=right-left+1;
b=(int*)malloc(len*sizeof(int));
while(begin1<=mid&&begin2<=right)
{
if(a[begin1]<=a[begin2])
b[k++]=a[begin1++];
else
b[k++]=a[begin2++];
}
while(begin1<=mid)
b[k++]=a[begin1++];
while(begin2<=right)
b[k++]=a[begin2++];
copy(b,a,len,left);
}
void mergesort(int a[],int left,int right)
{
int i;
if(left<right)
{
i=(left+right)/2;
mergesort(a,left,i);
mergesort(a,i+1,right);
merge(a,left,right);
}
}
int main()
{
int a[]={11,12,54,47,86,89,98,75,34,59};
int n=sizeof(a)/sizeof(int);
mergesort(a,0,n-1);
print(a,n);
return 0;
}

  除了以上几种算法以外,还有基数排序、桶排序、外部排序等等,不想写了,知道排序的思想就行。
            
温馨提示:
1.如果您喜欢这篇帖子,请给作者点赞评分,点赞会增加帖子的热度,评分会给作者加学币。(评分不会扣掉您的积分,系统每天都会重置您的评分额度)。
2.回复帖子不仅是对作者的最好奖励,还可以获得学币奖励,请尊重作者的劳动成果,拒绝做伸手党!
3.发广告、灌水回复等违规行为一经发现直接禁言,如果本帖内容涉嫌违规,请点击论坛底部的举报反馈按钮,也可以在【投诉建议】板块发帖举报。
论坛交流群:672619046
微信公众号
快速回复 返回顶部 返回列表