常见排序算法记录和理解

前言

博主是算法小白，刚刚接触数据结构和算法，只学了一些简单的算法，并且学的不是很透彻，想要通过写博客来抛砖引玉，分享一些我个人的见解和培养思维

常见排序分类

根据理解难度和效率分为三个档次：（仅代表博主自己的理解）

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

Medium：希尔排序、堆排序、外部排序

Hard：快速排序、归并排序、桶排序

Easy

（1）冒泡排序

核心思想：模仿水中的气泡一样一点一点浮起来的情景排序。通过比较相邻两个元素的大小来决定是否交换这两个元素，最终会把最值移到数组边界，每轮循环都遍历一遍，一步一步把最值排到未排序部分的边界，直到排好

博主自己的理解：最简单最适合小白的算法，博主上个学期刚接触编程时对这个算法也是一头雾水，自己敲了很久也没有学会，后来学了更难的算法再回头看就像小学生级别的算法

代码模板：

void sort(int arr[],int n)
{for(int i=0;i<n;i++){for(int j=0;j<n-i-1;j++){if(arr[j]<arr[j+1]){swap(arr[j],arr[j+1]);}}}
}

代码解释：

外层循环表示一共遍历n次，n是数组长度。内层循环表示每次遍历都只遍历未排序部分（因为每次内层循环都会把当前未排序部分的最值移到最右端），再比较相邻元素，如果前一个比后一个小，就把前一个挪到右边，这样逐步就可以实现降序排列了。

（2）选择排序

核心思想：通过比较当前位置元素与后续元素的大小来确定当前位置元素应该是哪一个。模拟一下就是：这个位置的人看着后边，比他牛逼的就标记一下，下一个比被标记的牛逼的再标记一下，一直看到最后一个人，然后与最后一个被标记的人换位置，一直持续到最后一个人

博主自己的理解：这个算法是博主超级小白期（没学过快排和STL里的sort的时候）最常用的排序算法，当时博主没有思考，只是无脑敲模板，然后就用这个笨重的排序算法做语法题

代码模板：

void sort(int arr[],int n)
{for(int i=0;i<n;i++){int min=i;for(int j=i+1;j<n;j++){if(arr[min]>arr[j]){min=j;}}if(min!=i){swap(arr[min],arr[i]);}}
}

代码解释：

外层循环是指每一个当前要考验后边的元素，用min当作标记，内层循环遍历完，如果标记已经离开，就和带着标记那个元素互换位置。内层循环的逻辑是遍历当前元素之后的每个元素，然后依次考验，最后标记上那个最小的。这样就可以实现升序了。

（3）插入排序

核心思想：每个元素都往前边已经排好的元素看，找一个适合自己的位置，然后站进去。类比一下就是：一条长队，站在最前边的是实力最强的，然后新来的人从最后一个（即最弱的）比较，比他牛逼就把他踹到后边去，然后再和下一个比，直到遇上比不过的大哥，就灰溜溜地站在大哥后边

博主自己的理解：这个排序算法上个学期的清朝课本上没写，专业的算法课也不会教这种时间复杂度很高的算法，这是博主昨天晚上在AI那里问的，才知道还有这种算法，就是更关注思想吧，反正也不会用

代码模板：

void sort(int arr[],int n)
{for(int i=1;i<n;i++){int key=arr[i];int j=i-1;while(j>=0&&arr[j]>key){arr[j+1]=arr[j];j--;}arr[j+1]=key;}
}

代码解释：

外层循环遍历从第二个元素到最后一个元素，因为第一个元素自成一个有序数组。设定一个标记变量存储这个要挑位置的元素，后续它的位置什么情况就不用管了，因为它已经被存上了。然后从它的前一个位置的元素开始比较，它的前边一定是已经排好的数组。内层循环的意思是如果这个元素没到最前边并且这个元素还没有遇到对手，那当前和它比较的元素就老老实实往后滚，给大哥留位置，然后它继续往前比较，一直到跑到最前边或者遇到打不过的。退出循环后就把这个位置占了

Medium

（1）希尔排序

核心思想：设定一个增量，相差相同增量的元素组成一个新的数组，然后对这个数组插入排序，然后逐渐减小增量，继续对新数组插入排序，直到数组中的每个元素自成一个数组，这个时候再来一次插入排序就排好了。

比插入排序快的原因：直接插入排序在安排一个元素最终位置时，往往要挪动大量的元素，而希尔排序分组的思想可以使元素移到最终位置时挪动的元素量较少；插入排序在处理基本有序的数组时效率能接近 O(n)

博主自己的理解：博主最初误解了希尔排序，认为分块指的是分成一个一个相邻的块，然后这些相邻的块内部比较。实际上分的块是一个间一个的块，这样可以使元素的跨度变大

代码模板：

void sort(int arr[],int n)
{for(int gap=n/2;gap>0;gap/=2){for(int i=gap;i<n;i++){int temp=arr[i];int j;for(j=i;j>=gap&&arr[j-gap]>temp;j-=gap){arr[j]=arr[j-gap];}arr[j]=temp;}}
}

代码解释：

最外层循环表示增量逐渐减小，刚开始是数组长度的一半，后来逐步减半，直到增量为1。中间层循环表示从分出来的数组的第二个元素开始比较（第一个元素是0-gap，第二个元素是gap-2*gap），然后一直遍历到数组末尾。设置一个临时变量用于存储当前要安排的元素，然后在组成的分块数组里自娱自乐，用插入排序的形式排序。

（2）堆排序

核心思想：用堆这一数据结构来实现排序，这个算法博主暂时没有理解透彻，后续更数据结构的时候再写。

（3）外部排序

核心思想：为了处理数据集非常大，很吃硬盘，栈空间一次存不下所有的数据的情况。需要把数据集拆成很多块，这些块分别导入硬盘里，然后分别排序，最后再用归并把这些分块排成一个完整的数组

博主自己的理解：这个算法在工程上可能用的比较多，但是算竞上用的并不是很多

代码模板：由于涉及到向硬盘导入数据，所有没有简单的代码实现

Hard

（1）快速排序

核心思想：在一个数组中确定一个标定元素，小于这个标定元素的放一边，大于这个标定元素的放一边。然后这两边再递归处理，继续设定标定元素排序，直到每个元素自成一个数组

博主自己的理解：这是博主第一个接触的比较难的算法，很明显，越难的算法越难理解，这个算法博主想了很久也没有吃透，只是可以简单使用

代码模板：

void sort(int arr[],int l,int r)
{if(l>=r){return;}int x=arr[(l+r)/2],i=l-1,j=r+1;while(i<j){do i++;while(arr[i]<x);do j--;while(arr[j]>x);if(i<j)swap(arr[i],arr[j]);}sort(arr,l,j);sort(arr,j+1,r);
}

代码解释：

如果传入的左边界已经和右边界贴上了，说明这个数组已经是单个元素了，就直接返回。设定标定元素，定义i为左边界，j为右边界。j没有贴到i之前一直执行循环：如果arr[i]这个元素满足小于标定元素这个条件就继续往右走，arr[j]这个元素满足大于标定元素这个条件就继续往左走。直到有不满足的情况，这样arr[i]和arr[j]就交换，继续移动。最后递归调用这个函数的左右两个部分

快排为什么快：利用分治思想，把复杂问题拆成许多小问题，然后减少问题的复杂度

（2）归并排序

核心思想：把一个数组分成两个部分，然后开一个新数组存被安排进去的新元素。依靠递归直到每个小数组只剩一个元素（一个元素就是有序状态），最后再把新元素里的元素存进原数组中，这样可以使两个有序数组归并。

博主自己的理解：这个思想非常巧妙也很常用。不同段不断地往新的靠，更小的就往进放。这个算法也是博主接触的比较早的难一些的算法。

代码模板：

int temp[100010];
void sort(int arr[],int l,int r)
{if(l>=r){return;}int mid=(l+r)/2;sort(arr,l,mid);sort(arr,mid+1,r);int k=0,i=l,j=mid+1;while(i<=mid&&j<=r){if(arr[i]<=arr[j]){temp[k++]=arr[i++];}else{temp[k++]=arr[j++];}}while(i<=mid){temp[k++]=arr[i++];	}while(j<=r){temp[k++]=arr[j++];}for(int i=l,j=0;i<=r;i++,j++){arr[i]=temp[j];}
}

代码解释：

先开一个临时数组，如果左边界和右边界贴上，就返回。定义一个中间位置，然后递归调用左半部分和右半部分。设定一个变量存储临时数组的下标，从数组左右两个部分分别开始遍历，取他们两个中较小的一个存进临时数组中。最后如果有一个部分遍历到最后一个位置，就退出循环，把另一个部分的所有元素都存进临时数组中。然后再把临时数组中的元素存进原数组中。

（3）桶排序

核心思想：根据数组元素的分布创造有限个桶来存储元素，对每个桶中的元素分别排序，然后再把这些桶里的元素取出合并

博主自己的理解：这个算法博主也是昨天晚上第一次接触，感觉和外部排序的思想差不多，而且代码量巨大，优势也并不明显，所以博主只想参考思想

代码模板：

void bucketSort(int arr[], int n) {if (n <= 0) return;// 找出数组中的最大值和最小值int min_val = arr[0];int max_val = arr[0];for (int i = 1; i < n; ++i) {if (arr[i] < min_val) {min_val = arr[i];}if (arr[i] > max_val) {max_val = arr[i];}}// 计算桶的数量int bucket_count = n;std::vector<std::vector<int>> buckets(bucket_count);// 计算每个桶的范围int range = (max_val - min_val) / bucket_count + 1;// 将元素分配到各个桶中for (int i = 0; i < n; ++i) {int bucket_index = (arr[i] - min_val) / range;buckets[bucket_index].push_back(arr[i]);}// 对每个桶内的元素进行排序for (int i = 0; i < bucket_count; ++i) {std::sort(buckets[i].begin(), buckets[i].end());}// 合并所有桶中的元素int index = 0;for (int i = 0; i < bucket_count; ++i) {for (int j = 0; j < buckets[i].size(); ++j) {arr[index++] = buckets[i][j];}}

代码解释：这个代码博主也没看懂