排序算法总结

Posted on | In ,

0 Offer(新的一天新的难过

1. 快速排序

思想：分治

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
/*
   快速排序
   思想：分治
   时间复杂度：最坏O(n^2), 一般O(nlogn)
*/

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+100;

int a[maxn],n, b[maxn];

void quick_sort(int l, int r)
{
    if(l>=r) return;
    int first=l, last=r, key=a[first];
    while(first<last)
    {
        while(first<last && a[last]>=key){
            --last;
        }
        a[first]=a[last];
        while(first<last && a[first]<=key){
            ++first;
        }
        a[last]=a[first];
    }
    a[first]=key;
    quick_sort(l, first-1);
    quick_sort(first+1, r);
}

int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)  scanf("%d", &a[i]);
    quick_sort(1, n);
    for(int i=1;i<=n;i++)  printf("%d ", a[i]);
    return 0;
}

2. 归并排序

思想：分治的思想。

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
/*
   归并排序
   思想：分治
   时间复杂度：O(nlogn)
*/

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+100;

int a[maxn],n, b[maxn];

void merge_sort(int l, int r)
{
    if(l==r) return;
    int mid=(l+r)/2;
    merge_sort(l, mid);
    merge_sort(mid+1, r);
    int st=l, ed=mid+1;
    int cnt=l-1;
    while(st<=mid && ed<=r){
        if(a[st]<=a[ed]){
            b[++cnt]=a[st];
            ++st;
        }
        else{
            b[++cnt]=a[ed];
            ++ed;
        }
    }
    while(st<=mid){  b[++cnt]=a[st];  ++st; }
    while(ed<=r){  b[++cnt]=a[ed]; ++ed;}
    for(int i=l;i<=r;i++)  a[i]=b[i];
}

int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)  scanf("%d", &a[i]);
    merge_sort(1, n);
    for(int i=1;i<=n;i++)  printf("%d ", a[i]);
    return 0;
}

3. 堆排序

思想：

1
2


4. 基数排序

思想：

1
2


5. 桶排序

思想：

1
2


6. 冒泡排序

思想：

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
/*
   冒泡排序
   思想：每次当次的 max 放到最后
   时间复杂度：O(n^2)
*/

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+100;

int a[maxn],n;

void mo()
{
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n-i;j++)
        {
            if(a[j]>a[j+1]){
                swap(a[j], a[j+1]);
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
    }
    mo();
    for(int i=1;i<=n;i++)
        printf("%d ", a[i]);
    return 0;
}

7. 选择排序

思想：不断找 min 从前往后放即可。

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
/*
   选择排序
   思想：不断找 min 从前往后放即可。
   时间复杂度：O(n^2)
*/

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+100;

int a[maxn],n;

void select()
{
    for(int i=1;i<=n;i++){
        int pos=i;
        for(int j=i+1;j<=n;j++)
        {
            if(a[j]<a[pos]){
                pos=j;
            }
        }
        swap(a[i], a[pos]);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
    }
    select();
    for(int i=1;i<=n;i++)
        printf("%d ", a[i]);
    return 0;
}

8. 插入排序

思想：不断找 min 从前往后放即可。

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
/*
   插入排序
   思想：不断找 min 从前往后放即可。
   时间复杂度：O(n^2)
*/

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+100;

int a[maxn],n;

void Insert()
{
    for(int i=1;i<=n-1;i++){
        int num=a[i+1];
        int pos=i;
        while(pos>=1 && num<a[pos]){
            a[pos+1]=a[pos];
            pos--;
        }
        a[pos+1]=num;
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
    }
    Insert();
    for(int i=1;i<=n;i++)
        printf("%d ", a[i]);
    return 0;
}

9. 希尔排序

思想：

1
2
3
4
5
6
7
```

---

#### 10. 计数排序
**思想：**
```c++