数据结构八大常见的排序
- 常见排序算法分类
- 1.插入排序
- 2.希尔排序(缩小增量排序)
- 3.选择排序
- 4.堆排序
- 5.冒泡排序
- 6.快速排序
- 7.归并排序
- 归并排序非递归的实现
- 8.计数排序
常见排序算法分类
1.插入排序
基本思想：把待排序的数组按大小逐个插入到一个已经排好序的有序序列中，直到所有的数据插入完为止，得到一个新的有序序列 。
动图解析：
代码实现思路：
定义一个临时变量tmp来遍历待排数组，定义一个end作为有序数组的最后一个下标，然后end遍历有序数组。在排序中有以下几种情况：
1.最初开始的时候第一趟排序tmp直接从第二个数据开始遍历即可。
2.tmp<a[end]
3.tmp>a[end]
代码实现：
void InsertSort(int* a, int n)//插入排序 最好为O(N) O(N2)
{
//思路：把数组中一个一个的插入，然后进行比较，把它们放到自己的位置
for (int i = 1; i < n; i++)
{
int end = i - 1;//end为控制数组的下标，使他放在temp的前一个
int temp = a[i];
//一趟插入一个数组，如果temp比a[end]小就放在a[end]左边，如果temp比a[end]大的话就放在，a[end]的右边
while (end >= 0)
{
if (temp < a[end])//如果temp小于a[end],那么tempd肯定插入到a[end],之前，那么就让a[end]向后移动一位
//接下来就拿temp和前面的比较，看是否小于a[end]前面的数
{
a[end + 1] = a[end];
end--;
}
else {
break;//如果temp>a[end]的话就跳出循环，将temp放在a[end]后面，插入的精髓就在于此temp永远在a[end]的后面
}
}
a[end + 1] = temp;//这种写法temp大于或小于a[end]两种情况都符合，temp放在左(小)右(大)边都符合
}
}
直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
2.希尔排序(缩小增量排序)
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有数据分成个gap组，所有距离为gap的数据分在同一组内，并对每一组内的数据进行排序，单趟排序的思路和直接插入排序一样。然后取重复上述分组和排序的工作。当到达gap=1时，所有数据在同一组内排序，gap=1是也就相当于直接插入排序。
代码实现：
void ShellSort(int* a, int n)//希尔排序
{
int gap = n;//gap在这里是一个不断变化的值
while (gap > 1)
{
gap = gap / 3 + 1;//保证gap最后一次为1，当gap等于1的时候相当于简单插入排序，就可以直接排序出来了
for (int i = 0; i < n - gap; i++)
{
int end = i;
int temp = a[end + gap];
//将数组分为gap组，当gap较大的时候，也就是第一循环gap为n/3+1，将数组分成gap(大约n/3)组，那么一组就有3个数据，
// 最差的情况while循环也只需要1+2次，外循环n，所以gap较大的时候的时间复杂度为O(N)
//当gap较小的时候，即gap为1的时候，这时候就是插入排序，但是因为gap越小数组就越接近有序，
//所以这时候的时间复杂度为O(N)
//所以希尔排序的时间复杂度的量级为 logN*N 大约为n^1.3
while (end >= 0)
{
if (temp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = temp;
}
}
}
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。 - 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的
希尔排序的时间复杂度都不固定：
- 稳定性：不稳定
3.选择排序
基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据排完 。我们实现的是单趟排序中选出最大值和最小值，分别放在数组的最右边和最左边。
动图实现的是将数组中最小的放在最左边：
代码实现：
void SelectSort(int* a, int n)//选择排序(升序) 最坏为O(N2) 最好O(N2)
{
int left = 0;
int right = n - 1;
while (left < right)
{
//一趟选出一个最大和最小的值然后放在数组的两边
int mini = left;//最小数的下标
int maxi = left;//最大数的下标
for (int i = left+1; i <= right; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[left], &a[mini]);//最小的放在左边
if (maxi == left)//如果刚好最大值再最左边，则会导致最大值交换到mini下标的位置
{
maxi = mini;
}
Swap(&a[right], &a[maxi]);
left++;
right--;
}
}
直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
4.堆排序
升序堆排序的一般思路就是将给定的一组数据放在堆的数据结构当中去，然后进行不断被的取堆顶元素放在数组当中，不断地pop（删除）。但是这种方法太麻烦了，自己还要手写一个堆的数据结构以及一些接口函数，还要创建数组等，显然不是最优解。
接上文的写的两种调整方式，向上调整和向下调整。 详细见数据结构二叉树顺序结构——堆的实现
思路：
①可以用向上调整或者向下对原数组进行调整，也就是建一个大堆（排升序大堆后面讲为啥）
②接下来利用堆删除的原理，将堆顶的数据和数组最后一个交换（也就是将堆顶和堆尾的数据进行交换），然后就相当于最大的数放在了最后一个位置，所以最后一个位置的数据确定了，接下来对剩下的数据进行向下调整，再重复以上操作。
ps:排升序建大堆而不是小堆的原因，反证思路来看，若建小堆的话，最小的数据在第一个，第一个数据确定了，但是剩下的数据很暖再重新调整成为一个新的小堆的数据结构，所以排升序建小堆很难实现。
向上调整和向下调整都可以完成建堆的操作，但是他们的时间复杂度有所不同，接下来讲一下他们的取舍。
向上调整建堆（时间复杂度：O(N * logN) ）
for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
}
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
向下调整建堆（时间复杂度：O(N) ）
for (int i = (n - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);//a是堆的数组，n是防止数组越界的数组数据个数，i是开始向下调整的位置
}
向下调整建堆得思路：从第一个非叶子结点开始从数组得后面向前面一个一个进行调整
复杂度证明：
看到这里很容易发现向下调整方法建堆得时间复杂度更加合适
代码实现：
void AdjustDown(int* a, int parent, int n)//向下调整
{
int child = parent * 2 + 1;
while (child < n)//这里child会先越界到达临界点，所以不用判断parent
{
//默认child是左右孩子中较大的值
if (child + 1 < n && a[child] < a[child + 1])
{
child = child + 1;
}
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;//符合堆的性质则跳出循环
}
}
}
// 对数组进行堆排序
void HeapSort(int* a, int n)
{
//思路：向上调整方法建堆建堆
//>这里排升序要建大堆，因为建小堆的话，接下来排升序第一个数据好处理，
//但是剩下的数据重新排成堆的话关系全都乱了
//所以这时候建大堆，和删除的思路一样，首先交换堆顶和堆尾，这时候最大的数据放到了最后一个位置
//然后将前面n-1个数据看成新的堆进行向下调整，然后再找次大的数放在倒数第二的位置
//建堆有两种方式 向上调整建堆和向下调整建堆，时间复杂度分别为O(N*logN)和O(N)
//向上调整建堆 建堆时间复杂度 O(N*logN)
/*for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
}*/
//向下调整建堆 时间复杂度为O(N)
//向下调整的条件是调整节点的左右子树都为大堆或者小堆
//所以从下边开始进行向下调整(大堆)，这时候大的数会慢慢上浮，最先调整的位置不能是叶子节点，那样会重复很多操作
//应该从最后一个父亲节点开始进行向下调整 最后一个父亲节点的下标为 (n-1)/2,然后按数组下标的顺序递减进行调整
for (int i = (n - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);//a是堆的数组，n是防止数组越界的数组数据个数，i是开始向下调整的位置
}
while (--n) //排序的时间复杂度为O(N*logN)
{
//此处为--n的原因：一共有n个数据，循环一次确定一个数据的位置，循环n-1次之后就可以确定n-1个数据的位置，
// 前面已经确定了n-1个位置，最后一个数据的位置也已经确定，所以当n=0的时候的那一次循环可以不需要进行就可以
//
//此时n已经自减1，所以此时n就为堆尾数据，且n为下一个新堆的数据个数，所以后面向下调整直接传参n
Swap(&a[0], &a[n]);//交换堆顶和堆尾的数据
AdjustDown(a, n, 0);//n为新堆的数据个数
}
//总结：堆排序的时间复杂度为O(N*logN)，因为堆排序有两个步骤①建堆②排序
//建堆向上调整建堆的时间复杂度为O(N*logN)，向下调整建堆的时间复杂度为O(N),相对较快，
//但是排序的时间复杂度都为O(N*logN)，所以决定了堆排序的时间复杂度为O(N*logN)。
}
堆排序的特性总结：
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
5.冒泡排序
基本思路：两两数据相比，大的元素向后移，也就是前一个数据大于后一个数据就交换，一趟能保证最大的数据放在数组的最右边。
代码实现：
void BubbleSort(int* a, int n)//冒泡排序 最坏O(N2) 最好O(N)
{
//这里起始位置如果i=0;那么就是a[i]和a[i+1]进行比较，i作为下标最后的位置落在n-2的位置，和n-1去比较
//这里起始位置如果i=1;那么就是a[i-1]和a[i]进行比较，i作为下标最后的位置落在n-1的0位置，和n-1-1去比较
while (n)
{
int i = 0;
bool exchange = false;
//这里定义一个记号，记录一下单趟循环中是否有交换，若单趟循环中没有交换就证明，已经有序了
//不需要接下来的排序
for (i = 1; i < n; i++)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = true;
}
}
if (exchange == false)
{
break;
}
n--;
}
}
6.快速排序
详细见数据结构——快速排序的三种方法和非递归实现快速排序
7.归并排序
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
动图详解：
代码实现思路：
子规模：
将数组分为两部分，然后分别把这两部分数据排成有序部分，然后将两组有序数组分别进行遍历比较，较小的数据放在临时数组tmp中，其中一个数组遍历结束后将另一组未比较的数据直接赋值到临时数组tmp，最后用memcpy函数将临时数组tmp的值拷贝放到指定数组中；
递归：
先将给定数组不断递归，直到数组中只有一个数据，也就代表有序，不需要进行排序，然后返回。
代码实现：
void MergeSort(int* a, int n)//归并排序
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("tmp malloc failed\n");
return;
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}
void _MergeSort(int* a, int left, int right, int* tmp)//归并排序的排序部分
{
//思路：将数组分为左右两部分，并且每组内是有序的，然后再将有序的两组分别遍历相比较，
//较小的放在临时数组中，一个数组遍历结束后，另一个数组的所有值直接赋值给临时数组
//最后用memcpy将临时数组的值拷贝到原数组
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
//递归到一组为一个值的时候开始比较
_MergeSort(a, begin1, end1, tmp);
_MergeSort(a, begin2, end2, tmp);
//比较
int i = begin1;//这里i的值必须是begin1，当递归到右半边的数据的时候，给tmp赋值的时候必须对应的也应该是右半边的空间
while (begin1 <= end1 && begin2 <= end2)//两组数据都没遍历结束的时候都可以进循环比较
{
if (a[begin1] <= a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
//将没有遍历完的数组赋值到临时数组tmp中
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
//这里memcpy中数组的起始地址要加上left的，因为我们每次只需要将递归中重新排序的那个组的数值拷贝到原来的数组即可
memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}
归并排序非递归的实现
归并排序的思路就是将数组分为左右两个有序数组然后进行排序，通过不断递归到子规模数组中只有一个元素的时候开始排序，然后一步一步的返回。那么我们可以直接模拟递归的子规模然后一步一步的的返回，也就是定义一个gap，初始值为1，gap的意义就是将数组分为每组为gap个数组的组，然后进行排序：
每两组然后开始进行单趟归并排序，排序后为6，10，1，7，3，9，2，4。接下来将数组分为每组数组为2的数组，也就是gap=2：
接下来进行单趟归并，归并后数组为1，6，7，10，2，3，4，9，接下来gap=4：
然后进行单趟归并排序后为1，2，3，4，6，7，9，10。完成递归。当然看到这里肯定有疑问，如果数组元素个数不是2的n次方怎么办呢，肯定会越界访问，先不急一步一步来，先实现这种理想状态下的代码
代码实现
void MergeSortNonR(int* a, int n)//归并排序(非递归)
{
int* tmp = (int*)malloc(sizeof(int) * n);//创建临时数组tmp用来存放归并后的数据然后最后再拷贝回去
if (tmp == NULL)
{
perror("tmp malloc failed\n");
return;
}
int gap = 1;
while(gap<n)
{
int i = 0;
int j = 0;//控制tmp数组
for (i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
while (begin1 <= end1 && begin2 <= end2)//两组数据都没遍历结束的时候都可以进循环比较
{
if (a[begin1] <= a[begin2])
{
//这两种写法一样不过我的编译器第一种会有点报错，有点强迫症哈哈
//tmp[j++] = a[begin1++];
*(tmp + j++) = a[begin1++];
}
else
{
*(tmp + j++) = a[begin2++];
}
}
//将没有遍历完的数组赋值到临时数组tmp中
while (begin1 <= end1)
{
*(tmp + j++) = a[begin1++];
}
while (begin2 <= end2)
{
*(tmp + j++) = a[begin2++];
}
//这里memcpy中数组的起始地址要加上i的，因为我们每次只需要将递归中重新排序的那个组的数值拷贝到原来的数组即可
memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));
}
gap *= 2;
}
free(tmp);
}
运行截图：
这里发现我们的思路暂时是没问题的，但是我们将数组改为11个数据的时候，会发现有越界的情况。
这时候我们可以加几行代码，把每次进行单趟排序的去加打印出来。
这时候我们发现划线部分都是越界部分，我们分析一下，begin1，end1，begin2，end2，谁有可能越界，因为begin1=i，i<n，所以begin1不会越界，那么也就是end1，begin2，end2会越界，这时候对这三种情况分情况讨论即可。
修改后代码：
void MergeSortNonR(int* a, int n)//归并排序(非递归)
{
int* tmp = (int*)malloc(sizeof(int) * n);//创建临时数组tmp用来存放归并后的数据然后最后再拷贝回去
if (tmp == NULL)
{
perror("tmp malloc failed\n");
return;
}
int gap = 1;
while(gap<n)
{
int i = 0;
int j = 0;//控制tmp数组
for (i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
if (end1 >= n || begin2 >= n)
{
break;
}
else if (end2 >= n)
{
end2 = n - 1;
}
//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);
while (begin1 <= end1 && begin2 <= end2)//两组数据都没遍历结束的时候都可以进循环比较
{
if (a[begin1] <= a[begin2])
{
//这两种写法一样不过我的编译器第一种会有点报错，有点强迫症哈哈
//tmp[j++] = a[begin1++];
*(tmp + j++) = a[begin1++];
}
else
{
*(tmp + j++) = a[begin2++];
}
}
//将没有遍历完的数组赋值到临时数组tmp中
while (begin1 <= end1)
{
*(tmp + j++) = a[begin1++];
}
while (begin2 <= end2)
{
*(tmp + j++) = a[begin2++];
}
//这里memcpy中数组的起始地址要加上left的，因为我们每次只需要将递归中重新排序的那个组的数值拷贝到原来的数组即可
memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));
}
gap *= 2;
//printf("\n");
}
free(tmp);
}
测试截图：
归并排序的特性总结：
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
8.计数排序
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
实现思路：
1.开辟一个数组CountA
首先遍历一遍数组找出数组中的最大值MAX，最小值MIN，然后开辟一个RANGE大小的新的数组CountA,其中RANGE=MAX-MIN+1。CountA数组每个元素分别用来记录待排数组中对应数据的出现次数。
2.统计次数
在以上例子中可以发现待排数组的最小值为1，最大值为9，RANGE=9,所以开辟9个空间，将CountA计数数组初始化为0，然后开始遍历待排数组，待排数组中1出现了一次，2出现了2次，3出现了1次，4出现了0次，5出现了2次，6出现了1次，7出现了0次，8出现了0次，9出现了1次。
这里计数数组CountA中第一个数据也就是下标0的位置映射的是待排数组中的MIN，下标1映射的就是MIN+1,···，最后一个数据RANGE-1映射的就是最大值MAX。
3.赋值到原数组
直接按照顺序将原数组的数据覆盖就好。
代码实现：
void CountSort(int* a, int n)
{
int max = a[0], min = a[0];
for (int i = 1; i < n; ++i)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
int range = max - min + 1;
int* countA = (int*)malloc(sizeof(int) * range);
if (countA == NULL)
{
perror("malloc fail\n");
return;
}
memset(countA, 0, sizeof(int) * range);
// 计数
for (int i = 0; i < n; i++)
{
countA[a[i] - min]++;
}
// 排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (countA[i]--)
{
a[j++] = i + min;
}
}
free(countA);
}
总结：基数排序适合范围集中，且范围不大的整型数组排序。不适合范围分散过着非整形的排序，如字符串、浮点数等
