选择排序

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

参考链接

算法描述

1、首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
2、再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
3、重复第二步,直到所有元素均排序完毕。

动图演示

在这里插入图片描述

代码实现

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package com.test;

import java.util.Arrays;

public class MySorts {


public static void main(String[] args) {
int[] arr = new int[]{23,20,32,5,45,6,8,9,15,1};
selectionSort(arr);
System.out.println("排序結果:"+ Arrays.toString(arr));
}

private static void selectionSort(int[] arr) {
for(int i=0;i<arr.length-1;i++){
int minIndex = i;//最小数位置
for(int j=i;j<arr.length-1;j++){
if(arr[j+1]<arr[minIndex]){
minIndex = j+1;
}
}
//内循环结束说明找到了最小数位置
if(minIndex != i){
swapReferences(arr,minIndex,i);
}
}
}

private static void swapReferences(int[] arr, int minIndex, int i) {
int tmp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = tmp;
}
}

排序結果:[1, 5, 6, 8, 9, 15, 20, 23, 32, 45]

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function selectionSort(arr) {
for(var i=0;i<arr.length-1;i++){
var minIndex = i;//最小数位置
for(var j=i;j<arr.length-1;j++){
if(arr[j+1]<arr[minIndex]){
minIndex = j+1;
}
}
//内循环结束说明找到了最小数位置
if(minIndex != i){
swapReferences(arr,minIndex,i);
}
}
return arr;
}

function swapReferences(arr,minIndex,i){
var tmp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = tmp;
}

var arr = [23,20,32,5,45,6,8,9,15,1];
var arrSorted = selectionSort(arr);
console.log(arrSorted);

(10) [1, 5, 6, 8, 9, 15, 20, 23, 32, 45]