直接選擇排序
- 置i初值為0
- 當i < n-1時，重複下列步驟
- 在無序子序列中｛a[i], ……a[n-1]｝中選出最小的a[min]
- 若min！=i，則交換
- i++
/**
* @description 直接選擇排序算法
* @return
* @time 2016年1月5日 上午1:28:19
*/
public static int[] selectSort(int[] before){
int[] a = Arrays.copyOf(before, before.length);
for(int i = ; i < a.length - ; i++){
// 每趟從a[i]開始的自序列中尋找最小關鍵字值的元素下标
int min = i;
for(int j = i + ; j < a.length; j++){
if(a[j] < a[min]){
min = j;
}
}
if(min != i){
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
return null;
}
算法性能分析
- 空間複雜度：O(1)
-
時間複雜度：O（n²）
外循環需執行n-1次，内循環需執行n-1-i次，是以總比較次數是∑（n-1-i）=1/2n(n-1)。最壞情況（逆序）下的移動次數是3（n-1），最好情況（有序）下的移動次數是0。
- 算法穩定性：不穩定
樹形選擇排序
在直接選擇排序中，關鍵字的比較次數為1/2n(n-1)，實際上，很多關鍵字之間進行了不止一次的比較。能否在選擇最小關鍵字的過程中，把關鍵字的比較的結果儲存下來，以便在以後需要的時候直接檢視這個比較結果呢？
樹形選擇排序又稱為錦标賽排序，将n個記錄兩兩比較，關鍵字值小的升到父結點，直到構成一個含有n個結點的完全二叉樹，這樣的二叉樹稱為勝者樹。如果開始的元素個數n不是2的k次幂，則将葉子節點補足到2的k次幂。
勝者樹采用順序存儲結構：
- 變量初始化，令待排序結點個數為n，則葉子結點個數為n，樹的結點總數為2*n-1，葉子結點在順序表中的起始存放位置n-1
- 将a[0……n-1]依次指派到tree[loadindex……TreeSize-1]
- 構造勝者樹，n個結點兩兩比較，得到n/2個關鍵字值小的結點；再将n/2個結點比較得到n/4，直到得到最小的關鍵字
- 調整勝者樹，先将根結點儲存到原數組a中，再把對應葉子結點值改為“極大值”，然後從該葉子結點開始修改到根上各結點的值。
- 重複上面兩個步驟
/**
* @description 樹形選擇排序算法，構造勝者樹的過程，取根結點是最小關鍵值
* @return
* @time 2016年1月5日 上午1:28:19
*/
public static int[] tournamentSort(int[] before){
int[] a= Arrays.copyOf(before, before.length);
TreeNode[] tree; //勝者樹結點數組
int leafSize = ; //勝者樹葉子結點數
//得到葉子結點的個數，該個數必須是2的次幂
while(leafSize < a.length){
leafSize *= ;
}
int TreeSize = * leafSize - ; //勝者樹的所有結點數
int loadIndex = leafSize - ; //葉子結點存放位置的起始位置
tree = new TreeNode[TreeSize];
int j = ;
//把待排序結點複制到勝者樹的葉子結點中
for(int i = loadIndex; i < TreeSize; i++){
tree[i] = new TreeNode();
tree[i].setIndex(i);
if(j < a.length){
tree[i].setActive();
tree[i].setData(a[j++]);
}
else{
tree[i].setActive();
}
}
int i = loadIndex; //進行初始化，比較查找關鍵字值最小的結點
while(i > ){
j = i;
//處理各對比賽者
while(j < TreeSize - ){
if(tree[j + ].getActive() == || (tree[j].getData() <= tree[j + ].getData())){
tree[(j - )/] = tree[j]; //左孩子勝出
}
else{
tree[(j - )/] = tree[j + ]; //右孩子勝出
}
j += ; //下一對比賽者
}
i = (i - )/; //處理上層結點，類似下一輪比賽（已經決出一輪了）
}
//處理剩餘的n-1個元素
for(i = ; i < a.length - ; i++){
a[i] = tree[].getData(); //将勝者樹的根（最小值）存入數組
tree[tree[].getIndex()].setActive(); //冠軍不再參加比賽
updateTree(tree, tree[].getIndex()); //調整有勝者樹
}
//最後一個元素隻需指派就結束了 不需要再調整（即再進行下一輪比賽）
a[a.length - ] = tree[].getData();
return a;
}
/**
* @description 樹形選擇排序的調整算法
* 從目前最小關鍵字的葉子結點開始到根結點路徑上的所有結點關鍵字的修改
* @param tree
* @param i i是目前最小關鍵字的下标
* @author liuquan
* @date 2016年1月5日
*/
private static void updateTree(TreeNode[] tree, int i){
//因為i是此時最小的關鍵字（已是冠軍），是以在葉子結點中要将其除去比賽資格，對手直接晉級（升為父結點）
if(i % == ){ //i為偶數，自己是右結點，對手是左結點,左結點晉級
tree[(i - )/] = tree[i - ];
}
else{
tree[(i - )/] = tree[i + ];
}
i = (i - ) / ;
int j = ;
while(i > ){
if(i % == ){ //i為偶數，自己是右結點，對手是左結點
j = i - ;
}
else{
j = i + ;
}
//比賽對手中有一個為空
if(tree[i].getActive() == || tree[j].getActive() == ){
if(tree[i].getActive() == ){
tree[(i - ) / ] = tree[i];
}
else{
tree[(i - ) / ] = tree[j];
}
}
//比賽對手都在
if(tree[i].getData() < tree[j].getData()){
tree[(i - ) / ] = tree[i];
}
else{
tree[(i - ) / ] = tree[j];
}
i = (i - ) / ;
}
}
/**
* @description 樹形選擇排序的勝者樹結點結構
*
* @author liuquan
* @date 2016年1月5日
*/
private static class TreeNode{
private int data; //資料域
private int index; //待插入結點在滿二叉樹中的序号
private int active; //參加選擇标志,1表示參選，0表示不參選
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public int getActive() {
return active;
}
public void setActive(int active) {
this.active = active;
}
}
算法性能分析
- 空間複雜度：勝者樹的葉子結點個數是2的k次幂，所需存儲空間是2*2^k-1
-
時間複雜度：O（n ㏒₂ n）
勝者樹高度為k+1。第一趟需進行n-1次關鍵字比較，其餘趟關鍵字比較次數為O（㏒₂ n），總的關鍵字比較次數為O（n ㏒₂ n）。由于結點移動次數不會超過比較的次數，是以時間複雜度是O（n ㏒₂ n）。
- 算法穩定性:穩定
堆排序
通俗了解，小頂堆就是每個父結點都比它的兩個子結點小；大頂堆則反之。
篩選法調整堆：
通俗說就是把頂元素一直換到最下面，重新構成新堆。
- 設待調整的堆的完全二叉樹存放在a[low……high]中
- 置初值i = low，j = 2*i+1，temp=a[i]
- 當 j < high時，重複下列操作
- 若 j < high-1，且a[j] > a[j+1],則j++
- 若temp > a[j]，則a[i]=a[j]; i = j; j = 2*i+1;否則 j =high
- a[i] = temp
建初始堆：
- 将待排序元素建成一棵完全二叉樹
- 将下标為[n/2]-1的元素作為開始調整的子樹的根結點
- 找出此結點的兩個孩子中的關鍵字值較小者，與此結點比較；若此結點大，則交換，然後交換後的子結點作為新的父結點，父結點就成了子結點重複此步驟直到沒有子結點為止。
- 以上步驟的原父結點的位置往前推進一個位置，作為新的調整的子樹的根結點，繼續重複上步驟
/**
* @description 堆排序算法
* @return
* @author liuquan
* @date 2016年1月5日
*/
public int[] heapSort(int[] before){
int[] a= Arrays.copyOf(before, before.length);
int n = a.length;
int temp;
for(int i = n / - ; i >= ; i--){ //建立初始堆
sift(i, n, a);
}
for(int i = n - ; i > ; i--){ //每趟将最小關鍵字值交換到後面，再調整成堆
temp = a[];
a[] = a[i];
a[i] = temp;
sift(, i, a);
}
return a;
}
/**
* @description 篩選法調整堆算法 ，以low為根結點的子樹調整成小頂堆
* @param low
* @param high
* @author liuquan
* @date 2016年1月5日
*/
private void sift(int low, int high, int[] a){
int i = low; //子樹的根結點
int j = * i + ;
int temp = a[i];
while(j < high){
//判斷條件j < high - 1 表示有右結點，即j+1 < high
if(j < high - && a[j] > a[j + ])
j++;
if(temp > a[j]){
a[i] = a[j]; //孩子結點中的較小值上移
i = j;
j = * i + ;
}
else
j = high + ;
}
a[i] = temp;
}
算法性能分析
- 空間複雜度：O(1)
-
時間複雜度：O(n㏒₂ n)
假設産生二叉樹的高是k，k=[㏒₂ n]- 1關鍵字的比較次數最多為2(k+1)次，交換記錄至多為k次，是以建好堆後篩選次數不超過2（[㏒₂ (n-1) +……+㏒₂ 2]）<2n[㏒₂ n]
由于建初始堆時比較次數不超過4n次，是以最壞情況下時間複雜度為O(n㏒₂ n)
- 算法穩定性：不穩定
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)