常用的選擇排序方法有兩種：直接選擇排序和堆排序预伺。
直接排序簡單直觀委造，但性能略差吵冒；
堆排序是一種較為高效的選擇排序方法，但實現(xiàn)起來略微復(fù)雜愿题。
直接選擇排序
直接選擇排序的思路很簡單损俭，它需要經(jīng)過n-1趟比較。
- 第1趟比較：程序?qū)⒂涗浂ㄎ辉诘?個數(shù)據(jù)上潘酗，拿第1個數(shù)據(jù)依次和它后面每個數(shù)據(jù)進(jìn)行比較杆兵，如果第1個數(shù)據(jù)大于后面某個數(shù)據(jù)，交換它們……依此類推仔夺。經(jīng)過第1趟比較琐脏，這組數(shù)據(jù)中最小的數(shù)據(jù)被選出，它被排在第1位。
- 第2趟比較：程序?qū)⒂涗浂ㄎ辉诘?個數(shù)據(jù)上日裙，拿第2個數(shù)據(jù)依次和它后面每個數(shù)據(jù)進(jìn)行比較吹艇，如果第2個數(shù)據(jù)大于后面某個數(shù)據(jù)，交換它們……依此類推昂拂。經(jīng)過第2趟比較受神，這組數(shù)據(jù)中第2小的數(shù)據(jù)被選出，它被排在第2位格侯。
……
按此規(guī)則一共進(jìn)行n-1趟比較鼻听，這組數(shù)據(jù)中第n-1小（第2大）的數(shù)據(jù)被選出联四，被排在第n-1位（倒數(shù)第1位）撑碴；剩下的就是最大的數(shù)據(jù)，它排在最后朝墩。
直接選擇排序的優(yōu)點是算法簡單醉拓，容易實現(xiàn)。
直接選擇排序的缺點是每趟只能確定一個元素收苏，n個數(shù)組需要進(jìn)行n-1趟比較亿卤。
封裝的實體類
public class DataWrap implements Comparable<DataWrap>{
int data;
String flag;
public DataWrap(int data, String flag) {
this.data = data;
this.flag = flag;
}
@Override
public String toString() {
return data+flag;
}
@Override
public int compareTo(DataWrap dw) {
return this.data > dw.data ? 1 : (this.data == dw.data ? 0 : -1);
}
}
具體的算法與測試
public class SelectSort {
public static void selectSort(DataWrap[] data) {
System.out.println("開始排序");
int arrayLength = data.length;
//依次進(jìn)行n-1趟比較，第i趟比較將第i大的值選出倒戏，放在i位置上
for (int i = 0; i < arrayLength - 1; i++) {
//第i個數(shù)據(jù)只需要和它后面的數(shù)據(jù)比較
for (int j = i + 1; j < arrayLength; j++) {
//如果第i位置的數(shù)據(jù) 大于 j位置上的數(shù)據(jù)怠噪，就交換他們
if (data[i].compareTo(data[j]) > 0) {
DataWrap tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
System.out.println("第 "+i+" 趟后："+Arrays.toString(data));
}
}
/**
* 優(yōu)化：
* 在一趟的排序過程中，記錄最小數(shù)據(jù)的位置杜跷。當(dāng)本趟比較完成時傍念，如果第i位于minIndex不相等時，才交換位置
* @param data
*/
public static void selectSort2(DataWrap[] data) {
System.out.println("開始排序");
int arrayLength = data.length;
//依次進(jìn)行n-1趟比較葛闷，第i趟比較將第i大的值選出憋槐，放在i位置上
for (int i = 0; i < arrayLength - 1; i++) {
//minIndex用于保留本趟比較中最小值的索引
int minIndex = i;
//第i個數(shù)據(jù)只需要和它后面的數(shù)據(jù)比較
for (int j = i + 1; j < arrayLength; j++) {
//如果第minIndex位置的數(shù)據(jù) 大于 j位置上的數(shù)據(jù)，將j的值賦給minIndex
if (data[minIndex].compareTo(data[j]) > 0) {
minIndex = j;
}
}
if (i != minIndex) {
DataWrap tmp = data[i];
data[i] = data[minIndex];
data[minIndex] = tmp;
}
System.out.println("第 "+i+" 趟后："+Arrays.toString(data));
}
}
public static void main(String[] args) {
DataWrap[] data = new DataWrap[]{
new DataWrap(21, ""),
new DataWrap(30, ""),
new DataWrap(49, ""),
new DataWrap(30, "*"),
new DataWrap(16, ""),
new DataWrap(9, "")
};
DataWrap[] data2 = Arrays.copyOf(data, data.length);
System.out.println("排序前："+Arrays.toString(data));
selectSort(data);
System.out.println("排序后："+Arrays.toString(data));
selectSort2(data2);
}
}
總結(jié)
直接選擇排序淑趾，時間效率為O(n2)
交換時阳仔，只需要一個附加程序單元用于交換，其空間效率為：O(1)
30與30* 排序后扣泊，位置發(fā)生了變化近范，所以排序是不穩(wěn)定的
堆排序
堆的概念
假設(shè)有n個數(shù)據(jù)元素的序列k0，k1延蟹，…评矩，kn-1，當(dāng)且僅當(dāng)滿足如下關(guān)系時阱飘，可以將這組數(shù)據(jù)稱為小頂堆（小根堆）斥杜。
ki <= k2i+1且ki <= k2i+2（其中i=0, 2,…虱颗，(n-1)/2）
或者，滿足如下關(guān)系時蔗喂，可以將這組數(shù)據(jù)稱為大頂堆（大根堆）忘渔。
ki >= k2i+1且ki >=k2i+2（其中i=0, 2,…，(n-1)/2）
對于滿足小頂堆的數(shù)據(jù)序列k0缰儿，k1畦粮，…，kn-1返弹，如果將它們順序排成一棵完全二叉樹锈玉，則此樹的特點是：樹中所有節(jié)點的值都小于其左右子節(jié)點的值，此樹的根節(jié)點的值必然最小义起。反之，對于滿足大頂堆的數(shù)據(jù)序列k0师崎，k1默终，…，kn-1犁罩，如果將它們順序排成一棵完全二叉樹齐蔽，則此樹的特點是：樹中所有節(jié)點的值都大于其左右子節(jié)點的值，此樹的根節(jié)點的值必然最大床估。
通過上面介紹不難發(fā)現(xiàn)一點含滴，小頂堆的仁義子樹也是小頂堆，大頂堆的任意子樹還是大頂堆
例：判斷數(shù)據(jù)序列
9,30,49,46,58,79是否為堆丐巫，將其轉(zhuǎn)換為一個完全二叉樹
判斷數(shù)據(jù)序列：93,82,76,63,58,67,55是否為堆谈况，將其轉(zhuǎn)換為一個完全二叉樹
堆排序的關(guān)鍵在于建堆，它按如下步驟完成排序递胧。
- 第1趟將索引0～n-1處的全部數(shù)據(jù)建大頂（或小頂）堆碑韵，就可以選擇出這組數(shù)組中的最大（或最小）值缎脾。
- 將上一步所建的大頂（或小頂）堆的根節(jié)點與這組數(shù)據(jù)的最后一個節(jié)點交換祝闻，就使得這組數(shù)據(jù)中最大（或最小）值排在最后遗菠。
- 第2趟將索引0～n-2處的全部數(shù)據(jù)建大頂（或小頂）堆联喘，就可以選擇出這組數(shù)組中的最大（或最小）值辙纬。
將上一步所建的大頂（或小頂）堆的根節(jié)點與這組數(shù)據(jù)的倒數(shù)第2個節(jié)點交換豁遭，就使得這組數(shù)據(jù)中最大（或最小）值排在倒數(shù)第2位牲平。
……- 第k趟將索引0～n-k處的全部數(shù)據(jù)建大頂（或小頂）堆堤框，就可以選擇出這組數(shù)組中最大（或最小）值。
- 將上一步所建的大頂（或小頂）堆的根節(jié)點與這組數(shù)據(jù)的倒數(shù)第k個節(jié)點交換蜈抓，使得這組數(shù)據(jù)中最大（或最衅舸隆）值排在倒數(shù)第k位。
通過上面介紹不難發(fā)現(xiàn)沟使，堆排序的步驟就是重復(fù)執(zhí)行以下2步委可。
（1）建堆；
（2）拿堆的根節(jié)點和最后一個節(jié)點交換腊嗡。
由此可見着倾，對于包含n個數(shù)據(jù)元素的數(shù)據(jù)組而言，堆排序需要經(jīng)過n-1次建堆燕少，每次建堆的作用就是選出該堆的最大值或最小值卡者。因為堆排序的本質(zhì)上依然是一種選擇排序。
例如如下數(shù)據(jù)組：
9客们，79崇决，46，30底挫，58恒傻，49
建堆過程
-
先將其轉(zhuǎn)換為完全二叉樹，轉(zhuǎn)換得到的完全二叉建邓，如下圖
將數(shù)據(jù)轉(zhuǎn)換為完全二叉樹 -
完全二叉樹的最后一個非葉子節(jié)點盈厘，也就是最后一個節(jié)點的父節(jié)點。最后一個節(jié)點的索引為數(shù)組長度-1官边，也就是len-1沸手，那么最后一個非葉子節(jié)點的索引應(yīng)該是為（len-2)/2。也就是從索引為2的節(jié)點開始拒逮，如果其子節(jié)點的值大于它本身的值罐氨，則把它和較大子節(jié)點進(jìn)行交換，即將索引2處節(jié)點和索引5處的元素交換滩援。交換后的結(jié)果如下圖
交換1次后的完全二叉樹 - 向前處理前一個節(jié)點栅隐，也就是處理索引為1的節(jié)點，此時79>30玩徊、79>58租悄，因此無須交換。
-
向前處理前一個節(jié)點恩袱，也就是處理索引為0的節(jié)點泣棋，此時 9<79、9<49畔塔，因此需要交換潭辈。應(yīng)該拿索引0的節(jié)點和索引1的節(jié)點交換（9的兩個子節(jié)點中鸯屿，索引為1的節(jié)點的值較大），交換后的完全二叉樹如下圖
交換2次后的完全二叉樹 -
如果某個節(jié)點和它的某個子節(jié)點交換后把敢，該子節(jié)點又有子節(jié)點寄摆，系統(tǒng)還需再次對該子節(jié)點進(jìn)行判斷。例如修赞，上圖中索引 0的節(jié)點和索引 1的節(jié)點交換后婶恼，索引 1的節(jié)點還有子節(jié)點，因此程序必須再次保證索引1處節(jié)點的值大于等于其左柏副、右子節(jié)點的值勾邦。因此還需要交換一次，交換后的大頂堆如下圖
大頂堆建立完成
具體算法
public class HeapSort {
public static void heapSort(DataWrap[] data){
System.out.println("開始排序");
int arrryLength = data.length;
//循環(huán)建堆割择， 第0個節(jié)點沒有父節(jié)點的所以可以少比較一次
for (int i = 0; i < arrryLength - 1; i++) {
//建堆
buildMaxdHeap(data, arrryLength - 1 - i);
//交換堆頂和最后一個元素
swap(data, 0, arrryLength - 1 - i);
System.out.println(Arrays.toString(data));
}
}
/**
* 對data數(shù)據(jù)從0到lastIndex建大頂堆
* @param data
* @param lastIndex
*/
private static void buildMaxdHeap(DataWrap[] data, int lastIndex){
//從lastIndex處節(jié)點（最后一個節(jié)點）的父節(jié)點開始眷篇，依次循環(huán)其前面的各個父節(jié)點
//說明： 不管lastIndex是左子樹還是右子樹， (lastIndex-1)/2 =(int)x锨推，最后取整后铅歼，就是他的父節(jié)點
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
//k保存當(dāng)前正在判斷的節(jié)點
int k=i;
//如果當(dāng)前k節(jié)點的子節(jié)點存在
while (k * 2 + 1 <= lastIndex) {
//k節(jié)點的左子節(jié)點的索引
int biggerIndex = 2 * k + 1;
//如果biggerIndex小于lastIndex，即biggerIndex+1
//代表k節(jié)點的右子節(jié)點存在（因為lastIndex是最后一個節(jié)點换可， biggerIndex<lastIndex，2k+2是k節(jié)點的右子節(jié)點厦幅，那么2k+2<=lastIndex）
if (biggerIndex < lastIndex) {
//如果右子節(jié)點的值較大
if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) {
//biggerIndex總是記錄較大子節(jié)點的索引
biggerIndex++;
}
}
//如果k節(jié)點的值小于其他較大子節(jié)點的值
if (data[k].compareTo(data[biggerIndex]) < 0) {
//交換它們
swap(data, k, biggerIndex);
//將biggerIndex賦給k沾鳄，開始while循環(huán)的下一次循環(huán)
//重新保證k節(jié)點的值大于其左、右子節(jié)點的值（重新建立此節(jié)點的堆）
k = biggerIndex;
}else{
break;
}
}
}
}
/**
* 交換data數(shù)組中i确憨，j兩個索引出的元素
* @param data
* @param i
* @param j
*/
private static void swap(DataWrap[] data, int i, int j){
DataWrap tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
public static void main(String[] args) {
DataWrap[] data = new DataWrap[]{
new DataWrap(21, ""),
new DataWrap(30, ""),
new DataWrap(49, ""),
new DataWrap(30, "*"),
new DataWrap(21, "*"),
new DataWrap(16, ""),
new DataWrap(9, "")
};
System.out.println("排序前：" + Arrays.toString(data));
heapSort(data);
System.out.println("排序后："+Arrays.toString(data));
}
}
總結(jié)
- 假設(shè)有n項數(shù)據(jù)译荞，需要進(jìn)行n-1次建堆，則其時間效率是O(log2n)
- 堆排序也只需要一個附加程序單元用于交換休弃，其空間效率為O(1)
- 堆排序是不穩(wěn)定的
