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

 

词条 直接选择排序
释义

直接选择排序的基本思想

直接选择排序(Straight Select Sorting) 也是一种简单的排序方法,它的基本思想是:第一次从R[0]~R[n-1]中选取最小值,与R[0]交换,第二次从R{1}~R[n-1]中选取最小值,与R[1]交换,....,

第i次从R[i-1]~R[n-1]中选取最小值,与R[i-1]交换,.....,第n-1次从R[n-2]~R[n-1]中选取最小值,与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列.

例如:给定n=8,数组R中的8个元素的排序码为(8,3,2,1,7,4,6,5),则直接选择排序的过程如下所示

由于百科不方便画出关联箭头 所以用 n -- n 表示 :

初始状态 [ 8 3 2 1 7 4 6 5 ] 8 -- 1

第一次 [ 1 3 2 8 7 4 6 5 ] 3 -- 2

第二次 [ 1 2 3 8 7 4 6 5 ] 3 -- 3

第三次 [ 1 2 3 8 7 4 6 5 ] 8 -- 4

第四次 [ 1 2 3 4 7 8 6 5 ] 7 -- 5

第五次 [ 1 2 3 4 5 8 6 7 ] 8 -- 6

第六次 [ 1 2 3 4 5 6 8 7 ] 8 -- 7

第七次 [ 1 2 3 4 5 6 7 8 ] 排序完成

直接选择排序算法实现

[c/c++]Code

elemtype 为所需排序的类型

void SelectSort(elemtype R[], int n)

{

int i, j, m;

elemtype t;

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

{

m = i;

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

{

if(R[j] < R[m])

m = j;

}

if(m != i)

{

t = R[i];

R[i] = R[m];

R[m] = t;

}

}

}

C#实现:

privatestaticvoidQuitSort(int[] numbers, intlength)

{

for(inti = 0; i < length - 1; i++)

{

inttemp = i;

for(intj = i + 1; j < length; j++)

{

if(numbers[j] < numbers[temp])

{

temp = j;

}

}

if(temp != i)

{

Swap(numbers, i, temp);

}

}

}

直接选择排序的效率分析

在直接选择排序中,共需要进行n-1次选择和交换,每次选择需要进行 n-i 次比较 (1<=i<=n-1),而每次交换最多需要3次移动,因此,总的比较次数C=1/2(n*n - n),

总的移动次数 3(n-1).由此可知,直接选择排序的时间复杂度为 O(n2) (n的平方),所以当记录占用字节数较多时,通常比直接插入排序的执行速度快些。

由于在直接选择排序中存在着不相邻元素之间的互换,因此,直接选择排序是一种不稳定的排序方法。

随便看

 

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

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2024/12/25 12:31:11