选择排序算法

选择排序是一种简单的排序算法。这种排序算法类似于插入排序，是一种基于就地比较的算法，将列表分为两部分：左端是已排序部分，右端是未排序部分。初始时，已排序部分为空，未排序部分为整个列表。

从未排序数组中选择最小元素，并将其与最左边的元素交换，该元素将成为已排序数组的一部分。此过程持续将未排序数组的边界向右移动一个元素。

此算法不适用于大型数据集，因为其平均和最坏情况复杂度均为 O(n²)，其中 n 为元素数量。

选择排序算法

这种排序称为选择排序，因为它通过重复对元素进行排序来工作。也就是说：我们首先找到数组中的最小值，并将其与第一个位置的元素交换，然后找到第二小的元素，并将其与第二个位置的元素交换，如此反复，直到整个数组排序完毕。

1. 将 MIN 设置为位置 0。
2. 搜索列表中的最小元素。
3. 与位置 MIN 处的值交换。
4. 增加 MIN 以指向下一个元素。
5. 重复此操作，直到列表排序完毕。

伪代码

Algorithm: Selection-Sort (A)
fori← 1 to n-1 do
   min j ←i;
   min x ← A[i]
   for j ←i + 1 to n do
      if A[j] < min x then
         min j ← j
         min x ← A[j]
   A[min j] ← A [i]
   A[i] ← min x

分析

选择排序是最简单的排序技术之一，它非常适合处理小文件。它有一个非常重要的应用，因为每个项目实际上最多移动一次。

分段排序是用于对包含非常大的对象（记录）和小键的文件进行排序的首选方法。最坏的情况是，如果数组已经按降序排序，而我们想按升序排序，则会发生这种情况。

尽管如此，选择排序算法所需的时间对待排序数组的原始顺序不太敏感：测试𝑨[𝒋] < A[j] < min x 的次数在每种情况下都完全相同。

选择排序的大部分时间都用于尝试在数组的未排序部分中找到最小元素。它清楚地显示了选择排序和冒泡排序之间的相似性。

• 冒泡排序在每个阶段都会选择最多的剩余元素，但在对数组中未排序的部分进行排序时会浪费一些精力。

• 选择排序在最坏情况和平均情况下都是二次函数，并且不需要额外的内存。

对于从 1 到 n - 1 的每个 i，都有一次交换和 n - i 次比较，因此总共有 n - 1 次交换和

(n − 1) + (n − 2) + ...+2 + 1 = n(n − 1)/2 次比较。

无论输入数据是。

在最坏的情况下，这个时间复杂度可能是二次方的，但在平均情况下，这个时间复杂度是O(n log n)。这意味着选择排序的运行时间对输入非常不敏感。

示例

以下图所示的数组为例。

对于排序列表中的第一个位置，将按顺序扫描整个列表。第一个位置当前存储的是 14，我们搜索整个列表，发现 10 是最小值。

因此，我们将 14 替换为 10。经过一次迭代后，恰好是列表中最小值的 10 出现在排序列表的第一个位置。

对于第二个位置，也就是 33 所在的位置，我们开始以线性方式扫描列表的其余部分。

我们发现 14 是列表中第二低的值，它应该出现在第二位。我们交换这些值。

经过两次迭代后，两个最小值将按排序方式放置在开头。

对数组中其余项应用相同的过程 −

实现

选择排序算法已在以下四种不同的编程语言中实现。给定的程序选择数组中的最小数字，并将其与第一个索引中的元素交换。将第二个最小数字与第二个索引中的元素交换。此过程持续进行，直到到达数组末尾。

#include <stdio.h>
void selectionSort(int array[], int size){
   int i, j, imin;
   for(i = 0; i<size-1; i++) {
      imin = i; //获取最小数据的索引
      for(j = i+1; j<size; j++)
         if(array[j] < array[imin])
            imin = j;
      
      //放置在正确的位置
      int temp;
      temp = array[i];
      array[i] = array[imin];
      array[imin] = temp;
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {12, 19, 55, 2, 16}; //初始化数组
   printf("排序前的数组：");
   for(int i = 0; i<n; i++)
      printf("%d ",arr[i]);
   printf("
");
   selectionSort(arr, n);
   printf("排序后的数组：");
   for(int i = 0; i<n; i++)
      printf("%d ", arr[i]);
   printf("
");
}

排序前的数组：12 19 55 2 16
排序后的数组：2 12 16 19 55

#include<iostream>
using namespace std;
void swapping(int &a, int &b) {  //交换a和b的内容
   int temp;
   temp = a;
   a = b;
   b = temp;
}
void selectionSort(int *array, int size){
   int i, j, imin;
   for(i = 0; i<size-1; i++) {
      imin = i; //获取最小数据的索引
      for(j = i+1; j<size; j++)
         if(array[j] < array[imin])
            imin = j;

      //放置在正确的位置
      swap(array[i], array[imin]);
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {12, 19, 55, 2, 16}; //初始化数组
   cout << "排序前的数组：";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
   selectionSort(arr, n);
   cout << "排序后的数组：";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
}

排序前的数组：12 19 55 2 16
排序后的数组：2 12 16 19 55

import java.io.*;
public class SelectionSort {
   public static void main(String args[]) {
      int n = 5;
      int[] arr = {12, 19, 55, 2, 16}; //初始化数组
      System.out.print("排序前的数组：");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
      int imin;
      for(int i = 0; i<n-1; i++) {
         imin = i; //获取最小数据的索引
         for(int j = i+1; j<n; j++)
            if(arr[j] < arr[imin])
               imin = j;
         
         //放置在正确的位置
         int temp;
         temp = arr[i];
         arr[i] = arr[imin];
         arr[imin] = temp;
      }
      System.out.print("排序后的数组：");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
   }
}

排序前的数组：12 19 55 2 16 

排序后的数组：2 12 16 19 55

def insertion_sort(array, size):
   for i in range(size):
      imin = i
      for j in range(i+1, size):
         if arr[j] < arr[imin]:
            imin = j
      temp = array[i];
      array[i] = array[imin];
      array[imin] = temp;

arr = [12, 19, 55, 2, 16]
n = len(arr)
print("排序前的数组：")
print(arr)
insertion_sort(arr, n);
print("排序后的数组：")
print(arr)

排序前的数组：
[12, 19, 55, 2, 16]
排序后的数组：
[2, 12, 16, 19, 55]