---

冒泡排序

思想：把任意两个相邻的大小相反的位置交换、最多进行N趟、

复杂度O(n^2)

#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
  
const int maxn = 1005;  
int a[maxn];  
  
int main() {  
    int n;  
    scanf("%d", &n);  
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);  
    for (int i = 1; i <= n; i++) {  
        for (int j = 1; j < n ;j++) {  
            if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);  
        }  
    }  
    for (int i = 1; i <= n; i++) {  
        printf("%d ", a[i]);  
    }  
    printf("\n");  
    return 0;  
}

 

选择排序

思想：每次从序列中选择最大/小的元素、适用于只求前K大的顺序、

复杂度O(K*n)

#include <cstdio>
#include <cstdlib>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
#define inf 1<<31
  
const int maxn = 1005;  
int a[maxn];  
  
int main() {  
    int n;  
    scanf("%d", &n);  
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);  
    for (int i = 1; i <= n; i++) {  
        int maxx = -inf;
        for (int j = i; j <= n ;j++) {  
            if (a[j] > maxx) {
                swap(a[i], a[j]);  
                maxx = a[j];
            }
        }  
    }  
    for (int i = 1; i <= n; i++) {  
        printf("%d ", a[i]);  
    }  
    printf("\n");  
    return 0;  
}  

 

插入排序

1、直接插入排序

思想：插入排序将数分为两部分、一部分为已经排好序的、一部分是待排序的、将待排序的数一个个插入已经排好序的序的数列中、最开始所有数都是待排序的、

复杂度：O(n^2)

2、折半插入排序

思想：其实是在直接插入排序的时候用二分查找来找、但实际上时间复杂度没有什么优化、所以不给出代码、

复杂度：O(n^2)

3、希尔排序

思想：一个挺有趣的分组插入算法、利用希尔增量来限制步长、初始时取步长为总数的一半、每次步长减半、直至减为1、复杂度O(n^2/3)

或许大家看到插入排序的复杂度和冒泡排序时间复杂度一样、觉得并没有什么卵用、可是你错了、

插入排序真正的亮点在于：

插入排序在对几乎已经排好序的数据操作时、效率高、即可以达到线性排序的效率

而插入排序的缺点是：

但插入排序一般来说是低效的、因为插入排序每次只能将数据移动一位

所以利用希尔排序改进了插入排序的缺点、缩小增量法避免了插排的大量元素位移的情况、

下面给出希尔排序的代码

#include <cstdio>
#include <cstdlib>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
#define inf 1<<31
  
const int maxn = 1005;  
int a[maxn];  
  
int main() {  
    int n;  
    scanf("%d", &n);  
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);  
    for (int div = n/2; div >= 1; div /= 2) {
        for (int i = div + 1; i <= n; i++) {  
            for (int j = i; a[j] < a[j - div] && j >= 1; j -= div) {  
                swap(a[j], a[j-div]);  
            }  
        }  
    }
    for (int i = 1; i <= n; i++) {  
        printf("%d ", a[i]);  
    }  
    printf("\n");  
    return 0;  
}  

 

堆排序

思想：堆排序比较复杂、感觉不是一两句话就能让别人明白、首先要理解什么堆、

建立堆、然后每次取堆的首部、有点类似选择排序、不过因为堆自身结构的性质、每次只需取堆的首部元素、

调整堆、将堆中最后一个元素调整到堆的首部、然后再对堆进行大小调整、剩余元素最后又形成一个合法堆、

下面给出二叉堆排序代码实现

#include <cstdio>
#include <cstdlib>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
#define inf 1<<31
  
const int maxn = 1005;  
int a[maxn];  

void HeapAdjust(int *a, int i, int n) {
    int lc = i << 1;
    int rc = (i << 1) + 1;
    int max = i;
    if (i > n / 2) return;
    if (lc <= n && a[lc] < a[max]) max = lc;
    if (rc <= n && a[rc] < a[max]) max = rc;
    if(max != i) {
        swap(a[i], a[max]);
        HeapAdjust(a, max, n);
    }
}

void BuildHeap(int *a, int n) {
    for (int i = n / 2; i >= 1; i--) {
        HeapAdjust(a, i, n);
    }
}

void HeapSort(int *a, int n) {
    BuildHeap(a, n);
    for (int i = n; i >= 1; i--) {
        swap(a[1], a[i]);
        HeapAdjust(a, 1, i - 1);
    }
}
  
int main() {  
    int n;  
    scanf("%d", &n);  
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);  
    HeapSort(a, n);
    for (int i = 1; i <= n; i++) {
        printf("%d ", a[i]);  
    }  
    printf("\n");  
    return 0;  
}  

 

快速排序

思想：快速排序主要是分治的思想、选取一个基准数、然后将数与基准数的大小比较划分为两边递归下去、

快速排序的复杂度与基准数的选取有关、最好情况为O(nlogn)、最坏情况为O(n^2)、平均复杂度为O(nlogn)

由于随机情况下快排复杂度期望是O(nlogn)、且常系数比较小、所以一般排序都使用快排来提高排序效率、

代码实现如下

#include <cstdio>
#include <cstdlib>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
#define inf 1<<31
  
const int maxn = 1005;  
int a[maxn];  

void Quick_Sort(int l, int r) {
    if(l >= r) return;
    int i = l;
    int j = r;
    int x = a[l];
    while (i < j) {
        while (i < j && a[j] >= x) j--;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] < x) i++;
        if (i < j) a[j--] = a[i];
    }
    a[i] = x;
    Quick_Sort(l, i - 1);
    Quick_Sort(i + 1, r);
}
  
int main() {  
    int n;  
    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]);  
    }  
    printf("\n");  
    return 0;  
}  

 

线性时间排序

在一般情况排序的最好的复杂度就是快排了、O(nlogn)已经是一种极限、

然而、上面介绍的算法属于通用型的、在某些情况、我们需要突破自己被禁锢已经的思维、

1、计数排序

思想：如果输入的n个数都比较小、最大的一个数为k、那么我们直接统计从1到k、每个数出现的次数就行、

#include <cstdio>
#include <cstdlib>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
#define inf 1<<31
  
const int maxn = 1005;  
int a[maxn];
int num[maxn];
  
int main() {  
    int n;  
    scanf("%d", &n);  
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);  
        num[a[i]]++;
    }
    for (int i = 0; i < maxn; i++) {
        while(num[i]--) printf("%d ", i);  
    }  
    printf("\n");  
    return 0;  
}  

 

2、基数排序

思想：基数排序其实就是按位排序、实现时用分桶的方法、可以从低位到高位、也可以从高位到低位、

#include <cstdio>
#include <cstdlib>  
#include <cstring>
#include <cmath>
#include <vector>  
#include <algorithm>  
using namespace std;  
#define inf 1<<31
  
const int maxn = 1005;  
int a[maxn];

void Radix_Sort(int n, int k) {
    vector<int> v[10];
    int radix = pow(10, k);
    int flag = 1;
    for (int i = 1; i <= n; i++) {
        if (a[i] >= radix) flag = 0;
        int w = (a[i] % radix) / (radix / 10);
        v[w].push_back(a[i]);
    }
    int cnt = 1;
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < v[i].size(); j++) {
            a[cnt++] = v[i][j];
        }
    }
    if (flag) return;
    Radix_Sort(n, k + 1);
}

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

 

3、桶排序

思想：桶排序其实是计数排序的一种改进、如果数据都集中在某一段区间内、这时将这段区间分桶、然后排序、最后合并、有点空间换时间的感觉、

桶排序根据实际情况变化较大、所以不给出代码、