排序算法

本文最后更新于 2024年9月18日 凌晨

Warning

此处不对排序的空间和时间复杂度进行分析，关注排序原理和代码实现。

排序算法

冒泡排序、选择排序、插入排序

这几种排序是较为基础且容易理解的所以就直接放代码了。

冒泡排序

代码如下： 

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
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
int a[1000001];
void random(int n);//随机数
void bubble_sort(int q);
int main()
{
    printf("参与排序的随机数个数：");
    int n;
    scanf("%d", &n);
    random(n);
    double start, finish;
    start = (double)clock();
    bubble_sort(n);
    for (int i = 1; i <= n; i++)printf("%d ", a[i]);
    finish = (double)clock();
    printf("%lf ms", finish - start);//运行时间
    return 0;
}
void bubble_sort(int q)
{
    for (int i = 1; i < q; i++) {
        for (int j = q - 1; j >= i; j--) {
            if (a[j + 1] < a[j]) {
                int tmp = a[j + 1]; a[j + 1] = a[j]; a[j] = tmp;
            }
        }
    }
}
void random(int n)
{
    for (int i = 1; i <= n; i++) {
        srand(i);
        a[i] = rand() % 100;
    }
}

选择排序

代码如下： 

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
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
int a[1000001];
void random(int n);//随机数
void selection_sort(int q);
int main()
{
    printf("参与排序的随机数个数：");
    int n;
    scanf("%d", &n);
    random(n);
    double start, finish;
    start = (double)clock();
    selection_sort(n);
    for (int i = 1; i <= n; i++)printf("%d ", a[i]);
    finish = (double)clock();
    printf("%lf ms", finish - start);//运行时间
    return 0;
}
void selection_sort(int q)
{
    for (int i = 1; i < q; i++) {
        int k = i;
        for (int j = i + 1; j <= q; j++) {
            if (a[k] > a[j]) {
                k = j;
            }
        }
        if (k != i) {
            int tmp = a[k]; a[k] = a[i]; a[i] = tmp;
        }
    }
}
void random(int n)
{
    for (int i = 1; i <= n; i++) {
        srand(i);
        a[i] = rand() % 100;
    }
}

插入排序

代码如下： 

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
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
int a[1000001];
void random(int n);//随机数
void insertion_sort(int q);
int main()
{
    printf("参与排序的随机数个数：");
    int n;
    scanf("%d", &n);
    double start, finish;
    start = (double)clock();
    random(n);
    insertion_sort(n);
    for (int i = 1; i <= n; i++)printf("%d ", a[i]);
	    finish = (double)clock();
	    printf("%lf ms", finish - start);//运行时间
    return 0;
}
void insertion_sort(int q)
{
    for (int i = 2; i <= q; i++) {
        for (int j = i - 1; j >= 1; j--) {
            if (a[j] <= a[i]) {
                int tmp = a[i];//插入
                for (int k = i - 1; k > j; k--) {
                    a[k + 1] = a[k];
                }
                a[j + 1] = tmp;
            }
        }
    }
}
void random(int n)
{
    for (int i = 1; i <= n; i++) {
        srand(i);
        a[i] = rand() % 100;
    }
}

桶排序

原理：对于确定范围的若干个数排序，先放上包括所有数据范围的桶，把数据放到对应编号的桶中，输出按照桶的编号从小到大输出。

假设数据范围为0~8：

数据

将数据全部放入桶中：

桶排序

结果：

结果

代码如下： 

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
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
void random(int n);//随机数
int a[10000004], b[10000004];
int main()
{
    printf("参与排序的随机数个数：");
    int n;
    scanf("%d", &n);
    double start, finish;
    start = (double)clock();
    random(n);
    for (int i = 1; i <= n; i++)b[a[i]]++;
    for (int i = 1; i <= 10000003; i++) {
        while (b[i] != 0) {
            printf("%d ", i);
            b[i]--;
        }
    }
    finish = (double)clock();
    printf("%lf ms", finish - start);//运行时间
    return 0;
}
void random(int n)
{
    for (int i = 1; i <= n; i++) {
        a[i] = rand() % 10000000;
    }
}
## 基数排序

原理：对于组数，按照位数从右向左对每个数进行排序。由于单个数字只有0~9故使用桶排序来提高效率。

假设有如下数据：

原数据

第一次操作：

第一次操作

第二次操作：

第二次操作

\[ \dots \] 最后的结果：

结果

代码如下：

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
#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>
#include <time.h>
int p[10000004],q[10000003];
void random(int n)
{
    for (int i = 1; i <= n; i++) {
        srand(i);
        p[i-1] = rand() % 100;
    }
}
int main()
{
    int n;
    printf("参与排序的个数：");
    scanf("%d", &n);
    random(n);
    double start, finish;
    start = (double)clock();
    //动态分配内存   
    int max = p[0], d = 1;
    for (int i = 1; i <= n; i++) {
        if (p[i - 1] > max)max = p[i - 1];
    }//求最大值  
    while (max > 0) {
        d++;
        max /= 10;
    }//求最大位数  
    int radx = 1;
    for (int i = 1; i < d; i++) {
        int a[11] = { 0 };//初始化，桶排序 
        for (int t = 0; t < n; t++) {
            a[p[t] / radx % 10+1]++;//记录个数
        }
        //标序 
        for (int t = 1; t < 10; t++) {
            a[t] = a[t] + a[t - 1];//记录开始的位置
        }
        //排序
        for (int j = 0; j < n; j++) {
            int k = (p[j] / radx) % 10;
            q[a[k]] = p[j];
            a[k]++;
        }
        //复制 
        for (int j = 0; j < n; j++) {
            p[j] = q[j];
        }
        radx *= 10;
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", p[i]);
    }
    finish = (double)clock();
    printf("%lf ms", finish - start);//运行时间
    return 0;
}

由于内存占用大，关键字值域小时可以采用

快速排序

单次操作：选择一个参照的数据（一般是第一个数），下标 i , j 分别从数组的头和尾开始，i , j 相向遍历，当下标 i 所指的数大于参照数据，下标 j 所指的数据小于参照数据时，两个数据相互换位置。 并且当i=j时，参照数据位置和 i/j 指向的数据交换位置，结束本次操作。

单次结果：参照数据被排在正确的位置，将原数组分为左右两个区间。

整体：通过递归使各个数据归位，完成排序。

这里提供作者 大卫·加勒斯 的quick sort动态图地址。

代码如下：

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
#include<stdio.h>  
void quicksort(int head,int tail,int* p);  
int main()  
{  
    int n,a[1000];  
    scanf("%d",&n);  
    for(int i=0;i<n;i++){  
        scanf("%d",&a[i]);  
    }  
    quicksort(0,n-1,a);  
    for(int i=0;i<n;i++){  
        printf("%d ",a[i]);  
    }  
    return 0;  
}  
void quicksort(int head,int tail,int*p)  
{  
    int i=head,j=tail;  
    int tmp=p[head];  
    if(i>j){  
        return;//函数递归结束  
    }  
    while(i!=j){  
        while(p[j]>=tmp&&j>i){  
            j--;  
        }  
        while(p[i]<=tmp&&j>i){  
            i++;  
        }  
        if(j>i){  
            int temp=p[j];p[j]=p[i];p[i]=temp;  
        }  
    }  
    p[head]=p[i];p[i]=tmp;  
    quicksort(head,i-1,p); //左区间递归 
    quicksort(i+1,tail,p);  //右区间递归
    return;  
}

同时c语言中也提供qsort()函数，在<stdlib.h>中，使用方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdlib.h>  
#include<stdio.h>  
int cmp(void* p1,void*p2);  
//如果compar返回值< 0，那么p1所指向元素会被排在p2所指向元素的前面  
//如果compar返回值= 0，那么p1所指向元素与p2所指向元素的顺序不确定  
//如果compar返回值> 0，那么p1所指向元素会被排在p2所指向元素的后面  
int main()  
{  
    int a[10]={5,9,56,356,36,6356};  
    qsort(a,10,sizeof(int),cmp);
    //参数（第一个元素的指针，元素个数，元素大小，函数指针）  
    for(int i=0;i<10;i++){  
        printf("%d ",a[i]);  
    }  
}  
int cmp(void*p1,void*p2)  
{  
    //因为比较的是数字所以是强制转化为(int*)  
    return(*(int*)p1-*(int*)p2);  
}//如果文件后缀名为cpp将函数声明中的void改为const void

归并排序

合并数组：取两组中 最小/最大 的数进行比较，并依照大小先后放入结果数组。

实现：对于一个无序数组a[N] \[ a[1],a[2],a[3] \dots a[N] \] 第一次：先处理 a[1],a[2] 形成一个有序数组 a[1-2] ，再处理 a[3],a[4] 形成一个有序数组 a[3-4] ，将 a[1-2] 和 a[3-4] 合并为 a[1-4] \[ a[1-2],a[3-4],a[5] \dots a[N] \] \[ a[1-4],a[5],a[6] \dots a[N] \] 第二次：同样的方法将 a[5] , a[6] , a[7] , a[8] 处理为有序数组 a[5-8] ,将 a[1-4] 和 a[5-8] 合并为 a[1-8] \[ a[1-4],a[5-8],a[9] \dots a[N] \] \[ a[1-8],a[9],a[10] \dots a[N] \] 第三次：同样的方法将 a[9] , a[10] , a[11] , a[12] , a[13] , a[14] , a[15] , a[16] 处理为有序数组 a[9-16] ,将 a[1-8] 和 a[9-16]合并为 a[1-16] \[ a[1-8],a[9-16],a[17] \dots a[N] \] \[ a[1-16],a[17],a[18] \dots a[N] \] \[ \dots \] 最后结果得到一个有序的数组。

这里提供作者 大卫·加勒斯 的merge sort动态图地址

(合并数组)代码如下：

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
#include<stdio.h>  
void merge(int n,int*a,int m,int*b,int*c);  
int main()  
{  
    int n,m;  
    int a[100],b[100],c[200];//c数组为结果数组  
    //数组1
    scanf("%d",&n);  
    for(int i=0;i<n;i++){  
        scanf("%d",&a[i]);  
    }  
    //数组2
    scanf("%d",&m);  
    for(int i=0;i<m;i++){  
        scanf("%d",&b[i]);  
    }  
    merge(n,a,m,b,c);  //函数实现
    for(int i=0;i<n+m;i++){  
        printf("%d ",c[i]);  
    }  
}  
void merge(int n,int *a,int m,int *b,int *c)  
{  
    int i=0,j=0,index=0;  
    while(i<n&&j<m){  
        if(a[i]<b[j]){  
            c[index]=a[i];  
            i++;  
        }  
        else{  
            c[index]=b[j];  
            j++;  
        }  
        index++;  
    }  
    if(i==n){  
        for(;j<m;j++){  
            c[index]=b[j];  
            index++;  
        }  
    }  
    else{  
        for(;i<n;i++){  
            c[index]=a[i];  
            index++;  
        }  
    }  
}

归并排序完整代码如下：

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
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
int arr[10000001];
void random(int n)
{
	for (int i = 0; i < n; i++) {
		srand(i);
		arr[i] = rand() % 10000;
	}
}
void Merge(int arr[], int tmp[], int start, int mid, int end)//合并操作
{
	int i = start;//i为左小组的第一个元素位置
	int j = mid + 1;//j为右小组的第一个元素位置
	int k = start;//tmp数组当前的起始位置
	while (i < mid + 1 && j < end + 1)//左小组越界或右小组越界才能退出
	{
		if (arr[i] <= arr[j])
		{
			tmp[k++] = arr[i++];
		}
		else
		{
			tmp[k++] = arr[j++];
		}
	}
	while (j < end + 1)//如果右边小组没有越界
	{
		tmp[k++] = arr[j++];
	}
	while (i < mid + 1)//如果左边小组没有越界
	{
		tmp[k++] = arr[i++];
	}
	for (i = start; i <= end; i++)
	{
		arr[i] = tmp[i];
	}
}
void MergeS(int arr[], int tmp[], int start, int end)
{
	if (start < end)
	{
		int mid = (start + end) / 2;
		//通过递归实现算法
		MergeS(arr, tmp, start, mid);
		MergeS(arr, tmp, mid + 1, end);
		Merge(arr, tmp, start, mid, end);
	}
}
void MergeSort(int arr[], int len)
{
	//开了一个排序后结果保存的临时数组
	int* tmp = (int*)malloc(sizeof(int) * len);
	MergeS(arr, tmp, 0, len - 1);
	free(tmp);
}
int main()
{
	printf("参与排序的个数：");
	int n;
	scanf("%d", &n);
	random(n);
	double start, finish;
	start = (double)clock();
	MergeSort(arr, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d  ", arr[i]);
	}
	printf("\n");
	finish = (double)clock();
	printf("%lf ms", finish - start);//运行时间
	return 0;
}

堆排序

这种排序可以看作是一种选择排序的优化.。

实现：首先要形成树，这里从最低的根部逐个向上对树进行生成。第一次维护后的树只能保证树的根为最大的数，因此将最大的数转移到树维护范围的最后一个数据（最后一个数的正确位置），并且将此时的最后一个数据移出树的维护范围，一直到将所有数都放到正确的位置，达到排序的效果。

假设数据如图：

原数据

第一次操作（生成树）:

第一次操作

第二次操作：

第二次操作

\[ \dots \]

最后结果：

结果

代码如下：

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
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int arr[100000006];
void random(int n)
{
    for (int i = 1; i <= n; i++) {
        arr[i - 1] = rand() % 10000000;
    }
}
void weihu(int* arr, int start, int end);
void dui(int* arr, int len);
int main()
{
    
    int n;
    printf("参与排序的个数：");
    scanf("%d", &n);
    random(n);
    double start, finish;
    start = (double)clock();
    dui(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    finish = (double)clock();
    printf("%lf ms", finish - start);//运行时间
    return 0;
}
void weihu(int* arr, int start, int end)
{
    int tmp = arr[start];
    for (int i = start*2+1; i <= end; i = i * 2 + 1) {//向左侧延申的树,从上往下维护  
        if (i < end && arr[i] < arr[i + 1]) {
            i++;//i标记为左右孩子的最大值  
        }
        if (arr[i] > tmp) {//tmp没有变，维护的是增加的顶部数字和右侧数字  
            arr[start] = arr[i];
            start = i;
        }
        else {
            break;//如果一个有序后面的都是有序的  
        }
    }
    arr[start] = tmp;//填回数字  
}
void dui(int* arr, int len)
{
    //从下往上形成树
    for (int i = len / 2 - 1; i >= 0; i--) {//维护的结点都是下面有孩子的数据  
        weihu(arr, i, len - 1);
    }
    int tmp;
    for (int i = 0; i < len - 1; i++) {
        tmp = arr[0];
        arr[0] = arr[len - 1 - i];
        arr[len - 1 - i] = tmp;
        weihu(arr, 0, len - 1 - i - 1);//变化后维护（最后一个数据不维护）  
    }
}

希尔排序

这种排序可以看作是插入排序的优化。

那为什么说希尔排序是针对插入排序的一种优化呢？ 我们都知道，插入排序在两种情况下工作量最小

  1. 在大多数元素基本有序的情况下。
    元素基本有序的话，元素之间也就不需要频繁地交换，工作量自然减少

  2. 在元素数量比较少的情况下。
    元素数量n变小，时间复杂度O(n^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
#include<stdio.h>  
void xiersort(int*arr,int length);  
int main()  
{  
    int arr[100];  
    int n;  
    scanf("%d",&n);  
    for(int i=0;i<n;i++){  
        scanf("%d",&arr[i]);  
    }  
    xiersort(arr,n);  
    for(int i=0;i<n;i++){  
        printf("%d ",arr[i]);  
    }  
    return 0;  
}  
void xiersort(int*arr,int length) {  
   int h = 1;  
    while (h < length / 3) { //此处的'3'是可改变的 
        h = 3 * h + 1;//为了最后“h/3”的值等于1  
    }  
    while (h >= 1){  //从尾部开始，前方的元素依此插入
        for(int i=h;i<length;i++){
	        //对相互间隔h个数的数组进行插入排序  
            for(int j=i;j>=h && arr[j]<arr[j-h];j-=h){
                int temp=arr[j];arr[j]=arr[j-h];arr[j-h]=temp;  
            }  
        }  
        h=h/3;  
    }  
}
计算机 > C语言
#算法学习
排序算法
http://example.com/posts/排序算法/
作者
晓寒
发布于
2022年11月12日
许可协议