本帖最后由 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;}
|
|