一、基本概念
每趟從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排序的記錄序列末尾，直到全部排序結(jié)束為止。
二、實現(xiàn)思路
從待排序序列中，找到關(guān)鍵字最小的元素；
如果最小元素不是待排序序列的第一個元素，將其和第一個元素互換；
從余下的 N - 1 個元素中，找出關(guān)鍵字最小的元素，重復(fù)(1)、(2)步，直到排序結(jié)束。
三、代碼實現(xiàn)
java" id="highlighter_372771">
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public class SelectionSort { public static void selectionSort(int[] list){ //需要遍歷獲得最小值的次數(shù) if (1>=list.length)return; for (int i=0;i<list.length-1;i++){ int temp=0; int index=i; //選擇當前值為最小值索引 for (int j=i+1;j<list.length;j++){ if (list[index]>list[j]){ index=j; //修改最小值索引 } } temp=list[index]; list[index]=list[i]; list[i]=temp; } } public static void main(String[] args){ int[] list={4,3,6,5,7,8,2,10,2,9}; selectionSort(list); for (int num:list){ System.out.print(num+" "); } }} |
四、時間復(fù)雜度
簡單選擇排序的比較次數(shù)與序列的初始排序無關(guān)。 假設(shè)待排序的序列有 N 個元素，則比較次數(shù)總是N (N - 1) / 2。
而移動次數(shù)與序列的初始排序有關(guān)。當序列正序時，移動次數(shù)最少，為 0.
當序列反序時，移動次數(shù)最多，為3N (N - 1) / 2。
所以，綜合以上，簡單排序的時間復(fù)雜度為 O(N2)。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://www.cnblogs.com/jiansen/p/7343870.html
