为什么要做一个营销型网站,WordPress文章预览篇幅,wordpress站长邮箱,广州网站建设q.479185700強1. 排序的概念
排序是一种常见的算法概念#xff0c;用于将一组数据按照特定的顺序进行排列。排序算法的目的是将一组数据按照递增或递减的顺序重新排列。常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。排序算法的选择通常取决于数据规模、数据分布…1. 排序的概念
排序是一种常见的算法概念用于将一组数据按照特定的顺序进行排列。排序算法的目的是将一组数据按照递增或递减的顺序重新排列。常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。排序算法的选择通常取决于数据规模、数据分布和性能需求等因素。排序算法在计算机科学中具有非常重要的地位被广泛应用于各种领域和问题的解决中。
1.1 稳定性的概念
在排序里面有一个非常重要的概念那就是稳定性。
简单来说就是排序结束后相同的数之间的相对位置关系不会发生改变。
比如如果有一个包含学生信息的列表需要按照学生的分数进行排序但是分数相同的学生可能会有不同的其他信息比如姓名、年龄等如果排序算法是稳定的那么相同分数的学生在排序后仍然保持着原本的顺序这对于保持其他信息的相对顺序是非常有用的。
2. 常见的排序算法 以上这张图里面的就是我们接下来要实现的一些排序法。同时他们又因为不同的排序方法分为不同的类别比如说常见的插入排序直接插入排序希尔排序选择排序选择排序堆排序和交换排序快速排序冒泡排序等等。
3. 插入排序
插入排序是一种简单直观的排序算法其基本思想是将一个数据插入到已经排好序的数据序列中从而逐步构建有序序列。
3.1直接插入排序
void InsertSort(int* a, int n)
{for (int i1;in;i){int end i-1;int tmp a[i];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}else{break;}a[end 1] tmp;}}
}
函数接受两个参数一个是整数指针 a 表示要排序的数组另一个是整数 n 表示数组的长度。通过一个 for 循环从数组的第二个元素开始索引为 1依次将每个元素插入到已排序的部分。在每次循环中 end 表示当前要比较的位置初始值为当前元素的前一个位置还定义了一个变量 tmp 保存当前要插入的元素值。然后通过一个 while 循环只要 end 大于等于 0 并且当前要插入的元素 tmp 小于 a[end] 就将 a[end] 向后移动一位a[end 1] a[end]同时 end 向前移动一位end--。当找到合适的位置tmp a[end]时就将 tmp 插入到该位置后面a[end 1] tmp。类似于抓了一把扑克牌然后从左往右排序
直接插入排序的特性总结 1. 元素集合越接近有序直接插入排序算法的时间效率越高 2. 时间复杂度 O(N^2) 3. 空间复杂度 O(1) 它是一种稳定的排序算法 4. 稳定性稳定 3.2 希尔排序
希尔排序是一种插入排序的改进版本也称为缩小增量排序。它是由美国计算机科学家希尔Donald Shell于1959年提出的。希尔排序的基本思想是将待排序的元素分成若干个子序列对每个子序列进行插入排序然后逐步缩小子序列的长度最终整个序列变成有序。
void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap / 2;for (int i 0; i n - gap; i){int end i ;int tmp a[igap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}a[endgap] tmp;}}}
}
首先通过一个 while 循环只要 gap 大于 1 就将 gap 不断除以 2 来调整步长。对于每次确定的 gap 值通过一个 for 循环从索引 0 开始对每隔 gap 个位置的元素进行插入排序的操作。在每次的插入排序过程中 end 为当前要比较的位置初始值为 i tmp 保存当前要插入的元素值即 a[i gap] 。通过一个 while 循环只要 end 大于等于 0 并且当前要插入的元素 tmp 小于 a[end] 就将 a[end] 向后移动 gap 个位置a[end gap] a[end]同时 end 向前移动 gap 个位置end - gap。当找到合适的位置tmp a[end]时就将 tmp 插入到该位置后面a[end gap] tmp。 有点类似于这张图然后通过减小gap来达到渐渐有序。这样做有一个好处就是大的数可以快速的跳到后面不用慢慢的一个一个向后调整 希尔排序就是通过这样的方式来实现优化。
PS:我们可以把直接插入排序理解为gap恒定为1的希尔排序。
4. 选择排序
4.1 选择排序
void SelectSort(int* a, int n)
{int left 0;int right n - 1;while (left right){int mymin left;int mymax left;for (int i left 1;i n; i){if (a[i] a[mymin]){mymin i;}if (a[i] a[mymax]){mymax i;}}Swap(a[left], a[mymin]);if (left mymax){mymax mymin;}Swap(a[right], a[mymax]);left;right--;}
}
首先定义了两个变量 left 和 right 分别表示数组的起始位置和结束位置。在 while 循环中只要 left 小于 right 就执行以下操作:在每次循环中先假设 left 位置的元素是最小的mymin left和最大的mymax left。然后通过一个 for 循环从 left 1 位置开始遍历数组找到当前最小元素的位置 mymin 和最大元素的位置 mymax 。接下来交换 left 位置和 mymin 位置的元素。如果此时 left 等于之前的 mymax 则更新 mymax 的值为 mymin 。再交换 right 位置和 mymax 位置的元素。最后将 left 向右移动一位right 向左移动一位。
PS简单来说我们可以想象现在我们手上有一把扑克牌然后我们一眼扫过去把最大和最小的依次放入左边和右边这就是这个选择排序的逻辑。 1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用 2. 时间复杂度 O(N^2) 3. 空间复杂度 O(1) 4. 稳定性不稳定 4.2 堆排序
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--;}
}
首先通过一个 for 循环从数组中间位置开始向前i (n - 1 - 1) / 2对每个非叶子节点调用 AdjustDown 函数进行调整构建一个大根堆。然后将堆顶元素即最大元素与最后一个未排序的元素交换位置并对堆顶元素重新调用 AdjustDown 函数进行调整使剩余元素仍保持大根堆的性质。这个过程一直持续到整个数组都被排序通过 end 从数组末尾逐渐向前移动来控制。
PS:在i(n-1-1)/2里面第一个 -1是为了获取最后一个元素的索引第二个-1是因为根据父节点公式 (子节点索引-1)/2计算该元素的父节点索引所以这里才会-1-1同时这是为了区分即更好的理解这段代码。
PS:这里面的这个while我们可以理解为堆本身的一种缺陷因为他不像AVL树红黑树那样即大的往右边小的往左边所以需要用到这里面的while。 1. 堆排序使用堆来选数效率就高了很多。 2. 时间复杂度 O(N*logN) 3. 空间复杂度 O(1) 4. 稳定性不稳定 5. 交换排序
5.1 冒泡排序
这个冒泡排序一般来说是我们学习的第一个排序算法。他非常的容易理解同时他的代码也容易实现。简单来说这个代码写起来的逻辑就像是水里面的泡泡一样小的上浮大的下沉。
void BubbleSort(int* a, int n)
{for (int j 0; j n; j){int ex 1;for (int i 0; i n - j-1; i){if (a[i] a[i 1]){Swap(a[i], a[i 1]);ex 0;}}if (ex 1)break;}
}
外层的 for 循环控制排序的轮数一共进行 n 轮。在每一轮中初始化一个标志变量 ex 为 1表示假定这一轮不需要交换元素数组已经有序。内层的 for 循环用于比较相邻的元素如果前一个元素大于后一个元素就交换它们的位置并将 ex 置为 0表示这一轮进行了交换操作。每一轮结束后如果 ex 仍然为 1说明在这一轮中没有进行交换即数组已经完全有序此时通过 break 语句提前结束排序。
PS:ex是我加的一种优化并不是必须的。
冒泡排序的时间复杂度是O(n^2)相对较低效特别是在对大量数据进行排序时。然而冒泡排序是一种容易实现和理解的算法适用于小规模数据的排序。 1. 冒泡排序是一种非常容易理解的排序 2. 时间复杂度 O(N^2) 3. 空间复杂度 O(1) 4. 稳定性稳定 5.2 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 三数取中法选key int ChooseMid(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 left;}else{return right;}}else{if (a[left] a[right])return left;else if(a[mid]a[right]){return mid;}else{return right;}}
}首先计算区间的中间位置 mid 。然后通过比较区间左右端点和中间点的值来确定返回哪个位置的索引作为中间值的索引。如果 a[left]a[mid] 再判断 a[mid] 和 a[right] 的大小。如果 a[mid]a[right]返回 mid 如果 a[left]a[right]返回left否则返回right。如果 a[left]a[mid]同样再判断 a[left] 和 a[right] 的大小。如果 a[left]a[right] 返回 left 如果 a[mid]a[right]返回mid否则返回right。 PS:这个函数是为了取出一个不是最大或者最小的值因为max或者min的值会影响快速排序的效率。 5.2.1 Hoare版快速排序 void QuickSort1(int* a, int left, int right)
{if (left right)return;int begin left;int end right;int keyi ChooseMid(a, left, right);Swap(a[keyi], a[left]);while (left right){while(a[right] a[begin]leftright){--right;}while(a[left] a[begin]leftright){left;}Swap(a[left], a[right]);}Swap(a[begin], a[left]);keyi left;
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi 1, end);
} 首先检查区间的起始位置 left 是否大于等于结束位置 right 如果是则直接返回因为这种情况不需要排序。然后初始化起始和结束位置的变量 begin 和 end 通过 ChooseMid 函数选择一个 keyi 并将keyI与起始位置的元素交换。接下来通过两个 while 循环从右向左找到小于keyi从左向右找到大于keyi然后交换它们的位置直到左右指针相遇。相遇后将keyi与当前指针位置的元素交换确定keyi 的最终位置 。最后对keyi左右两侧的子区间分别递归调用 QuickSort1 函数进行排序。 PS:我个人认为Hoare版本的快速排序挺简单的也好理解,个人比较推荐掌握这种。 我们把这个快速排序递归部分具体出来就是这个样子通过这种方式来把它变的有序。 5.1.2 挖坑法版快速排序 void QuickSort2(int* a, int left, int right)
{if (left right)return;int begin left;int end right;int keyi ChooseMid(a, left, right);Swap(a[keyi], a[left]);int hole begin;int key a[hole];while (left right){while (a[right] key left right){--right;}a[hole] a[right];hole right;while (a[left] key left right){left;}a[hole] a[left];hole left;}//Swap(stay, a[left]);//keyi left;a[hole] key;keyi hole;QuickSort2(a, begin, keyi - 1);QuickSort2(a, keyi 1, end);
} 首先如果区间的起始位置 left 大于等于结束位置 right 则直接返回因为这种情况不需要排序。然后初始化起始和结束位置的变量 begin 和 end 通过 ChooseMid 函数选择一个基准元素的索引 keyi 并将基准元素与起始位置的元素交换。接着定义一个变量 hole 并初始化为起始位置同时记录基准元素的值 key 。通过两个 while 循环从右向左找到小于key的值将其放到 hole 位置更新 hole 为当前的右指针位置从左向右找到大于基准元素的值将其放到 hole 位置更新 hole 为当前的左指针位置简单来说就是先右边找比key小的找到后给他放到key的位置然后key变到右边接着左边找比key小的再换给已经到右边的key最后循环往复。循环结束后将key放到 hole 位置确定基准元素的最终位置 keyi 。最后对key左右两侧的子区间分别递归调用 QuickSort2 函数进行排序。 5.1.3 前后指针版快速排序 void QuickSort3(int* a, int left, int right)
{if (left right)return;int begin left;int end right;int keyi ChooseMid(a, left, right);//int keyi left;Swap(a[keyi], a[left]);int first left;int second left 1;while (second right){if (a[second] a[keyi]first!second){//first;Swap(a[first], a[second]);}second;}Swap(a[keyi], a[first]);keyi first;QuickSort3(a, begin, keyi - 1);QuickSort3(a, keyi 1, end);
}如果左边的位置大于等于右边就不排序直接返回。先记录下开始和结束的位置选一个基准元素并和左边的元素交换。然后设两个指针一个从左边开始另一个从左边下一个位置开始。在一个循环里如果第二个指针second指向的元素小于基准元素并且两个指针位置不同(因为同一位置交换没有意义就交换它们指向的元素两个指针再移动。如果second指向的元素比keyi大那就不走if语句直接加加second。循环完后把基准元素和第一个指针指向的元素交换确定基准位置。最后对keyi两边的子区间再分别进行同样的排序操作。 5.3 快速排序非递归版 我们之所以要学习非递归版本的是因为递归版本的快速排序在面对大数量级的时候容易造成栈溢出从而导致错误所以我们要学习非递归版本的快速排序。 int PartSort3(int* a, int left, int right)
{int midi GetMidNumi(a, left, right);if (midi ! left)Swap(a[midi], a[left]);int keyi left;int prev left;int cur left 1;while (cur right){if (a[cur] a[keyi] prev ! cur)Swap(a[cur], a[prev]);cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
}void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(st);STPush(st, right);STPush(st, left);while (!STEmpty(st)){int begin STTop(st);STPop(st);int end STTop(st);int keyi PartSort3(a, begin, end);if (keyi 1 end){STPush(st, end);STPush(st, keyi 1);}if (begin keyi - 1){STPush(st, keyi - 1);STPush(st, begin);}}STDestroy(st);
} PartSort3 函数前后指针版快速排序只不过去掉了递归。 QuickSortNonR 函数实现非递归的快速排序。首先创建一个栈 st 并初始化将排序区间的左右边界压入栈。在循环中取出栈顶的两个值作为当前排序区间的起止位置调用 PartSort3 进行部分排序得到基准索引。若基准右边区间可继续划分将右边新的区间边界压入栈若基准左边区间可继续划分将左边新的区间边界压入栈。循环结束后销毁栈。 PS:其实本质这就是通过栈来进行一种对递归的模拟实现。 6. 归并排序 void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)return;int mid (begin end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid1, end, tmp);int begin1 begin; int end1 mid;int begin2 mid 1;int end2 end;int i begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}for (int i 0; i end-begin1; i){a[ibegin] tmp[ibegin];}
}void MergeSort(int*a,int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}_MergeSort 函数用于对数组的指定区间进行归并排序的核心操作。如果起始位置大于等于结束位置函数直接返回。通过计算中间位置对左右子区间分别递归调用 _MergeSort 进行排序。然后通过循环比较两个子区间的元素将较小的元素依次放入临时数组 tmp 中。当其中一个子区间遍历完后将另一个子区间剩余的元素放入 tmp 。最后将 tmp 中的元素复制回原数组。MergeSort 函数用于对外提供归并排序的接口。首先分配一个与原数组大小相同的临时空间 tmp 如果分配失败则报错并返回。然后调用 _MergeSort 对整个数组进行排序排序完成后释放临时空间。 PS其实他的本质就是分成一块一块然后进行小区间排序然后小块合并再进行小区间排序最后达到有序。 6.1 归并排序非递归版 void _MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){int begin1 i;int end1 i gap - 1;int begin2 i gap;int end2 i 2 * gap - 1;int j i;if (end1 n || begin2 n){break;}if (end2 n){end2 n - 1;}while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}int k begin1;memcpy(a i, tmp i, sizeof(int)*(end2 - i 1));}gap * 2;}free(tmp);
}void MergeSort(int*a,int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}MergeSortNonR(a,n);free(tmp);
} 首先分配一个与原数组大小相同的临时数组tmp用于辅助排序。然后通过一个循环不断增加归并的子数组大小gap每次循环对数组进行分组归并。对于每个分组确定两个子数组的起始和结束位置然后比较并合并两个子数组到tmp中最后将tmp中的排序结果复制回原数组。当gap小于数组长度n时不断重复这个过程。MergeSort函数主要用于分配临时空间调用_MergeSortNonR进行排序最后释放临时空间。 PS:非递归版的归并排序在代码实现的部分要格外注意边界处理。 7. 计数排序 void CountSort(int* a, int n)
{int max a[0];int min a[0];for (int i 0; i n; i){if (max a[i]){max a[i];}if (min a[i]){min a[i];}}int range max - min 1;int* cmp (int*)malloc(sizeof(int*) * range);if (cmp NULL){perror(malloc fail);return;}memset(cmp, 0, sizeof(int) * range);for (int i 0; i n; i){cmp[a[i] - min];}int j 0;for (int i 0; i n; i){while (cmp[i]--){a[j] i min;}}free(cmp);
} 首先通过遍历数组找到数组中的最大值 max 和最小值 min 。然后计算数据的范围 range 并分配一个与范围大小相同的辅助数组 cmp 。接着再次遍历原数组对每个元素在辅助数组中对应的位置进行计数。之后通过另一个循环根据辅助数组中的计数将元素按顺序放回原数组。最后释放辅助数组的内存。 PS简单来说他的原理就类似于这种画的有点丑陋通过记录出现的数的次数最后把他们依次放入原始数组里面。从这张图我们也可以看出计数排序在原数组数字重复多并且数字间隔比较密的时候max-min1计数排序会格外的好用。 6. 总结 在实际工程中没有绝对的最优算法。当处理百万级数据时快速排序往往表现优异面对海量数据时归并排序的稳定性优势凸显在资源受限的嵌入式系统中堆排序可能是更安全的选择。理解算法本质分析数据特征结合具体场景才能做出最合适的决策。愿这些排序算法成为你解决实际问题的利剑在编程之路上助你披荆斩棘 建议读者在实践中尝试用不同算法处理同一数据集直观感受性能差异。当面对特殊业务场景时也可以考虑将多种算法组合使用或者基于这些经典思想进行改良创新。排序的世界永远充满惊喜期待你在实践中发现更多精妙之处
