当前位置：首页 > news >正文

排序（1）

news 来源：原创 2025/9/6 12:28:33

排序（1）

日常生活中，有很多场景都会用到排序。比如你买东西，在购物软件就有几种展现方式，按照评论数量给你排序出来，让你选，还是说按照价钱高低排序出来让你选。

排序其实是一种为了更好解决问题的手段，就像你想问题，思绪混乱的时候，是不是得捋一捋，这捋一捋就是排序。排序在我看来主要作用就是：为了让一个看起来比较混乱的问题变成一个相对明晰的问题，去我们更好的解决问题。

那么排序方式多种多样，那么我们就要去学习各种各样的排序，去帮助我们在不同问题，不同情境下选择一个合适的排序。
在这里插入图片描述

冒泡排序

算法原理

冒泡排序的核心原理是通过相邻元素的比较和交换，使较大（或较小）的元素逐渐 “浮” 到数列的一端。具体步骤如下：

比较相邻元素：从数列的第一个元素开始，将相邻的两个元素进行比较。
交换元素位置：如果顺序错误（如升序排列时前一个元素比后一个大），则交换这两个元素的位置。
重复步骤 1 和 2：对数列中的每一对相邻元素重复上述比较和交换操作，直到最后一对。经过一轮比较和交换后，最大（或最小）的元素会被排到数列的末尾。
缩小比较范围：排除已经排好序的元素，对剩余未排序的元素重复上述步骤，直到整个数列都有序。

//冒泡排序
void BubbleSort(int *a,int n)
{for(int j=0;j<n;j++){int change=0;for(int i=1;i<n-j;i++){if(a[i-1]>a[i]){Swap(&a[i-1],&a[i]);change=1;}}if(change==0)break;}}

在这里插入图片描述

优缺点

优点：实现简单，代码容易理解，适用于小规模数据的排序。
缺点：时间复杂度较高，在处理大规模数据时效率较低。

直接插入排序

算法原理

直接插入排序的实现步骤如下：(就像斗地主的时候对牌进行排序，类似，就是拿后面的牌和前面的牌比大小，小的就往前面去，大的往后面去)

初始状态：把数组的第一个元素视为一个已排序的子序列，从第二个元素开始，将其作为待插入元素。
查找插入位置：将待插入元素与已排序子序列中的元素从后往前依次比较，找到合适的插入位置。
移动元素：若待插入元素小于已排序子序列中的某个元素，则将该元素及其后面的元素依次向后移动一位，为待插入元素腾出位置。
插入元素：把待插入元素放到合适的位置。
重复步骤 2 - 4：对数组中的每个元素重复上述操作，直到整个数组有序。

//直接插入排序
void InsertSort(int *a,int n)
{for(int i=0;i<n-1;i++){int end=i;int tmp=a[end+1];while(end>=0){if(a[end]>tmp){a[end+1]=a[end];}else{break;}end--;}a[end+1]=tmp;}
}

在这里插入图片描述

复杂度分析

时间复杂度：
- 最好情况：数组已经有序，此时每个元素只需要和前一个元素比较一次，不需要移动元素，时间复杂度为 (O(n))，其中 n 是数组的长度。
- 最坏情况：数组是逆序的，对于每个元素，都需要将其插入到已排序子序列的最前面，每次插入都需要移动已排序子序列中的所有元素，时间复杂度为 (O(n^2))。
- 平均情况：平均时间复杂度为 (O(n^2))。
空间复杂度：直接插入排序只需要常数级的额外空间，因此空间复杂度为 (O(1))。

在这里插入图片描述

希尔排序

主播个人的理解，对于希尔排序来说，其实就是直接排序，没那么多有的没的。这个东西，用的就是直接插入排序这个东西，但是呢，它厉害就厉害在，它把一次直接插入排序，换成若干次，哎呀我去，比直接插入排序效果好太多了。

这有点像啥，主播最近晾衣服，主播洗完烘干发现没完全干，就想着拿去外面晾晒。之前我都是直接洗完，然后用衣架把衣服穿好之后，一口气把衣服挂在杆子上量，你们应该知道，一堆衣服加上水，加上衣架的重量吧。

不过由于主播这里最近回南天，下暴雨，不敢晾衣服在外面，然后烘干。结果发现没完全干，我是用衣架穿好了一些衣服才发现的，觉得不行，得拿出去吹一吹，然后我就分次，本来一大堆的衣服一次性挂外面凉，现在我是分了3次挂出去，每次挂一些，诶，你还真别说，我觉得老轻松了。虽然是烘干水了，但是你收衣服一次性把所有衣服收完，之后一次性全部拿回放衣柜，也是很重的，你分几次来就会轻松一些。

这大概就是希尔排序，虽然不太恰当，但是意思就是这个意思。有点大任务分成小任务的意思。每次小任务都用的直接插入排序。

希尔排序呢，主要是把大任务分成小任务，没做完一次小任务，都离最终的结果进一点，每次一点，直到最后整合答案的时候，答案其实已经写好99%了，这就有点像你写数学题，最后一个：综上所诉……，就是这样。

//希尔排序
void ShellSort(int *a,int n)
{int gap=n;while(gap>1){gap=gap/3+1;for(int i=0;i<n-gap;i++){int end=i;int tmp=a[end+gap];while(end>=0){if(a[end]>tmp){a[end+gap]=a[end];end-=gap;}else{break;}}a[end+gap]=tmp;}}
}

在这里插入图片描述

结合以上所讲的，应该可以比较好的理解上面给出来的代码了。复杂度分析比较难，毕竟是数学问题了，而且还没有被解决，只是根据一些资料来看是O(N^1.3)。其实只要理解好直接插入排序，希尔排序并不难的。

选择排序

选择排序就很无脑了，选择排序就是遍历一遍数组找到一个最大值，放到数组后面，每次遍历都找到一个最大值。

比如4321，遍历一次变成3214，再遍历一次变成2134，直到1234 。不过这里可以做个优化，每次遍历把最小的也找到，如4321，遍历一次就是1324，再遍历一次就是1234了。

void SelectSort(int *a,int n)
{int begin = 0, end = n - 1;while (begin < end){// [begin, end]int mini = begin, maxi = begin;for (int i = begin+1; i <= end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}Swap(&a[begin], &a[mini]);// max如果被换走了，修正一下//如例子4321if (maxi == begin){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

大家用一个简单的例子套一下就明白了。

还有一个堆排序，这个我在讲二叉树（堆）的时候已经讲了，就不赘述了

整体的代码：

sort.h

#include <stdio.h>
#include<time.h>
#include<stdlib.h>
//打印数组
void PrintArray(int *a,int n);//交换函数
void Swap(int *x,int *y);//冒泡排序
void BubbleSort(int *a,int n);//直接插入排序
void InsertSort(int *a,int n);
//希尔排序
void ShellSort(int *a,int n);//选择排序
void SelectSort(int *a,int n);

sort.c

#include "sort.h"//打印数组
void PrintArray(int *a,int n)
{for(int i=0;i<n;i++){printf("%d ",a[i]);}printf("\n");
}
//交换函数
void Swap(int *x,int *y)
{int tmp=*x;*x=*y;*y=tmp;
}
//冒泡排序
void BubbleSort(int *a,int n)
{for(int j=0;j<n;j++){int change=0;for(int i=1;i<n-j;i++){if(a[i-1]>a[i]){Swap(&a[i-1],&a[i]);change=1;}}if(change==0)break;}}//直接插入排序
void InsertSort(int *a,int n)
{for(int i=0;i<n-1;i++){int end=i;int tmp=a[end+1];while(end>=0){if(a[end]>tmp){a[end+1]=a[end];}else{break;}end--;}a[end+1]=tmp;}
}//希尔排序
void ShellSort(int *a,int n)
{int gap=n;while(gap>1){gap=gap/3+1;for(int i=0;i<n-gap;i++){int end=i;int tmp=a[end+gap];while(end>=0){if(a[end]>tmp){a[end+gap]=a[end];end-=gap;}else{break;}}a[end+gap]=tmp;}}
}
//选择排序
void SelectSort(int *a,int n)
{int begin = 0, end = n - 1;while (begin < end){// [begin, end]int mini = begin, maxi = begin;for (int i = begin+1; i <= end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}Swap(&a[begin], &a[mini]);// max如果被换走了，修正一下if (maxi == begin){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

test.c

#include "sort.h"void TestBubbleSort()
{int a[]={8,9,6,1,3,2,5,7,10,4};BubbleSort(a,sizeof (a)/sizeof (int));PrintArray(a, sizeof(a)/ sizeof(int));
}
void TestInsertSort()
{int a[]={8,9,6,1,3,2,5,7,10,4};InsertSort(a,sizeof (a)/sizeof (int));PrintArray(a, sizeof(a)/ sizeof(int));
}
void TestShellSort()
{int a[]={8,9,6,1,3,2,5,7,10,4};int b[]={7,6,5,4,3,2,1};ShellSort(b,sizeof (b)/sizeof (int));PrintArray(b, sizeof(b)/ sizeof(int));
}
void TestSelectSort()
{int a[]={8,9,6,1,3,2,5,7,10,4};int b[]={7,6,5,4,3,2,1};SelectSort(a,sizeof (a)/sizeof (int));PrintArray(a, sizeof(a)/ sizeof(int));
}int main()
{//TestBubbleSort();//TestInsertSort();//TestShellSort();TestSelectSort();
}

还有一个测试代码，就是测试效率的，大家可以自己试试

#include "sort.h"void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);//int* a4 = (int*)malloc(sizeof(int) * N);//int* a5 = (int*)malloc(sizeof(int) * N);//int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = N-1; i >= 0; --i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];//a4[i] = a1[i];//a5[i] = a1[i];//a6[i] = a1[i];a7[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin7 = clock();BubbleSort(a7, N);int end7 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();//HeapSort(a4, N);int end4 = clock();int begin5 = clock();//QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();//MergeSort(a6, N);int end6 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("BubbleSort:%d\n", end7 - begin7);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);free(a1);free(a2);free(a3);//free(a4);//free(a5);//free(a6);free(a7);
}int main()
{//TestBubbleSort();//TestInsertSort();//TestShellSort();//TestSelectSort();TestOP();
}

在这里插入图片描述

这里运行效率结果，数字越大，说明时间越久，效率越低下。

排序（1）

冒泡排序

算法原理

优缺点

直接插入排序

算法原理

复杂度分析

希尔排序

选择排序

相关文章：