选择排序算法

选择排序是一种简单的排序算法。这种排序算法与插入排序一样，是一种原地比较排序算法，其中列表被分成两个部分，排序部分在左侧，未排序部分在右侧。最初，排序部分为空，未排序部分是整个列表。

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

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

选择排序算法

这种类型的排序称为选择排序，因为它通过重复排序元素来工作。也就是说：我们首先找到数组中最小的值并将其与第一个位置的元素交换，然后找到第二小的元素并将其与第二个位置的元素交换，我们继续这个过程，直到整个数组被排序。

1. Set MIN to location 0.
2. Search the minimum element in the list.
3. Swap with value at location MIN.
4. Increment MIN to point to next element.
5. Repeat until the list is sorted.

伪代码

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` 在每种情况下执行的次数完全相同。

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

• 冒泡排序在每个阶段选择剩余的最大元素，但浪费了一些努力来对数组的未排序部分进行排序。

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

对于从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; //get index of minimum data
      for(j = i+1; j<size; j++)
         if(array[j] < array[imin])
            imin = j;
      
      //placing in correct position
      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}; // initialize the array
   printf("Array before Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ",arr[i]);
   printf("\n");
   selectionSort(arr, n);
   printf("Array after Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ", arr[i]);
   printf("\n");
}

Array before Sorting: 12 19 55 2 16
Array after Sorting: 2 12 16 19 55

#include<iostream>
using namespace std;
void swapping(int &a, int &b) {  //swap the content of a and 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; //get index of minimum data
      for(j = i+1; j<size; j++)
         if(array[j] < array[imin])
            imin = j;

      //placing in correct position
      swap(array[i], array[imin]);
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {12, 19, 55, 2, 16}; // initialize the array
   cout << "Array before Sorting: ";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
   selectionSort(arr, n);
   cout << "Array after Sorting: ";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
}

Array before Sorting: 12 19 55 2 16
Array after Sorting: 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}; //initialize an array
      System.out.print("Array before Sorting: ");
      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; //get index of minimum data
         for(int j = i+1; j<n; j++)
            if(arr[j] < arr[imin])
               imin = j;
         
         //placing in correct position
         int temp;
         temp = arr[i];
         arr[i] = arr[imin];
         arr[imin] = temp;
      }
      System.out.print("Array After Sorting: ");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
   }
}

Array before Sorting: 12 19 55 2 16 

Array After Sorting: 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("Array before Sorting: ")
print(arr)
insertion_sort(arr, n);
print("Array after Sorting: ")
print(arr)

Array before Sorting: 
[12, 19, 55, 2, 16]
Array after Sorting: 
[2, 12, 16, 19, 55]