插入排序：
稳定
最优时间复杂度：O(n) 此时数列顺序排列
最差时间复杂度：O(n^2) 此时数列逆序排列
插入排序的思想：固定一个元素a,分别比较a之前的元素，如果a之前的元素比a大，则元素后移，将a插入比a小的元素后面。
要理解插入排序，实际上递归和不递归的思想是个相反的过程，递归的最后一层相当于非递归循环的第一层
递归版的插入排序：
#include<stdio.h>
#include<stdlib.h>
void Insert(int *a,int p,int q)
{
int key;
key=a[q+1];
int j;
j=q;
while(j>=0 &&a[j]>key)
{
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
void Recursive_InsertSort(int *a,int p,int q)
{
if(p<q)
{
Recursive_InsertSort(a,p,q-1);
Insert(a,p,q-1);
}
}
int main()
{
int a[10]={1,5,7,9,8,2,6,4,0,3};
int b[10];
int i,j,tem;
Recursive_InsertSort(a,0,10);
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
system("pause");
}
非递归版插入排序
#include<stdio.h>
#include<stdlib.h>
int main()
{
int a[10]={1,5,7,9,8,2,6,4,0,3};
int b[10];
int i,j,tem;
for(i=1;i<10;i++)
{
tem=a[i];
j=i-1;
printf("ai1=%d
",a[i]);
printf("tem1=%d
",tem);
while(a[j]>tem&&j>=0) //这里只能用tem而不能用a[i]
{
printf("ai=%d
",a[i]);
printf("tem=%d
",tem);
a[j+1]=a[j];
j--;
}
a[j+1]=tem;
}
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
system("pause");
}
冒泡排序：
稳定
最优时间复杂度：O(n^2)
最差时间复杂度：O(n^2)
冒泡排序算法的思想是每一次循环分别让i...n中的最小值到通过交换到达i点。
递归版冒泡排序算法：
#include<stdio.h>
#include<stdlib.h>
void Insert(int *a,int p,int q)
{
int i,j,tem;
for(i=p;i<q;i++)
{
if(a[i-1]>a[i])
{
tem=a[i-1];
a[i-1]=a[i];
a[i]=tem;
}
}
}
void Recursive_BubbleSort(int *a,int p,int q)
{
if(p<q)
{
Insert(a,p,q);
Recursive_BubbleSort(a,p,q-1);
}
}
int main()
{
int a[10]={5,1,7,9,8,2,6,4,0,3};
int b[10];
int i,j,tem;
Recursive_BubbleSort(a,1,10);
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
system("pause");
}
冒泡排序算法：
#include<stdio.h>
#include<stdlib.h>
void BubbleSort(int *a,int n)
{
int tem,i,j;
for(i=0;i<n;i++)
{
for(j=n-1;j>i;j--)
{
if(a[j]<a[j-1])
{
tem=a[j];
a[j]=a[j-1];
a[j-1]=tem;
}
}
}
}
int main()
{
int a[10]={1,5,7,9,8,2,6,4,0,3};
int b[10];
int i,j,tem;
BubbleSort(a,10);
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
system("pause");
}
选择排序：
不稳定
最优时间复杂度：O(n^2)
最差时间复杂度：O(n^2)
选择排序算法的思想是每一次循环分别让i...n中的最小值到通过交换到达i点，与冒泡算法不同的是，冒泡算法是与相邻元素交换。#include<stdio.h>
#include<stdlib.h>
void SelectSort(int *a,int m,int n)
{
int i,j,min,tem;
for(i=m;i<n;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(a[min]>a[j])
{
min=j;
}
}
tem=a[min];
a[min]=a[i];
a[i]=tem;
}
}
int main()
{
int a[10]={5,1,7,9,8,2,6,4,0,3};
int b[10];
int i,j,tem;
SelectSort(a,0,10);
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
system("pause");
}
版权声明：本文为博主原创文章，未经博主允许不得转载。