选择排序

选择排序 首页 / 结构和算法入门教程 / 选择排序

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

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

链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/selection-sort-algorithm.html

来源:LearnFk无涯教程网

该算法不适用于大型数据集,因为其平均和最坏情况下的复杂度为Ο(n 2 ),其中 n 是元素。

选择排序

以下面描述的数组为示例。

Unsorted Array

对于排序列表中的第一个位置,将顺序扫描整个列表,当前存储14的第一个位置,我们搜索整个列表,发现10是最低值。

Selection Sort

因此,我们将10替换为14。一次迭代10(恰好是列表中的最小值)出现在已排序列表的第一位置。

Selection Sort

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

Selection Sort

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

Selection Sort

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

Selection Sort

将相同的进程应用于数组中的其余项目。

无涯教程网

以下是整个分类进程的图示-

Selection Sort

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

伪代码

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语言进行选择排序实现

#include <stdio.h>
#include <stdbool.h>

#define MAX 7

int intArray[MAX] = {4,6,3,2,1,9,7};

void printline(int count) {
   int i;
	
   for(i = 0;i < count-1;i++) {
      printf("=");
   }
	
   printf("=\n");
}

void display() {
   int i;
   printf("[");
	
   // navigate through all items 
   for(i = 0;i < MAX;i++) {
      printf("%d ", intArray[i]);
   }
	
   printf("]\n");
}

void selectionSort() {
   int indexMin,i,j;
	
   // loop through all numbers 
   for(i = 0; i < MAX-1; i++) { 
	
      // set current element as minimum 
      indexMin = i;
		
      // check the element to be minimum 
      for(j = i+1;j < MAX;j++) {
         if(intArray[j] < intArray[indexMin]) {
            indexMin = j;
         }
      }

      if(indexMin != i) {
         printf("Items swapped: [ %d, %d ]\n" , intArray[i], intArray[indexMin]); 
			
         // swap the numbers 
         int temp = intArray[indexMin];
         intArray[indexMin] = intArray[i];
         intArray[i] = temp;
      }          

      printf("Iteration %d#:",(i+1));
      display();
   }
}  

void main() {
   printf("Input Array: ");
   display();
   printline(50);
   selectionSort();
   printf("Output Array: ");
   display();
   printline(50);
}
Input Array: [4 6 3 2 1 9 7 ]
==================================================
Items swapped: [ 4, 1 ]
Iteration 1#:[1 6 3 2 4 9 7 ]
Items swapped: [ 6, 2 ]
Iteration 2#:[1 2 3 6 4 9 7 ]
Iteration 3#:[1 2 3 6 4 9 7 ]
Items swapped: [ 6, 4 ]
Iteration 4#:[1 2 3 4 6 9 7 ]
Iteration 5#:[1 2 3 4 6 9 7 ]
Items swapped: [ 9, 7 ]
Iteration 6#:[1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

Go语言核心36讲 -〔郝林〕

玩转Spring全家桶 -〔丁雪丰〕

Serverless入门课 -〔蒲松洋(秦粤)〕

手把手教你玩音乐 -〔邓柯〕

零基础实战机器学习 -〔黄佳〕

朱涛 · Kotlin编程第一课 -〔朱涛〕

说透低代码 -〔陈旭〕

AI绘画核心技术与实战 -〔南柯〕

结构思考力 · 透过结构看表达 -〔李忠秋〕

好记忆不如烂笔头。留下您的足迹吧 :)