＜呕心沥血＞一文总结数据结构八大排序（持续更新）
目录
一、常见的八大排序
二、八大排序的算法思想
1、冒泡排序
2、选择排序
3、插入排序
4、希尔排序
5、归并排序
6、快速排序
7、堆排序
8、计数排序
三、八大排序的算法实现
一、常见的八大排序
常见的八大排序算法如下：
冒泡排序（Bubble Sort）：比较相邻元素，如果第一个比第二个大，就交换它们两个的位置。
选择排序（Selection Sort）：从未排序的部分找到最小值并放在已排序部分的末尾。
插入排序（Insertion Sort）：将待排序序列分为已排序和未排序两部分，每次从未排序部分中取出第一个元素插入已排序部分的正确位置。
希尔排序（Shell Sort）：是插入排序的改进版，通过对比较远距离的元素进行交换来提高效率。
归并排序（Merge Sort）：采用分治思想，将待排序序列分成若干小段，先排序小段，再合并为整体有序序列。
快速排序（Quick Sort）：选择一个基准元素，比基准元素小的放左边，比基准元素大的放右边，递归地对左右部分进行排序。
堆排序（Heap Sort）：将待排序序列构建成一个大根堆或小根堆，每次取堆顶元素进行排序。
计数排序（Counting Sort）：对于给定的一组输入元素，计算出每个元素出现的次数，再根据次数从小到大输出元素。
这八种排序算法各有优劣，应根据实际情况选择合适的算法。
二、八大排序的算法思想
1、冒泡排序
冒泡排序是一种最简单的排序算法，它的基本思想是通过相邻元素之间的交换来把小的元素往前移，大的元素往后移。经过多轮的排序操作，最终实现了整个数组的排序。
具体过程如下：
比较相邻的两个元素，如果第一个元素比第二个元素大，就把它们两个交换位置。
对相邻的元素对进行比较的过程称为一次遍历。一次遍历后，最后一个元素应该是当前未排序部分中的最大值。
对除已排序好的元素外的所有元素，不断进行遍历操作，直到所有元素都排序好。
时间复杂度为 O(n*2)，是一个不稳定的排序算法。
2、选择排序
选择排序是一种简单直观的排序算法，其总体思路是找到数据结构中的最小值并将其放在第一位，接着找到第二小的元素并将其放在第二位，以此类推，直到所有元素都排序好。
具体过程如下：
遍历整个数组，找到最小的元素。
将最小元素放在数组的最前面，即第一个位置。
在剩下的未排序序列中，重复步骤一和步骤二。
时间复杂度为 O(n*2)，是一个不稳定的排序算法。
3、插入排序
插入排序的基本思想是将待排序的元素插入到已排序的序列中。假设当前已经拍好的序列为 a1,a2,…,aia1,a2,…,ai，待插入的元素为 ai+1ai+1，则插入操作是将 ai+1ai+1 与 aiai 进行比较，如果 ai+1<aiai+1<ai，则将 aiai 后移，继续与前一个元素进行比较，直到找到合适的位置将 ai+1ai+1 插入。
具体过程如下：
将待排序的数组分成已排序和未排序两个部分。
从未排序部分中取出第一个元素，将其和已排序部分的元素依次比较并插入到正确的位置。
重复执行第二步，直到所有元素都被插入到已排序部分。
时间复杂度为 O(n*2)，是一个稳定的排序算法。
4、希尔排序
希尔排序是插入排序算法的一种改进版，其基本思想是将待排序的数组划分为若干子序列，对每个子序列进行插入排序，通过逐步缩小子序列的间隔，最终完成整个数组的排序。
具体过程如下：
选择一个增量序列 t1,t2,…,tkt1,t2,…,tk，其中 t1=n/2t1=n/2，ti+1=ti/2ti+1=ti/2（向下取整）。
对于每个增量 titi（i=k,k−1,…,1i=k,k−1,…,1），分别将待排序序列分割成若干长度为 titi 的子序列，分别进行直接插入排序。
最后对整个序列进行一次直接插入排序。
时间复杂度为 O()，是一个不稳定的排序算法。
5、归并排序
归并排序是一种效率比较高的排序算法，它的基本思路是采用分治法的思想，将待排序的序列分成若干个子序列，分别进行排序，在将已排序的子序列合并，最终得到完整的排序序列。
具体过程如下：
将待排序序列分成若干个子序列，在保证子序列内部有序的前提下，对所有子序列进行排序。
将排好序的子序列依次合并，直到得到完整的排序序列。
时间复杂度为 O()，是一个稳定的排序算法。
6、快速排序
快速排序是一种高效的排序算法，也是一种基于分治思想的排序算法。它的基本思路是选择一个基准元素，将待排序的序列分为两个部分：小于基准的元素和大于基准的元素。然后对这两个部分分别进行递归排序，最终得到完整的排序序列。
具体过程如下：
选择一个基准元素，通常选择第一个或最后一个元素。
将序列中比基准元素小的所有元素放在基准元素的左边，比基准元素大的所有元素放在基准元素的右边。
对基准元素左边和右边的序列分别递归执行上述过程。
时间复杂度为 O()O(nlog2n)，是一个不稳定的排序算法。
7、堆排序
堆排序是一种树形选择排序算法，堆可以看成是一棵完全二叉树。堆排序的基本思想是将待排序的序列构建成一个大根堆或小根堆，每次取出堆顶元素进行排序。
具体过程如下：
构建堆：根据给定的序列构建大根堆或小根堆。
取出堆顶元素：每次从堆顶取出堆顶元素，放到已排序的序列中。
调整堆：将剩余的元素重新构建成一个堆。
重复执行步骤二和步骤三，直到所有元素都排序好。
时间复杂度为 O()，是一个不稳定的排序算法。
8、计数排序
计数排序是一种基于桶排序思想的排序算法，它通过计算给定序列中每个元素出现的次数，然后根据元素的出现次数进行排序，并将排序结果存储在新的数组中。
具体过程如下：
找出待排序数组中的最大值和最小值。
新建一个数组用于记录待排序数组中每个元素出现的次数。
统计每个元素在待排序数组中的出现次数。
对于每个元素，统计比它小的元素个数，确定它在新数组中的位置。
将待排序数组中的元素一个个放入新数组中对应的位置。
时间复杂度为 O(n+k)，其中 k 是待排序数组中的最大值，是一个稳定的排序算法。