江苏省建设执业网站,电商网站建设怎么样,北京空间信息传输中心,个人网站备案备注信息文章目录 一、选择排序二、堆排序三、时间复杂度四、稳定性 一、选择排序
思想#xff1a; 将数组第一个元素作为min#xff0c;然后进行遍历与其他元素对比#xff0c;找到比min小的数就进行交换#xff0c;直到最后一个元素就停止#xff0c;然后再将第二个元素min 将数组第一个元素作为min然后进行遍历与其他元素对比找到比min小的数就进行交换直到最后一个元素就停止然后再将第二个元素min再遍历以此下去直到最后一个数据 流程图 代码实现
//交换
void Swap(int* a,int* b) {int t *a;*a *b;*b t;
}
//打印
void Print(int* arr, int n) {for (int i 0;i n; i)printf(%d , arr[i]);
}
//直接选择排序
void SelectSort(int* arr, int size) {for (int i 0; i size; i){int min i;//从第一个开始//每次从i1的位置开始就不会影响到前面的了for (int j i1; j size; j) {//比较if (arr[min] arr[j])min j;//记录下标}Swap(arr[i], arr[min]);//交换}}
int main() {int arr[] { 43152};
SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
Print(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}运行结果 选择排序优化 我们可以设置一个min和一个max将小的放到左边大的放到右边我们再设置两个控制左右两边下标的变量pq当它们相遇时就结束。 流程图 特殊情况max的位置等于p时我们先交换arr[p]和arr[min],但是max指向p这个位置但是p这位置的值已经改变了这时我们就要进行纠正将maxmin这样才能成功找到原来在p位置的值 如 代码实现
//交换
void Swap(int* a,int* b) {int t *a;*a *b;*b t;
}
//打印
void Print(int* arr, int n) {for (int i 0;i n; i)printf(%d , arr[i]);
}
//优化选择排序void SelectSort1(int* arr, int size) {int p 0, q size-1;//p指向数组开头q指向数组最后一个位置while (p q) {//当错过或者相遇就结束int min p, max p;//迭代位置for (int i p; i q; i){if (arr[min] arr[i])//找到最小值min i;if (arr[max] arr[i])//找到最大值max i;}Swap(arr[min], arr[p]);//交换if (max p)//5 2 3 4 1//判断是否要纠正max min;Swap(arr[max], arr[q]);//交换p, q--;}
}
int main() {int arr[] { 4,3,1,5,2 };SelectSort1(arr, sizeof(arr) / sizeof(arr[0]));Print(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}运行结果
二、堆排序
堆 结构性:用数组表示的完全二叉树; 有序性:任一结点的关键字是其子树所有结点的最大值(或最小值) “最大堆(MaxHeap)”,也称“大顶堆”即最大值所有父亲大于等于孩子 “最小堆(MinHeap)”,也称“小顶堆”即最小值所有父亲小于等于孩子 小堆:堆顶数据是最小的并且所有节点都小于左右子树
大堆:堆顶数据是最大的 并且所有节点都大于左右子树 用堆来实现排序 1使用向下调整算法 前提左右子树必须是小堆或者大堆 作用建堆 如 左右子树对比选择再与根比较 2建堆 当我们要实现升序时通过向下调整法要建大堆 建的过程因为使完全二叉树我们可以从最后非叶点节点开始建直到没有节点就结束。 如 建大堆 找左右子树位置 树的左子树的下标等于根的下标*21的下标等于根的下标 *22 建完后我们可以将最后一个元素和第一个元素交换然后再做向下调整即可不用重新建堆了再让第一个元素和倒数第二个元素交换以此类推… 为什么不建小堆呢如果建小堆的话用第一个根最小值就是数组的第一个元素了我们不能动它那么再让数组的第二元素重新做根但是这样的话顺序就会被打破又要重新建堆了那样时间复杂度会提高如何实现降序的话可以建小堆
代码实现
//交换
void Swap(int* a,int* b) {int t *a;*a *b;*b t;
}
//打印
void Print(int* arr, int n) {for (int i 0;i n; i)printf(%d , arr[i]);
}
//向下调整 大堆
void AdjustDwon(int *arr,int p,int size) {int q p;//节点位置int z q * 2 1;//节点左子树z1就是右子树的位置了while (zsize) {//当z大于数组长度时就说明该节点不存在左右子树//判断左右子树大小后面是判断是否有右子树if (arr[z] arr[z 1]z1size)z 1;if (arr[z] arr[q]) {//判断是否比根大Swap(arr[z], arr[q]);q z;z q * 2 1;//迭代}elsebreak;}
}
void HeapSort(int* arr, int size) {//建堆size-1-1就是除2求子树公式反过来用最后减一是因为我们求的是下标for (int i (size - 1 - 1) / 2; i 0; i--) {AdjustDwon(arr, i, size);}int ned size - 1;
//最后一个下标位置开始和下标为0的元素交换一直交换下去并且交换一次就调整一次//当ned1就证明排好了while (ned0) {Swap(arr[0], arr[ned]);AdjustDwon(arr, 0, ned);//重新调整ned--;}
}int main() {int arr[] { 4,3,1,5,2 };HeapSort(arr, sizeof(arr)/sizeof(arr[0]));Print(arr, sizeof(arr) / sizeof(arr[0]));
return 0}运行结果
三、时间复杂度
选择排序 n-1 ,n-2…21 是一个等差数列求前n-1项和粗略来算就是n^2 所以时间复杂度为On^2
堆排序 建堆On 向下调整的时间复杂度为 假设树高为 h树的结点为n因为n2^h-1,那么hlogn-1以2为底 所以为O(logn-1) 我们还要进行n次这个向下调整当然在进行的过程中n是会变化的 那么总的次数nnlogn 所以时间复杂度为Onlogn
四、稳定性
稳定性: 假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[4]且r[1]在r[4]之前而在排序后的序列中r[1]仍在r[4]之前则称这种排序算法是稳定的;否则称为不稳定的。 选择排序不稳定 如 堆排序不稳定 第一个9直接到最后了
以上就是我的分享了如果有什么错误欢迎在评论区留言。 最后谢谢大家的观看
