请输入您要查询的百科知识:

 

词条 选择法排序
释义

选择法排序是一种简单的容易实现的对数据排序的算法。不论待排序是正序还是逆序,它们所经过的时间复杂度都是一样的,即经过n*(n-1)/2.因此选择法的时间复杂度为O(n^2).

以整形数组元素为例,有数组A[10](以C语言为例描述),即A[0],A[1],…,A[8],A[9](假设其元素均互不相同)。要求对其元素排序使之递增有序。

首先以一个元素为基准,从一个方向开始扫描,比如从左至右扫描,以A[0]为基准。

接下来从A[1],…,A[9]中找出最小的元素,将其与A[0]交换。

然后将基准位置右移一位,重复上面的动作,比如,以A[1]为基准,找出A[1]~A[9]中最小的,将其与A[1]交换。

一直进行到基准位置移到数组最后一个元素时排序结束(此时基准左边所有元素均递增有序,而基准为最后一个元素,故完成排序)。

以下为一个用C描述的函数用两者方式(本质都是选择排序法,但是第二种代码较少)实现上述排序:

第一种:

void sort(int array[],int n)

{ // n 为数组元素个数

int i,j,k,temp; // i 为基准位置,j 为当前被扫描元素位置,k 用于暂存出现的较小的元素的位置

for(i=0;i<n-1;i++)

{k=i;//初始化为基准位置

for(j=i+1;j<n;j++)

{

if (array[j]<array[k]) k=j ; // k 始终指示出现的较小的元素的位置

} //for

if(k!=i)

{ temp=array[i];

array[i]=array[k];

array[k]=temp; // 将此趟扫描得到的最小元素与基准互换位置

}

}

}

第二种:

void sort(int array[],int n)

{ // n 为数组元素个数

int i,j,k,temp; // i 为基准位置,j 为当前被扫描元素位置,k 用于暂存出现的较小的元素的位置

for(i=0;i<n-1;i++)

{k=i;//初始化为基准位置

for(j=i+1;j<n;j++)

{

if (array[j]<array[k]) // k 始终指示出现的较小的元素的位置

{ temp=array[j];

array[j]=array[k];

array[k]=temp;}// 将此趟扫描得到的最小元素与基准互换位置

}

}

}

其实现相对简单,效率比较低,时间复杂度为O(n2) (n 的平方) ,为就地排序。

--------------

选择排序(Straight Selection 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趟直接选择排序得到有序结果。

using System;

using System.Collections.Generic;

using System.Text;

namespace ExSelectionSorter

{

class SelectionSorter

{

private int min;

public void Sort(int[] arr)

{

for (int i = 0; i < arr.Length - 1; ++i)

{

min = i;

for (int j = i + 1; j < arr.Length; ++j)

{

if (arr[j] < arr[min])

min = j;

}

int t = arr[min];

arr[min] = arr[i];

arr[i] = t;

}

}

static void Main(string[] args)

{

int[] array = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };

SelectionSorter s = new SelectionSorter();

s.Sort(array);

foreach (int m in array)

Console.WriteLine("{0}", m);

}

}

}

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/3/4 18:13:41