个人中心
文章发布
退出
作者热门文章
- Java锁的逻辑（结合对象头和ObjectMonitor）
- 还在用饼状图？来瞧瞧这些炫酷的百分比可视化新图形（附代码实现）⛵
- 自动注册实体类到EntityFrameworkCore上下文，并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
25
4
。
选择排序（Selection Sort）是一种简单直观的排序算法。跟冒泡、插入排序一样，它将数列分为已排序和待排序两个区间。首先在待排序序列中找到最小（或最大）的元素，追加到已排序序列中，然后继续从待排序序列中寻找最小（或最大）的元素，追加到已排序序列的尾部。以此类推，直到所有元素均排序完毕。可以通过同时找出最小和最大项来优化性能，详见源码.
。
。
。
。
。
平均时间复杂度：O(N^2)
最佳时间复杂度：O(N^2)
最差时间复杂度：O(N^2)
空间复杂度：O(1)
排序方式：In-place
稳定性：不稳定
选择排序的交换操作介于和(n-1)次之间。选择排序的比较操作为n(n-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。
比较次数O(n^2)，比较次数与关键字的初始状态无关，总的比较次数N = (n-1) + (n-2) +…+ 1 = n x (n-1)/2。交换次数O(n)，最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。
。
//
java选择排序标准版，更多版本请看源码文件
class
SelectionSort {
static
int
[] selectionSort1(
final
int
[] arr) {
int
min;
int
minIdx;
int
tmp;
int
l =
arr.length;
for
(
int
i = 0; i < l - 1; i++
) {
min
=
arr[i];
minIdx
=
i;
int
j = i + 1
;
for
(; j < l; j++
) {
//
从待排序列表找到最小值和位置
if
(arr[j] <
min) {
min
=
arr[j];
minIdx
=
j;
}
}
System.out.println(
"i=" + i + " j=" + j + " min=" + min + "minIdx=" + minIdx + " arr[]" +
Arrays.toString(arr));
//
将待排序里最小值交换到已排序最后面
if
(minIdx !=
i) {
tmp
=
arr[i];
arr[i]
=
min;
arr[minIdx]
=
tmp;
}
}
return
arr;
}
}
//
选择排序优化版，同时找出最小和最大值进行交换，可减少1半遍历
//
把数列分为前中后三个区间，分别代表最小已排序、中间待排序以及最大已排序区间
//
遍历中间待排序同时找最大和最小值，分别交换到最小值区间和最大值区间
class
SelectionSort {
static
int
[] sort(
final
int
[] arr) {
int
minValue, maxValue, minIdx, maxIdx;
int
minListIdx, maxListIdx;
int
arrLen =
arr.length;
for
(
int
i = 0; i < arrLen - 1; i++
) {
//
待排序里面初始最小值和下标
minIdx =
i;
minValue
=
arr[minIdx];
//
待排序里面初始最大值和下标
maxIdx =
i;
maxValue
=
arr[maxIdx];
//
最小和最大序列里最新待交换的下标
//
最小序列的下标从0开始，自前往后递加
minListIdx =
minIdx;
//
最大序列的下标从数组最后1位开始，自后往前递减
maxListIdx = arrLen - 1 -
i;
//
如果最小和最大下标相同，说明只剩下1个数字，则终止循环
if
(minListIdx ==
maxListIdx) {
break
;
}
//
逐一遍历待排序区间，找出最小和最大值
//
待排序区间在最小值序列和和最大值序列之间
//
待比较区间的下标j从i+1开始，到最大已排序前结束
for
(
int
j = i + 1; j < arrLen - i; j++
) {
//
从待排序列表中分别找到最小值和最大值
if
(arr[j] <
minValue) {
minIdx
=
j;
minValue
=
arr[minIdx];
}
else
if
(arr[j] >
maxValue) {
maxIdx
=
j;
maxValue
=
arr[maxIdx];
}
}
//
如果最小值等于最小序列待交换的值，且最大值等于最大序列里待交换的值，则跳过
if
(arr[minIdx] == arr[minListIdx] && arr[maxIdx] ==
arr[maxListIdx]) {
continue
;
}
//
先交换小值，再交换大值
arr[minIdx] =
arr[minListIdx];
arr[minListIdx]
=
minValue;
//
如果最大值被交换了，则需要更新最大值的下标
if
(arr[minIdx] ==
maxValue) {
maxIdx
=
minIdx;
}
arr[maxIdx]
=
arr[maxListIdx];
arr[maxListIdx]
=
maxValue;
}
return
arr;
}
}
。
。
#
python选择排序标准版本，更多实现版本请查看源文件
#
新建数组版，无需交换
def
selection_sort2(arr):
new_list
=
[]
i
=
0
l
=
len(arr)
while
(i <
l):
min
=
arr[i]
min_idx
=
i
j
= i + 1
while
(j <
l):
#
找到并记录下最小值和位置
if
(arr[j] <
min):
min
=
arr[j]
min_idx
=
j
j
+= 1
#
将待排序里最小值添加到新数组中去
new_list.append(min)
#
原数组中删除对应的项
arr.remove(min)
l
-= 1
return
new_list
"""
# 选择排序优化版，同时找出最小和最大值进行交换，可减少1半遍历
# 把数列分为前中后三个区间，分别代表最小已排序、中间待排序以及最大已排序区间
# 遍历中间待排序同时找最大和最小值，分别交换到最小值区间和最大值区间
"""
def
selection_sort(arr):
arr_len
=
len(arr)
for
i
in
range(arr_len - 1
):
#
初始最小值和下标
min_idx =
i
min_value
=
arr[min_idx]
#
初始最大值和下标
max_idx =
i
max_value
=
arr[max_idx]
#
最小和最大序列里最新待交换的下标
#
最小序列的下标从0开始，自前往后递加
min_list_idx =
min_idx
#
最大序列的下标从数组最后1位开始，自后往前递减
max_list_idx = arr_len - 1 -
i
#
如果最小和最大下标相同，说明只剩下1个数字，则终止循环
if
min_list_idx ==
max_list_idx:
break
#
逐一遍历待排序区间，找出最小和最大值
#
待排序区间在最小值序列和和最大值序列之间
#
待比较区间的下标j从i+1开始，到最大已排序前结束
j = i + 1
while
j < arr_len -
i:
#
从待排序列表找到最小值和最大值及位置
if
arr[j] <
min_value:
min_idx
=
j
min_value
=
arr[min_idx]
elif
arr[j] >
max_value:
max_idx
=
j
max_value
=
arr[max_idx]
j
+= 1
#
如果最小值等于最小序列待交换的值，且最大值等于最大序列里待交换的值，则跳过
if
arr[min_idx] == arr[min_list_idx]
and
arr[max_idx] ==
arr[
max_list_idx]:
continue
print
(
'
min_value=
'
, min_value,
'
max_value=
'
, max_value,
'
min_idx=
'
,
min_idx,
'
max_idx=
'
, max_idx,
'
min_list_idx=
'
, min_list_idx,
'
max_list_idx=
'
, max_list_idx)
#
先交换小值，再交换大值
arr[min_list_idx], arr[min_idx] =
arr[min_idx], arr[min_list_idx]
#
如果最大值被交换了，则需要更新最大值的下标
if
arr[min_idx] ==
max_value:
max_idx
=
min_idx
arr[max_list_idx], arr[max_idx]
=
arr[max_idx], arr[max_list_idx]
return
arr
。
。
//
go选择排序标准版，其他版本请查看源文件
func
selectionSort1(arr []
int
) []
int
{
var
min = arr[
0
]
var
minIdx =
0
var
tmp = -
1
var
arrLen =
len
(arr)
for
i :=
0
; i < arrLen-
1
; i++
{
min
=
arr[i]
minIdx
=
i
var
j = i +
1
for
; j < arrLen; j++
{
//
从待排序列表中找到最小值和位置，用作交换
if
arr[j] <
min {
min
=
arr[j]
minIdx
=
j
}
}
fmt.Println(
"
i=
"
, i,
"
j=
"
, j,
"
min=
"
, min,
"
minIdx=
"
, minIdx,
"
arr[]=
"
, arr)
//
将待排序里最小值交换到已排序最后面
if
minIdx !=
i {
tmp
=
arr[i]
arr[i]
=
min
arr[minIdx]
=
tmp
}
}
return
arr
}
//
选择排序优化版，同时找出最小和最大值进行交换，可减少1半遍历
//
把数列分为前中后三个区间，分别代表最小已排序、中间待排序以及最大已排序区间
//
遍历中间待排序同时找最大和最小值，分别交换到最小值区间和最大值区间
func
selectionSort(arr []
int
) []
int
{
var
minValue
int
var
maxValue
int
var
minIdx
int
var
maxIdx
int
var
minListIdx
int
var
maxListIdx
int
var
arrLen =
len
(arr)
for
i :=
0
; i < arrLen-
1
; i++
{
//
待排序里面初始最小值和下标
minIdx =
i
minValue
=
arr[minIdx]
//
待排序里面初始最大值和下标
maxIdx =
i
maxValue
=
arr[maxIdx]
//
最小和最大序列里最新待交换的下标
//
最小序列的下标从0开始，自前往后递加
minListIdx =
minIdx
//
最大序列的下标从数组最后1位开始，自后往前递减
maxListIdx = arrLen -
1
-
i
//
如果最小和最大下标相同，说明只剩下1个数字，则终止循环
if
minListIdx ==
maxListIdx {
break
}
//
逐一遍历待排序区间，找出最小和最大值
//
待排序区间在最小值序列和和最大值序列之间
//
待比较区间的下标j从i+1开始，到最大已排序前结束
for
j := i +
1
; j < arrLen-i; j++
{
//
从待排序列表中分别找到最小值和最大值
if
arr[j] <
minValue {
minIdx
=
j
minValue
=
arr[minIdx]
}
else
if
arr[j] >
maxValue {
maxIdx
=
j
maxValue
=
arr[maxIdx]
}
}
//
如果最小值等于最小序列待交换的值，且最大值等于最大序列里待交换的值，则跳过
if
arr[minIdx] == arr[minListIdx] && arr[maxIdx] ==
arr[maxListIdx] {
continue
}
fmt.Println(
"
minValue=
"
, minValue,
"
maxValue=
"
, maxValue,
"
minIdx=
"
, minIdx,
"
maxIdx=
"
, maxIdx,
"
minListIdx=
"
, minListIdx,
"
maxListIdx=
"
, maxListIdx)
//
先交换小值，再交换大值
arr[minListIdx], arr[minIdx] =
arr[minIdx], arr[minListIdx]
//
如果最大值被交换了，则需要更新最大值的下标
if
arr[minIdx] ==
maxValue {
maxIdx
=
minIdx
}
arr[maxListIdx], arr[maxIdx]
=
arr[maxIdx], arr[maxListIdx]
}
return
arr
}
。
//
js选择排序徐标准版，更多实现版本详见源码文件
//
新建数组版，无需交换
function
selectionSort2(arr) {
var
min, minIdx
var
newArr =
[]
var
arrLen =
arr.length
for
(
var
i = 0; i < arrLen; i++
) {
min
=
arr[i]
minIdx
=
i
let j
= i + 1
for
(; j < arrLen; j++
) {
//
找到并记录下最小值和位置
if
(arr[j] <
min) {
min
=
arr[j]
minIdx
=
j
}
}
console.log(
'i=' + i, ' j=' + j, 'min=' + min, 'minIdx=' + minIdx, 'arr[]='
, arr)
//
将待排序里最小值添加到新数组中去
newArr.push(min)
//
原数组中删除对应的项
arr.splice(minIdx, 1
)
arrLen
--
i
--
}
return
newArr
}
//
选择排序优化版，同时找出最小和最大值进行交换，可减少1半遍历
//
把数列分为前中后三个区间，分别代表最小已排序、中间待排序以及最大已排序区间
//
遍历中间待排序同时找最大和最小值，分别交换到最小值区间和最大值区间
function
selectionSort(arr) {
let minValue, maxValue, minIdx, maxIdx
let minListIdx, maxListIdx
const arrLen
=
arr.length
//
外循环，从第1项开始与后面待排序项逐个对比，最后1位无需再比较
for
(let i = 0; i < arrLen - 1; i++
) {
//
待排序里面初始最小值和下标
minIdx =
i
minValue
=
arr[minIdx]
//
待排序里面初始最大值和下标
maxIdx =
i
maxValue
=
arr[maxIdx]
//
最小和最大序列里最新待交换的下标
//
最小序列的下标从0开始，自前往后递加
minListIdx =
minIdx
//
最大序列的下标从数组最后1位开始，自后往前递减
maxListIdx = arrLen - 1 -
i
//
如果最小和最大下标相同，说明只剩下1个数字，则终止循环
if
(minListIdx ===
maxListIdx) {
break
}
//
逐一遍历待排序区间，找出最小和最大值
//
待排序区间在最小值序列和和最大值序列之间
//
待比较区间的下标j从i+1开始，到最大已排序前结束
for
(let j = i + 1; j < arrLen - i; j++
) {
//
从待排序列表中分别找到最小值和最大值
if
(arr[j] <
minValue) {
minIdx
=
j
minValue
=
arr[minIdx]
}
else
if
(arr[j] >
maxValue) {
maxIdx
=
j
maxValue
=
arr[maxIdx]
}
}
//
如果最小值等于最小序列待交换的值，且最大值等于最大序列里待交换的值，则跳过
if
(arr[minIdx] === arr[minListIdx] && arr[maxIdx] ===
arr[maxListIdx]) {
continue
}
console.log(
'minValue=', minValue, 'maxValue=', maxValue, 'minIdx=', minIdx, 'maxIdx=', maxIdx, 'minListIdx=', minListIdx, 'maxListIdx='
, maxListIdx)
//
先交换小值，再交换大值
;[arr[minListIdx], arr[minIdx]] =
[arr[minIdx], arr[minListIdx]]
//
如果最大值被交换了，则需要更新最大值的下标
if
(arr[minIdx] ===
maxValue) {
maxIdx
=
minIdx
}
;[arr[maxListIdx], arr[maxIdx]]
=
[arr[maxIdx], arr[maxListIdx]]
}
return
arr
}
。
。
//
TS标准版，其他版本请查看源码文件
class SelectionSort {
constructor() {}
//
标准版
selectionSort1(arr: Array<number>
) {
let min: number, minIdx: number, tmp: number
let l
=
arr.length
for
(let i = 0; i < l - 1; i++
) {
min
=
arr[i]
minIdx
=
i
let j
= i + 1
for
(; j < l; j++
) {
//
从待排序列表找到最小值和位置
if
(arr[j] <
min) {
min
=
arr[j]
minIdx
=
j
}
}
//
将待排序里最小值交换到已排序最后面
if
(minIdx !==
i) {
tmp
=
arr[i]
arr[i]
=
min
arr[minIdx]
=
tmp
}
}
return
arr
}
}
class SelectionSort {
//
选择排序优化版，同时找出最小和最大值进行交换，可减少1半遍历
//
把数列分为前中后三个区间，分别代表最小已排序、中间待排序以及最大已排序区间
//
遍历中间待排序同时找最大和最小值，分别交换到最小值区间和最大值区间
sort(arr: Array<number>
) {
let minValue: number, maxValue: number, minIdx: number, maxIdx: number
let minListIdx: number, maxListIdx: number
const arrLen
=
arr.length
//
外循环，从第1项开始与后面待排序项逐个对比，最后1位无需再比较
for
(let i = 0; i < arrLen - 1; i++
) {
//
待排序里面初始最小值和下标
minIdx =
i
minValue
=
arr[minIdx]
//
待排序里面初始最大值和下标
maxIdx =
i
maxValue
=
arr[maxIdx]
//
最小和最大序列里最新待交换的下标
//
最小序列的下标从0开始，自前往后递加
minListIdx =
minIdx
//
最大序列的下标从数组最后1位开始，自后往前递减
maxListIdx = arrLen - 1 -
i
//
如果最小和最大下标相同，说明只剩下1个数字，则终止循环
if
(minListIdx ===
maxListIdx) {
break
}
//
逐一遍历待排序区间，找出最小和最大值
//
待排序区间在最小值序列和和最大值序列之间
//
待比较区间的下标j从i+1开始，到最大已排序前结束
for
(let j = i + 1; j < arrLen - i; j++
) {
//
从待排序列表中分别找到最小值和最大值
if
(arr[j] <
minValue) {
minIdx
=
j
minValue
=
arr[minIdx]
}
else
if
(arr[j] >
maxValue) {
maxIdx
=
j
maxValue
=
arr[maxIdx]
}
}
//
如果最小值等于最小序列待交换的值，且最大值等于最大序列里待交换的值，则跳过
if
(arr[minIdx] === arr[minListIdx] && arr[maxIdx] ===
arr[maxListIdx]) {
continue
}
//
先交换小值，再交换大值
arr[minIdx] =
arr[minListIdx];
arr[minListIdx]
=
minValue;
//
如果最大值被交换了，则需要更新最大值的下标
if
(arr[minIdx] ==
maxValue) {
maxIdx
=
minIdx;
}
arr[maxIdx]
=
arr[maxListIdx];
arr[maxListIdx]
=
maxValue;
}
return
arr
}
}
。
。
//
c语言选择排序标准版，其他版本请查看源码文件
void
*selection_sort1(
int
arr[],
int
len)
{
int
min_value, min_idx, tmp;
for
(
int
i =
0
; i < len -
1
; i++
)
{
min_value
=
arr[i];
min_idx
=
i;
int
j = i +
1
;
for
(; j < len; j++
)
{
//
从待排序列表找到最小值和位置
if
(arr[j] <
min_value)
{
min_value
=
arr[j];
min_idx
=
j;
}
}
//
将待排序里最小值交换到已排序最后面
if
(min_idx !=
i)
{
tmp
=
arr[i];
arr[i]
=
min_value;
arr[min_idx]
=
tmp;
}
}
return
arr;
}
//
选择排序优化版，同时找出最小和最大值进行交换，可减少1半遍历
//
把数列分为前中后三个区间，分别代表最小已排序、中间待排序以及最大已排序区间
//
遍历中间待排序同时找最大和最小值，分别交换到最小值区间和最大值区间
void
*selection_sort(
int
arr[],
int
len)
{
int
min_value, max_value, min_idx, max_idx;
int
min_list_idx, max_list_idx;
for
(
int
i =
0
; i < len -
1
; i++
)
{
//
待排序里面初始最小值和下标
min_idx =
i;
min_value
=
arr[min_idx];
//
待排序里面初始最大值和下标
max_idx =
i;
max_value
=
arr[max_idx];
//
最小和最大序列里最新待交换的下标
//
最小序列的下标从0开始，自前往后递加
min_list_idx =
min_idx;
//
最大序列的下标从数组最后1位开始，自后往前递减
max_list_idx = len -
1
-
i;
//
如果最小和最大下标相同，说明只剩下1个数字，则终止循环
if
(min_list_idx ==
max_list_idx)
{
break
;
}
//
逐一遍历待排序区间，找出最小和最大值
//
待排序区间在最小值序列和和最大值序列之间
//
待比较区间的下标j从i+1开始，到最大已排序前结束
for
(
int
j = i +
1
; j < len - i; j++
)
{
//
从待排序列表中分别找到最小值和最大值
if
(arr[j] <
min_value)
{
min_idx
=
j;
min_value
=
arr[min_idx];
}
else
if
(arr[j] >
max_value)
{
max_idx
=
j;
max_value
=
arr[max_idx];
}
}
//
如果最小值等于最小序列待交换的值，且最大值等于最大序列里待交换的值，则跳过
if
(arr[min_idx] == arr[min_list_idx] && arr[max_idx] ==
arr[max_list_idx])
{
continue
;
}
//
先交换小值，再交换大值
arr[min_idx] =
arr[min_list_idx];
arr[min_list_idx]
=
min_value;
//
如果最大值被交换了，则需要更新最大值的下标
if
(arr[min_idx] ==
max_value)
{
max_idx
=
min_idx;
}
arr[max_idx]
=
arr[max_list_idx];
arr[max_list_idx]
=
max_value;
}
return
arr;
}
。
。
选择排序算法源码： https://github.com/microwind/algorithms/tree/master/sorts/selectionsort 。
其他排序算法源码： https://github.com/microwind/algorithms 。
最后此篇关于【选择排序算法详解】Java/Go/Python/JS/C不同语言实现的文章就讲到这里了,如果你想了解更多关于【选择排序算法详解】Java/Go/Python/JS/C不同语言实现的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
25
4
0
我正在学习构建单页应用程序 (SPA) 所需的所有技术。总而言之，我想将我的应用程序实现为单独的层，其中前端仅使用 API Web 服务(json 通过 socket.io)与后端通信。前端基本上是
当我看到存储在我的数据库中的日期时。 这是 正常 。日期和时间就是这样。 但是当我运行 get 请求来获取数据时。 此格式与存储在数据库 中的格式不同。为什么会发生这种情况？ 最佳答案 我认为您可以将
就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the
我正在尝试使用backbone.js 实现一些代码 和 hogan.js (http://twitter.github.com/hogan.js/) Hogan.js was developed ag
我正在使用 Backbone.js、Node.js 和 Express.js 制作一个 Web 应用程序，并且想要添加用户功能(登录、注销、配置文件、显示内容与该用户相关)。我打算使用 Passpor
关闭。这个问题需要多问focused 。目前不接受答案。 想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post . 已关闭 8 年前。 Improve this ques
我尝试在 NodeJS 中加载数据，然后将其传递给 ExpressJS 以在浏览器中呈现 d3 图表。 我知道我可以通过这种方式加载数据 - https://github.com/mbostock/q
在 node.js 中，我似乎遇到了相同的 3 个文件名来描述应用程序的主要入口点: 使用 express-generator 包时，会创建一个 app.js 文件作为生成应用的主要入口点。 通过 n
最近，我有机会观看了 john papa 关于构建单页应用程序的精彩类(class)。我会喜欢的。它涉及服务器端和客户端应用程序的方方面面。 我更喜欢客户端。在他的实现过程中，papa先生在客户端有类
就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the
我是一个图形新手，需要帮助了解各种 javascript 2D 库的功能。 . . 我从 Pixi.js 中得到了什么，而我没有从 Konva 等基于 Canvas 的库中得到什么？ 我从 Konva
我正在尝试将一些 LESS 代码(通过 ember-cli-less)构建到 CSS 文件中。 1) https://almsaeedstudio.com/ AdminLTE LESS 文件2) Bo
尝试查看 Express Passport 中所有登录用户的所有 session ，并希望能够查看当前登录的用户。最好和最快的方法是什么？ 我在想也许我可以在登录时执行此操作并将用户模型数据库“在线”
我有一个 React 应用程序，但我需要在组件加载完成后运行一些客户端 js。一旦渲染函数完成并加载，运行与 DOM 交互的 js 的最佳方式是什么，例如 $('div').mixItUp() 。对
请告诉我如何使用bodyparser.raw()将文件上传到express.js服务器 客户端 // ... onFilePicked(file) { const url = 'upload/a
我正在尝试从 Grunt 迁移到 Gulp。这个项目在 Grunt 下运行得很好，所以我一定是在 Gulp 中做错了什么。 除脚本外，所有其他任务均有效。我现在厌倦了添加和注释部分。 我不断收到与意外
我正在尝试更改我的网站名称。找不到可以设置标题或应用程序名称的位置。 最佳答案 您可以在 config/ 目录中创建任何文件，例如 config/app.js 包含如下内容: module.expor
经过多年的服务器端 PHP/MySQL 开发，我正在尝试探索用于构建现代 Web 应用程序的新技术。 我正在尝试对所有 JavaScript 内容进行排序，如果我理解得很好，一个有效的解决方案可以是服
我是 Nodejs 的新手。我在 route 目录中有一个 app.js 和一个 index.js。我有一个 app.use(multer....)。我还定义了 app.post('filter-re
我正在使用 angular-seed用于构建我的应用程序的模板。最初，我将所有 JavaScript 代码放入一个文件 main.js。该文件包含我的模块声明、 Controller 、指令、过滤器和
我是一名优秀的程序员,十分优秀！