C语言八大排序详解
排序的概念及其应用
排序的概念及其运用
1、排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
2、排序的运用
（1）、淘宝网上对商品的排序，可以根据品牌、销量、性能、价格等进行排序，我们可以根据不同的排序方式，筛选出自己想要的结果。
（2）2021年国内大学排名
3、常见的排序算法
常见的八大排序算法
直接插入排序
1、基本思想
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
当插入第i(i>=1)个元素时，前面的arr[0],arra1],…,arr[i-1]已经排好序，此时用array[i]的排序码与arr[i-1],arr[i-2],…的排序码顺序进行比较，找到插入位置即将arr[i]插入，原来位置上的元素顺序后移
直接插入排序代码实现
// 插入排序 时间复杂度O(N*N),数组逆序的情况下
void InsertSort(int* a, int n)
{
//多趟排序
int i = 0;
for (i = 0; i < n - 1; i++) //{ 5,2,4,6,1,3 }
{
//单层排序
int end = i; //end的区间在[0,n-1),n-1的位置放tmp
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end]) //将‘<’改成‘>'就是降序排列
{
a[end + 1] = a[end]; //记得要把比tmp大的数向后移一位
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
//打印函数
void Print(int* a, int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
int main()
{
int a[] = {
5,2,4,6,1,3 };
int n = sizeof(a) / sizeof(a[0]);
InsertSort(a, n);
Print(a, n);
return 0;
}
直接插入排序算法时间复杂度及稳定性分析
时间复杂度分析：
1、最坏情况，就是逆序情况下排序，例如要排升序，而所要排序的数组是降序，那么时间复杂度就是O(N^2).
例
如果要排升序，而数组本身就是升序，那么时间复杂度就最优，O(N).
而时间复杂度是以最坏标准来衡量，所以直接插入排序的时间复杂度是O(N^2).
插入排序是稳定排序算法吗？
所谓稳定，指的是当数组中出现相同数值元素的时候，排序是否会造成相同数值元素相对位置的改变。可以看出在插入排序算法中，对于相同数值的元素可以选择插入到已排序区间等值元素的后边，所以相同数值元素的相对位置不会发生改变，因此插入排序算法是稳定的排序算法。
直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
希尔排序
希尔排序是根据插入排序推想出来的，因为插入排序在最好的情况下，时间复杂度可以达到O(N),所以希尔想到，能不能找到一种方法，使所要排的序列接近有序，这样再排序就可以大大降低时间复杂度。
希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达gap=1时，就是上述的插入排序。
gap越大，大的和小的数可以更快的挪到对应的方向去
gap越大，越不接近有序
gap越小，大的和小的数可以更慢的挪到对应的方向去
gap越小，就越接近有序
gap==1;
就是直接插入排序。
希尔排序代码实现
void ShellSort(int* a, int n)
{
// gap > 1的时候，预排序
// gap == 1的时候，直接插入排序 O(N)
int gap = n;
while (gap > 1) // n/3/3/3.../3 == 1 -》 3^x = n x就是这个while循环跑的次数
{
gap = (gap / 2 ); //一般写成gap = (gap / 2+1 )；+1是为了保证，最后一次gap为1
// 最坏的情况：逆序，gap很大的时-》O(N)
// ...
//
// gap很小时本来应该是O(N*N),但是经过前面的预排序，数组已经很接近有序的，所这里还是O(N)
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;
}
printf("gap:%d->", gap);
Print(a, n);
}
}
int main()
{
int a[] = {
9,1,2,5,7,4,8,6,3,5 };
int n = sizeof(a) / sizeof(a[0]);
ShellSort(a, n);
Print(a, n);
return 0;
}
希尔排序算法时间复杂度及稳定性分析
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。 - 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N1.3—N2）
- 稳定性：不稳定
选择排序
1、基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
2、 直接选择排序:
在元素集合arr[i]–》arr[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的arr[i]–arr[n-2]（arr[i+1]–arr[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
选择排序代码实现
#pragma once
#include <stdio.h>
#include<time.h>
#include<stdlib.h>
#include<stdio.h>
//打印
void PrintArray(int* a, int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// 选择排序
void SelectSort(int* a, int n) //{ 0, 1, 5, 3, 6, 7, 4, 2, 8, 9 }
{
int left = 0;
int right = n - 1;
while (left < right)
{
//选出最大的放在右边，最小的放在左边
int max = left;
int min = left;
for (int i = left; i <= right; i++)
{
if (a[i] > a[max])
{
max = i;
}
else if (a[i] < a[min])
{
min = i;
}
}
Swap(&a[max], &a[right]);
//有可能最小的位置在最右边，被max换走了，换到最大的位置去了
if (right == min)
{
min = max; //把最大的位置给最小的位置
}
Swap(&a[min], &a[left]);
left++;
right--;
//PrintArray(a, n);
}
}
int main()
{
int arr[] = {
5,8,6,3,9,2,1,7 };
int n = sizeof(arr) / sizeof(arr[0]);
SelectSort(arr, n);
PrintArray(arr, n);
return 0;
}
选择排序算法时间复杂度及稳定性分析
转载：https://blog.csdn.net/qq_49613557/article/details/117413719