排序總結之選擇式排序

一，直接選擇排序

介紹：直接選擇排序(Selection sort)是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩余未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬於非常好的一種。

復雜度分析：

數據結構 數組 最差時間復雜度 О(n²) 最優時間復雜度 О(n²) 平均時間復雜度 О(n²) 最差空間復雜度 О(n) total, O(1)auxiliary

選擇排序的交換操作介於0和(n-1)次之間。選擇排序的比較操作為n(n-1)/2次之間。選擇排序的賦值操作介於0和3(n-1)次之間。比較次數O(n^2),比較次數與關鍵字的初始狀態無關，總的比較次數N=(n-1)+(n-2)+...+1=n*(n-1)/2。 交換次數O(n),最好情況是，已經有序，交換0次；最壞情況是，逆序，交換n-1次。 交換次數比冒泡排序少多了，由於交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快。

java code：

private void select(int[] a) {
for(int i=0;i<a.length-1;i++){
int k=i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[k])
k = j;
}
if (k != i) {
int temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
}

二，堆排序

介紹：（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

堆的操作：通常堆是通過一維數組來實現的。在堆的數據結構中，堆中的最大值總是位於根節點。堆中定義以下幾種操作：最大堆調整（Max_Heapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點；創建最大堆（Build_Max_Heap）：將堆所有數據重新排序；堆排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆調整的遞歸運算。

堆排序的過程是：
1，創建一個堆H[0..n-1]
2，把堆首（最大值）和堆尾互換
3，把堆的尺寸縮小1，把新的數組頂端數據調整到相應位置
4，重復步驟2，直到堆的尺寸為1

復雜度分析：

數據結構 數組 最差時間復雜度 最優時間復雜度 平均時間復雜度 最差空間復雜度 total, auxiliary

java code：

import java.util.Arrays;

public class HeapSortDemo {
// 堆排序是不穩定的排序方法
private void heapSort(int[] a) {
for (int i = (a.length - 1) / 2; i >= 0; i--) {
siftDown(a, i, a.length - 1);//建堆
}
for (int i = a.length - 1; i >= 0; i--) {
swap(a, 0, i);//交換堆頂元素到相應位置
siftDown(a, 0, i - 1);
}
}
//調整堆
private void siftDown(int[] a, int left, int right) {
int origin = a[left];
int i = left, j = 2 * i + 1;
while (j <= right) {
if (j < right && a[j] < a[j + 1])
j++;
if (origin >= a[j])
break;
else {
a[i] = a[j];
i = j;
j = 2 * j + 1;
}
}
a[i] = origin;
}
private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) {
int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62,
99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51 };
HeapSortDemo hsd = new HeapSortDemo();
hsd.heapSort(a);
System.out.println(Arrays.toString(a));
}
}

Java編程思想(第4版) 中文清晰PDF完整版 http://www.linuxidc.com/Linux/2014-08/105403.htm

編寫高質量代碼 改善Java程序的151個建議 PDF高清完整版 http://www.linuxidc.com/Linux/2014-06/103388.htm

Java 8簡明教程 http://www.linuxidc.com/Linux/2014-03/98754.htm

Java對象初始化順序的簡單驗證 http://www.linuxidc.com/Linux/2014-02/96220.htm

Java對象值傳遞和對象傳遞的總結 http://www.linuxidc.com/Linux/2012-12/76692.htm