算法实现/排序/选择排序

本文介绍了选择排序算法在各种实际编程语言中的实现。

BASIC

For i = 1 To n - 1
   min = i
   For j = i + 1 To n
      If x(min) > x(j) Then
         min = j
      End If
   Next j
   temp = x(i)
   x(i) = x(min)
   x(min) = temp
Next

C/C++

void selection(int *array, int length)
{
    int max, i, temp;
    while (length > 0)
    {
        max = 0;
        for (i = 1; i < length; i++)
            if (array[i] > array[max])
                max = i;

        temp = array[length-1];
        array[length-1] = array[max];
        array[max] = temp;
        length--;
    }
}

C

这是一个不稳定变体的实现

int selectionSort(int data[], int count)
{
    int i, j;
    int tmp;
    int minimum;
    for (i = 0; i < count - 1; i++)
    {
        minimum = i; /* current minimum */

        /* find the global minimum */
        for (j = i + 1; j < count; j++)
            if (data[minimum] > data[j])
                minimum = j; /* new minimum */

        /* swap data[i] and data[minimum] */
        tmp = data[i];
        data[i] = data[minimum];
        data[minimum] = tmp;
    }
    return 0;
}

这是一个稳定变体的实现

void selectionSort(int data[], int count)
{
    int i, j, m, mi;
    for (i = 0; i < count - 1; i++)
    {
        /* find the minimum */
        mi = i;
        for (j = i + 1; j < count; j++)
            if (data[j] < data[mi])
                mi = j;

        m = data[mi];

        /* move elements to the right */
        for (j = mi; j > i; j--)
            data[j] = data[j-1];

        data[i] = m;
    }
}

C++

#include <algorithm> // for: std::iter_swap, std::min_element

template <typename Iterator>
void selection_sort(Iterator begin, Iterator end)
{
    Iterator min;
    while (begin != end)
    {
        min = std::min_element(begin, end);
        std::iter_swap(begin, min);
        ++begin;
    }
}

C#

public void sortArray(int[] intArray)
{
    int min, temp;

    for (int i = 0; i < intArray.Length - 1; i++)
    {
        min = i;
        for (int j = i + 1; j < intArray.Length; j++)
            if (intArray[j] < intArray[min])
                min = j;

        // swap the values
        temp = intArray[i];
        intArray[i] = intArray[min];
        intArray[min] = temp;
    }
}

Java

迭代实现

public static int[] selectionsort(int[] numbers)
{
    for (int i = 0; i < numbers.length - 1; i++)
    {
        int index = i;
        for (int j = i + 1; j < numbers.length; j++)
            if (numbers[j] < numbers[index]) //Finds smallest number
                index = j;

        int smallerNumber = numbers[index];  //Swap
        numbers[index] = numbers[i];
        numbers[i] = smallerNumber;

    }
    return numbers;
}

递归实现

public static int findMin(int[] array, int index)
{
    int min = index - 1;
    if (index < array.length - 1)
        min = findMin(array, index + 1);
    if (array[index] < array[min])
        min = index;
    return min;
}

public static void selectionSort(int[] array)
{
    selectionSort(array, 0);
}

public static void selectionSort(int[] array, int left)
{
    if (left < array.length - 1)
    {
        swap(array, left, findMin(array, left));
        selectionSort(array, left+1);
    }
}

public static void swap(int[] array, int index1, int index2)
{
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}

JavaScript

function selectionSort (sortMe)
{
    var i, j, tmp, tmp2;
    for (i = 0; i < sortMe.length - 1; i++)
    {
        tmp = i;
        for (j = i + 1; j < sortMe.length; j++){
            if (sortMe[j] < sortMe[tmp]){
                tmp = j;
            }
        }
        if(tmp!=i){
            tmp2 = sortMe[tmp];
            sortMe[tmp] = sortMe[i];
            sortMe[i] = tmp2;
        }
    }
}

ML

(* Selection sort is modified slightly for use on linked lists (which are the only inbuilt array-like structures in ML)
      in a functional programming language *)
fun selection_sort [] = []
|   selection_sort (first::lst) =
    let
      fun select_r small ([], output) = small::(selection_sort output)
      |   select_r small (x::xs, output) =
            if (x< small) then
              select_r x (xs, small::output)
            else
              select_r small (xs, x::output)
    in
      select_r first (lst, [])
    end
;

Ocaml

(* Gets the minimum element of the list *)
let rec min lst =
    match lst with
       x::[] -> x
     | (x::tl) -> let mintl = min tl in
                    if x < mintl then x else mintl;;

(* Removes a given element from the list *)
let rec remove(x,lst) =
    match lst with
       [] -> []
     | (y::tl) -> if x=y then tl else y::(remove(x,tl));;

(* Sorts a list by repeatedly extracting the minimum *)
let rec selectionSort(lst) =
    match lst with
       [] -> []
     | _  -> let m = min lst in m::(selectionSort(remove(m,lst)));;

Phix

function selection_sort(sequence s)
integer m
    for i=1 to length(s) do
        m = i
        for j=i+1 to length(s) do
            if s[j]<s[m] then
                m = j
            end if
        end for
        {s[i],s[m]} = {s[m],s[i]}
    end for
    return s
end function

PHP

function selectionSort(&$a)
{
    $n = count($a);
    for ($i = 0; $i < $n - 1; $i++)
    {
        $min = $i;
        for ($j = $i + 1; $j < $n; $j++)
            if ($a[$j] < $a[$min])
                $min = $j;

        list($a[$i], $a[$min]) = array($a[$min], $a[$i]);
    }
}

Python

newList = [6,7,4,5,1]
for outer in range(len(newList)):
    minimum = min(newList[outer:]) #find minimum element
    minIndex = newList[outer:].index(minimum) #find index of minimum element
    newList[outer + minIndex] = newList[outer] #replace element at minIndex with first element
    newList[outer] = minimum #replace first element with min element
print newList

Ruby

  def sort!(keys)
    for i in 0..keys.size-2
      min = i
      for j in i+1..keys.size-1
        min = j if keys[j] < keys[min]
        end
      keys[i], keys[min] = keys[min], keys[i]
      end
    keys
  end