大家都學(xué)習(xí)過(guò)數(shù)據(jù)結(jié)構(gòu)，都知道各種各樣的排序方法，比如冒泡排序，選擇排序，堆排序，歸并排序等等，我學(xué)習(xí)的教材是C語(yǔ)言版的，今天處于好奇，寫(xiě)了一個(gè)用Java語(yǔ)言實(shí)現(xiàn)的直接選擇排序的程序，與大家分享一下。
直接選擇排序的思想是；
n個(gè)記錄的文件的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果：
①初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空。
②第1趟排序
在無(wú)序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)。
……
③第i趟排序
第i趟排序開(kāi)始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R[i..n](1≤i≤n-1)。該趟排序從當(dāng)前無(wú)序區(qū)中選出關(guān)鍵字最小的記錄R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R[i]交換，使R[1..i]和R[i+1..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)。
這樣，n個(gè)記錄的文件的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果。
用Java實(shí)現(xiàn)的代碼如下：
/**//*
*@author 我為J狂 建立日期 2007-4-16
*
*/
package net.blogjava.lzqdiy;
public class MySort
{
/** *//**
* @param args
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
int n = Integer.parseInt(args[0]);// 輸入數(shù)組長(zhǎng)度
double R[] = new double[n];
if (n == 0)
System.out.println("數(shù)組為空");
else
{
System.out.println("排序前：");
for (int i = 0; i < n; i++)
R[i] = Double.parseDouble(args[i + 1]);// 輸入數(shù)組元素。
for (int i = 0; i < n; i++)
{
if (i > 0)
System.out.print(",");
System.out.print(R[i]);
}
double temp = 0;
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
if (R[j] < R[i])
{
temp = R[i];
R[i] = R[j];
R[j] = temp;
}
}
}
System.out.println();
System.out.println("排序后：");
for (int i = 0; i < n; i++)
{
if (i > 0)
System.out.print(",");
System.out.print(R[i]);
}
}
}
}
程序的運(yùn)行結(jié)果是:
排序前：
3.6,7.4,2.1,3.3,2.0
排序后：
2.0,2.1,3.3,3.6,7.4
算法分析
（1）關(guān)鍵字比較次數(shù) 無(wú)論文件初始狀態(tài)如何，在第i趟排序中選出最小關(guān)鍵字的記錄，需做n-i次比較，因此，總的比較次數(shù)為：
n(n-1)/2=0(n
2)
（2）記錄的移動(dòng)次數(shù) 當(dāng)初始文件為正序時(shí)，移動(dòng)次數(shù)為0
文件初態(tài)為反序時(shí)，每趟排序均要執(zhí)行交換操作，總的移動(dòng)次數(shù)取最大值3(n-1)。
直接選擇排序的平均時(shí)間復(fù)雜度為O(n
2)。
（3）直接選擇排序是一個(gè)就地排序
（4）穩(wěn)定性分析 直接選擇排序是不穩(wěn)定的
【例】反例[2，
2，1]