直接选择排序法 java数组中sort是升序
直接选择排序的基本思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:
①初始状态:无序区为R[1..n],有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R[i]交换,使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
#include <iostream>
using namespace std;
void selectsort(int array[],int length)
{
int i,j,k,temp;
for(i=0;i<length-1;i++)
{
k=i;
for(j=i+1;j<length;j++)
{
if(array[j]<array[k])
k=j;
}
temp=array[i];
array[i]=array[k];
array[k]=temp;
for(k=0;k<length;k++)
cout<<array[k]<<"";
cout<<endl;
}
}
int main()
{
inta[]={41,82,51,63,47,78,56,17,15,77,94};
selectsort(a,11);
}
运行结果:
[root@localhost sort]# make selectsort
g++ -c selectsort.cpp
g++ -o selectsort selectsort.o
[root@localhost sort]# ./selectsort
15 82 5163 47 7856 17 4177 94
15 17 5163 47 7856 82 4177 94
15 17 4163 47 7856 82 5177 94
15 17 4147 63 7856 82 5177 94
15 17 4147 51 7856 82 6377 94
15 17 4147 51 5678 82 6377 94
15 17 4147 51 5663 82 7877 94
15 17 4147 51 5663 77 7882 94
15 17 4147 51 5663 77 7882 94
15 17 4147 51 5663 77 7882 94
[root@localhost sort]#
算法分析
(1)关键字比较次数
无论文件初始状态如何,在第i趟排序中选出最小关键字的记录,需做n-i次比较,因此,总的比较次数为:
n(n-1)/2=0(n2)
(2)记录的移动次数
当初始文件为正序时,移动次数为0
文件初态为反序时,每趟排序均要执行交换操作,总的移动次数取最大值3(n-1)。
直接选择排序的平均时间复杂度为O(n2)。
(3)直接选择排序是一个就地排序
(4)稳定性分析
直接选择排序是不稳定的
更多阅读
Asp中数组元素列表的分页显示 数组分页
设有一数组a(100,3),其中保存的数据是:A(i,1):姓名A(i,2):性别A(i,3):年龄现要将其显示在名为list.asp页面中一张如下的表格中:序姓名
C#的动态数组 c 动态数组的用法
在使用数组的过程中,有时候希望数组的长度和元素个数能随程序的运行不断改变,但改变一次就要重新开辟一个新的数组对象,这样将占用内存空间。为了解决这个问题,Microsoft.NET Framework 体统了一个ArrayList类,专门用于处理可按动态增减
c语言中求数组长度的问题 c语言求数组的长度
求数组长度的方法有两种 第一种是intarray[n];strlen(array);//这个方法可以求得字符串数组的长度char sizeof(array);sizeof(array);//可以求的数组的长度
C++冒泡排序法 java冒泡排序法
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。相同元素的前后顺序不会发生变化,冒泡法是一种稳定的排序算法。例如:inta[10]={3,7,2,4,5,8,9,0,6,1};size_tn=sizeof
二维数组与数组指针的用法 二维数组指针传递
二维数组与数组指针的用法 严格地说,一个指针是一个地址,是一个常量。而一个指针变量却可以被赋予不同的指针值,是变量。但常把指针变量简称为指针。既然指针变量的值是一个地址,那么这个地址不仅可以是变量的地址,也可以是其它数据结构