网站开发与设计维护的收费标准,郑州市网络科技有限公司,莱芜民生网站,苏州seo排名优化目录
1 - 选择排序
1.1 - 基本思想
1.2 - 直接选择排序
1.2.1 - 代码实现
1.3 - 堆排序
1.3.1 - 代码实现 1 - 选择排序
1.1 - 基本思想
每一次从待排序的数据元素中选出最小(或最大)的一个元素#xff0c;存放在序列的起始位置…目录
1 - 选择排序
1.1 - 基本思想
1.2 - 直接选择排序
1.2.1 - 代码实现
1.3 - 堆排序
1.3.1 - 代码实现 1 - 选择排序
1.1 - 基本思想
每一次从待排序的数据元素中选出最小(或最大)的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。
1.2 - 直接选择排序
在元素集合arr[i] -- arr[n - 1]中选择关键码最大(或最小)的数据元素若它不是这组元素中的最后一个(或第一个)元素则将它与这组元素中的最后一个(或第一个)元素交换在剩余的arr[i] -- arr[n - 2] (arr[i 1] -- arr[n - 1]) 集合中重复上述步骤直到集合剩余1个元素 直接选择排序的特性总结
好理解但效率不是很好实际中很少使用时间复杂度空间复杂度稳定性不稳定
1.2.1 - 代码实现
#define _CRT_SECURE_NO_WARNINGS 1#includestdio.h
#includestdlib.h
#includestdbool.h// 交换
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}// 打印
void PrintArray(int* a, int n)
{for (int i 0; i n; i)printf(%d , a[i]);printf(\n);
}// 选择排序
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int maxi begin, 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]);// 如果maxi和begin重叠修正一下即可if (begin maxi){maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
}void TestSelectSort()
{int a[] { 9, 2, 6, 1, 7, 3 ,0, 5, 8, 4 };PrintArray(a, sizeof(a) / sizeof(int));SelectSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestSelectSort();return 0;
} 1.3 - 堆排序 堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 堆排序特性总结
堆排序用堆来选数效率较高时间复杂度空间复杂度稳定性不稳定
1.3.1 - 代码实现
#define _CRT_SECURE_NO_WARNINGS 1#includestdio.h
#includestdlib.h
#includestdbool.h// 交换
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}// 打印
void PrintArray(int* a, int n)
{for (int i 0; i n; i)printf(%d , a[i]);printf(\n);
}// 堆排序
void AdjustUp(int* a, int child)
{int father (child - 1) / 2;while (child 0){if (a[child] a[father]){Swap(a[child], a[father]);//更新下标child father;father (father - 1) / 2;}else{break;//一旦符合小堆了就直接退出}}
}void AdjustDown(int* a, int n, int parent)
{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 HeapSort(int* a, int n)
{// 建大堆for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}void TestHeapSort()
{int a[] { 9, 2, 6, 1, 7, 3 ,0, 5, 8, 4 };PrintArray(a, sizeof(a) / sizeof(int));HeapSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestHeapSort();return 0;
} 感谢大佬们的支持
互三啦
