排序算法用于根据元素上的比较运算符重新排列给定的数组或元素列表。比较运算符用于决定相应数据结构中元素的新顺序。
例如:下面的字符列表按其 ASCII 值的升序排序。也就是说,具有较小 ASCII 值的字符将比具有较高 ASCII 值的字符先放置。
选择排序是一种简单而高效的排序算法,其工作原理是重复从列表的未排序部分中选择最小(或最大)元素并将其移动到列表的已排序部分。
让我们以以下数组为例:arr[] = {64, 25, 12, 22, 11}
<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>
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
时间复杂度:选择排序的时间复杂度为O(N 2 ),因为有两个嵌套循环:
辅助空间: O(1),因为在交换数组中的两个值时,唯一使用的额外内存用于临时变量。选择排序不会进行超过 O(N) 的交换,并且在内存写入成本高昂时非常有用。
Q1. 选择排序算法稳定吗?
选择排序算法的默认实现并不稳定。
Q2。选择排序算法是否到位?
是的,选择排序算法是一种原地算法,因为它不需要额外的空间。
阅读量:934
点赞量:0
收藏量:0