初学者能学会的数据结构与算法|初阶数据结构与算法——经典八大排序算法||初步学习至熟练掌握(附动图演示，初学者也能看懂) 算法|排序算法|数据结构

你还在数据结构的苦海中挣扎吗？
你难道还在抱着一本厚厚的数据结构书在那里硬啃吗？
你难道还是对于数据结构一无所措吗？
别急，因为~~~
在未来的几个月里，我会为大家推出精品的数据结构文章。涵盖广、内容深。
如果你能够静下心来，看了我的文章以后，你会发现，课本就是一本小说。
我在未来还会给大家推出视频，用视频的方式讲解。
想要了解我的视频，以及我的文章，那就持续关注我，订阅专栏《完全自学数据结构与算法和C++》吧
给个关注吧，蟹蟹各位啦~~~

目录
一、冒泡排序（Bubble_sort）
1、文字表述版：
2、动画演示版：
3、代码实现版本：
复杂度分析：
适用情况：
二、选择排序（select_sort）
1、文字表述版：
2、动画演示版：
3、代码实现版：
复杂度分析：
适用场景：
三、插入排序（insert_sort）
1、文字表述版：
2、动画演示版：
?
3、代码实现版：
时间复杂度：
适用情况：
四、希尔排序（shell_sort）
1、文字表述版：
2、动图演示版：
3、代码实现版：
时间复杂度：
适用情况：
五、堆排序（Heap_sort）
时间复杂度：
适用场景：
六、快速排序（quick_sort）
文字表述版：
动图演示版：
代码实现版：
时间复杂度：
适用场景：
七、归并排序（Merge_sort）
文字表述版：
动图演示版：
代码实现版：
时空复杂度分析：
适用场景

八、计数排序（count_sort）
文字描述版：
动图展示版：
代码实现版：
时空复杂度：
说明

排序算法汇总：
对于一个数组，比如

int a[] = {0,2,3,6,4,1,2,3,45,20,16,45};

随便给的哈，我们让其排成有序，我们有下面这8大方法，换句话说，这8种方法都是用来排序用的

一、冒泡排序（Bubble_sort）总体表述：重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法分析：
1、文字表述版：以排升序为例，设一个数组中有n个元素：

（1）将相邻的元素两两比较，如果左边的元素比右边的元素要小，就交换位置。
（2）依次从左向右两两比较，直至到数组末尾（或者到已经固定位置的元素）。
（3）重复过程（1）（2）n次。

2、动画演示版：

初学者能学会的数据结构与算法|初阶数据结构与算法——经典八大排序算法||初步学习至熟练掌握(附动图演示，初学者也能看懂)

文章图片

3、代码实现版本：

void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void Bubble_sort(int* a, int n) { for (int end = n; end; --end) { int exchange = 0; for (int i = 0; i < end; i++) { if (a[i] < a[i + 1]) { swap(&a[i], &a[i + 1]); exchange= 1; } } if (exchange == 0) { break; } } }

笔者认为，这个算法没有什么好说的。就这样呗。

复杂度分析：我们可以看到，如果按照其最坏的情况，其复杂度为O(N^2)，即使我们已经优化(从上面可以看出，我们在内层的循环中做了两次优化，第一次是第二个for循环随着外层循环的进行，其循环次数在减少；第二次是我们用来exchange，如果没有一次交换那就直接跳出来)，但是其复杂度还是好高。

适用情况：数据元素的个数比较少，对算法的时间限制不是太高时可以考虑使用。它的最大的特点，是思路简单。

二、选择排序（select_sort）综述：一种简单直观的排序算法。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
1、文字表述版：

（1）遍历一遍，找出最小的和最大的，放在两侧；
（2）除去（1）中交换过的元素，重复（1）过程，最多重复n/2次。

2、动画演示版：

文章图片

（注：该动画演示的每次遍历只找出了最小值，我们实际为了可以少遍历几遍数组，一般会同时找出最大的和最小的数，然后交换）

3、代码实现版：

void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } //选择排序 void SelectSort(int* a, int n) { int left = 0, right = n - 1; //给出最左边和最右边的下标， while (left <= right) { int minIndex = left, maxIndex = right; //我们暂且认为它们一边是最小的，一边是最大的for (int i = left; i <= right; i++) { if (a[i] < a[minIndex])//如果a[i]比最小的还要小 { minIndex = i; //则最小元素的下标给到i } if (a[i] > a[maxIndex]) //同理，如果a[i]比最大的还要大 { maxIndex = i; //则最大的元素下标给到i } } swap(&a[left], &a[minIndex]); //交换左值和最小的值 if (left == maxIndex)//分类讨论，如果最大的值刚刚好就是最左边的值， {//由于刚刚我们已经将最小的值换了过来，所以最大的值就 //跑到别处去了 maxIndex = minIndex; //由于刚刚是和minIndex交换的，所以现在最大的值在 //minIndex处 } swap(&a[right], &a[maxIndex]); //再交换最右边位置和maxIndex（也就是最大值）的位置 ++left; --right; //左右两边的值就不计入下一次循环的考虑范围内了 } }

复杂度分析：实际上，选择排序和冒泡排序一样，用的很少。因为它的时间复杂度O(N^2)，效率太低了（即便我们做了一次遍历找两个值的优化。但也是改变不了其效率低的事实）

适用场景：对于选择排序来说，它的地位是和冒泡排序差不多的。当元素个数少，并且接近有序的时候，我们优先选用选择排序，而不用冒泡排序。

三、插入排序（insert_sort） 1、文字表述版：

(1)想象两个集合，或者说两个区域，一个是已排区，一个是未排区。
(2)从未排区向已排区一个一个拿元素。
(3)与此同时，从左向右依次寻找，插入到合适的位置。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
2、动画演示版：

文章图片

3、代码实现版：

void insertsort(int arr[], const int len) { // 外循环表示遍历所有元素 for (int i = 0; i < len; i++) { // 内循环表示折回寻找本元素合适的插入位置 // 保存当前的数据 int temp = arr[i]; int j = i; while (j > 0 && arr[j - 1] > temp) { // 如果data[j-1]的数据大于temp，说明第j个位置不是合适的位置 // 我们需要将data[j-1]的数据移动到data[j]的位置上，并访问下一个元素 arr[j] = arr[j - 1]; j--; } arr[j] = temp; //找到了合适的位置，然后赋值 } }

时间复杂度：插入排序的时间复杂度也是比较高的，考虑最坏的情况的话，也是O(N^2)
适用情况：其时间复杂度虽然说也是O(N^2)，但是比与冒泡和选择相比，不会显得那么蠢~~哈哈，但适用的情况还是比较少的。
因为我们在实际当中，与其使用插入排序，还不如使用希尔排序。

四、希尔排序（shell_sort）希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的数据个数越来越少，当增量减至1时，整个文件恰被分成一组，算法便终止。
1、文字表述版：

(1)对一个数组，先分成间隔相等的几组数据。
(2)对这几组数据进行分别插入排序。
(3)缩小间隔，重复(1)和(2)，直至间隔小于1停止。

也就是说，如果间隔为1，其就是插入排序。
2、动图演示版：

文章图片

（动图来源：五分钟学算法）
3、代码实现版：

void shellsort(int* a, int n)//希尔排序 {//n/3/3/3/3.../3 == 1 int gap = n; while (gap > 1) { //gap > 1的时候，预排序 //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 (tmp < a[end]) { a[end + gap] = a[end]; end -= gap; }//小范围的插入排序 else { break; } } a[end + gap] = tmp; } } }

时间复杂度：有人专门计算统计过，希尔排序的时间复杂度大概是O(N^1.3)左右。
适用情况：快排不适用的时候。（但是快排如果优化过后和它是差不多的）

五、堆排序（Heap_sort）有关堆排序的内容，我们昨天已经详细地介绍过了，今天我们就不罗嗦了。
我们把链接给在这里：数据结构与算法——第五节树和堆_jxwd的博客-CSDN博客

文章图片

在这个位置呦

文章图片

时间复杂度：我们之前说它的时间复杂度是O(N*logN)，原因是建堆要O(N)，然后还要调整，是O（logN），二者相乘，得到O(N*logN)
适用场景：堆排序比较和交换次数比快速排序多，所以平均而言比快速排序慢，

但有时候你要的不是“排序”，而是另外一些与排序相关的东西，比如topK，这时候堆排序的优势就出来了。在一个巨大的数据流里找到top K，快速排序是不合适的，堆排序更省地方。

另外一个适合用heap的场合是优先队列，需要在一组不停更新的数据中不停地找最大/小元素，快速排序也不合适。

六、快速排序（quick_sort）这个我们要来好好说一说。
快速排序是日常中用到的最多的一种排序方法。
总体来说，快速排序至少有三种以上的方法，但是今天，笔者就只详细介绍一种，其余两种给上代码和思路。
综述：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序
我们直接给上优化之后的思路：
文字表述版：（方法有很多，该方法仅供参考）

（1）从最左、最右、最中间三个位置取出中间值，然后和最左边的位置交换（即三数取中）
（2）选取最左边的数（因为选最左边的数方便，实际选哪里都可以）为基准，作为keyi。
（3）定义左指针和右指针，分别位于数组的两边，然后向中间走，直至相遇。（这叫左右指针法）（走的规则是：以排升序为例，右指针先走，右指针找比keyi值小的停下来，左指针再走，找到比keyi值大的停下来，左右指针指向的值交换，然后右指针再走，再找...直至相遇）
（4）交换keyi和相遇位置的值。
（5）以相遇位置作为分界线，将分界线左右两边看成是两个子序列，重复操作步骤(1)(2)(3)(4)(5)，直至不再有子序列产生。

可以看出，这又是一种递归的思路。
动图演示版：

文章图片

（注：该动图展示的是前后指针法，区别在于前后指针是两个指针同向而行，而左右指针法是两个指针从数组的左右两边相向而行，其他的都一样）
代码实现版：

int GEtmidIndex(int* a, int left, int right)//三数取中 { int mid = (left + right) >> 1; if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if(a[left] > a[right]) { return left; } else { return right; } } else { if (a[mid] > a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } } int PartSort(int* a, int begin, int end)//左右指针法 { //int midIndex = GEtmidIndex(a, begin, end); //swap(&a[begin], &a[midIndex]); int left = begin, right = end; //一趟 int keyi = left; while (left < right) { while (left < right && a[right] >= a[keyi])//右指针先走，右指针找小 { right--; } while (left < right && a[left] <= a[keyi])//左指针后走，左指针找大 { ++left; } swap(&a[left], &a[right]); } int meeti = left; return left; //返回分界点 }int PartSort1(int* a, int left, int right)//挖坑法 { int midIndex = GEtmidIndex(a, left, right); swap(&a[left], &a[midIndex]); int key = a[left]; while (left < right) { while(left = key) { right--; }//放在左边的坑位中 a[left] = a[right]; //找大 while (left < right && a[left] <= key) { left++; } a[right] = a[left]; //放到右边的坑位中，左边形成新的坑 } a[left] = key; return left; }int PartSort2(int* a, int left, int right)//前后指针法 { int midIndex = GEtmidIndex(a, left, right); swap(&a[left], &a[midIndex]); int cur = left + 1; int keyi = a[left]; int prev = left; while (cur <= right) { if (a[cur] <= keyi) { prev++; swap(&a[prev], &a[cur]); } cur++; } swap(&a[prev], &a[left]); return prev; }void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } int keyi = PartSort1(a, begin, end); //PartSort多少都可以。返回分界点的位置 QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); //递归调用 }

时间复杂度：快速排序的时间复杂度是O(NlogN）。
适用场景：快速排序是日常生活中使用频率最高的一种排序方法之一，它主要的特点就是快。
但是也有不足，当元素趋向于有序的时候，如果不进行优化，它的效率就没有希尔排序、堆排序高。同样，当解决top K问题的时候，还是优先选择堆排序。

七、归并排序（Merge_sort）和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
文字表述版：

（1）将数组拆分，分成各个小份（一般最后一组有1~3个元素，可以自己调）
（2）将拆分后的子数组进行排序。
（3）将子数组两两合并，并形成一个新的有序数组。
（4）重复（3），直至合并完全。

动图演示版：

文章图片

代码实现版：

void _MergeSort(int* a, int left, int right,int* temp) //内置调用，用于递归调用计算 { if (left >= right)//如果左边数右边数大，就直接返回 { return; } int mid = (left + right) >> 1; //取中间的数 _MergeSort(a, left, mid, temp); //拆分 _MergeSort(a, mid + 1, right, temp); //拆分 //两段有序，归并到temp; int begin1 = left , end1 = mid; int begin2 = mid + 1, end2 = right; int i = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { temp[i++] = a[begin1++]; } else { temp[i++] = a[begin2++]; } }//归并 while(begin1 <= end1)temp[i++] = a[begin1++]; while(begin2 <= end2)temp[i++] = a[begin2++]; //归并 for (int j = left; j <= right; j++)//拷贝回去 { a[j] = temp[j]; } }void MergeSort(int* a, int n)//真正的归并排序 { int* temp = (int*)malloc(sizeof(int) * n); if (temp == NULL) { printf("malloc fail\n"); exit(-1); } _MergeSort(a, 0, n - 1,temp); free(temp); }

时空复杂度分析：其时间复杂度为O(NlogN)
但是需要注意，归并排序的空间复杂度是O（N）
适用场景所以，当有很多个（比如10亿）数据需要排时，一般并不选择归并，而是选择快排。

八、计数排序（count_sort）计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
文字描述版：

（1）找到最小的数和最大的数，在最小的数和最大的数之间开辟数组。
（2）统计每一个数，其是多少，直接放在相应的数组下标里面（即相应数组下标对应的那个元素的值加一）。
（3）然后按照自己想要排的顺序将数一个一个拿出来。

动图展示版：

文章图片

代码实现版：

void CountSort(int* a, int n) { int max = a[0], min = a[0]; for (int i = 0; i < n; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; }//遍历一遍找出max和min int range = max - min + 1; //给出范围 int* count = (int*)malloc(sizeof(int) * range); //开辟空间 if (count == NULL) { printf("malloc fail"); } else { memset(count, 0, sizeof(int) * range); //先初始化0 for (int i = 0; i < range; i++) { count[a[i] - min]++; //是谁就让相应的下标所对应的元素加1 } int i = 0; for (int j = 0; i < range; j++) { while (count[j]--) { a[i++] = count[j] + min; } }//再按照排列的依次输出到a中 free(count); count = NULL; } }

时空复杂度：算法的时间复杂度为O(N+k)，空间复杂度为O(k)，k就是上面代码中的range。
说明这是一种非比较类排序，是一种很好的、巧妙的算法思路。计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

至于桶排序和基数排序我们今天就不介绍了，它们和计数排序有着相似之处，等我们日后oj需要，我们再做介绍。把今天所说的八种排序整理吸收好，就很不错了。
尤其是快速排序、希尔排序和堆排序。

好啦，本节的内容到此结束，蟹蟹各位~~~

欢迎关注关注关注我呀呀哎呀呀呀~~~~

【初学者能学会的数据结构与算法|初阶数据结构与算法——经典八大排序算法||初步学习至熟练掌握(附动图演示，初学者也能看懂)】