衡水seo_衡水网站建设-燕丰收,物业管理系统业务流程图,小困网络科技泰安有限公司,网站建设设计 网络服务选择排序 1. 直接选择排序2. 堆排序2.1 堆2.2 堆的实现#xff08;以大根堆为例#xff09;2.3 堆排序 3. 堆排序#xff08;topK问题#xff09; 1. 直接选择排序 思想 以排升序为例。以a[i]为最大值#xff08;或最小值#xff09;#xff0c;从a[i1]到a[n-1-i]比较选… 选择排序 1. 直接选择排序2. 堆排序2.1 堆2.2 堆的实现以大根堆为例2.3 堆排序 3. 堆排序topK问题 1. 直接选择排序 思想 以排升序为例。以a[i]为最大值或最小值从a[i1]到a[n-1-i]比较选出最大值放在a[n-1-i]或最小值放在a[i]。简单讲就是将以每轮排序的第一个数作为最大值或者最小值比较剩余的元素得到最大值或者最小值将最大值放在剩余数据的最后一位最小值放在剩余数据的第一位。 升级版 以排升序为例。每轮排序中选出最大值和最小值分别放在数据的左右两端。 例子排升序 代码实现
//选择排序以排升序为例
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void SelectSort(int* a, int n)
{int left 0;int right n - 1;while (left right){int maxi left, mini left;for (int i left 1; i right; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}Swap(a[maxi], a[right]);//这里要考虑特殊情况如果最小值miniright那么在交换maxi和right后//最小值就发生改变所以要最小值的下标要改变。if (mini right){mini maxi;}Swap(a[mini], a[left]);right--;left;}
}算法分析 时间复杂度 假设有n个元素第一次排序要遍历n-2个元素第二次排序要遍历n-4个元素往后每次排序的元素个数都减2总的遍历次数是等差数列的前n项和所以时间复杂度是ON^2。 空间复杂度 空间复杂度是O1。 稳定性 是不稳定的排序。如上面的例子中的12在选出最大值和最小值时前后顺序发生改变。 注意 直接选择排序的最好情况和最坏情况的时间复杂度都是ON^2。 2. 堆排序
2.1 堆 概念 堆其实是一种树形结构分为大根堆和小根堆。大根堆是树中所有父节点大于子节点小根堆是树中所有父节点小于子节点。但父节点的左右孩子谁大谁小没有要求。 预备知识 1堆的逻辑结构是树物理结构是数组即在内存中以数组的形式存储。
2父节点和子节点的关系 已知子节点下标它的父节点下标parent child - 1/2。 已知父节点下标它的子节点下标leftchild parent * 2 1rightchild parent * 2 2。 3种存储结构只适用于满二叉树和完全二叉树否则会浪费很多空间。
2.2 堆的实现以大根堆为例
堆的定义
//堆的实现
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;//用来申请空间int size;//记录当前堆的元素个数int capacity;//记录当前堆的最大容量
};堆的初始化
//堆的初始化
void HeapInit(HP* ph)
{assert(ph);ph-a (HPDataType*)malloc(sizeof(HPDataType)*10);//初始化容量设置为10if (ph-a NULL){perror(malloc failed);return;}ph-capacity 10;ph-size 0;
}入堆
//入堆
void HeapPush(HP* ph, HPDataType x)
{assert(ph);//首先要检查堆是否已满if (ph-size ph-capacity){HPDataType* tmp (HPDataType*)realloc(ph-a, sizeof(HPDataType) * ph-capacity * 2);if (tmp NULL){perror(realloc failed);return;}ph-a tmp;ph-capacity * 2;//每次容量不够时扩容两倍}ph-a[ph-size] x;//因为要实现大根堆如果入堆元素大于前面的元素就要把它向上调整。AdjustUp(ph-a, ph-size - 1);//第一次参数是要调整的数据元素第二个参数是入堆元素的下标。
}向上调整
//向上调整
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}
void AdjustUp(HPDataType* a, int child)
{//得到父节点的下标int parent (child - 1) / 2;while (child 0)//当子节点爬到下标为0的位置就达到顶部了此时可以停止循环{//比较父节点和子节点谁大谁上去//让大的节点不断往上爬if (a[chil] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}出堆 疑惑 1 出堆其实就是弹出根节点。但我们要考虑弹出根节点后后面的数据要如何处理将数据往前移动这样数据间的关系就全乱了且所有数据往前移效率低O(N^2)。 正确的做法是交换堆顶元素和最后一个元素然后删除最后一个元素然后将堆顶元素向下调整。 2 为什么要弹出根节点弹出最后一个元素岂不是更简单这就涉及到堆的应用。我们所写的是大根堆根结点是这组数据的最大值弹出根节点后向下调整可以得到次大值然后再弹出根节点。就这样我们就得到这组数据的前n个最大值比如得到年纪前50名得到产品销量前100名。由此可见弹出根结点是非常有用的。 代码实现
//堆空
bool HeapEmpty(HP* ph)
{assert(ph);return ph-size 0;
}//出堆
void HeapPop(HP* ph)
{assert(ph);//首先判断堆是否为空assert(!HeapEmpty(ph));//交换堆顶元素和最后一个元素Swap(ph-a[0], ph-a[ph-size - 1]);//删除最后一个元素ph-size--;//向下调整AdjustDown(ph-a, ph-size, 0);//第一个参数是要调整的数据第二个参数是数据的个数第三个参数是要调整的位置
}向下调整
//向下调整条件左右子树都是大根堆或者小根堆
void AdjustDown(HPDataType* a, int n, int parent)
{int child 2 * parent 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 2 * parent 1;}else{break;}}
}堆顶
//堆顶
HP* HeapTop(HP* ph)
{assert(ph);//首先判断堆是否为空assert(!HeapEmpty(ph));return ph-a[ph-size - 1];
}打印前K个元素
//打印前K个元素
void PrintK(HP* ph, int k)
{while (!HeapEmpty(ph) k--){printf(%d , HeapTop(ph));HeapPop(ph);}printf(\n);
}销毁
//销毁
void HeapDestroy(HP* ph)
{assert(ph);free(ph-a);ph-a 0;ph-capacity 0;ph-size 0;
}2.3 堆排序
了解堆的基本操作后就可以实现堆排序。
//法一
//堆排序以排升序为例
void HeapSort(int* a, int n)
{//建堆大根堆或者小根堆for (int i 1; i n; i){AdjustUp(a, i);//从下标为1的元素不断插入从而向上调整}//建大根堆后就交换根结点和最后一个元素每次交换都将最大值放在数据的最后面int end n - 1;while (end 0){Swap(a[end], a[0]);//交换最大值和最后一个元素AdjustDown(a, end, 0);//交换后最后一个元素不参与调整所有元素个数只有end个//每次调整后都会将最大值放在根节点的位置--end;}
}//法二
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[end], a[0]);AdjustDown(a, end, 0);--end;}
}时间复杂度 这两种方法唯一的不同就是法一前面是向上调整法二前面是向下调整。要比较两种方法的时间复杂度就得比较向下调整和向上调整的时间复杂度。 向下调整的时间复杂度是ON 向上调整的时间复杂度是ONlogN 咋一看好像第二种方法时间复杂度更牛但实际上这两种方法的时间复杂度都是ONlogN。我们讨论的只是向下调整和向上调整。 总的来说堆排序的时间复杂度是ONLogN。两种方法都在这个量级但第二种方法稍微高一点点。 3. 堆排序topK问题
找出N个数中最大的或最小的前K个数。 有两种方法 法一建N个大根堆然后PopK次就可以。 法二建有K个数的小根堆遍历剩下的数据如果数据比堆顶元素大就替换它然后向下调整最后这个小根堆的数据就是最大的前K个。 这里主要用法二
void PrintTopK(const char* file, int k)
{//首先要建立小根堆int* topk (int*)malloc(sizeof(int) * k);if (topk NULL){perror(malloc failed);return;}//从文件中读取K个数据FILE* f fopen(file, r);if (f NULL){perror(fopen failed);return;}for (int i 0; i k; i){fscanf(f, %d, topk[i]);}//建小堆之前写的向下调整是调整大根堆只需修改其中一些或者即可for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(topk, k, i);}//将剩下的n-k个元素依次与根节点比较比它大就入堆且向下调整//这样将大的元素往下沉小的元素不断换掉最终只剩下最大的K个元素int val 0;int ret fscanf(f, %d, val);while (ret ! EOF){if (val topk[0]){topk[0] val;AdjustDown(topk, k, 0);}ret fscanf(f, %d, val);}for (int i 0; i k; i){printf(%d , topk[i]);}fclose(f);
}
void CreateData()
{int n 1000;srand(time(0));const char* file TestData.txt;FILE* f fopen(TestData.txt, w);//以写的形式打开if (f NULL){perror(fopen fail);return;}for (int i 0; i n; i){int x rand() % 1000;//获得0~999的数字fprintf(f, %d , x);}fclose(f);
}
