常见的排序算法及其理解_Android, Python及开发编程讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  Android, Python及开发编程讨论区 »
总帖数
2
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 2861 | 回复: 1   主题: 常见的排序算法及其理解        下一篇 
jian.chen
注册用户
等级:上尉
经验:781
发帖:17
精华:0
注册:1970-1-1
状态:离线
发送短消息息给jian.chen 加好友    发送短消息息给jian.chen 发消息
发表于: IP:您无权察看 2015-8-20 17:59:32 | [全部帖] [楼主帖] 楼主

1、冒泡排序

     冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,
交换也发生在这两个元素之间。所以,如果两个元素相等,是不用交换的;如果两个相等的元素没有相邻,
那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改 变,
所以冒泡排序是一种稳定排序算法

代码如下:

void bubble_sort(int a[],int n)
{
      _FUNC;
      for(int i=n-1;i>0;i--)
      for(int j=0;j<i;j++)
      if(a[j]>a[j+1])
      swap(a[j],a[j+1]);
}


2、快速排序

     快速排序(Quicksort)是对冒泡排 序的一种改进。由C. A. R. Hoare在1962年提出。
它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,
其中一部分的所有数据都比另外一部分的所有数据都要小,然 后再按此方法对这两部分数据分别进行快速排序,
整个排序过程可以递归进行,以此达到整个数据变成有序序列

 代码如下:

void qsort(int a[],int l,int r){
      int pvt=a[(l+r)/2];
      int i=l,j=r;
      while(i<=j){
            while(a[i]<pvt)
            i++;
            while(a[j]>pvt)
            j--;
            if(i<=j){
                  if(i!=j)
                  swap(a[i],a[j]);
                  i++;
                  j--;
            }
      }
      if(j>l)
      qsort(a,l,j);
      if(i<r)
      qsort(a,i,r);
}
void quick_sort(int a[],int n){
      qsort(a,0,n-1);
}


3、直接插入排序

直接插入排序(straight insertion sort)的作法是:每次从无序表中取出第一个元素,
把它插入到有序表的合适位置,使有序表仍然有序。

第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描,
把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序属于稳定的排序,时间复杂性为o(n^2),空间复杂度为O(1)。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。
内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,
所以外层循环是从第二个数值开始的。当前一数值比待比较数 值大的情况下继续循环比较,
直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。(从小到大)

值得注意的是,我们必需用一个存储空间来保存当前待比较的数值,因为当一趟比较完成时,
我们要将待比较数值置入比它小的数值的后一位。插入排序类似玩牌时整理手中纸牌的过程

代码如下:

void insert_sort(int a[],int n)
{
      _FUNC;
      for(int i=1;i<n;i++) {
            int t=a[i];
            int j;
            for(j=i-1;j>=0&&a[j]>t;j--) {
                  a[j+1]=a[j];
            }
            a[j+1]=t;
            print(a,n);
      }
}


4、折半插入排序

    折半插入排序(binary insertion sort)是对插入排序算法的一种改进,由于排序算法过程中,
就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列,
这样我们不用按顺序依次寻找插入点,可以采用折半查找的方法来加快寻找插入点的速度。
    折半插入排序算法的具体操作为:在将一个新元素插入已排好序的数组的过程中,寻找插入点时,
将待插入区域的首元素设置为a[low],末元素设置为 a[high],则轮比较时将待插入元素与a[m],
其中m=(low+high)/2相比较,如果比参考元素小,则选择a[low]到a[m-1]为新 的插入区域(即high=m-1),
否则选择a[m+1]到a[high]为新的插入区域(即low=m+1),如此直至low<=high不成 立,
即将此位置之后所有元素后移一位,并将新元素插入a[high+1]。

代码如下:

void binary_insert_sort(int a[],int n){
      for(int i=1;i<n;i++){
            int low=0;
            int high=i-1;
            int t=a[i];
            int mid;
            while(low<=high){
                  mid=(low+high)/2;
                  if(t<a[mid])
                  high=mid-1;
                  else
                  low=mid+1;
            }
            for(int j=i;j>mid;j--)
            a[j]=a[j-1];
            a[low]=t;
      }
}


5、希尔排序

     希尔排序(Shell Sort)又叫做缩小增量排序(diminishing increment sort),是一种很优秀的排序法,
算法本身不难理解,也很容易实现,而且它的速度很快。
 基本思想:
   先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。
所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入 排序;然后,
取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),
即所有记录放在同一组中进行直接插入排序为止。

void shell_sort(int a[],int n)
{
      _FUNC;
      int gap=n/2;
      bool flag=true;
      while(gap>1 flag)
      {
            flag=false;
            for(int i=0;i+gap<n;i++)
            if(a[i]>a[i+gap])
            {
                  swap(a[i],a[i+gap]);
                  flag=true;
            }
            print(a,n);
            if(gap>1)
            gap/=2;
      }
}




赞(0)    操作        顶端 
dream007
注册用户
等级:少校
经验:1086
发帖:53
精华:0
注册:2015-7-2
状态:离线
发送短消息息给dream007 加好友    发送短消息息给dream007 发消息
发表于: IP:您无权察看 2015-8-20 23:39:01 | [全部帖] [楼主帖] 2  楼

虽然基础,但确实是最应该具备的知识! 北京联动北方科技有限公司



赞(0)    操作        顶端 
总帖数
2
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论