内部排序的全部过程都是在内存中进行的。按排序策略的不同可以将内部排序划分为直接插入排序、冒泡排序、简单选择排序、希尔排序、快速排序、堆排序、归并排序、基数排序等。其中前三种排序方法属于简单的排序方法,其特点是排序过程直观、易于理解和实现,都属于稳定的排序方法,但效率较低;其他几种方法则称为先进的排序方法,算法原理相对复杂,不稳定,但效率较高。
直接插入排序
(1)直接插入排序的基本思想是把新的未排序的元素逐个插入已排序的有序表种。直接插入排序算法可以借助减治法的减一技术进行设计。
(2)假设待排序序列中有k个元素(1<=k<=N-2)已经按照关键字值递增顺序排列,将一个未排序的元素list[i](1<=i<=N-1)直接插入适当的位置。整个排序过程进行N-1趟插入,即首先从右向左顺序搜索表中已排序的序列,直到找到一个元素list[j-1](1<=j-1<=k-1)的关键字值比list[i]的关键字值小;将已排序序列中比list[i]的关键字值大的元素list[j],list[i+1],……,list[k]依次在线性表中后移一个位置;将元素list[i]插入表中的j的位置上成为元素list[j]。
(3)直接插入排序算法
void insertSort(int list[],int n){
int i,j;
for(i=2;i<=n;i++){
list[0]=list[i];
j=i-1;
while(j>0&&list[0]<list[j]){
list[j+1]=list[j];
--j;
}
list[j+1]=list[0];
}
}
(4)完整程序
#include<stdio.h>
#define N 20
int list[N+1];
void insertSort(int list[],int n){
int i,j;
for(i=2;i<=n;i++){
list[0]=list[i];
j=i-1;
while(j>0&&list[0]<list[j]){
list[j+1]=list[j];
j--;
}
list[j+1]=list[0];
}
}
int main(){
int i,n;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&list[i]);
}
insertSort(list,n);
for(i=1;i<=n;i++){
printf("%d ",list[i]);
}
return 0;
}