/*************************************************************************
 > File Name: sort.cpp
 > Author: SongLee
 ************************************************************************/
#include<iostream>
using namespace std;

typedef int ElementType;

/*
 *<<直接插入排序>>
 * 為了實(shí)現(xiàn)N個數(shù)的排序，將后面N-1個數(shù)依次插入到前面已排好的子序列中，
 *假定剛開始第1個數(shù)是一個已排好序的子序列。經(jīng)過N-1趟就能得到一個有序序列。
 *****時(shí)間復(fù)雜度：最好情況O(n)，最壞情況O(n^2)，平均情況O(n^2).
 *****空間復(fù)雜度：O(1)
 *****穩(wěn)定性：穩(wěn)定
 */
void InsertSort(ElementType A[], int n)
{
 int i,j;
 ElementType temp; // 臨時(shí)變量

 for(i=1; i<n; ++i)
 {
 temp = A[i]; 
 for(j = i; j>0 && A[j-1]>temp; --j)
 A[j] = A[j-1];
 A[j] = temp;
 }
}

/*
 *<<折半插入排序>>
 * 與直接插入排序不同的是，折半插入排序不是邊比較邊移動，而是將比較和移
 *動操作分離出來，即先折半查找出元素的待插入位置，然后再統(tǒng)一地移動待插入位
 *置之后的所有元素。不難看出折半插入排序僅僅是減少了比較的次數(shù)。
 *****時(shí)間復(fù)雜度：O(n^2)
 *****空間復(fù)雜度：O(1)
 *****穩(wěn)定性：穩(wěn)定
 */
void BinaryInsertSort(ElementType A[], int n)
{
 int i, j, low, high, mid;
 ElementType temp;
 for(i=1; i<n; ++i)
 {
 temp = A[i];
 low = 0; high = i-1; // 設(shè)置折半查找的范圍
 while(low <= high)
 {
 mid = (low+high)/2; // 取中間點(diǎn)
 if(A[mid] > temp)
 high = mid-1;
 else
 low = mid+1;
 }

 for(j=i-1; j>=high+1; --j) // 統(tǒng)一后移
 A[j+1] = A[j];
 A[high+1] = temp; // 插入
 }
}

/*
 *<<希爾排序>>
 * 希爾排序通過比較相距一定間隔的元素，即形如L[i,i+d,i+2d,...i+kd]的序列
 *然后縮小間距，再對各分組序列進(jìn)行排序。直到只比較相鄰元素的最后一趟排序?yàn)?
 *止，即最后的間距為1。希爾排序有時(shí)也叫做*縮小增量排序*
 *****時(shí)間復(fù)雜度：依賴于增量序列的選擇，但最壞情況才為O(N^2)
 *****空間復(fù)雜度：O(1)
 *****穩(wěn)定性：不穩(wěn)定
 */
void ShellSort(ElementType A[], int n)
{
 int i, j, dk; // dk是增量
 ElementType temp;
 
 for(dk=n/2; dk>0; dk/=2) // 增量變化
 {
 for(i=dk; i<n; ++i) // 每個分組序列進(jìn)行直接插入排序
 {
 temp = A[i];
 for(j=i-dk; j>=0 && A[j]>temp; j-=dk)
 A[j+dk] = A[j]; // 后移
 A[j+dk] = temp;
 }
 }
}

/*
 *<<冒泡排序>>
 * 冒泡排序的基本思想是從后往前（或從前往后）兩兩比較相鄰元素的值，若為
 *逆序，則交換它們，直到序列比較完。我們稱它為一趟冒泡。每一趟冒泡都會將一
 *個元素放置到其最終位置上。
 *****時(shí)間復(fù)雜度：最好情況O(n)，最壞情況O(n^2)，平均情況O(n^2)
 *****空間復(fù)雜度：O(1)
 *****穩(wěn)定性：穩(wěn)定
 */
void BubbleSort(ElementType A[], int n)
{
 for(int i=0; i<n-1; ++i)
 {
 bool flag = false; // 表示本次冒泡是否發(fā)生交換的標(biāo)志
 for(int j=n-1; j>i; --j) // 從后往前
 {
 if(A[j-1] > A[j]) 
 {
 flag = true;
 // 交換
 A[j-1] = A[j-1]^A[j];
 A[j] = A[j-1]^A[j];
 A[j-1] = A[j-1]^A[j];
 }
 }

 if(flag == false)
 return;
 }
}

/*
 *<<快速排序>>
 * 快速排序是對冒泡排序的一種改進(jìn)。其基本思想是基于分治法：在待排序表L[n]
 *中任取一個元素pivot作為基準(zhǔn)，通過一趟排序?qū)⑿蛄袆澐譃閮刹糠諰[1...K-1]和
 *L[k+1...n]，是的L[1...k-1]中的所有元素都小于pivot，而L[k+1...n]中所有元素
 *都大于或等于pivot。則pivot放在了其最終位置L(k)上。然后，分別遞歸地對兩個子
 *序列重復(fù)上述過程，直至每部分內(nèi)只有一個元素或空為止，即所有元素放在了其最終
 *位置上。
 *****時(shí)間復(fù)雜度：快排的運(yùn)行時(shí)間與劃分是否對稱有關(guān)，最壞情況O(n^2),最好情況
 *O(nlogn),平均情況為O(nlogn)
 *****空間復(fù)雜度：由于需要遞歸工作棧，最壞情況為O(n)，平均情況為O(logn)
 *****穩(wěn)定性：不穩(wěn)定
 */
int Partition(ElementType A[], int low, int high)
{
 // 劃分操作有很多版本，這里就總以當(dāng)前表中第一個元素作為樞紐/基準(zhǔn)
 ElementType pivot = A[low];
 while(low < high)
 {
 while(low<high && A[high]>=pivot)
 --high;
 A[low] = A[high]; // 將比樞紐值小的元素移到左端
 while(low<high && A[low]<=pivot)
 ++low;
 A[high] = A[low]; // 將比樞紐值大的元素移到右端
 }

 A[low] = pivot; // 樞紐元素放到最終位置
 return low;  // 返回樞紐元素的位置
}

void QuickSort(ElementType A[], int low, int high)
{
 if(low < high) // 遞歸跳出的條件
 {
 int pivotPos = Partition(A, low, high); // 劃分操作，返回基準(zhǔn)元素的最終位置
 QuickSort(A, low, pivotPos-1); // 遞歸
 QuickSort(A, pivotPos+1, high);
 }
}

/*
 *<<簡單選擇排序>>
 * 選擇排序的算法思想很簡單，假設(shè)序列為L[n]，第i趟排序即從L[i...n]中選擇
 *關(guān)鍵字最小的元素與L(i)交換，每一趟排序可以確定一個元素的最終位置。經(jīng)過n-1
 *趟排序就可以使得序列有序了。
 *****時(shí)間復(fù)雜度：始終是O(n^2)
 *****空間復(fù)雜度：O(1)
 *****穩(wěn)定性：不穩(wěn)定
 */
void SelectedSort(ElementType A[], int n)
{
 for(int i=0; i<n-1; ++i) // 一共進(jìn)行n-1趟
 {
 int minPos = i; // 記錄最小元素的位置

 for(int j=i+1; j<n; ++j)
 if(A[j] < A[minPos])
 minPos = j;

 if(minPos != i) // 與第i個位置交換
 {
 A[i] = A[i]^A[minPos];
 A[minPos] = A[i]^A[minPos];
 A[i] = A[i]^A[minPos];
 }
 }
}

/*
 *<<堆排序>>
 * 堆排序是一種樹形選擇排序方法，在排序過程中，將L[n]看成是一棵完全二叉
 *樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親節(jié)點(diǎn)和孩子節(jié)點(diǎn)之間的內(nèi)在關(guān)系，在當(dāng)
 *前無序區(qū)中選擇關(guān)鍵字最大（或最小）的元素。堆排序的思路是：首先將序列L[n]
 *的n個元素建成初始堆，由于堆本身的特點(diǎn)（以大根堆為例），堆頂元素就是最大
 *值。輸出堆頂元素后，通常將堆底元素送入堆頂，此時(shí)根結(jié)點(diǎn)已不滿足大根堆的性
 *質(zhì)，堆被破壞，將堆頂元素向下調(diào)整使其繼續(xù)保持大根堆的性質(zhì)，再輸出堆頂元素。
 *如此重復(fù)，直到堆中僅剩下一個元素為止。
 *****時(shí)間復(fù)雜度：O(nlogn)
 *****空間復(fù)雜度：O(1)
 *****穩(wěn)定性：不穩(wěn)定
 */

void AdjustDown(ElementType A[], int i, int len)
{
 ElementType temp = A[i]; // 暫存A[i]
 
 for(int largest=2*i+1; largest<len; largest=2*largest+1)
 {
 if(largest!=len-1 && A[largest+1]>A[largest])
 ++largest;   // 如果右子結(jié)點(diǎn)大
 if(temp < A[largest])
 {
 A[i] = A[largest];
 i = largest;   // 記錄交換后的位置
 }
 else
 break;
 }
 A[i] = temp; // 被篩選結(jié)點(diǎn)的值放入最終位置
}
void BuildMaxHeap(ElementType A[], int len)
{
 for(int i=len/2-1; i>=0; --i) // 從i=[n/2]~1，反復(fù)調(diào)整堆
 AdjustDown(A, i, len);
}
void HeapSort(ElementType A[], int n)
{
 BuildMaxHeap(A, n);  // 初始建堆
 for(int i=n-1; i>0; --i) // n-1趟的交換和建堆過程 
 {
 // 輸出最大的堆頂元素（和堆底元素交換）
 A[0] = A[0]^A[i];
 A[i] = A[0]^A[i];
 A[0] = A[0]^A[i];
 // 調(diào)整，把剩余的n-1個元素整理成堆
 AdjustDown(A, 0, i); 
 }
}

/*
 *<<2-路歸并排序>>
 * 顧名思義，2-路歸并就是將2個有序表組合成一個新的有序表。假定待排序表
 *有n個元素，則可以看成是n個有序的子表，每個子表長度為1，然后兩兩歸并...不
 *停重復(fù)，直到合成一個長度為n的有序序列為止。Merge()函數(shù)是將前后相鄰的兩個
 *有序表歸并為一個有序表，設(shè)A[low...mid]和A[mid+1...high]存放在同一順序表的
 *相鄰位置上，先將它們復(fù)制到輔助數(shù)組B中。每次從對應(yīng)B中的兩個段取出一個元素
 *進(jìn)行比較，將較小者放入A中。
 *****時(shí)間復(fù)雜度：每一趟歸并為O(n),共log2n趟，所以時(shí)間為O(nlog2n)
 *****空間復(fù)雜度：O(n)
 *****穩(wěn)定性：穩(wěn)定
 */
ElementType *B = new ElementType[13]; // 和數(shù)組A一樣大
void Merge(ElementType A[], int low, int mid, int high)
{
 int i, j, k;
 for(k=low; k<=high; ++k)
 B[k] = A[k];    // 將A中所有元素復(fù)制到B
 for(i=low,j=mid+1,k=i; i<=mid&&j<=high; ++k)
 {
 if(B[i] <= B[j])  // 比較B的左右兩段序列中的元素
 A[k] = B[i++]; // 將較小值復(fù)制到A中
 else
 A[k] = B[j++];
 }
 while(i<=mid) A[k++] = B[i++]; // 若第一個表未檢測完，復(fù)制
 while(j<=high) A[k++] = B[j++]; // 若第二個表未檢測完，復(fù)制
}

void MergeSort(ElementType A[], int low, int high)
{
 if(low < high)
 {
 int mid = (low + high)/2;
 MergeSort(A, low, mid);  // 對左側(cè)子序列進(jìn)行遞歸排序
 MergeSort(A, mid+1, high); // 對右側(cè)子序列進(jìn)行遞歸排序
 Merge(A, low, mid, high);  // 歸并
 }
}

/*
 * 輸出函數(shù)
 */
void print(ElementType A[], int n)
{
 for(int i=0; i<n; ++i)
 {
 cout << A[i] << " ";
 }
 cout << endl;
}

/*
 * 主函數(shù)
 */
int main()
{
 ElementType Arr[13] = {5,2,1,8,3,6,4,7,0,9,12,10,11};
 //InsertSort(Arr, 13);
 //BinaryInsertSort(Arr, 13);
 //ShellSort(Arr, 13);
 //BubbleSort(Arr, 13);
 //QuickSort(Arr, 0, 12);
 //SelectedSort(Arr, 13);
 //HeapSort(Arr, 13);
 //MergeSort(Arr, 0, 12);
 print(Arr, 13);
 return 0;
}