选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录,顺序存放在已排序的记录序列的后面,直到全部排完。选择排序中主要使用直接选择排序和堆排序。
①. 直接选择排序(不稳定)
直接选择排序的过程是:首先在所有记录中选出序码最小的记录,把它与第1个记录交换,然后在其余的记录内选出排序码最小的记录,与第2个记录交换......依次类推,直到所有记录排完为止。
无论文件初始状态如何,在第i趟排序中选出最小关键字的记录,需要做n-i次比较,因此,总的比较次数为n(n-1)/2=O(n^2)。当初始文件为正序时,移动次数为0;文件初态为反序时,每趟排序均要执行交换操作,总的移动次数取最大值3(n-1)。直接选择排序的平均时间复杂度为O(n^2)。直接选择排序是不稳定的。
代码如下:
void DirChooseSort(int A[], int n) //直接选择排序
{
int k;
实现:
#include
#include
void selectsort(int arr[],int n)
{
int smallIndex;
int pass,j;
int temp;
for(pass=0;pass
smallIndex=pass; //对应1
for(j=pass+1;j if(arr[j] smallIndex=j;
if(smallIndex!=pass){ //对应2
temp=arr[pass];
arr[pass]=arr[smallIndex];
arr[smallIndex]=temp;
}
}
}
int main(void){
int i,n;
int a[100]; //可以是一个比n大的数
//int a[]={23,3,5,21,7,2,18,6};
scanf("%d",&n);
for(i=0;i scanf("%d",&a[i]);
selectsort(a,n);
for(i=0;i printf("%d\n", a[i]);
system("pause");
return 0;
}
阅读(289) | 评论(0) | 转发(0) |