✨✨小新课堂开课了，欢迎欢迎~✨✨
🎈🎈养成好习惯，先赞后看哦~🎈🎈
所属专栏：数据结构与算法
小新的主页：编程版小新-CSDN博客
1.冒泡排序
1.1算法思想
冒泡排序的基本思想就是，遍历原数组的元素，比较相邻的两个元素，如果这两个元素的顺序不对，就是把这两个元素交换，直到都不需要交换的时候，排序结束。
1.2具体步骤
比较相邻的两个元素，把大的(小的)往后换，就这样重复此步骤，每遍历完数组一次，就能将最大的(最小的)元素放在最后。重复遍历该数组，直至都不需要交换的时候，排序就结束了。
1.3动图演示
1.4代码实现
void Swap(int*a,int*b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//冒泡排序
void BubbleSort(int* arr, int len)
{
for (int i = 0; i < len - 1; i++)//比较次数
{
for (int j = 0; j < len-1-i; j++)//单趟比较
{
if (arr[j] > arr[j + 1])
{
Swap(&arr[j], &arr[j + 1]);
}
}
}
}有的时候不用遍历数组len次，排序就已经排好了，我们知道遍历完数组一次后，如果不存在交换，那就不用再继续比较了。此时排序已经排好了。
优化：
void Swap(int*a,int*b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//冒泡排序
void BubbleSort(int* arr, int len)
{
int flag = 0;
for (int i = 0; i < len - 1; i++)//比较次数
{
for (int j = 0; j < len-1-i; j++)//单趟比较
{
if (arr[j] > arr[j + 1])
{
Swap(&arr[j], &arr[j + 1]);
flag = 1;
}
}
if(flag ==0)//未发生交换，排序已经完成
break;
}
}1.5复杂度分析
时间复杂度：这里很容易就能看出来是O(N^2)。以最坏的情况来看，n-1+n-2+n-3+……+2+1=n*(n-1)/2。
空间复杂度: 因为没有额外的开空间，所以空间复杂度为O(1)。
1.6稳定性分析
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
简而言之，相同值相对位置不变称之为稳定。
冒泡排序是相邻位置的元素比较，决定交不交换，一样的元素，在排序过程中相对位置不会发生变化，因此冒泡排序是稳定的。
2.选择排序
2.1算法思想
遍历原数组，找出最小或者最大的那个元素，与起始位置或则末尾的元素交换，每遍历完一次，起始位置向后移(末尾的位置往前移），当起始位置移到最后一个位置时(末尾位置移到数组的第一个元素的位置时），排序结束。
2.2具体步骤
遍历数组，找到最大或者最小的元素，与起始位置交换。
从剩余的元素中找继续找最大或最小的元素，排到已排序序列的末尾。
以此类推，直到所有的元素都排列完毕。
2.3动图演示
2.4代码实现
基于动态演示实现的代码：
void SelectSort(int* arr, int len)//选择排序
{
for (int i = 0; i < len - 1; i++)//起始位置
{
int mini = i;
for (int j = i + 1; j < len; j++)//寻找最小元素
{
if (arr[j] < arr[mini])
{
mini = j;
}
}
swap(&arr[mini], &arr[i]);
}
}
上面的代码效率比较低，我们在遍历一遍数组的时候，可以找到该数组中最大和最小的元素，让最大的元素与end交换，最小的元素与begin交换，不断的这样缩小区间，完成排序。
这里要注意的是，我们在交换的时候，可能会改变最大或最小元素的位置 。
//选择排序
void Swap(int*a,int*b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void SelectSort(int* arr, int len)
{
int begin = 0;
int end = len - 1;
while (begin < end)
{
int mini = begin;
int maxi = begin;
for (int i = begin + 1; i <=end; i++)
{
//遍历一遍找最大和最小
if (arr[i] > arr[maxi])
{
maxi = i;
}
if (arr[i] < arr[mini])
{
mini = i;
}
}
Swap(&arr[begin], &arr[mini]);
if (maxi == begin)//如果begin和maxi重合，就要对maxi更正
{
maxi = mini;
}
Swap(&arr[end], &arr[maxi]);
begin++;
end--;
}
}
2.5复杂度分析
时间复杂度：优没优化，算时间复杂度的时候都是等差数列，时间复杂度为O(N^2)。
空间复杂度：没有额外开辟空间，因此空间复杂度为O(N)。
2.6稳定性分析
3.插入排序
3.1算法思想
把待排元素逐一与已排序的部分元素进行比较，把它插入到已排序序列中的适当位置，直到把元素全部插入完毕。
3.2具体步骤
把第一个元素看成有序序列，从第二个元素开始，将该元素与前面已排好序的元素比较，如果该元素比较小，就将前面的元素依次往后移动一位，将该元素插入到腾出的位置上。
重复上面的插入过程，直至整个序列都被排序完成。
3.3动图演示
3.4代码实现
// 插入排序
void InsertSort(int* a, int n)
{
//【0-end】有序，将end+1的值插入到区间内，形成新的区间
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];//往后移
end--;
}
else
{
break;//找到合适的位置了
//也有可能合适的位置就是数组的起始位置，没有进break，此时end为-1越界，在
// end+1的位置插入,就是把该元素插入到起始位置
}
}
a[end + 1] = tmp;//在腾出来的位置插入该元素
}
}3.5复杂度分析
时间复杂度：以最坏的情况，逆序来算，移动的次数是等差数列的前n-1项和，O(N^2)。
空间复杂度：没有额外开辟空间，空间复杂度为O(1)。
3.6稳定性分析
插入排序不会改变相同元素的相对位置，在前面的和在后面的那个在插入到腾出的位置后，还是一前一后。因此插入排序稳定。
4.希尔排序
4.1算法思想
希尔排序是对插入排序的改进。它先将整个待排的序列分割成若干个子序列，对每一个子序列分别进行插入排序，然后不断缩小缩小子序列的间隔，重复这个过程直至间隔为1 时进行一次完整的插入排序。
4.2具体步骤
希尔排序分为两步：1.预排序(使数组接近有序） 2.插入排序
选取一个gap，间隔gap个数据为一组，把整个数组进行分组，一共gap组。
以gap为基准，对其进行插入排序。
不断缩小gap，直至gap为1，进行一次完整的插入排序。
gap>1时是在进行预排序，gap==1是在进行直接插入排序。
4.3动图演示
4.4代码实现
// 希尔排序
//希尔排序分为两步：第一步是预排序(使其接近有序),第二步是进行插入排序
void ShellSort(int* a, int n)
{
int gap = n;//gap代表每间隔gap个为一组即一共分成gap组
while (gap > 1)
{
//gap>1是进行预排序
//gap==1是在进行插入排序
gap = gap / 3 + 1;//+1是保证最后一组gap一定为1,
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];//i之所以小于n-gap;是防止这里越界
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}4.5复杂度分析
时间复杂度：希尔排序的时间复杂度可以直接记，因为比较难算。O(N^1.3)
空间复杂度：没有额外开辟空间，空间复杂度为O(1)。
4.6稳定性分析
在排序过程中，可能相同数据分到不同的组，这个无法控制，因此希尔排序不稳定。
