内部排序:
稳定的排序算法: 冒泡排序、插入排序、基数排序、归并排序
不稳定的排序算法: 选择排序、希尔排序、堆排序、快速排序
外部排序: 基本原理是归并排序
选择排序
要求:从小到大排序
算法思想:
①输入并用数组存储N个数据，
②令 i=0,从i向N-1依次遍历；
③对于每一个i,令j=i+1，自j向N依次遍历；如果a[i]>a[j]，交换a[i]、a[j]的值；
④i遍历结束时(排序完成)，END。
示例数据： 23 19 34 12 34 12 0 -3
排序过程:
i=0时，j=i:7;
23 19 34 12 34 12 0 -3 首先选中23、19；因为23>19；交换23与19
19 23 34 12 34 12 0 -3 选中19、34；因为19<34；继续
19 23 34 12 34 12 0 -3 ……
12 23 34 19 34 12 0 -3 ……
12 23 34 19 34 12 0 -3 ……
12 23 34 19 34 12 0 -3
0 23 34 19 34 12 12 -3
-3 23 34 19 34 12 12 0 END
至此，i=0这一趟已经完成，成功的把最小值-3移到数组的最左边。之后各趟的操作与此类似，不再赘述。
代码：
#include<stdio.h>
int main(void)
{
int a[200],tmp;
int n,i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(a[i]>a[j]){
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
for(i=0;i<n;i++)
printf("%d\t",a[i]);
return 0;
}复杂度分析:
时间复杂度：
当数据无序时，平均情况:O(N^2)
最坏情况:O(N^2)
当数据已经是顺序排列时，存在最优时间:O(N)
空间复杂度分析: o(1)
冒泡排序
要求:从小到大排序
算法思想:
①输入并用数组存储N个数据，
②令 i=0,从i向N-1依次遍历；
③对于每一个i,令j=0，自j向N-i-1依次遍历；如果a[j]>a[j+1]，交换a[j]、a[j-1]的值；
④i遍历结束时(排序完成)，END。
示例数据： 23 19 34 12 34 12 0 -3
排序过程:
i=0时，j=i:7;
23 19 34 12 34 12 0 -3 选中23、1;因为23>19,所以交换23与19
19 23 34 12 34 12 0 -3 选中23、34;因为23<34,所以继续
19 23 34 12 34 12 0 -3 选中34、12;因为34>12,交换34与12
19 23 12 34 34 12 0 -3 选中34、34;因为34==34,所以继续
19 23 12 34 34 12 0 -3 选中34、12;因为34>12,交换34与12
19 23 12 34 12 34 0 -3 选中34、0;因为34>0,交换34与0
19 23 12 34 12 0 34 -3 选中34、-3;因为34>-3,交换34和-3
19 23 34 19 34 0 -3 34 END
至此，i=0这一趟已经完成，成功的把最大值34移到数组的最右边；。之后的操作与此类似，不再赘述。
核心代码:
for(i=0;i<n-1;i++)
for(j=0;j+1<n-i;j++)
if(a[j]>a[j+1]) {
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}算法分析:
空间复杂度分析:O(1)
时间复杂度分析:
最坏情况:O(N^2)
平均情况:O(N^2)
最优情况:O(N)
插入排序:
要求:从小到大排序
算法思想:
①输入并用数组存储N个数据，令 i=1
②令tmp=a[i],从i向N-1依次遍历；
③对于每一个i,令j=i，自 j 向 1 依次遍历；如果 j-1>=0 且 a[j-1]>tmp,令a[j]=a[j-1]；循环结束后，令a[j]=tmp;
④如果i<N-1;i+=1;返回②;
⑤i遍历结束时(排序完成)，END。
示例数据： 23 19 34 12 34 12 0 -3
排序过程:
i=0时，j=i:7;
23 19 34 12 34 12 0 -3
19 23 34 12 34 12 0 -3
19 23 34 12 34 12 0 -3
12 19 23 34 34 12 0 -3
12 19 23 34 34 12 0 -3
12 12 19 23 34 34 0 -3
0 12 12 19 23 34 34 -3
-3 0 12 12 19 23 34 34
至此，i=0这一趟已经完成，成功的把最大值34移到数组的最右边；。之后的操作与此类似，不再赘述。
核心代码:
for(i=1;i<n;i++){
tmp=a[i];
for(j=i;j-1>=0 && a[j-1]>tmp;j--)
a[j]=a[j-1];
a[j]=tmp;
}算法分析:
空间复杂度分析:O(1)
时间复杂度分析:
最坏情况:O(N^2)
平均情况:O(N^2)
最优情况:O(N)
原文：http://executer.blog.51cto.com/10404661/1732591