数据结构&算法 选择排序
-
选择排序
选择排序是一种简单的排序算法。该排序算法是一种基于就地比较的算法,其中,列表分为两部分,左端为已排序部分,右端为未排序部分。最初,已排序部分为空,未排序部分为整个列表。从未排序的数组中选择最小的元素,并与最左边的元素交换,该元素成为排序数组的一部分。此过程继续将未排序的数组边界向右移动一个元素。该算法不适用于大型数据集,因为它的平均和最坏情况下的复杂度为Ο(n2),其中n是项数。 -
选择排序如何工作?
以下面描述的数组为例。对于排序列表中的第一个位置,将顺序扫描整个列表。当前存储14的第一个位置,我们搜索整个列表,发现10是最低值。因此,我们将10替换为14。一次迭代10(恰好是列表中的最小值)出现在已排序列表的第一位置。对于第二个位置(33个位置),我们开始以线性方式扫描列表的其余部分。我们发现14是列表中第二低的值,它应该出现在第二位。我们交换这些值。经过两次迭代后,两个最小值以排序的方式位于开头。将相同的过程应用于数组中的其余项目。以下是整个分类过程的图示-现在,让我们学习选择排序的一些编程方面。 -
算法
现在,我们对这种排序技术的工作原理有了更全面的了解,因此我们可以推导简单的步骤来实现选择排序。步骤 1 − 将最小值设置为位置0 步骤 2 − 搜索列表中的最小元素 步骤 3 − 在最小位置用值交换 步骤 4 − 增加最小值以指向下一个元素 步骤 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语言的实现
尝试一下#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); }