黑马程序员技术交流社区

标题: 排序 [打印本页]

---

作者: lorem    时间: 2016-2-26 19:29
标题: 排序


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;}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2