直接选择排序法 java数组中sort是升序

直接选择排序(Straight SelectionSort)

直接选择排序的基本思想

 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趟直接选择排序得到有序结果。
直接选择排序法 java数组中sort是升序
#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)稳定性分析
 直接选择排序是不稳定的

  

爱华网本文地址 » http://www.413yy.cn/a/25101016/325539.html

更多阅读

C#的动态数组 c 动态数组的用法

在使用数组的过程中,有时候希望数组的长度和元素个数能随程序的运行不断改变,但改变一次就要重新开辟一个新的数组对象,这样将占用内存空间。为了解决这个问题,Microsoft.NET Framework 体统了一个ArrayList类,专门用于处理可按动态增减

C++冒泡排序法 java冒泡排序法

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。相同元素的前后顺序不会发生变化,冒泡法是一种稳定的排序算法。例如:inta[10]={3,7,2,4,5,8,9,0,6,1};size_tn=sizeof

二维数组与数组指针的用法 二维数组指针传递

二维数组与数组指针的用法 严格地说,一个指针是一个地址,是一个常量。而一个指针变量却可以被赋予不同的指针值,是变量。但常把指针变量简称为指针。既然指针变量的值是一个地址,那么这个地址不仅可以是变量的地址,也可以是其它数据结构

声明:《直接选择排序法 java数组中sort是升序》为网友心素如简分享!如侵犯到您的合法权益请联系我们删除