CCF-CSP备战NO.1排序

数据结构合集 - 归并排序(非递归与递归算法过程, 效率分析, 稳定性分析)_哔哩哔哩_bilibili1.直接排序#include bits/stdc.h using namespace std; // 直接插入排序函数 void InsertSort(int* a, int len) { // i从1开始第一个元素默认有序 for (int i 1; i len; i) { int temp a[i]; // 保存待插入元素 int j; // 向前遍历有序区间大于temp的元素全部后移 for (j i - 1; j 0 a[j] temp; j--) { a[j 1] a[j]; } // 找到插入位置放入temp a[j 1] temp; } } int main(){ int n; cin n; vectorint arr(n); for(int i 0; i n; i){ cin arr[i]; } // vector底层数组首地址传入 InsertSort(arr[0], n); for(int i 0; i n; i){ cout arr[i] ; } return 0; }最好O(n) 最坏O(n^2) 平均O(n^2) 空间复杂度O(1) 稳定2.快排有待优化#include bits/stdc.h using namespace std; void QuickSort(int array[], int low, int high) { int i low; int j high; if(i j) { return; } swap(array[low], array[low (high - low )/2]); int temp array[low]; while(i ! j) { while(array[j] temp i j) { j--; } while(array[i] temp i j) { i; } if(i j) { swap(array[i], array[j]); } } swap(array[low], array[i]); QuickSort(array, low, i - 1); QuickSort(array, i 1, high); } int main() { int n; cin n; vectorint arr(n); for(int k 0; k n; k) { cin arr[k]; } QuickSort(arr.data(), 0, n - 1); for(int k 0; k n; k) { if(k) cout ; cout arr[k]; } return 0; }最好O(nlogn) 最坏O(n^2) 平均O(nlogn) 空间复杂度O(logn) 不稳定2.希尔排序#include bits/stdc.h using namespace std; void InsertSort(int arr[],int len) { for(int gaplen/2;gap1;gap/2){ for(int igap;ilen-1;i){ int temparr[i]; int j; for(ji-gap;j0arr[j]temp;j-gap){ arr[jgap]arr[j]; } arr[jgap]temp; } } } int main() { int n; cinn; vectorint arr(n); for(int i0;in;i){ cinarr[i]; } InsertSort(arr[0],n); for(int i0;in;i){ if(i0) cout ; coutarr[i]; } return 0; } // 直接插入法排序 // main,冒泡排序#include bits/stdc.h using namespace std; void BubbleSort(int arr[],int n) { for(int i1;in-1;i){ bool flagfalse; for(int j0;jn-i;j){ if(arr[j]arr[j1]){ flagtrue; swap(arr[j],arr[j1]); } } if(flagfalse) break; } } int main() { int n; cinn; vectorint arr(n); for(int i0;in;i){ cinarr[i]; } BubbleSort(arr[0],n); for(int i0;in;i){ if(i0) cout ; coutarr[i]; } return 0; } // 直接插入法排序 // main,双向冒泡排序#include bits/stdc.h using namespace std; void BiBubbleSort(int arr[],int n) { int left0; int rightn-1; while(leftright){ bool flagfalse; for(int ileft;iright;i){ if(arr[i]arr[i1]){ swap(arr[i],arr[i1]); flagtrue; } } if(flagfalse){ break; } flagfalse; for(int jright;jleft;j--){ if(arr[j]arr[j-1]){ swap(arr[j],arr[j-1]); flagtrue; } } if(flagfalse){ break; } } } int main() { int n; cinn; vectorint arr(n); for(int i0;in;i){ cinarr[i]; } BiBubbleSort(arr[0],n); for(int i0;in;i){ if(i0) cout ; coutarr[i]; } return 0; } // 直接插入法排序 // main,3.归并排序#include bits/stdc.h using namespace std; void Merge(int a[],int l,int mid,int r){ int *temp (int*)malloc((r-l1)*sizeof(int)); int il,jmid1,k0; // 合并左右两个有序子区间 while(imidjr){ if(a[i]a[j]){ temp[k]a[i]; }else{ temp[k]a[j]; } } // 处理左区间剩余元素 while(imid) temp[k]a[i]; // 处理右区间剩余元素 while(jr) temp[k]a[j]; // 将临时数组内容拷贝回原数组 for(il,k0;ir;i,k) a[i]temp[k]; free(temp); } void MergeSort(int a[],int l,int r){ if(lr){ int mid (lr)/2; MergeSort(a,l,mid); MergeSort(a,mid1,r); Merge(a,l,mid,r); } } // 主函数测试使用vector int main() { int n; cin n; vectorint arr(n); for (int i 0; i n; i) { cin arr[i]; } // 传入vector底层数组首地址对[0, n-1]区间归并排序 MergeSort(arr[0], 0, n-1); // 输出结果 for (int i 0; i n; i) { if (i 0) cout ; cout arr[i]; } return 0; }最好O(nlogn) 最坏O(nlogn) 平均O(nlogn) 空间复杂度O(n) 稳定基数排序#include bits/stdc.h using namespace std; #define MaxDigit 3 #define Radix 10 typedef struct Node{ int data; struct Node *next; } Node; // 尾插法建立单链表(不带头结点) Node* CreateListR(int n){ Node *pNULL,*rNULL,*temp; for(int i0;in;i){ temp (Node*)malloc(sizeof(Node)); cintemp-data; if(pNULL){ prtemp; }else{ r-nexttemp;rtemp; } } r-nextNULL; return p; } void RadixSort(Node *p){ //构建并初始化所有桶 Node *h[Radix],*t[Radix],*r; for(int i0;iRadix;i){ h[i]t[i]NULL; } //逐位进行分配和收集 int b1; for(int d1;dMaxDigit;d){ //分配过程:依次将每个数按位放入桶中 while(p!NULL){ int k p-data/b%Radix; if(h[k]NULL){ h[k]t[k]p; }else{ t[k]-nextp;t[k]p; } pp-next; } b*Radix; //收集过程:依次将每个桶的元素取出 for(int i0;iRadix;i){ if(h[i]!NULL){ if(pNULL){ ph[i];rt[i]; }else{ r-nexth[i];rt[i]; } } h[i]t[i]NULL; } r-nextNULL; } } int main() { int n; cin n; Node* head CreateListR(n); RadixSort(head); // main内直接输出无单独打印函数 Node* cur head; bool flag true; while(cur ! NULL) { if(!flag) cout ; flag false; cout cur-data; cur cur-next; } return 0; }