排序算法之选择排序

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。
它的基本思想是:首先在未排序的数列中找到最小(or最大)元素,然后将其存放到数列的起始位置;接着,再从剩余未排序的元素中继续寻找最小(or最大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

  流程如图所示

排序流程

第1趟:i=0。找出a[1...5]中的最小值a[3]=10,然后将a[0]和a[3]互换。 数列变化:20,40,30,10,60,50 -- > 10,40,30,20,60,50
第2趟:i=1。找出a[2...5]中的最小值a[3]=20,然后将a[1]和a[3]互换。 数列变化:10,40,30,20,60,50 -- > 10,20,30,40,60,50
第3趟:i=2。找出a[3...5]中的最小值,由于该最小值大于a[2],该趟不做任何处理。 
第4趟:i=3。找出a[4...5]中的最小值,由于该最小值大于a[3],该趟不做任何处理。 
第5趟:i=4。交换a[4]和a[5]的数据。 数列变化:10,20,30,40,60,50 -- > 10,20,30,40,50,60

代码实现:

1.Python实现

1ARRAY = [20, 40, 30, 10, 60, 50] 2for i in range(len(ARRAY) - 1): 3 4 for j in range(i + 1, len(ARRAY)): 5 if ARRAY[j] < ARRAY[i]: 6 temp = ARRAY[j] 7 ARRAY[j] = ARRAY[i] 8 ARRAY[i] = temp 9 print(ARRAY) 10 11

2.C语言实现

1 int i; // 有序区的末尾位置 2 int j; // 无序区的起始位置 3 int min; // 无序区中最小元素位置 4 int a[6]={20, 40, 30, 10, 60, 50} 5 for(i=0; i<n; i++) 6 { 7 min=i; 8 9 // 找出"a[i+1] ... a[n]"之间的最小元素,并赋值给min。 10 for(j=i+1; j<n; j++) 11 { 12 if(a[j] < a[min]) 13 min=j; 14 } 15 16 // 若min!=i,则交换 a[i] 和 a[min]。 17 // 交换之后,保证了a[0] ... a[i] 之间的元素是有序的。 18 if(min != i) 19 swap(a[i], a[min]); 20 } 21

 

3.汇编实现

1DATAS SEGMENT 2 ARRAY DB 20, 40, 30, 10, 60, 50 3 NUM EQU $-ARRAY 4 NEWSPACE DB ' ','$' 5DATAS ENDS 6 7STACKS SEGMENT 8 9 DW 40H DUP(?) 10 TOP LABEL WORD 11STACKS ENDS 12 13CODES SEGMENT 14 ASSUME CS:CODES,DS:DATAS,SS:STACKS 15START: 16 MOV AX,DATAS 17 MOV DS,AX 18 MOV AX,STACKS 19 MOV SS,AX 20 LEA SP,TOP 21 MOV CX,NUM 22 LEA BX,ARRAY 23 MOV SI,0 24 MOV DI,0 25 DEC CX ;需要对比几趟 26OUTTER: 27 PUSH CX;保存外层第几趟 28 MOV AH,[BX+SI];前后俩数大小 29 MOV DI,SI 30 INC DI 31 32INNER: 33 34 35 MOV AL,[BX+DI];前后俩数大小 36 CMP AL,AH;前后俩数大小 37 JB XCHANGE;前者大于后者则交换位置 38NEXT: 39 40 INC DI 41 LOOP INNER 42 INC SI 43 POP CX 44 LOOP OUTTER 45 JMP EXIT 46 47XCHANGE: 48 ;交换位置 49 50 MOV [BX+SI],AL 51 MOV [BX+DI],AH 52 JMP NEXT 53 54 55EXIT: 56 MOV CX,NUM 57 MOV SI,0 58 PRINTF: 59 XOR AX,AX 60 PUSH CX 61 MOV AL,ARRAY[SI] 62 INC SI 63 MOV CX,0 64 PUSHIN: 65 XOR DX,DX 66 MOV BX,10 67 DIV BX 68 PUSH DX 69 INC CX 70 CMP AX,0 71 JNE PUSHIN 72 POPOUT: 73 POP DX 74 ADD DL,30H 75 MOV AH,2H 76 INT 21H 77 78 LOOP POPOUT 79 80 POP CX 81 LEA DX,NEWSPACE 82 MOV AH,9H 83 INT 21H 84 LOOP PRINTF 85 86 MOV AH,4CH 87 INT 21H 88CODES ENDS 89 END START 90 91 92 93 94 95 96

 

上一篇:插入排序

代码交流 2021