本文概述
- 例
- 复杂
- 算法
- C程序
- C ++程序
- Java程序
- C＃程序
- Python程序
- 休息计划
- JavaScript程序
- PHP程序
首先, 找到数组的最小元素并将其放在第一个位置。然后, 找到数组的第二个最小元素并将其放在第二个位置。这个过程一直持续到我们得到排序数组为止。
使用选择排序算法的n-1遍对具有n个元素的数组进行排序。
- 在第一遍中, 将找到数组的最小元素及其索引pos。然后, 交换A [0]和A [pos]。因此, 对A [0]进行了排序, 现在我们有n -1个要排序的元素。
- 在第二步中, 找到子数组A [n-1]中存在的最小元素的位置pos。然后, 交换A [1]和A [pos]。因此, 对A [0]和A [1]进行了排序, 现在剩下n-2个未排序的元素。
- 在第n-1次通过中, 将找到A [n-1]和A [n-2]之间较小元素的位置pos。然后, 交换A [pos]和A [n-1]。
例考虑以下包含6个元素的数组。通过使用选择排序对数组的元素进行排序。
A = {10, 2, 3, 90, 43, 56}。
| 通过 | 发布 | A [0] | A [1] | A2] | A [3] | A [4] | A [5] |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 10 | 3 | 90 | 43 | 56 |
| 2 | 2 | 2 | 3 | 10 | 90 | 43 | 56 |
| 3 | 2 | 2 | 3 | 10 | 90 | 43 | 56 |
| 4 | 4 | 2 | 3 | 10 | 43 | 90 | 56 |
| 5 | 5 | 2 | 3 | 10 | 43 | 56 | 90 |
复杂
| 复杂 | 最好的情况 | 平均情况 | 最差的情况 |
|---|---|---|---|
| Time | Ω(n) | θ(n2) | o(n2) |
| Space | o(1) |
- 步骤1：对于K = 1到N-1, 重复步骤2和3
- 步骤2：呼叫最小（ARR, K, N, POS）
- 第3步：用ARR [POS]交换A [K] [LOOP结束]
- 步骤4：退出
- 第1步：[初始化]设置小= ARR [K]
- 步骤2：[INITIALIZE] SET POS = K
- 步骤3：对J = K + 1到N -1重复, 如果SMALL> ARR [J] SET SMALL = ARR [J] SET POS = J [IF结束] [LOOP结束]
- 步骤4：退回POS
#include<
stdio.h>
int smallest(int[], int, int);
void main ()
{
int a[10] = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};
int i, j, k, pos, temp;
for(i=0;
i<
10;
i++)
{
pos = smallest(a, 10, i);
temp = a[i];
a[i]=a[pos];
a[pos] = temp;
}
printf("\nprinting sorted elements...\n");
for(i=0;
i<
10;
i++)
{
printf("%d\n", a[i]);
}
}
int smallest(int a[], int n, int i)
{
int small, pos, j;
small = a[i];
pos = i;
for(j=i+1;
j<
10;
j++)
{
if(a[j]<
small)
{
small = a[j];
pos=j;
}
}
return pos;
}输出：
printing sorted elements...
7
9
10
12
23
23
34
44
78
101C ++程序
#include<
iostream>
using namespace std;
int smallest(int[], int, int);
int main ()
{
int a[10] = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};
int i, j, k, pos, temp;
for(i=0;
i<
10;
i++)
{
pos = smallest(a, 10, i);
temp = a[i];
a[i]=a[pos];
a[pos] = temp;
}
cout<
<
"\n printing sorted elements...\n";
for(i=0;
i<
10;
i++)
{
cout<
<
a[i]<
<
"\n";
}
return 0;
}
int smallest(int a[], int n, int i)
{
int small, pos, j;
small = a[i];
pos = i;
for(j=i+1;
j<
10;
j++)
{
if(a[j]<
small)
{
small = a[j];
pos=j;
}
}
return pos;
}输出：
printing sorted elements...
7
9
10
12
23
23
34
44
78
101Java程序
public class SelectionSort {
public static void main(String[] args) {
int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};
int i, j, k, pos, temp;
for(i=0;
i<
10;
i++)
{
pos = smallest(a, 10, i);
temp = a[i];
a[i]=a[pos];
a[pos] = temp;
}
System.out.println("\nprinting sorted elements...\n");
for(i=0;
i<
10;
i++)
{
System.out.println(a[i]);
}
}
public static int smallest(int a[], int n, int i)
{
int small, pos, j;
small = a[i];
pos = i;
for(j=i+1;
j<
10;
j++)
{
if(a[j]<
small)
{
small = a[j];
pos=j;
}
}
return pos;
}
}输出：
printing sorted elements...
7
9
10
12
23
23
34
44
78
101C＃程序
using System;
public class Program
{
public void Main() {
int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};
int i, pos, temp;
for(i=0;
i<
10;
i++)
{
pos = smallest(a, 10, i);
temp = a[i];
a[i]=a[pos];
a[pos] = temp;
}
Console.WriteLine("\nprinting sorted elements...\n");
for(i=0;
i<
10;
i++)
{
Console.WriteLine(a[i]);
}
}
public static int smallest(int[] a, int n, int i)
{
int small, pos, j;
small = a[i];
pos = i;
for(j=i+1;
j<
10;
j++)
{
if(a[j]<
small)
{
small = a[j];
pos=j;
}
}
return pos;
}
}输出：
printing sorted elements...
7
9
10
12
23
23
34
44
78
101Python程序
def smallest(a, i):
small = a[i]
pos=i
for j in range(i+1, 10):
if a[j] <
small:
small = a[j]
pos = j
return pos a=[10, 9, 7, 101, 23, 44, 12, 78, 34, 23]
for i in range(0, 10):
pos = smallest(a, i)
temp = a[i]
a[i]=a[pos]
a[pos]=temp
print("printing sorted elements...")
for i in a:
print(i)输出：
printing sorted elements...
7
9
10
12
23
23
34
44
78
101休息计划
fn main ()
{
let mut a: [i32;
10] = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];
for i in 0..10
{
let mut small = a[i];
let mut pos = i;
for j in (i+1)..10
{
if a[j]<
small
{
small = a[j];
pos=j;
}
}
let mut temp = a[i];
a[i]=a[pos];
a[pos] = temp;
}
println!("\nprinting sorted elements...\n");
for i in &
a
{
println!("{}", i);
}
}输出：
printing sorted elements...7
9
10
12
23
23
34
44
78
101JavaScript程序
<
html>
<
head>
<
title>
Selection Sort
<
/title>
<
/head>
<
body>
<
script>
function smallest(a, n, i)
{
var small = a[i];
var pos = i;
for(j=i+1;
j<
10;
j++)
{
if(a[j]<
small)
{
small = a[j];
pos=j;
}
}
return pos;
}
var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];
for(i=0;
i<
10;
i++)
{
pos = smallest(a, 10, i);
temp = a[i];
a[i]=a[pos];
a[pos] = temp;
}
document.writeln("printing sorted elements ...\n"+"<
br>
");
for(i=0;
i<
10;
i++)
{
document.writeln(a[i]+"<
br>
");
}
<
/script>
<
/body>
<
/html>
输出：
printing sorted elements ...
7
9
10
12
23
23
34
44
78
101PHP程序
<
html>
<
head>
<
title>
Selection sort<
/title>
<
/head>
<
body>
<
?php
function smallest($a, $n, $i)
{
$small = $a[$i];
$pos = $i;
for($j=$i+1;
$j<
10;
$j++)
{
if($a[$j]<
$small)
{
$small = $a[$j];
$pos=$j;
}
}
return $pos;
}
$a = array(10, 9, 7, 101, 23, 44, 12, 78, 34, 23);
for($i=0;
$i<
10;
$i++)
{
$pos = smallest($a, 10, $i);
$temp = $a[$i];
$a[$i]=$a[$pos];
$a[$pos] = $temp;
}
echo "printing sorted elements ...\n";
for($i=0;
$i<
10;
$i++)
{
echo $a[$i];
echo "\n";
}
?>
<
/body>
<
/html>
输出：
printing sorted elements ...
7
9
10
12
23
23
34
44
78
101
