首页 > 代码库 > 选择排序详解
选择排序详解
选择排序
选择排序是最简单的排序方法之一,它的做法是这样的:首先,找出数组中最小的那个元素,将最小的元素与第一个元素的位置互换,然后找出数组中第二小的元素,与数组中第二个元素互换位置(如果要比较的元素是当前最小,则自己和自己交换),以此类推,直到遍历了整个数组。这种方法叫做选择排序,因为它会不断地选择剩余元素中的最小者。
初始值: | 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~(N2/2)次比较,因此选择排序的时间复杂度为O(n2)
以下代码分别为C、Java、Python、Scala
算法1-2为选择排序的C语言实现
#include <stdio.h> 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-8 def 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] = temp arr = [1, 10, -5, 9, 8, 7, 3] print "待排序数组:", arr selection_sort(arr) print "排序后数组", arr
算法1-5为选择排序的Scala实现
import java.util.Arrays object 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)) } }
选择排序详解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。