go-数据结构[8]-选择排序

选择排序

选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理如下,首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的序列进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

实例分析

以数组 arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 为例,先直观看一下每一步的变化,后面再介绍细节

第一次从数组 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 中找到最小的数 0,放到数组的最前面(与第一个元素进行交换):

1
2
3
4
5
                               min

8 5 2 6 9 3 1 4 0 7

└───────────────────────────────┘

交换后:

1
0   5   2   6   9   3   1   4   8   7

在剩余的序列中 [5, 2, 6, 9, 3, 1, 4, 8, 7] 中找到最小的数 1,与该序列的第一个个元素进行位置交换:

1
2
3
4
5
                       min

0 5 2 6 9 3 1 4 8 7
↑ ↑
└───────────────────┘

交换后:

1
0   1   2   6   9   3   5   4   8   7

在剩余的序列中 [2, 6, 9, 3, 5, 4, 8, 7] 中找到最小的数 2,与该序列的第一个个元素进行位置交换(实际上不需要交换):

1
2
3
4
5

min

0 1 2 6 9 3 5 4 8 7

重复上述过程,直到最后一个元素就完成了排序。

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
                   min

0 1 2 6 9 3 5 4 8 7
↑ ↑
└───────┘
min

0 1 2 3 9 6 5 4 8 7
↑ ↑
└───────────┘
min

0 1 2 3 4 6 5 9 8 7
↑ ↑
└───┘
min

0 1 2 3 4 5 6 9 8 7

min

0 1 2 3 4 5 6 9 8 7
↑ ↑
└───────┘
min

0 1 2 3 4 5 6 7 8 9

min

0 1 2 3 4 5 6 7 8 9

go语言实现

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package main

import "fmt"
//打印
func print(arr []int){

for _,data := range arr{
fmt.Printf("%d ",data)
}

fmt.Println()
}



func main(){

arr:= []int{8, 5, 2, 6, 9, 3, 1, 4, 0, 7}
print(arr)

selectSort(arr)

print(arr)
}

//选择排序
func selectSort(arr []int){

length := len(arr)
//第一个循环从第一个元素到倒数第二个元素。
for i:= 0;i<length-1;i++{
//最小的序号
index:= i
//遍历其后面的节点,找到最小的节点的下标。
for j:= i+1;j<length;j++{
if arr[index]> arr[j]{
//保留下标
index = j
}
}
//index != i,就将最小的数交换到a[i]的位置。
if index != i{
temp := arr[i]
arr[i] = arr[index]
arr[index] = temp
}
}
}

c语言实现

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<stdio.h>
#include<stdlib.h>

void select_sort(int *a,int length) ;
void show(int *a,int length);
void main()
{
int a[10] = { 1,3,2,4,9,2,6,5,4,8 };
show(a, 10);
select_sort(a, 10);
show(a, 10);
system("pause");
}
//打印
void show(int *a,int length)
{
for (int i = 0; i < length; i++)
{
printf("%d\n", a[i]);
}
printf("---------------------------\n");
}
//选择排序
//选择排序排序,a为数组,length为其长度
void select_sort(int *a,int length)
{
//最小的序号
int min = 0;
//第一个循环从第一个元素到倒数第二个元素。
for (int i = 0; i < length - 1; i++)
{
//保留下标
min = i;
//遍历其后面的节点,找到最小的节点的下标。
for (int j = i + 1; j < length; j++)
{
if (a[j] > a[min])
{
min = j;
}
}
//如果min != i,就将最小的数交换到a[i]的位置。
if (min != i)
{
int temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
}

js实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function selectionSort(array) {
var length = array.length,
i,
j,
minIndex,
minValue,
temp;
for (i = 0; i < length - 1; i++) {
minIndex = i;
minValue = array[minIndex];
for (j = i + 1; j < length; j++) {
if (array[j] < minValue) {
minIndex = j;
minValue = array[minIndex];
}
}
// 交换位置
temp = array[i];
array[i] = minValue;
array[minIndex] = temp;
}
return array
}

参考文献