作者：nnngu
GitHub：https://github.com/nnngu
博客園：http://www.cnblogs.com/nnngu
簡(jiǎn)書(shū)：http://www.itdecent.cn/users/1df20d76ea5c
知乎：https://www.zhihu.com/people/nnngu/posts
上一篇總結(jié)了交換排序的冒泡排序和快速排序。這一篇要總結(jié)的是選擇排序，選擇排序分為直接選擇排序和堆排序，主要從以下幾點(diǎn)進(jìn)行總結(jié)。
1、直接選擇排序及算法實(shí)現(xiàn)
2、堆排序及算法實(shí)現(xiàn)
1、直接選擇排序及算法實(shí)現(xiàn)
直接選擇排序(Straight Select Sort) 是一種簡(jiǎn)單的排序方法，它的基本思想是：通過(guò)length-1 趟元素之間的比較，從length-i+1個(gè)元素中選出最小的元素，并和第i個(gè)元素交換位置。直接選擇排序的最壞時(shí)間復(fù)雜度為O(n2)，平均時(shí)間復(fù)雜度為O(n2)
下圖展示了直接選擇排序的過(guò)程。
1-1、示意圖
1-2、代碼
SelectionSort.java
public class SelectionSort {
public static void main(String[] args) {
int[] list = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
System.out.println("************直接選擇排序************");
System.out.println("排序前：");
display(list);
System.out.println("");
System.out.println("排序后：");
selectionSort(list);
display(list);
}
/**
* 直接選擇排序算法
*/
public static void selectionSort(int[] list) {
// 要遍歷的次數(shù)（length-1次）
for (int i = 0; i < list.length - 1; i++) {
// 將當(dāng)前下標(biāo)定義為最小值下標(biāo)
int min = i;
// 遍歷min后面的數(shù)據(jù)
for (int j = i + 1; j <= list.length - 1; j++) {
// 如果有小于當(dāng)前最小值的元素，將它的下標(biāo)賦值給min
if (list[j] < list[min]) {
min = j;
}
}
// 如果min不等于i，說(shuō)明找到真正的最小值
if (min != i) {
swap(list, min, i);
}
}
}
/**
* 交換數(shù)組中兩個(gè)位置的元素
*/
public static void swap(int[] list, int min, int i) {
int temp = list[min];
list[min] = list[i];
list[i] = temp;
}
/**
* 遍歷打印
*/
public static void display(int[] list) {
System.out.println("********展示開(kāi)始********");
if (list != null && list.length > 0) {
for (int num :
list) {
System.out.print(num + " ");
}
System.out.println("");
}
System.out.println("********展示結(jié)束********");
}
}
測(cè)試結(jié)果：
2、堆排序及算法實(shí)現(xiàn)
堆排序(Heap Sort) 利用堆（一般為大根堆）進(jìn)行排序的方法。它的基本思想是：將待排序的元素構(gòu)造成一個(gè)大根堆。此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將它移走（其實(shí)就是將它與數(shù)組的末尾元素進(jìn)行交換，此時(shí)末尾元素就是最大值），然后將剩余的length-1 個(gè)元素重新構(gòu)造成一個(gè)大根堆，這樣就會(huì)得到length個(gè)元素中的次大值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序的序列。
堆是具有下列性質(zhì)的完全二叉樹(shù)：每個(gè)節(jié)點(diǎn)的值都大于或等于其左右孩子節(jié)點(diǎn)的值，稱為大根堆；每個(gè)節(jié)點(diǎn)的值都小于或等于其左右孩子節(jié)點(diǎn)的值，稱為小根堆。
堆排序的最壞時(shí)間復(fù)雜度為O(n*log2n)，平均時(shí)間復(fù)雜度為O(n*log2n)
2-1、示意圖
圖一：
圖二：
圖三：
圖四：
圖五：
圖六：
2-2、代碼
HeapSort.java
public class HeapSort {
public static void main(String[] args) {
int[] list = {1, 3, 4, 5, 2, 6, 9, 7, 8, 0};
System.out.println("************堆排序************");
System.out.println("排序前：");
display(list);
System.out.println("");
System.out.println("排序后：");
heapSort(list);
display(list);
}
/**
* 堆排序算法
*/
public static void heapSort(int[] list) {
// 將無(wú)序堆構(gòu)造成一個(gè)大根堆，大根堆有l(wèi)ength/2個(gè)父節(jié)點(diǎn)
for (int i = list.length / 2 - 1; i >= 0; i--) {
headAdjust(list, i, list.length);
}
// 逐步將每個(gè)最大值的根節(jié)點(diǎn)與末尾元素交換，并且再調(diào)整其為大根堆
for (int i = list.length - 1; i > 0; i--) {
// 將堆頂節(jié)點(diǎn)和當(dāng)前未經(jīng)排序的子序列的最后一個(gè)元素交換位置
swap(list, 0, i);
headAdjust(list, 0, i);
}
}
/**
* 構(gòu)造大根堆
*/
public static void headAdjust(int[] list, int parent, int length) {
// 保存當(dāng)前父節(jié)點(diǎn)
int temp = list[parent];
// 得到左孩子節(jié)點(diǎn)
int leftChild = 2 * parent + 1;
while (leftChild < length) {
// 如果parent有右孩子，則要判斷左孩子是否小于右孩子
if (leftChild + 1 < length && list[leftChild] < list[leftChild + 1]) {
leftChild++;
}
// 父親節(jié)點(diǎn)大于子節(jié)點(diǎn)，就不用做交換
if (temp >= list[leftChild]) {
break;
}
// 將較大子節(jié)點(diǎn)的值賦給父親節(jié)點(diǎn)
list[parent] = list[leftChild];
// 然后將子節(jié)點(diǎn)做為父親節(jié)點(diǎn)
parent = leftChild;
// 找到該父親節(jié)點(diǎn)較小的左孩子節(jié)點(diǎn)
leftChild = 2 * parent + 1;
}
// 最后將temp值賦給較大的子節(jié)點(diǎn)，以形成兩值交換
list[parent] = temp;
}
/**
* 交換數(shù)組中兩個(gè)位置的元素
*/
public static void swap(int[] list, int top, int last) {
int temp = list[top];
list[top] = list[last];
list[last] = temp;
}
/**
* 遍歷打印
*/
public static void display(int[] list) {
System.out.println("********展示開(kāi)始********");
if (list != null && list.length > 0) {
for (int num :
list) {
System.out.print(num + " ");
}
System.out.println("");
}
System.out.println("********展示結(jié)束********");
}
}
測(cè)試結(jié)果：
