A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© lorem 中级黑马   /  2016-2-26 19:29  /  797 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 lorem 于 2016-2-26 19:32 编辑

1.直接插入排序(straight insertion sort)
思想:第一趟比较前两个数,然后把第二个数按大小插入到有序表中;
第二趟对前两个数从后向前扫描,把第三个数按大小插入到有序表中;依次进行下去,进行(n-1)趟扫描
以后就完成了整个排序过程
属于稳定的排序,最坏时间复杂度O(n^2),空间复杂度为O(1)
#include <stdio.h>void move(int start,int end,int *s,int e)
{   
for(int t=end;t>=start;t--)        
s[t+1] = s[t];}
void InsertSort(int *s,int n)
{  
  int t;   
  for(int i=1;i<n;i++)   
{        
t = s;        
for(int j=i-1;j>=0;j--)            
if(t >= s[j])           
{               
move(j+1,i-1,s,t);               
s[j+1] = t;               
break;           
}        
if(j < 0)
//当前比较的数应该插入到最前面        
{            
move(0,i-1,s,t);

s[0] = t;        
}    }}
int main()
{    int s[] = {6,3,1,5,7,2,8,4};
    InsertSort(s,8);
   for(int i=0;i<8;i++)
   printf("%d ",s);
   return 0;}
2二分归并排序
属于稳定排序,时间复杂度O(n log n) 空间复杂度O(n)
以样例{10,4,,6,3,8,2,5,7}作操作说明
归并排序的算法我们通常用递归实现
先把待排序区间[s,t]以中点二分,
接着把左边子区间排序,再把右边子区间排序,
最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
归并操作的工作原理如下:
第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置
第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
#include <stdio.h>

#include <stdlib.h>
void Merge(int *s,int start,int mid,int end)
//两个顺序表长度可能不一
{    int *s1 = (int *)malloc(sizeof(int)*(end - start + 1));
   int t = 0,i,j;    i = start,j = mid + 1;
//两个指针指向两个已经排序序列的起始位置   
while(i <= mid && j <= end)//两个指针都未超出序列尾   
{        if(s > s[j])        {            s1[t++] = s[j];            j ++;        }        
else{            s1[t++] = s;            i ++;        }    }   
if(i > mid)
//第一个顺序表指针超出序列尾,则将第二个顺序表剩下的所有元素直接复制到合并序列尾,反之亦然  
  {        for(int k=j;k<=end;k++)               
s1[t++] = s[k];    }  
  if(j > end)   
{        for(int k=i;k<=mid;k++)                s1[t++] = s[k];    }  
  for(int k=0;k<t;k++)//将合并后的顺序表又复制回去    {
//        s[start++] = s1[k];数组溢出        s[start] = s1[k];        start ++;    }   
free(s1);}
void MergeSort(int *s,int start,int end)
{    if(end - start == 0)        return;    else if(end - start == 1)
{        if(s[end] < s[start])
//交换的前提            
s[end] = s[start] + s[end] - (s[start] = s[end]);
//swap        return;    }   
else{        MergeSort(s,start,(end-start)/2+start);      
  MergeSort(s,(end-start)/2+start+1,end);        
Merge(s,start,(end-start)/2+start,end);
//2-way Merge    }}int main()
{    int s[] = {10,4,6,3,8,2,5,7};
   MergeSort(s,0,7);  
  for(int i=0;i<=7;i++)   
    printf("%d ",s);    return 0;}

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马