本文介绍几种常用的排序算法:冒泡排序、选择排序、插入排序、希尔排序、归并排序。
冒泡排序
冒泡排序(Bubble Sort):它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
实例:
#include
void bubble_sort(int [],int);
int main()
{
int i;
int arr[]={22,34,3,32,82,55,89,50,37,5,64,35,9,70};
int len=(int)sizeof(arr)/sizeof(*arr);
bubble_sort(arr,len);
for(i=0;iarr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
运行结果:
3 5 9 22 32 34 35 37 50 55 64 70 82 89
选择排序
选择排序(Selection Sort):首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
实例:
#include
void selection_sort(int [],int);
int main()
{
int i;
int arr[]={22,34,3,32,82,55,89,50,37,5,64,35,9,70};
int len=(int)sizeof(arr)/sizeof(*arr);
selection_sort(arr,len);
for(i=0;i
运行结果:
3 5 9 22 32 34 35 37 50 55 64 70 82 89
插入排序
插入排序(英语:Insertion Sort):通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
实例:
#include
void insertion_sort(int [],int);
int main()
{
int i;
int arr[]={22,34,3,32,82,55,89,50,37,5,64,35,9,70};
int len=(int)sizeof(arr)/sizeof(*arr);
insertion_sort(arr,len);
for(i=0;i0&&arr[j-1]>temp;j--)
arr[j]=arr[j-1];
arr[j]=temp;
}
}
运行结果:
3 5 9 22 32 34 35 37 50 55 64 70 82 89
希尔排序
希尔排序(Shell Sort):也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
- 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
- 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位
实例
#include
void shell_sort(int [],int);
int main()
{
int i;
int arr[]={22,34,3,32,82,55,89,50,37,5,64,35,9,70};
int len=(int)sizeof(arr)/sizeof(*arr);
shell_sort(arr,len);
for(i=0;i>1;gap>0;gap=gap>>1)
for(i=gap;i=0&&arr[j]>temp;j-=gap)
arr[j+gap]=arr[j];
arr[j+gap]=temp;
}
}
运行结果:
3 5 9 22 32 34 35 37 50 55 64 70 82 89
归并排序
归并排序(Merge Sort):把数据分为两段,从两段中逐个选最小的元素移入新数据段的末尾。
可从上到下或从下到上进行。
实例
迭代法
#include
#include
int mini(int,int);
void merge_sort(int [],int);
int main()
{
int i;
int arr[]={22,34,3,32,82,55,89,50,37,5,64,35,9,70};
int len=(int)sizeof(arr)/sizeof(*arr);
merge_sort(arr,len);
for(i=0;i
递归法
#include
#include
#define N 14
void merge_sort_recursive(int [],int [],int,int);
void merge_sort(int [],const int);
int main()
{
int i;
int arr[]={22,34,3,32,82,55,89,50,37,5,64,35,9,70};
int len=(int)sizeof(arr)/sizeof(*arr);
merge_sort(arr,len);
for(i=0;i=end)
return;
len=end-start;
mid=(len>>1)+start;
start1=start;
end1=mid;
start2=mid+1;
end2=end;
merge_sort_recursive(arr,reg,start1,end1);
merge_sort_recursive(arr,reg,start2,end2);
k=start;
while(start1
运行结果:
3 5 9 22 32 34 35 37 50 55 64 70 82 89
备注:常用排序算法的时间复杂度和空间复杂度
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net