互动网站欣赏,二维码制作工具网页,asp企业营销型网站建设,网店货源目录
前言#xff1a;
1.排序的概念及其运用
1.1排序的概念
1.2排序运用
1.3 常见的排序算法
2.常见排序算法的实现 2.1 堆排序
2.1 1 向下调整算法
2.1 2 建堆
2.1 3 排序
2.2 插入排序 2.1.1基本思想#xff1a;
2.1.2直接插入排序#xff1a;
2.1.3 插…目录
前言
1.排序的概念及其运用
1.1排序的概念
1.2排序运用
1.3 常见的排序算法
2.常见排序算法的实现 2.1 堆排序
2.1 1 向下调整算法
2.1 2 建堆
2.1 3 排序
2.2 插入排序 2.1.1基本思想
2.1.2直接插入排序
2.1.3 插入排序实现
2.3 希尔排序
2.4 选择排序 2.4.1基本思想
2.4.2 直接选择排序:
2 .4.3 选择排序实现 前言 当我们学到数据结构时就无法避开算法排序是一类常见且常用的算法在日常生活中我们在网上购物筛选价格时用到了排序查看该商品销量的高低时用到了排序而这些功能都是我们程序员使用排序算法将其转化成代码实现的。既然排序如此重要我们当然要好好把排序学好了。
1.排序的概念及其运用
1.1排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。内部排序数据元素全部放在内存中的排序。外部排序数据元素太多不能同时放在内存中根据排序过程的要求不断地在内外存之间移动数据的排序。
1.2排序运用 排序的重要性在前面我们已经讲解在这里就不再过多赘述。 1.3 常见的排序算法 在学习排序算法之前我们应该了解常见的排序算法有哪些排序一般分为插入排序选择排序交换排序归并排序而细分的话可以分成下面的样子 2.常见排序算法的实现 2.1 堆排序 堆排序我们在学习二叉树堆时已经讲过了将它放在这里一是复习一遍堆排序二是将这些排序都总结在一起方便我们查看。堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 简单来说堆排序的算法就是先建一个堆如果我们要排升序就建大堆将堆最大的那个数——也就是根节点中的那个数与堆尾交换这样最大的数就排到最后一位了此时的数组已经不是堆了我们使用向下调整算法重新建堆这样数组中第二大的数就在根结点中了我们再将它和堆倒数第二个位置的数交换这样第二大的数就在数组倒数第二的位置了像这样一种走到根节点我们也就完成了排序的操作。 2.1 1 向下调整算法 第一个双亲结点默认是数组中下标为0的位置我们需要算出它的孩子结点而公式也个很简单双亲*21就是这个结点的左孩子双亲*22就是这个结点的右孩子。假设我们建的是大堆双亲结点比孩子结点小就交换我们默认这棵树是完全二叉树所以大多数结点都有两个孩子我们需要选出两个孩子结点中大的那个与双亲结点交换位置交换完就刷新双亲结点和子节点的下标而前提是两个结点都在数组中所以有
int child parent * 2 1;
//假设左孩子就是要交换的那个孩子
if (child 1 n a[child 1] a[child])
{child;
}
//如果某个结点比左孩子小而右孩子比左孩子大
//就让该节点的右孩子与自己交换位置 我们设置一个循环如果某个结点的孩子的下标大于等于n说明我们已经完成了交换就不进入循环如果发现这是一个堆就跳出循环
void AdjustDown(int* a, size_t n, int parent)
{int child parent * 2 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[parent] a[child]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}}
2.1 2 建堆 给我们一组无序的数字我们采用从后往前向下调整的方法来建堆。如果我们将这组数据看成完全二叉树除了叶子结点其余的结点都有孩子也就是说有几个有孩子结点的结点这组数据中就有几棵树我们可以从最后一个有孩子结点的结点开始使用向下调整算法当走到这棵树的根节点时就将堆建好了 例如这棵树从9这个结点开始往前都可以组成一棵树而如何得到呢这个也很简单我们只需要反转计算孩子结点的公式得到计算双亲结点的公式为孩子-1÷ 2 假设这棵树有n个结点这棵树的尾结点为n-1所以假设我们要得到9这个结点公式为n-1-1÷2。
得到代码
for (int i (size - 1 - 1) / 2; i 0; i--)
{AdjustDown(a, size, i);
}
2.1 3 排序 建好堆之后我们就可以排序了按前面讲的排得到代码
//定义一个end方便交换每次交换完往前走一步
int end size - 1;
//size为数组大小
while (end 0)
{Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;
} 堆排序完整代码
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void AdjustDown(int* a, size_t n, int parent)
{int child parent * 2 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[parent] a[child]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}} 我们定义一个数组给一些数测数一下
int a[] { 454,24,34,43543,676,67,676,23,1,0 };
size_t size sizeof(a) / sizeof(int);
HeapSort(a, size);
for (int i 0; i size; i)
{printf(%d , a[i]);
} 可以看到一个有序的数组就完成了。
2.2 插入排序 2.1.1基本思想
直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。
实际中我们玩扑克牌时就用了插入排序的思想 2.1.2直接插入排序
当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 直接插入排序的特性总结 1. 元素集合越接近有序直接插入排序算法的时间效率越高 2. 时间复杂度O(N^2) 3. 空间复杂度O(1)它是一种稳定的排序算法 4. 稳定性稳定
2.1.3 插入排序实现 我们定义一个end在end下标及end之前下标的数都是有序的数依次从end之后取数据来插入end之前如果我们要排升序我们从end1开始取数据存起来只要这个数小于end就让end覆盖end1然后让end向前走一位直到这个数比end下标的数大或者等于这个数我们让end往前走一位然后将这个数插入到end1的位置。以上是一轮插入要实现插入排序需要让end走遍整个数组而每次插入都只插入一个数假设某个数据为n那么当执行完endn-2时这个数组也就有序了代码展示
void InsertSort(int* a, size_t n)
{int end;int tmp;for (int i 0; i n - 1; i){end i;tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}}
我们准备一个无序数组调用插入排序
int a[] { 9,8,7,6,5,4,3,2,4,5,98,43,67,879,4543,687686,676,1,0 };
size_t size sizeof(a) / sizeof(a[0]);
InsertSort(a, size);
来看结果 调用插入排序后这个数组就被排成了升序。
2.3 希尔排序 希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。本质上希尔排序是对插入排序的优化。 先对一组数进行预排序再对这组数据进行插入排序这就是希尔排序。而上面的操作就是对这组数据进行预排序预排序可以让一个很大或者很小的数更快走到它排序之后的位置假如gap5我们需要排升序整个数组中最大的数只需要走两次就可以走到最后一个位置。事实上插入排序就是希尔排序当gap为1时一个数一次只能走1步。因此我们得出gap越大大数越快走到后面小数越快走到后面越不接近有序。为什么呢因为当gap1时执行这个程序该组数据就有序了所以gap越小大数越满走到后面小数越慢走到前面数组却越接近有序。
希尔排序的特性总结 1. 希尔排序是对直接插入排序的优化。 2. 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 3. 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些书中给出的希尔排序的时间复杂度都不固定 数据结构-用面相对象方法与C描述》--- 殷人昆 4.稳定性不稳定
2.4 选择排序 2.4.1基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。
2.4.2 直接选择排序:
1在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素 2若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换 3在剩余的array[i]--array[n-2]array[i1]--array[n-1]集合中重复上述步骤直到集合剩余1个元素 2 .4.3 选择排序实现 在我们的介绍中选择排序就是我们多次遍历一个数组如果要排升序那么第一次遍历出来最小的数放到第一位第二次遍历出来最小的数放到第二位依次遍历完整个数组就完成了排序。我们可以对其优化一下定义一个max和min也就是每一次遍历都选出最小的数和最大的数最小的数放在最前面最大的数放在最后面依次执行像这样优化的速度是普通选择排序的2倍。 定义一个起始位置的下标begin和末尾位置的下标end接着是max和min从begin1的位置开始往前走让maxmin下标的数与整个数组的其他数比较只要有比max大的数就让那个数成为max只要有比min小的数就让这个数成为min遍历完一遍后让begin下标的数和min下标的数交换接着让end下标的数和max下标的数交换这样最大的数和最小的数都排好了让begin往前走一步end往后走一步做完这些后让max和min重新从begin们开始走代码实现
void SecletSort(int* a, size_t n)
{int begin 0, end n - 1;int maxi begin;int mini begin;while (begin end){mini begin;maxi begin;for (int i begin 1; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}Swap(a[mini], a[begin]);if (begin maxi)maxi mini;Swap(a[maxi], a[end]);begin;end--;}} 依旧是一组无序的数调用选择排序
int a[] { 9,8,7,6,5,4,3,2,4,5,98,43,67,879,4543,687686,676,1,0 };
size_t size sizeof(a) / sizeof(a[0]);
SecletSort(a, size);
来看结果 选择排序也没有任何问题将一组无序数排成升序。
未完待续。。。。。。
