#include#include#include#include#includeusing namespace std; void print(int a[], int n, int i) { cout << i << ":"; for (int j = 0; j<8; j++) { cout << a[j] << " "; } cout << endl; } void swap(int a, int b) { int temp; temp = a; a = b; b = temp; } /*插入排序: 將第1待排序序列第1個元素看作1個有序序列，把第2個元素到最后1個元素當做是未排序序列。 從頭到尾順次掃描未排序序列，將掃描到的每一個元素插入有序序列的適當位置。 如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。 * 時間復雜度也為O(n^2), 比冒泡法和選擇排序的性能要更好1些 */ void InsertSort(int a[], int n) { for (int i = 1; i1; j--) { if(a[j] i; j--) { if (a[j] < a[j - 1]) swap(a[j], a[j - 1]); } } } /*快速排序 從數列中挑出1個元素，稱為 “基準”（pivot）， 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任1邊）。在這個分區退出以后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。*/ void QuickSort(int a[], int n)//n為數組的長度 { int low=0,high=n⑴; int temp,temq; int pivot=a[low];//樞軸值 if(n >1 ) { while(low = pivot ) --high; a[low]= a[high];//比pivot小的都放在左側 while(low=1; div/=2) { for(int i=div; i=0; j-=div) swap(a[j],a[j-div]); } } } /*堆排序 首先，按堆的定義將數組R[0..n]調劑為堆（這個進程稱為創建初始堆），交換R[0]和R[n]； 然后，將R[0..n⑴]調劑為堆，交換R[0]和R[n⑴]； 如此反復，直到交換了R[0]和R[1]為止。 只不過直接選擇排序中，為了從R[1...n]當選擇最大記錄，需比較n⑴次，然后從R[1...n⑵]當選擇最大記錄需比較n⑵次。 事實上這n⑵次比較中有很多已在前面的n⑴次比較中已做過，而樹形選擇排序恰好利用樹形的特點保存了部份前面的比較結果， 因此可以減少比較次數。對n個關鍵字序列，最壞情況下每一個節點需比較log2(n)次，因此其最壞情況下時間復雜度為nlogn。 堆排序為不穩定排序，不合適記錄較少的排序。 */ void HeapAdjust(int a[],int i,int n) //調劑堆 { int lchild=2*i; //i的左孩子節點序號 int rchild=2*i+1; //i的右孩子節點序號 int max=i; //臨時變量 if(i<=n/2) //如果i不是葉節點就不用進行調劑 { if(lchild<=n&&a[lchild]>a[max]) { max=lchild; } if(rchild<=n&&a[rchild]>a[max]) { max=rchild; } if(max!=i) { swap(a[i],a[max]); HeapAdjust(a,max,n); //避免調劑以后以max為父節點的子樹不是堆 } } } void BuildHeap(int a[],int n) //建立堆 { int i; for(i=n/2;i>=1;i--) //非葉節點最大序號值為size/2 { HeapAdjust(a,i,n); } } void HeapSort(int a[],int n) //堆排序 { int i; BuildHeap(a,n); for(i=n;i>=1;i--) { //cout<= n⑴) right = n-b; else right = length; int* temp = new int[length+right]; int i=0, j=0; while(i<=length⑴ && j<=right⑴){ if(data[a+i] <= data[b+j]){ temp[i+j] = data[a+i];i++; } else{ temp[i+j] = data[b+j]; j++; } } if(j == right){//a中還有元素，且全都比b中的大,a[i]還未使用 memcpy(temp + i + j, data + a + i, (length - i) * sizeof(int)); } else if(i == length){ memcpy(temp + i + j, data + b + j, (right - j)*sizeof(int)); } memcpy(data+a, temp, (right + length) * sizeof(int)); delete [] temp; } void MergeSort(int* data, int n){ int step = 1; while(step < n){ for(int i=0; i<=n-step⑴; i+=2*step) Merge(data, i, i+step, step, n); //將i和i+step這兩個有序序列進行合并 //序列長度為step //當i以后的長度小于或等于step時，退出 step*=2;//在按某1步長歸并序列以后，步長加倍 } } /* 基數排序 可以對個位數、10位數、百位數也依照這類方法進行排序，最后就可以得到排序完成的序列。 */ int maxbit(int data[], int n) //輔助函數，求數據的最大位數 { int d = 1; //保存最大的位數 int p = 10; for(int i = 0; i < n; ++i) { while(data[i] >= p) { p *= 10; ++d; } } return d; } void radixsort(int data[], int n) //基數排序 { int d = maxbit(data, n); int *tmp = new int[n]; int *count = new int[10]; //計數器 int i, j, k; int radix = 1; for(i = 1; i <= d; i++) //進行d次排序 { for(j = 0; j < 10; j++) count[j] = 0; //每次分配前清空計數器 for(j = 0; j < n; j++) { k = (data[j] / radix) % 10; //統計每一個桶中的記錄數 count[k]++; } for(j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; //將tmp中的位置順次分配給每一個桶 for(j = n - 1; j >= 0; j--) //將所有桶中記錄順次搜集到tmp中 { k = (data[j] / radix) % 10; tmp[count[k] - 1] = data[j]; count[k]--; } for(j = 0; j < n; j++) //將臨時數組的內容復制到data中 data[j] = tmp[j]; radix = radix * 10; } delete[]tmp; delete[]count; } //主程序 int main() { int n; cin>>n; int k=n; int* a=new int[n]; while(k--){ cin>>a[n-k⑴]; } //int a[8] = { 3,1,5,7,2,4,9,6 }; InsertSort(a, 8); //BubbleSort(a, 8); //DirectSort(a, 8); //radixsort(a,8); //HeapSort(a,8); //ShellSort(a,8); //QuickSort(a,8); //MergeSort(a,8); print(a, 8, 8); }