数据结构和算法选择排序

选择排序是一种简单的排序算法.这种排序算法是一种就地比较算法,其中列表分为两部分,左端的排序部分和右端的未排序部分.最初,排序的部分是空的,未排序的部分是整个列表.

从未排序的数组中选择最小的元素并与最左边的元素交换,并且该元素成为排序的数组.此过程继续将未排序的数组边界向右移动一个元素.

此算法不适用于大型数据集,因为其平均和最差情况复杂度为Ο(n 2 ),其中 n 是项目数.

选择排序如何工作?

考虑以下描述的数组作为示例.

未排序数组

排序列表中的第一个位置,按顺序扫描整个列表.目前存储14的第一个位置,我们搜索整个列表并发现10是最低值.

选择排序

所以我们用10代替14.经过一次迭代10,恰好是列表中的最小值,出现在排序列表的第一个位置.

选择排序

对于第二个位置,33居住,我们开始扫描列表的其余部分以线性方式.

选择排序

我们发现14是列表中的第二个最低值,它应该出现在第二个位置.我们交换这些值.

选择排序

经过两次迭代后,两次最小值以排序方式位于开头.

选择排序

相同的过程应用于数组中的其余项目.

以下是整个排序过程的图示描述 :


现在,让我们学习一些选择排序的编程方面.

算法

 第1步 : 将MIN设置为位置0 步骤2  : 搜索列表中的最小元素步骤3  : 在地点交换价值MIN 第4步 : 增加MIN指向下一个元素步骤5  : 重复直到列表排序

伪代码

procedure selection sort 
   list  : array of items
   n     : size of list

   for i = 1 to n - 1
   /* set current element as minimum*/
      min = i    
  
      /* check the element to be minimum */

      for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for
	
end procedure

了解选择用C编程语言排序实现.