分类:
2012-03-13 20:17:55
原文地址:面试的三种经典排序 作者:huanghaibodd
点击(此处)折叠或打开
#include
#define MAX 6
int array[MAX];
int count = MAX;
/********创建数组,并输入元素************/
void BuildArray()
{
int a,i=0;
printf("请输入数组元素: ");
for(; i
scanf("%d", &a);
array[i] = a;
}
printf("\n");
}
/**********遍历输出数组元素*************/
void Traverse(int arr[], int count)
{
int i;
printf("数组输出: ");
for(i=0; i
printf("\n");
}
/*******************************************************
冒泡排序
算法:将相邻的两个数比较,将小的调到前头;
有n个数,则要进行n-1趟比较,第一次比较中要进行
n-1次两两比较,在第j趟比较要进行n-j次两两比较
********************************************************/
void BublleSort(int arr[], int count)
{
int i,j,temp;
for(j=0; j
if(arr[i]>arr[i 1])/* 把值比较大的元素沉到底 */
{
temp=arr[i 1];
arr[i 1]=arr[i];
arr[i]=temp;
}
}
}
/*******************************************************
插入排序
算法: 在得到要排序的数组以后,将数组分为两部分,
数组的第一个元素为一部分,剩下的元素为一部分,
然后从数组的第二个元素开始,和该元素以前的所有元素比较,
如果之前的元素没有比该元素大的,那么该元素的位置不动,
如果有的元素的值比该元素大,那么记录下他所在的位置,
例如为i,该元素的位置例如为k,则将从i到k位置上的
所有元素统统向后移动,然后将k移到i元素的位置上。
这样就找到了k所在的位置。每一个元素都这样进行,
最终就会得到排好顺序的数组。
********************************************************/
void InsertSort(int arr[],int count)
{
int i,j,temp;
for(i=1; i
temp = arr[i];//操作当前元素,先保存在其它变量中
for(j=i-1; j>-1&&arr[j]>temp;j--)//从当前元素的上一个元素开始查找合适的位置,一直查找到首元素
{
arr[i] = arr[j];
arr[j] = temp;
}
}
}
/*******************************************************
选择排序
算法:首先以一个元素为基准,从一个方向开始扫描,
比如从左至右扫描,以A[0]为基准。接下来从A[0]...A[9]
中找出最小的元素,将其与A[0]交换。然后将基准位置右
移一位,重复上面的动作,比如,以A[1]为基准,找出
A[1]~A[9]中最小的,将其与A[1]交换。一直进行到基准位
置移到数组最后一个元素时排序结束(此时基准左边所有元素
均递增有序,而基准为最后一个元素,故完成排序)。
********************************************************/
void SelectSort(int arr[], int count)
{
int i,j,min,temp;
for(i=0; i
min = arr[i];//以此元素为基准
for(j=i 1; j
if(min>arr[j])//把剩下元素中最小的那个放到arr[j]中
{
temp = arr[j];
arr[j] = min;
min = temp;
}
}
}
}
int main()
{
BuildArray();//创建数组
Traverse(array, count);//输出最初数组
BublleSort(array, count);//冒泡排序
Traverse(array, count);//输出排序后的数组
InsertSort(array, count);//插入排序
Traverse(array, count);//输出排序后的数组
SelectSort(array, count);//插入排序
Traverse(array, count);//输出排序后的数组
return 0;
}