选择排序

选择排序是最简单的排序方法之一，它的做法是这样的：首先，找出数组中最小的那个元素，将最小的元素与第一个元素的位置互换，然后找出数组中第二小的元素，与数组中第二个元素互换位置（如果要比较的元素是当前最小，则自己和自己交换），以此类推，直到遍历了整个数组。这种方法叫做选择排序，因为它会不断地选择剩余元素中的最小者。

 

表格1-1排序步骤

初始值：	1	10	-5	9	8	7	3
第一趟：	-5	10	1	9	8	7	3
第二趟：	-5	1	10	9	8	7	3
第三趟：	-5	1	3	9	8	7	10
第四趟：	-5	1	3	7	8	9	10
第五趟：	-5	1	3	7	8	9	10
第六趟：	-5	1	3	7	8	9	10
第七趟：	-5	1	3	7	8	9	10

 

如表格1-1所示，红色代表已经排序好的序列，每次交换都能排定一个元素，因此交换的总次数是N，算法的运行时间和输入无关，因为内循环会进行(N-1)+(N-2)+……+1=N(N-1)/2~(N²/2)次比较，因此选择排序的时间复杂度为O(n²)

 

以下代码分别为C、Java、Python、Scala

　　

 代码1-2为选择排序的C语言实现

#include 
     
      void selection_sort( int arr[], int len );void selection_sort( int arr[], int len ){    int i = 0, j = 0, min = 0, temp = 0;    for ( i = 0; i < len; i++ )    {        min = i;        for ( j = min + 1; j < len; j++ )        {            if ( arr[min] > arr[j] )            {                min = j;            }        }        temp        = arr[i];        arr[i]        = arr[min];        arr[min]    = temp;    }}void main(){    int    i    = 0;    int    arr[]    = { 1, 10, -5, 9, 8, 7, 3 };    int    len    = sizeof(arr) / sizeof(arr[0]);    printf( "待排序数组:" );    for ( i = 0; i < len; i++ )    {        printf( "%d ", arr[i] );    }    printf( "\n" );    selection_sort( arr, len );    printf( "排序后数组:" );    for ( i = 0; i < len; i++ )    {        printf( "%d ", arr[i] );    }}
     

　　

 代码1-3为选择排序的Java实现

import java.util.Arrays;public class Selection {    public static void selectionSort(int... arr) {        for (int i = 0; i < arr.length; i++) {            int min = i;            for (int j = min + 1; j < arr.length; j++) {                if (arr[min] > arr[j]) {                    min = j;                }            }            int temp = arr[i];            arr[i] = arr[min];            arr[min] = temp;        }    }    public static void main(String[] args) {        int[] arr = { 1, 10, -5, 9, 8, 7, 3 };        System.out.print("待排序数组:" + Arrays.toString(arr));        System.out.println();        selectionSort(arr);        System.out.println("排序后数组:" + Arrays.toString(arr));    }}

　　

代码1-4为选择排序的Python实现

# coding:utf-8def selection_sort(arr):    for i in range(0, len(arr)):        min = i        for j in range(min + 1, len(arr)):            if arr[min] > arr[j]: min = j        temp = arr[i]        arr[i] = arr[min]        arr[min] = temparr = [1, 10, -5, 9, 8, 7, 3]print "待排序数组:", arrselection_sort(arr)print "排序后数组", arr

　　

代码1-5为选择排序的Scala实现

import java.util.Arraysobject Selection {  def selectionSort(comparator: (Int, Int) => Boolean)(arr: Array[Int]) {    for (i <- 0 until arr.length) {      var min = i      for (j <- min + 1 until arr.length) {        if (comparator(arr(min), arr(j))) {          min = j        }      }      var temp = arr(i)      arr(i) = arr(min)      arr(min) = temp    }  }  def main(args: Array[String]): Unit = {    val arr = Array(1, 10, -5, 9, 8, 7, 3)    println("待排序数组:" + Arrays.toString(arr))    selectionSort(_ > _)(arr)    println("排序后数组:" + Arrays.toString(arr))  }}