八大排序算法

单链表代码

#include
#include
#include
using namespace std;
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
void print(LNode *L){
    for(LNode *p=L;p!=NULL;p=p->next){
        cout << p->data << " ";
    }
    cout << endl;
}
int main(){
    LinkList L=new LNode;
    L->next=NULL;
    L->data=1;
    print(L);
    //尾插法
    LinkList a=new LNode;
    a->next=NULL;
    a->data=2;
    L->next=a;
    print(L);
    LinkList b=new LNode;
    b->next=NULL;
    b->data=3;
    a->next=b;
    print(L);
    //头插法  
    LinkList c=new LNode;
    c->next=NULL;
    c->data=4;
    c->next=L->next;  
    L->next=c;
    print(L);
    //删除中间节点
    c->next=c->next->next;
    free(a);
    print(L);
    //删除头结点
    LNode *p=L;  // 为什么要构造一个P  直接L=L->next 不是也能删除吗
    L=L->next;   // 构造一个P是因为要释放原来的头结点的那个空间
    free(p);
    print(L);
    return 0;
}
//链表一到八题代码
void One(List &a,List &b,List &c){
    pa=a->next;
    pb=b->next;
    pc=c=pa;
    while(pa&&pb){
        if(pa->data>pb->data){
            pc->next=pb;
            pc=pc->next;
            pb=pb->next;
        }
        else if(pa->data<pb->data){
            pc->next=pa;
            pc=pc->next;
            pa=pa->next;
        }
        else {
            pc->next=pa;
            pc=pc->next;
            u=pb;
            pa=pa->next;
            pb=pb->next;
            free(u);
        }
    }
    while(pa) {
        pc->next=pa;
        pc=pc->next;
        pa=pa->next;
    }
    while(pb) {
        pc->next=pb;
        pc=pc->next;
        pb=pb->next;
    }
    free(pb);
}
void Two(List &a,List &b,List &c){
    pa=a->next;
    pb=b->next;
    c=pc=a;  
    c->next=NULL;
    while(pa&&pb){
        if(pa->data<=pb->data){
            u=pa;
            u->next=c->next;     //头插法操作的是头结点
            c->next=u;
            pa=pa->next;
        }
        else if(pa->data>pb->data){
            u=pb;
            u->next=c->next;
            c->next=u;
            pb=pb->next;
        }
    }
    while(pa) {
        u=pa;
        u->next=c->next;
        c->next=u;
        pa=pa->next;
    }
    while(pb){
        u=pb;
        u->next=c->next;
        c->next=u;
        pb=pb->next;
    }
    free(b);
}
void Three(List &a,List &b,List &c){
    pa=a->next;
    pb=b->next;
    c=pc=a;
    while(pa&&pb){
        if(pa->data>pb->data){
            u=pb;
            pb=pb->next;
            free(u);
        }
        else if(pa->data<pb->data){ // 这特么a里面没用到的点也得删除
            u=pa;
            pa=pa->next;
            free(u);
        }
        else {
            u=pb;
            pc->next=pa;
            pc=pc->next;
            pa=pa->next;
            pb=pb->next;
            free(u);
        }
    }
    while(pa){  // 这他妈也要删除
        u=pa;
        pa=pa->next;
        free(u);
    }
    while(pb){
        u=pb;
        pb=pb->next;
        free(u);
    }
    pc->next=NULL;
    free(b);
}
void Four(List &a,List &b,List &c){  //这题为啥不释放B链表的节点了?
    pa=a->next;
    pb=b->next;
    pre=a;//注意这一题不用开新表,只用操作A表,pre用来方便删除A中的节点
    int n=0;
    while(pa&&pb){
        if(pa->data==pb->data){
            pre->next=pa->next;
            u=pa;
            pa=pa->next;
            pb=pb->next;
            free(u);
        }
        if(pa->data>pb->data){
            pb=pb->next;
        }
        else {
            n++;
            pre=pa;
            pa=pa->next;
        }
    }
    while(pa){
        n++;
        pa=pa->next;
    }
    while(pb){
        u=pb;
        pb=pb->next;
        free(u);
    }
    free(b);
}
void Five(List &a){
    b=pb=a;
    pa=a->next;
    c=new List();
    pc=c;
    c->next=NULL;
    while(pa){
        if(pa->data<0){
            pb->next=pa;
            pb=pb->next;
            pa=pa->next;
        }
        else {
            pc->next=pa;
            pc=pc->next;
            pa=pa->next;
        }
    }
}
void six(List a){
    pmax=a->next;
    pa=a->next;
    while(pa){
        if(pa->data>pmax->data){
            pmax=pa;
        }
        pa=pa->next;
    }
    return pmax->data;
}
void seven(List &a){
    pa=a->next;
    pc=c=a;
    c->next=NULL;
    while(pa){
        u=pa;
        pa=pa->next;
        u->next=c->next;
        c->next=u;
    }
}
void eight(List &a,int mink,int maxk){
    pa=a->next;
    pre=a;
    while(pa){
        if(pa->data>mink&&pa->data<maxk){
            pre->next=pa->next;
            u=pa;
            pa=pa->next;
            delete u;
        }
        else pa=pa->next;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245

排序算法

#include
#include
#include
using namespace std;
const int N=1e5+10;
int q[N];
int w[N],s[N];
int n,sz;
//直接插入排序 ,对于某一个元素加入到一个有序的序列中，将该元素依次从该位置开始
//从后往前比较，
//大于该元素的都往后挪一位，直到找到比他小的元素，将该元素插入到比他小的元素的后面。
// 稳定 平均 n^2 最好 n
void insert_sort(){
    for(int i=0;i<n;i++){   // 这里i=1 开始也对
        int t=q[i],j=i;
        while(j>0&&q[j-1]>t){
            swap(q[j],q[j-1]);  // 这里写成q[j]=q[j-1] 也对
            j--;
        }
        q[j]=t;
    }
}
//折半插入排序 就是在排序的基础上进行二分优化，就是在“将该元素依次从后往前比较”
//这一步中 直接通过二分找到比他小的最大元素 
//稳定 平均 n^2 最好 n
void binary_search_insert_sort(){
    for(int i=0;i<n;i++){
        int t=q[i];
        if(t>=q[i-1]){
            q[i]=t;
            continue;
        }
        int l=0,r=i;
        while(l<r){
            int mid=l+r>>1;
            if(q[mid]>t) r=mid;
            else l=mid+1;
        }
        for(int j=i-1;j>=r;j--){
            q[j+1]=q[j];
        }
        q[r]=t;
    }
}
//冒泡排序  a,b,c,d 从后往前依次做 if c > d 交换二者位置，这样每遍历一次，可以将
//第 i 小的数 放在第i个位置 一共只需要做n-1次。
//y总写的这个是把小的往前冒
//也可以把大的往后冒
//稳定 平均 n^2 最好 n
void bubble_sort(){
    for(int i=0;i<n-1;i++){
        bool has_swap=false;//小优化  如果说当前遍历的过程中，没发生一次交换，说明
        //当前序列已经是有序的了 可以直接break
        for(int j=n-1;j>i;j--){
            if(q[j]<q[j-1]) {
                swap(q[j],q[j-1]);
                has_swap=true;
            }
        }
        if(!has_swap) break;
    }
}
//最简单的一集,依次从前往后遍历，每次把后面的最小的一个选出来 放到当前位置。
//总共需要遍历n-1次，因为最后一个位置肯定是符合有序的
//不稳定 n^2
void select_sort(){
    for(int i=0;i<n-1;i++){
        int k=i;
        for(int j=i+1;j<n;j++){
            if(q[j]<q[k]){
                k=j;
            }
        }
        swap(q[k],q[i]);
    }
}
//希尔排序:分组+插入排序
//不稳定 n^(3/2)
void shell_sort(){
    for(int d=n/3;d;d = d == 2 ? 1 : d / 3){  // 因为希尔排序最后要求公差必须是1
    //但你每次除三到最后不一定是1 可能是2  2的话我们令公差为1
        for(int start=0;start<d;start++){
            for(int i=start+d;i<n;i+=d){
                int t=q[i],j=i;
                while(j>start&&t<q[j-d]){
                    swap(q[j],q[j-d]);
                    j=j-d;
                }
                q[j]=t;
            }
        }
    }
}
//具体理解 可以参考B站动画演示
//不稳定 平均 nlogn 最坏 n^2
void quick_sort(int l,int r){
    if(l>=r) return;
    int i=l-1,j=r+1,x=q[(l+r)>>1];
    while(i<j){
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    quick_sort(l,j);
    quick_sort(j+1,r);
}
//堆排序要从下标1开始,具体过程可以参考B站动画演示

void down(int t){
    int u=t;
    if(u*2<=sz&&q[u*2]>q[t]) t=u*2;
    if(u*2+1<=sz&&q[u*2+1]>q[t]) t=u*2+1;
    if(u!=t){ //如果t不是叶子结点 且与儿子结点发生了交换 那么需要递归重新构建儿子的大根堆
        swap(q[u],q[t]);
        down(t);//重新构建叶子节点大根堆
    }
}
// 不稳定 nlogn
void heap_sort(){
    sz=n;
    for (int i = n / 2; i; i -- ) down(i);//从最大的非叶子结点开始 将原数组变为一个大根堆
    for(int i=0;i<n-1;i++){
        swap(q[1], q[sz]);  // 将堆顶与堆低元素互换 
        sz -- ;//并且删除堆低元素
        down(1);//因为发生了交换 破坏了原有的大根堆 需要重新构造大根堆
    }
}
//归并排序
//稳定  nlogn
void merge_sort(int l,int r){
    if(l>=r) return;
    int mid=l+r>>1;
    merge_sort(l,mid),merge_sort(mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j]) w[k++]=q[i++];
        else w[k++]=q[j++];
    }
    while(i<=mid) w[k++]=q[i++];
    while(j<=r) w[k++]=q[j++];
    for(i=l,j=0;i<=r;i++,j++) q[i]=w[j];
}
void bucket_sort(){
    for(int i=0;i<n;i++) s[q[i]]++;
    for(int i=1;i<N;i++) s[i]=s[i]+s[i-1];
    for(int i=n-1;i>=0;i--) w[--s[q[i]]]= q[i];// 举个例子  5 3 4 1 1 
    //s[1]=2  则w[--2]=1  也即w[1]=1 第1个位置应该放后一个1 
    //s[1]=1  则w[--1]=1  也即w[0]=1 第0个位置应该放前一个1 （先后顺序未发生改变稳定！）
    //s[4]=4  则w[--4]=4  也即w[3]=4 第三个位置应该放4
    //s[3]=3  则w[--3]=3  也即w[2]=3 第二个位置应该放3
    //s[5]=5  则w[--5]=5  也即w[4]=5 第四个位置应该放5
    //倒着排序可以保证稳定性
    for(int i=0;i<n;i++) q[i]=w[i];
}
int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> q[i];
    }
    //insert_sort();
    //binary_search_insert_sort();
    //bubble_sort();
    //select_sort();
    //shell_sort();
    //quick_sort(0,n-1);
    //heap_sort();
    //merge_sort(0,n-1);
    bucket_sort();
    for(int i=0;i<n;i++){
        cout << q[i] << " ";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173