网站第三方统计工具下载,lovefort表白网站制作,网站建设与制作段考试题,500m主机空间能做视频网站吗食用指南#xff1a;本文在有C基础的情况下食用更佳 #x1f525;这就不得不推荐此专栏了#xff1a;C语言 ♈️今日夜电波#xff1a;靴の花火—ヨルシカ 0:28━━━━━━️#x1f49f;──────── 5:03 … 食用指南本文在有C基础的情况下食用更佳 这就不得不推荐此专栏了C语言 ♈️今日夜电波靴の花火—ヨルシカ 0:28━━━━━━️──────── 5:03 ◀️ ⏸ ▶️ ☰ 关注点赞收藏您的每一次鼓励都是对我莫大的支持 目录
♉️一、前置知识—什么是交换排序 ♊️二、冒泡排序 冒泡排序的思想 冒泡排序的实现 ♋️三、快速排序 排序算法中的重点肥肠重要 快速排序的思想 快速排序的三种版本实现 1、hoare版本基础版本 ♒️快排的优化 2、 挖坑法 3、前后指针法 ♉️一、前置知识—什么是交换排序 交换排序的基本思想是通过比较相邻元素的大小关系如果两个相邻元素的大小关系不满足排序要求就交换它们的位置以达到排序的目的。交换排序分为两种即冒泡排序和快速排序。 ♊️二、冒泡排序 冒泡排序的思想 冒泡排序是一种基本的排序算法它的思想是将待排序的元素依次比较相邻的两个元素根据比较结果交换它们的位置从而使较大(或较小)的元素逐渐往后移动最终实现整个序列的排序。 具体的实现过程如下 1. 从序列的第一个元素开始依次比较相邻的两个元素的大小。 2. 如果前一个元素比后一个元素大或小则交换它们的位置。 3. 继续比较序列中下一个相邻的元素直至最后一个元素。 4. 重复以上操作每一轮比较都将序列中最大或最小的元素排到了序列的末尾。 5. 经过多轮比较后序列中的元素就按照从小到大或从大到小的顺序排好了。 一图理解~ 冒泡排序的实现 太简单了就不多解释了看代码即可 void BubbleSort(int* a, int n)
{for (int j 0; j n; j){bool exchange false;for (int i 1; i n-j; i){if (a[i - 1] a[i]){int tmp a[i];a[i] a[i - 1];a[i - 1] tmp;exchange true;}}if (exchange false){break;}}
} ♋️三、快速排序 排序算法中的重点肥肠重要 快速排序的思想 快速排序的基本思想是选定一个轴值将待排序序列划分为两部分一部分是小于轴值的元素一部分是大于轴值的元素。然后对于这两部分分别递归地进行快速排序直到排序完成。具体实现时可以选择待排序序列的第一个元素作为轴值通常需要进行比较选出后面会详讲也可以随机选择一个元素作为轴值然后将序列中的元素与轴值进行比较小于轴值的元素放在轴值的左边大于轴值的元素放在轴值的右边相等的元素可以放在任 一 一边最后将左右两部分序列递归地进行快速排序即可。快速排序一般有三种实现方法hoare法、挖坑法、前后指针法。 一图先有个大概的了解~ 以下的内容是循序渐进的建议大家一步一步往下看 快速排序的三种版本实现 1、hoare版本基础版本 上来请先看一张图~ 具体实现步骤如下 选择一个基准元素 key通常可以选择第一个或者最后一个元素作为基准元素这里的key值选第一个。 定义两个指针 left和 right 分别指向数组的开头和结尾。 从右向左扫描数组如果当前元素大于或等于基准元素则指针 right 向左移动一位。 从左向右扫描数组如果当前元素小于或等于基准元素则指针 left 向右移动一位。 如果 left right则交换指针所指向的元素。 当 left right 时说明当前分区操作已经完成交换基准元素和 left 指针指向的元素并返回 left 的值。 对基准元素左侧的子数组和右侧的子数组分别递归执行上述步骤直到数组长度为 1 或 0此时数组就已经排好序了。 一些注意事项 Hoare 版本的快速排序可以避免对基准元素相同的元素的不必要交换操作因此比 Lomuto 版本效率更高。 在实现时需要注意边界条件的处理尤其是数组下标越界问题。 在这里大家可能会有一个疑惑两个指针i,j相遇的位置的值如何保证要比key的值小呢 答案右边的值先走就能做到 当右侧的值先走时如果它遇到了一个比基准元素小的值那么它就会停下来等待左侧的值去找到一个比基准元素大的值。接着左侧的值找到了一个比基准元素大的值后交换左右值的位置此时右侧的值就会从原来的位置继续走下去。由于左侧的值都比基准元素小所以右侧的值再次遇到比基准元素小的值时仍然会停下来等待左侧的值交换位置。这样右侧的值先走就可以保证最后相遇的位置的值一定比基准元素的值小。 在这里大家可能会有一个疑惑了那我们能左边先走吗 当然可以同样的道理只需要key值在右边就行了 代码实现 详见代码内注释 void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}int Partsort(int* a, int left, int right)
{int key left;while (left right){//找小注意这里是右向左靠在最后会的一步将是靠向左边while (left right a[right] a[key]){--right;}//找大while (left right a[left] a[key]){left;}Swap(a[left], a[right]);//交换大于key和小于key位置的值}Swap(a[key], a[left]);//此时leftright交换key和left的值return left;//用于递归下一步的key的左半边以及右半边}void Quicksort(int* a, int begin, int end)
{if (begin end)//当下标越界时直接退出return;int key Partsort(a, begin, end);// [begin, key-1] key [key1, end] 大致形状Quicksort(a, begin, key - 1);//对左key半边进行排序Quicksort(a, key 1, end);//对右半边进行排序
}♒️快排的优化 先看个例子当我们的快排是排升序然而我们要排的数据确是一个降序时 对此快速排序有相应的优化采用“三点取中法”即在待排序序列中随机选取三个元素取中间值作为key值。这样做是为了避免选取到最大或最小值作为 key值从而导致快排算法性能下降的问题。 代码实现 详见代码内注释 void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}int Getmid(int* a, int left, int right)//三点取中值
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return right;}else{return left;}}else{if (a[mid] a[right]){return mid;}else if (a[right] a[left]){return left;}else{return right;}}
}int Partsort(int* a, int left, int right)
{int mid Getmid(a, left, right);//三点取中值优化Swap(a[left], a[mid]);//将中值放到最左边int key left;while (left right){//找小注意这里是右向左靠在最后会的一步将是靠向左边while (left right a[right] a[key]){--right;}//找大while (left right a[left] a[key]){left;}Swap(a[left], a[right]);//交换大于key和小于key位置的值}Swap(a[key], a[left]);//此时leftright交换key和left的值return left;//用于递归下一步的key的左半边以及右半边}void Quicksort(int* a, int begin, int end)
{if (begin end)//当下标越界时直接退出return;int key Partsort(a, begin, end);// [begin, key-1] key [key1, end] 大致形状Quicksort(a, begin, key - 1);//对左key半边进行排序Quicksort(a, key 1, end);//对右半边进行排序
}2、 挖坑法 上来请先看一张图~ 挖坑法的实现步骤如下 设置左指针left和右指针right以及基准元素key。 从右指针开始向左遍历数组直到找到第一个小于准元素key的元素将其填入左指针所在位置的坑中并将右指针指向左边一位。 从左指针开始向右遍历数组直到找到第一个大于准元素key的元素将其填入右指针所在位置的坑中并将左指针指向右边一位。 重复执行步骤2和步骤3直到左指针等于右指针。 将基准元素填入最后的坑中。 对基准元素左边的子数组和右边的子数组分别递归执行以上步骤直到完成排序。 一些注意事项 坑位可以是基准元素的位置也可以是左指针或右指针的位置。 在填坑的过程中需要先将当前指针指向的元素保存起来然后将其填入对应的坑中。 在左指针等于右指针时需要将基准元素填入最后的坑中。 代码实现 详见代码内注释 void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}int Getmid(int* a, int left, int right)//三点取中值
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return right;}else{return left;}}else{if (a[mid] a[right]){return mid;}else if (a[right] a[left]){return left;}else{return right;}}
}int Partsort2(int* a, int left, int right)
{int midi Getmid(a, left, right);Swap(a[left], a[midi]);int key a[left];// 保存key值以后左边形成第一个坑int hole left;while (left right){// 右边先走找小填到左边的坑右边形成新的坑位while (left right a[right] key){--right;}a[hole] a[right];hole right;// 左边再走找大填到右边的坑左边形成新的坑位while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}void Quicksort(int* a, int begin, int end)
{if (begin end)//当下标越界时直接退出return;int key Partsort2(a, begin, end);// [begin, key-1] key [key1, end] 大致形状Quicksort(a, begin, key - 1);//对左key半边进行排序Quicksort(a, key 1, end);//对右半边进行排序
}3、前后指针法 上来请先看一张图~ 前后指针法的实现步骤如下 选取基准数。可以选择数组的第一个元素、最后一个元素、中间元素等。 设置两个指针一个指向数组的第一个位置另一个指向数组的最后一个位置。 从后往前遍历找到第一个比基准数小的数停止遍历。 从前往后遍历找到第一个比基准数大的数停止遍历。 交换两个数的位置。 重复步骤3到步骤5直到前后指针相遇。 将基准数放到前后指针相遇的位置。 对基准数左右两边的子序列分别进行快速排序。 重复以上步骤直到数组被完全排序。 一些注意事项 在交换两个数的位置时如果前后指针指向的数相同那么就不能进行交换操作因为这样会导致两个数的值发生变化。同时在递归的过程中需要对子序列进行边界检查避免出现数组越界的情况。 代码实现 详见代码内注释 void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}int Getmid(int* a, int left, int right)//三点取中值
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return right;}else{return left;}}else{if (a[mid] a[right]){return mid;}else if (a[right] a[left]){return left;}else{return right;}}
}// 前后指针
int Partsort3(int* a, int left, int right)
{int midi Getmid(a, left, right);Swap(a[left], a[midi]);int prev left;//前指针从最左边开始int cur prev 1;//后指针int keyi left;while (cur right){if (a[cur] a[keyi] prev ! cur)//当后指针cur找到比key小的值时先让前指针prev让prev到交换位置因为原来比cur小1个位置再判断前指针是否更cur相等如果相等了就没有必要再交换了{Swap(a[prev], a[cur]);}cur;//继续遍历找比key值小的值}Swap(a[prev], a[keyi]);//最后交换prev与key的值return prev;//此时prev在key最终位置后续用于递归
}void Quicksort(int* a, int begin, int end)
{if (begin end)//当下标越界时直接退出return;int key Partsort3(a, begin, end);// [begin, key-1] key [key1, end] 大致形状Quicksort(a, begin, key - 1);//对左key半边进行排序Quicksort(a, key 1, end);//对右半边进行排序
} 感谢你耐心的看到这里ღ( ´ᴗ )比心如有哪里有错误请踢一脚作者o(╥﹏╥)o 给个三连再走嘛~
