目录
一、 直接插入排序
1.1 动态图
1.2 静态图
1.3 代码
1.4 复杂度分析
1.5 特性
二、希尔排序(直接插入排序思想上的优化)
2.1 特性
2.2 动态图
2.3 静态图编辑
2.4 代码
2.4.1按照黑色组、红色组、蓝色组顺序来进行排序
2.4.2 多组并排
2.5 时间复杂度
三、直接选择排序
3.1 动态图
3.2 代码
3.3 优化版
3.4 代码
3.5 特性
四、 堆排序
4.1 动态图
4.2 代码
4.2.1 向下调整(HeapSort1)
4.2.2 向上调整(HeapSort2)
4.3 1000000个数 向下调整(HeapSort1)和向上调整(HeapSort2)建大根堆然后排成升序的速度比较
4.4 特性
五、100000个数4种排序的速度比较
一、 直接插入排序
直接插入排序是一种简单的插入排序法，其基本思想是： 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。举例: 如我们玩扑克牌时，就用了插入排序的思想
1.1 动态图 1.2 静态图 1.3 代码void InsertSort(int* a,int n)
{
//比较的次数为n-2次
for (int i = 0;i < n-1;i++)
{
int end = i;
int x = a[end+1];
//end结束的条件为end>=0,只是每次单趟的条件
while (end >= 0)
{
if (a[end] > x)
{
a[end + 1] = a[end];
end--;
}
else
{
//不需要再进行循环
break;
}
}
//把x的值放入end下标的后一个位置即可
a[end + 1] = x;
}
}运行结果:
1.4 复杂度分析时间复杂度:o(n^2)
最坏时间复杂度:o(n^2) -- 逆序，每一个都要挪动--> 1+2+ ... + n
最好时间复杂度:o(n) -- 顺序有序或者接近有序即每次插入基本都不需要挪动，直接插入在最后
空间复杂度:o(1) -- 值开辟了end,x常数量个（算法在执行过程种开辟的额外的空间）
1.元素集合越接近有序,直接插入排序算法的时间效率越高
2.稳定性:稳定
1.分组预排序 -- 数组接近有序，按gap分组，分成gap组
2.直接插入排序(gap == 1)
3.稳定性:不稳定
2.4 代码 2.4.1按照黑色组、红色组、蓝色组顺序来进行排序
//分组gap组,一组结束后再进行下一组
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 2;
//分为gap组
for (int j = 0; j < gap; j++)
{
//一组的范围
for (int i = j; i < n - gap; i += gap)
{
//1.先进行一组的排序
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end = end - gap;//x再和前面的数比，直到end < 0
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}
}运行结果 :
2.4.2 多组并排思想:黑色组的第一个和其第二个排序之后，再进行红色组的第一个和第二个排序，然后再进行蓝色组的第一个和第二个排序，即多组一起进行排序，并不是如(1)中，一组排完再排下一组
多次预排序(gap > 1) + 直接排序(gap == 1)
//希尔排序 -- 多组并排
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
//gap = gap / 2;
gap = gap / 3 + 1;//效率更快,+1的原因是使得最后一次gap == 1;进行直接插入排序 ,比如gap == 6 -- 3 -- 2 -- 1
for (int i = 0; i < n - gap; i++)
{
//1.先进行一组的排序
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end = end - gap;//x再和前面的数比，直到end < 0
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}运行结果:
2.5 时间复杂度最好:o(N) -- 基本不用挪动
最坏:F(N，gap) = (1 + 2 + 3 + ... N/gap) * gap -- gap表示被分成的组数,N/gap 表示每组大概被分为N/gap个数,通过此公式得出,gap 越大,预排序越快，预排后越不接近有序。反之,gap越小,预排序越慢,预排序越接近有序,然而希尔排序的时间复杂度的分析是非常困难的，平均时间复杂度约为o(N^1.3)
void Swap(int* px, int* py)
{
int temp = *px;
*px = *py;
*py = temp;
}
void SelectSort(int* a, int n)
{
int begin = 0;
while (begin < n-1)
{
int min = begin;
for (int i = begin; i < n; i++)
{
if (a[i] < a[min])
{
min = i;
}
}
Swap(&a[begin], &a[min]);
begin++;
}
}运行结果:
利用begin和end，遍历找到最小值放入begin位置,找到最大值放入end位置,begin++,end--,但是容易出现问题的是如果第一个为最大值,最大值与之后的最小值交换时，第一个就不为最大值了，但是end还是会和第一个交换，就会出现问题了，此时解决办法是调整交换之后的最大值的位置即可
3.4 代码void Swap(int* px,int* py)
{
int temp = *px;
*px = *py;
*py = temp;
}
//选择排序优化版
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int maxi = begin;
int mini = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] > a[maxi])
{
maxi = i;
}
if (a[i] < a[mini])
{
mini = i;
}
}
Swap(&a[begin],&a[mini]);
//begin == maxi时,最大值被换走了,修正一下maxi的位置
if (begin == maxi)
{
maxi = mini;
}
Swap(&a[end],&a[maxi]);
begin++;
end--;
}
}运行结果:
3.5 特性1.直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2.最好时间复杂度和最坏时间复杂度：o(n^2) -- 因为遍历次数分别为 n + n-2 + n-4 ....
3.空间复杂度：o(1)
4.稳定性: 不稳定
分别运用向下调整(HeapSort1)和向上调整(HeapSort2)建大根堆(升序)
4.2.1 向下调整(HeapSort1)//向下调整
void AdujustDown(int* a, int n, int parent)
{
assert(a);
int child = parent * 2 + 1;
while (child < n)
{
if (child+1 < n && a[child + 1] > a[child])
{
child++;
}
if (a[child] > a[parent])
{
Swap(&a[child],&a[parent]);
parent = child;
child = parent * 2 + 1;
}
//孩子小于父亲结点就没必要再比了，因为最大的孩子都没有父亲大
else
{
break;
}
}
}
//堆排序
void HeapSort1(int* a, int n)
{
//从最后一个分支结点开始建大堆 o(n)
int i = n - 1;
for (i = (i - 1)/2;i >= 0;i--)
{
AdujustDown(a,n,i);
}
//O(N * logn)
for (int j = n-1;j > 0;j--)
{
//第一个为最大的数，与最后一个交换，然后最后一个剔除掉，继续向下调整
Swap(&a[0],&a[j]);
AdujustDown(a,j,0);
}
}//向上调整
void AdjustUp(int* a,int n,int child)
{
assert(a);
int parent = (child - 1) / 2;
while (child > 0)//child == 0为终止条件
{
if (a[child] > a[parent])
{
Swap(&a[child],&a[parent]);
//进行下一次
child = parent;
parent = (child - 1) / 2;
}
else
{
break;//因为其他都是有序的，如果a[parent] > a[child],则不需要再进行调整
}
}
}
//向下调整
void AdujustDown(int* a, int n, int parent)
{
assert(a);
int child = parent * 2 + 1;
while (child < n)
{
if (child+1 < n && a[child + 1] > a[child])
{
child++;
}
if (a[child] > a[parent])
{
Swap(&a[child],&a[parent]);
parent = child;
child = parent * 2 + 1;
}
//孩子小于父亲结点就没必要再比了，因为最大的孩子都没有父亲大
else
{
break;
}
}
}
//堆排序(向上调整)
void HeapSort2(int* a, int n)
{
//从最后一个分支结点开始建大堆 o(n)
int i = n - 1;
for (i = (i - 1)/2;i >= 0;i--)
{
AdujustDown(a,n,i);
}
//O(N * logn)
for (int j = n-1;j > 0;j--)
{
//第一个为最大的数，与最后一个交换，然后最后一个剔除掉，继续向下调整
Swap(&a[0],&a[j]);
AdujustDown(a,j,0);
}
}运行结果:
4.3 1000000个数 向下调整(HeapSort1)和向上调整(HeapSort2)建大根堆然后排成升序的速度比较可以看出俩这速度相差不多。
4.4 特性 1. 堆排序使用堆来选数，效率就高了很多。 2. 时间复杂度： O(N*logN) 3. 空间复杂度： O(1) 4. 稳定性：不稳定 五、100000个数4种排序的速度比较欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）