2023 跟我一起学算法：排序算法

用户1418987

发布于 2023-11-24 10:44:46

1280

发布于 2023-11-24 10:44:46

文章被收录于专栏：codercoder

排序算法

什么是排序？

排序算法用于根据元素上的比较运算符重新排列给定的数组或元素列表。比较运算符用于决定相应数据结构中元素的新顺序。

例如： 下面的字符列表按其 ASCII 值的升序排序。也就是说，具有较小 ASCII 值的字符将比具有较高 ASCII 值的字符先放置。

选择排序

选择排序是一种简单而高效的排序算法，其工作原理是重复从列表的未排序部分中选择最小（或最大）元素并将其移动到列表的已排序部分。

“选择排序”算法工作原理

让我们以以下数组为例：arr[] = {64, 25, 12, 22, 11}

第一遍：

对于排序数组中的第一个位置，从索引 0 到 4 顺序遍历整个数组。当前存储64的第一个位置，遍历整个数组后很明显11是最低值。
因此，将 64 替换为 11。一次迭代后， 11（恰好是数组中的最小值）往往会出现在排序列表的第一个位置。

第二遍：

对于存在 25 的第二个位置，再次按顺序遍历数组的其余部分。
遍历完后，我们发现12是数组中倒数第二小的值，它应该出现在数组的第二位，因此交换这些值。

第三遍：

现在，对于第三个位置，其中存在**25，**再次遍历数组的其余部分并找到数组中存在的第三个最小值。
遍历时，22是第三个最小值，它应该出现在数组中的第三个位置，因此将22与第三个位置上的元素交换。

第四遍：

类似地，对于第四个位置，遍历数组的其余部分并找到数组中第四小的元素
由于25是第四低的值，因此它将排在第四位。

第五遍：

最后，数组中存在的最大值自动放置在数组的最后一个位置
结果数组是排序后的数组。

代码实现：

javascript

<script>
// 选择排序的JavaScript程序实现
function swap(arr,xp, yp)
{
	var temp = arr[xp];
	arr[xp] = arr[yp];
	arr[yp] = temp;
}

function selectionSort(arr, n)
{
	var i, j, min_idx;
	// 逐个移动未排序子数组的边界
	for (i = 0; i < n-1; i++)
	{
    // 在未排序的数组中找到最小元素
		min_idx = i;
		for (j = i + 1; j < n; j++)
		if (arr[j] < arr[min_idx])
			min_idx = j;
		// 将找到的最小元素与第一个元素交换位置
		swap(arr,min_idx, i);
	}
}

function printArray( arr, size)
{
	var i;
	for (i = 0; i < size; i++)
		console.log(arr[i] + " ");
}

var arr = [64, 25, 12, 22, 11];
	var n = 5;
	selectionSort(arr, n);
	document.write("Sorted array: <br>");
	printArray(arr, n);
</script>

golang

package main

import (
	"testing"

	"github.com/stretchr/testify/assert"
)

type ArrT interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 | ~float32 | ~float64
}

// SelectSort 选择排序
func SelectSort[T ArrT](arr []T) []T {
	var length = len(arr)
	for i := 0; i < length-1; i++ {
		var minIndex = i
		for j := i + 1; j < length; j++ {
			if arr[minIndex] > arr[j] {
				minIndex = j
			}
		}
		arr[minIndex], arr[i] = arr[i], arr[minIndex]
	}

	return arr
}

func Test_SelectSort(t *testing.T) {
	var arr = []int{64, 25, 12, 22, 11}

	var except = []int{11, 12, 22, 25, 64}
	assert.Equal(t, except, SelectSort[int](arr))
}

输出

排序数组： 11 12 22 25 64