排序大全V1.1.3！！！
2024-03-08 22:51:21
发布于：广东
92阅读
0回复
0点赞
没活了不更新了
1.1.3基数排序可以自己调进制，增加灵活性
1.1.2把基数排序的取第i位方法改变，把快排取枢轴方法优化（好像优化了又好像没有）
1.1.1优化了基数排序（再用么么set我是勾！！！）
1.1版本增加了基数排序 基数排序是版本之子所以从A变成S了（）
#include <iostream>
#include <cstdio>
#include <windows.h>
#include <ctime>
using namespace std;
int a[100005], arr[100005], jishu[105][100005];
bool cmp(int a, int b){
return a < b;
}
void bubblesort(int *a, int len){
"冒泡排序 综合:B 时间复杂度:O(n^2) (n~n^2) 稳定:√ 难度:☆ 新手必备！";//别问我为什么不用注释，问就是斜着太难受了
for(int i = 1; i <= len; i++){
for(int j = 1; j <= len - i; j++){
if(cmp(a[j + 1], a[j])) swap(a[j], a[j + 1]);//遇到右边比左边大（小）就交换
}
}
}
void insertsort(int *a, int left, int right){//你猜猜这里为什么要用left和right^_^
"插入排序 综合:B 时间复杂度:O(n^2) (n~n^2) 稳定:√ 难度:☆☆ 顶级辅助";
for(int i = left + 1; i <= right; i++){//把前面的当成有序数组
int tmp = i - 1, cur = a[i];
while(tmp >= left){
if(cmp(cur, a[tmp])){
a[tmp + 1] = a[tmp];//逐一比较，继续向前，为新数让开位置
tmp--;
}
else break;
}a[tmp + 1] = cur;//插入
}
}
void selectionsort(int *a, int len){
"选择排序 综合:B 时间复杂度:O(n^2) 稳定:× 难度:☆ 新手必备，但是不如冒泡（";
for(int i = 1; i <= len; i++){
int mi = a[i], idx = i;
for(int j = i + 1; j <= len; j++){
if(cmp(a[j], mi)) mi = a[j], idx = j;//寻找最小值
}swap(a[i], a[idx]);//交换
}
}
void bucketsort(int *a, int len){
"桶排序(计数?) 综合:B+ 时间复杂度:O(n) (实际你自己定，我这是n) 空间复杂度:O(a(max) - a(min)) 稳定:√ 难度:☆";
int mn = 0x7fffffff, mx = -1e9;
for(int i = 1; i <= len; i++){
mn = min(mn, a[i]), mx = max(mx, a[i]);
}for(int i = 1; i <= len; i++){
arr[a[i] - mn]++;//放入桶
}
mx -= mn;
int ct = 1;
for(int i = 0; i <= mx; i++){
while(arr[i]--){
a[ct++] = i + mn;//复制数组
}
}
}
//基数排序
void radixsort(int, int, int);
int getweishu(int x, int r){//求位数
int ct = 0;
while(x){
ct++;
x /= r;
}return ct;
}int pow(int r, int i){//
int ct = 1;
while(i--){
ct *= r;
}return ct;
}
void radixsort(int *a, int len, int r){
"基数排序 综合:S 时间复杂度:O(d(n + r)) (其中d为最大数的位数(即log(a(max))，底数为r)，r因为是十个桶所以一般是10，可以自己调)";
"空间复杂度:O(nr) 稳定:√ 难度:☆☆☆ 桶排序pro max";
int weishu = 0;
for(int i = 1; i <= len; i++){
weishu = max(weishu, getweishu(a[i], r));//确定最大数的位数
}
int dgt, x;
for(int i = 1; i <= weishu; i++){//重复位数次排序
dgt = pow(r, i - 1);
for(int j = 1; j <= len; j++){
x = a[j] / dgt % r;//求这个数的第x位
jishu[x][++jishu[x][0]] = a[j];//录入数，其中jishu[dgt][0]是jishu[dgt]的长度，每次录入加1
}
int ct = 1;
for(int i = 0; i < r; i++){
for(int j = 1; j <= jishu[i][0]; j++){
a[ct++] = jishu[i][j];//复制回数组
jishu[i][j] = 0;//同时清零
}jishu[i][0] = 0;//位数也要清空
}
}//这下可以变成S了(骄傲)
}
//归并排序
void mergesort(int, int, int);
void merge(int *a, int left, int right){
int mid = (left + right) / 2;
int i = left, j = mid + 1, st = left;
//left和right中间因为被mid分割，可看做两个有序数组
while(i <= mid && j <= right){
if(cmp(a[i], a[j])) arr[st++] = a[i++];//把两个有序的数组里的元素一个一个进行比较，小的放进备用数组
else arr[st++] = a[j++];
}
while(i <= mid) arr[st++] = a[i++];//没被遍历完
while(j <= right) arr[st++] = a[j++];
for(int i = left; i <= right; i++){
a[i] = arr[i];
}
}
void mergesort(int *a, int left, int right){
"归并排序 综合:S+ 时间复杂度:O(nlogn) 稳定:√ 难度:☆☆☆ 神！！！";
if(left >= right) return;
int mid = (left + right) / 2;
mergesort(a, left, mid);
mergesort(a, mid + 1, right);//分割成一个个的小数组再去合并
merge(a, left, right);
}
//快速排序
void sort(int, int, int);
int midof3(int a, int b, int c){//三数取中
if(cmp(a, b)){
if(cmp(b, c)) return b;
else{
if(cmp(a, c)) return c;//一堆if else就为了贪一点点
else return a;
}
}else{
if(cmp(b, c)){
if(cmp(a, c)) return a;
else return c;
}else return b;
}
}
int part_it_i_on(int *a, int left, int right){
int i = left, j = right;
int pivot = midof3(a[left], a[(left + right) / 2], a[right]);//枢轴取中间最快
while(1){
while(i < j && cmp(a[i], pivot)) i++;
while(i < j && cmp(pivot, a[j])) j--;//双指针一直扫描
if(i >= j) return i;
swap(a[i], a[j]);//交换，使i左边始终大于j右边
j--;//这个实际上有错误，但是我不想判断相等了
}
}
void quicksot(int *a, int left, int right){
if((right - left) < 5){
return;
}
int i = part_it_i_on(a, left, right);
quicksot(a, left, i - 1);
quicksot(a, i + 1, right);//分割
}void sort(int *a, int left, int right){
"快速排序 综合:S 时间复杂度:O(nlogn) (nlogn~n^2) 稳定:× 难度:☆☆☆ 神！！！（这里是乱排）";
quicksot(a, left, right);
insertsort(a, left, right);
}
int main(){
srand(time(0));
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a, 1, n);
for(int i = 1; i <= n; i++) cout << a[i] << ' ';//输入输出
cout << endl;
for(int i = 1; i < n; i++){
if(cmp(a[i + 1], a[i])) cout << a[i] << ' ' << a[i + 1] << endl;
}//纠错环节
return 0;
}
这里发个对应的题目吧（
冒泡
插入
选择
桶
归并（两个都可以点）
快排太多了就不列了，直接用algorithm的sort做就行
全部评论 9
我再用memset我是勾！！！
我再用memset我是勾！！！
我再用memset我是勾！！！
我再用memset我是勾！！！
我再用memset我是勾！！！
我再用memset我是勾！！！
我再用memset我是勾！！！
我再用memset我是勾！！！
我再用memset我是勾！！！
我再用memset我是勾！！！
我再用memset我是勾！！！
我再用memset我是勾！！！
我再用memse2024-02-04 来自 湖南
0
有帮助，赞一个