/************************************************************************* > File Name: sort.cpp > Author: SongLee ************************************************************************/#include<iostream>using namespace std;typedef int ElementType;/* *<<直接插入排序>> * 為了實現(xiàn)N個數的排序，將后面N-1個數依次插入到前面已排好的子序列中， *假定剛開始第1個數是一個已排好序的子序列。經過N-1趟就能得到一個有序序列。 *****時間復雜度：最好情況O(n)，最壞情況O(n^2)，平均情況O(n^2). *****空間復雜度：O(1) *****穩(wěn)定性：穩(wěn)定 */void InsertSort(ElementType A[], int n){ int i,j; ElementType temp; // 臨時變量 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)一地移動待插入位 *置之后的所有元素。不難看出折半插入排序僅僅是減少了比較的次數。 *****時間復雜度：O(n^2) *****空間復雜度：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; // 設置折半查找的范圍 while(low <= high) { mid = (low+high)/2; // 取中間點 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]的序列 *然后縮小間距，再對各分組序列進行排序。直到只比較相鄰元素的最后一趟排序為 *止，即最后的間距為1。希爾排序有時也叫做*縮小增量排序* *****時間復雜度：依賴于增量序列的選擇，但最壞情況才為O(N^2) *****空間復雜度：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) // 每個分組序列進行直接插入排序 { temp = A[i]; for(j=i-dk; j>=0 && A[j]>temp; j-=dk) A[j+dk] = A[j]; // 后移 A[j+dk] = temp; } }}/* *<<冒泡排序>> * 冒泡排序的基本思想是從后往前（或從前往后）兩兩比較相鄰元素的值，若為 *逆序，則交換它們，直到序列比較完。我們稱它為一趟冒泡。每一趟冒泡都會將一 *個元素放置到其最終位置上。 *****時間復雜度：最好情況O(n)，最壞情況O(n^2)，平均情況O(n^2) *****空間復雜度：O(1) *****穩(wěn)定性：穩(wěn)定 */void BubbleSort(ElementType A[], int n){ for(int i=0; i<n-1; ++i) { bool flag = false; // 表示本次冒泡是否發(fā)生交換的標志 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; }}/* *<<快速排序>> * 快速排序是對冒泡排序的一種改進。其基本思想是基于分治法：在待排序表L[n] *中任取一個元素pivot作為基準，通過一趟排序將序列劃分為兩部分L[1...K-1]和 *L[k+1...n]，是的L[1...k-1]中的所有元素都小于pivot，而L[k+1...n]中所有元素 *都大于或等于pivot。則pivot放在了其最終位置L(k)上。然后，分別遞歸地對兩個子 *序列重復上述過程，直至每部分內只有一個元素或空為止，即所有元素放在了其最終 *位置上。 *****時間復雜度：快排的運行時間與劃分是否對稱有關，最壞情況O(n^2),最好情況 *O(nlogn),平均情況為O(nlogn) *****空間復雜度：由于需要遞歸工作棧，最壞情況為O(n)，平均情況為O(logn) *****穩(wěn)定性：不穩(wěn)定 */int Partition(ElementType A[], int low, int high){ // 劃分操作有很多版本，這里就總以當前表中第一個元素作為樞紐/基準 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); // 劃分操作，返回基準元素的最終位置 QuickSort(A, low, pivotPos-1); // 遞歸 QuickSort(A, pivotPos+1, high); }}/* *<<簡單選擇排序>> * 選擇排序的算法思想很簡單，假設序列為L[n]，第i趟排序即從L[i...n]中選擇 *關鍵字最小的元素與L(i)交換，每一趟排序可以確定一個元素的最終位置。經過n-1 *趟排序就可以使得序列有序了。 *****時間復雜度：始終是O(n^2) *****空間復雜度：O(1) *****穩(wěn)定性：不穩(wěn)定 */void SelectedSort(ElementType A[], int n){ for(int i=0; i<n-1; ++i) // 一共進行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é)點和孩子節(jié)點之間的內在關系，在當 *前無序區(qū)中選擇關鍵字最大（或最?。┑脑亍６雅判虻乃悸肥牵菏紫葘⑿蛄蠰[n] *的n個元素建成初始堆，由于堆本身的特點（以大根堆為例），堆頂元素就是最大 *值。輸出堆頂元素后，通常將堆底元素送入堆頂，此時根結點已不滿足大根堆的性 *質，堆被破壞，將堆頂元素向下調整使其繼續(xù)保持大根堆的性質，再輸出堆頂元素。 *如此重復，直到堆中僅剩下一個元素為止。 *****時間復雜度：O(nlogn) *****空間復雜度：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;   // 如果右子結點大 if(temp < A[largest]) { A[i] = A[largest]; i = largest;   // 記錄交換后的位置 } else break; } A[i] = temp; // 被篩選結點的值放入最終位置}void BuildMaxHeap(ElementType A[], int len){ for(int i=len/2-1; i>=0; --i) // 從i=[n/2]~1，反復調整堆 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]; // 調整，把剩余的n-1個元素整理成堆 AdjustDown(A, 0, i);  }}/* *<<2-路歸并排序>> * 顧名思義，2-路歸并就是將2個有序表組合成一個新的有序表。假定待排序表 *有n個元素，則可以看成是n個有序的子表，每個子表長度為1，然后兩兩歸并...不 *停重復，直到合成一個長度為n的有序序列為止。Merge()函數是將前后相鄰的兩個 *有序表歸并為一個有序表，設A[low...mid]和A[mid+1...high]存放在同一順序表的 *相鄰位置上，先將它們復制到輔助數組B中。每次從對應B中的兩個段取出一個元素 *進行比較，將較小者放入A中。 *****時間復雜度：每一趟歸并為O(n),共log2n趟，所以時間為O(nlog2n) *****空間復雜度：O(n) *****穩(wěn)定性：穩(wěn)定 */ElementType *B = new ElementType[13]; // 和數組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中所有元素復制到B for(i=low,j=mid+1,k=i; i<=mid&&j<=high; ++k) { if(B[i] <= B[j])  // 比較B的左右兩段序列中的元素 A[k] = B[i++]; // 將較小值復制到A中 else A[k] = B[j++]; } while(i<=mid) A[k++] = B[i++]; // 若第一個表未檢測完，復制 while(j<=high) A[k++] = B[j++]; // 若第二個表未檢測完，復制}void MergeSort(ElementType A[], int low, int high){ if(low < high) { int mid = (low + high)/2; MergeSort(A, low, mid);  // 對左側子序列進行遞歸排序 MergeSort(A, mid+1, high); // 對右側子序列進行遞歸排序 Merge(A, low, mid, high);  // 歸并 }}/* * 輸出函數 */void print(ElementType A[], int n){ for(int i=0; i<n; ++i) { cout << A[i] << " "; } cout << endl;}/* * 主函數 */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;}