当前位置：首页 > news >正文

CCF-CSP备战NO.1排序

news 2026/7/27 23:49:26

数据结构合集 - 归并排序(非递归与递归算法过程, 效率分析, 稳定性分析)_哔哩哔哩_bilibili

1.直接排序

#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; vector<int> 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; vector<int> 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 gap=len/2;gap>=1;gap/=2){ for(int i=gap;i<=len-1;i++){ int temp=arr[i]; int j; for(j=i-gap;j>=0&&arr[j]>temp;j-=gap){ arr[j+gap]=arr[j]; } arr[j+gap]=temp; } } } int main() { int n; cin>>n; vector<int> arr(n); for(int i=0;i<n;i++){ cin>>arr[i]; } InsertSort(&arr[0],n); for(int i=0;i<n;i++){ if(i>0) cout<<" "; cout<<arr[i]; } return 0; } // 直接插入法排序， // main,

冒泡排序

#include <bits/stdc++.h> using namespace std; void BubbleSort(int arr[],int n) { for(int i=1;i<=n-1;i++){ bool flag=false; for(int j=0;j<n-i;j++){ if(arr[j]>arr[j+1]){ flag=true; swap(arr[j],arr[j+1]); } } if(flag==false) break; } } int main() { int n; cin>>n; vector<int> arr(n); for(int i=0;i<n;i++){ cin>>arr[i]; } BubbleSort(&arr[0],n); for(int i=0;i<n;i++){ if(i>0) cout<<" "; cout<<arr[i]; } return 0; } // 直接插入法排序， // main,

双向冒泡排序

#include <bits/stdc++.h> using namespace std; void BiBubbleSort(int arr[],int n) { int left=0; int right=n-1; while(left<right){ bool flag=false; for(int i=left;i<right;i++){ if(arr[i]>arr[i+1]){ swap(arr[i],arr[i+1]); flag=true; } } if(flag==false){ break; } flag=false; for(int j=right;j>left;j--){ if(arr[j]<arr[j-1]){ swap(arr[j],arr[j-1]); flag=true; } } if(flag==false){ break; } } } int main() { int n; cin>>n; vector<int> arr(n); for(int i=0;i<n;i++){ cin>>arr[i]; } BiBubbleSort(&arr[0],n); for(int i=0;i<n;i++){ if(i>0) cout<<" "; cout<<arr[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-l+1)*sizeof(int)); int i=l,j=mid+1,k=0; // 合并左右两个有序子区间 while(i<=mid&&j<=r){ if(a[i]<=a[j]){ temp[k++]=a[i++]; }else{ temp[k++]=a[j++]; } } // 处理左区间剩余元素 while(i<=mid) temp[k++]=a[i++]; // 处理右区间剩余元素 while(j<=r) temp[k++]=a[j++]; // 将临时数组内容拷贝回原数组 for(i=l,k=0;i<=r;i++,k++) a[i]=temp[k]; free(temp); } void MergeSort(int a[],int l,int r){ if(l<r){ int mid = (l+r)/2; MergeSort(a,l,mid); MergeSort(a,mid+1,r); Merge(a,l,mid,r); } } // 主函数测试（使用vector） int main() { int n; cin >> n; vector<int> 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 *p=NULL,*r=NULL,*temp; for(int i=0;i<n;i++){ temp = (Node*)malloc(sizeof(Node)); cin>>temp->data; if(p==NULL){ p=r=temp; }else{ r->next=temp;r=temp; } } r->next=NULL; return p; } void RadixSort(Node *&p){ //构建并初始化所有桶 Node *h[Radix],*t[Radix],*r; for(int i=0;i<Radix;i++){ h[i]=t[i]=NULL; } //逐位进行分配和收集 int b=1; for(int d=1;d<=MaxDigit;d++){ //分配过程:依次将每个数按位放入桶中 while(p!=NULL){ int k = p->data/b%Radix; if(h[k]==NULL){ h[k]=t[k]=p; }else{ t[k]->next=p;t[k]=p; } p=p->next; } b*=Radix; //收集过程:依次将每个桶的元素取出 for(int i=0;i<Radix;i++){ if(h[i]!=NULL){ if(p==NULL){ p=h[i];r=t[i]; }else{ r->next=h[i];r=t[i]; } } h[i]=t[i]=NULL; } r->next=NULL; } } 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; }

查看全文

http://www.jsqmd.com/news/1277105/