本文實例講述了java數(shù)據(jù)結(jié)構(gòu)與算法之簡單選擇排序。分享給大家供大家參考，具體如下：
在前面的文章中已經(jīng)講述了交換類的排序算法，這節(jié)中開始說說選擇類的排序算法了，首先來看一下選擇排序的算法思想；
選擇排序的基本算法思想：
每一趟在 n-i+1 (i=1,2,3,……,n-1)個記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個記錄。
簡單選擇排序：
設(shè)所排序序列的記錄個數(shù)為n。i取1,2,…,n-1,從所有n-i+1個記錄（Ri,Ri+1,…,Rn）中找出排序碼最小的記錄，與第i個記錄交換。執(zhí)行n-1趟 后就完成了記錄序列的排序。
算法實現(xiàn)代碼如下：
|
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
28
29
30
|
package exp_sort;public class SimpleSelectSort { static int i; static int temp; public static void selectSort(int array[]) { for (i = 0; i < array.length; i++) { int k = i; //記錄當(dāng)前位置 for (int j = i + 1; j < array.length; j++) { if (array[j] < array[k]) { //找出最小的數(shù)，并用k指向最小數(shù)的位置 k = j; } } //交換最小數(shù)array[k]與第i位上的數(shù) if (k != i) { temp = array[i]; array[i] = array[k]; array[k] = temp; } } } public static void main(String[] args) { // TODO Auto-generated method stub int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 }; selectSort(array); for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println("\n"); }} |
算法分析：
在此排序過程中，需要移動記錄的次數(shù)比較少。最好情況下，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動記錄；最壞情況下，即待排序記錄初始狀態(tài)是按照逆序排列的，則需要移動次數(shù)最多是：3(n-1)。排序過程中需要進行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況無關(guān)。當(dāng)i=1時，需要進行n-1次比較；當(dāng)i=n時，共需要進行的比較次數(shù)是：n(n-1)/2，即比較操作的時間復(fù)雜度是：O(n^2)，進行移動操作的時間復(fù)雜度為O(n)；該排序是不穩(wěn)定排序。
希望本文所述對大家java程序設(shè)計有所幫助。
