网站做外链怎么样,防城港装修公司口碑排行,国内做医疗耗材的网站,进度环wordpress前言#xff1a;前面我们已经学过了许许多多的排序方法#xff0c;如冒泡排序#xff0c;选择排序#xff0c;堆排序等等#xff0c;那么我们就来将排序的方法总结一下。 我们的排序方法包括以下几种#xff0c;而快速排序和归并排序我们后面进行详细的讲解。
直接插入… 前言前面我们已经学过了许许多多的排序方法如冒泡排序选择排序堆排序等等那么我们就来将排序的方法总结一下。 我们的排序方法包括以下几种而快速排序和归并排序我们后面进行详细的讲解。
直接插入排序
void InsertSort(int* a, int n)
{// [0, end] end1for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];--end;}else{break;}}a[end 1] tmp;}
} 直接插入排序顾名思义把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 我们用一个变量来保存我们插入数据的原数组中的后一个数据我们排的是降序那么我们的后一个数据比前一个数据大的话我们的后一个数据tmp就被前一个覆盖直到end0或者我们的后一个数据比前一个小我们就跳出循环我们保存的数据就等于我们跳出循环的这个数。 希尔排序
void ShellSort(int* a, int n)
{int gap n;// gap 1时是预排序目的让他接近有序// gap 1是直接插入排序目的是让他有序while (gap 1){//gap gap / 2;gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}希尔排序的思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。 我们利用希尔排序法可以将数组分成gap组gap是我们没组两个树之间的间隔 如果我们的gap是3时我们就分成了三组当gap等于0时我们的红色这组就进行插入排序当gap为1时我们蓝色这组就进行插入排序当gap为2时我们绿色这组就进行插入排序这样我们将完成了第一趟排序。我们要完成整个排序的话我们就得在嵌套一层循环我们的gap大于1时就进行预排序我们的gap为1时就是最后一趟排序我们的gap无论是几只要最后gap的值为1我们就完成了排序。 选择排序
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int mini begin, maxi begin;for (int i begin 1; i end; i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}Swap(a[begin], a[mini]);if (maxi begin){maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
}我们这里用两个变量来保存小数和大数的下标我们的后面循环里的数如果比下标为0的数小的话小数据mini的下标就是我们比第一个数据小的数据i的坐标我们排序排的是升序我们的第一个数就是应该是下标为mini的数据所以我们将就下标为mini的数据与第一个数据交换们的后面循环里的数如果比下标为0的数大的话就是存放大数据下标为maxi我们就用最后一个数据和下标为maxi的数据交换。如果我们最后循环退出的时候我们的maxi还等于begin那么我们的下标为begin的数据就是最小的。 堆排序
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){// 假设左孩子小如果解设错了更新一下if (child 1 size a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}// 升序
void HeapSort(int* a, int n)
{// O(N)// 建大堆for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end n - 1;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 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]){Swap(a[i - 1], a[i]);exchange true;}}if (exchange false)break;}冒泡排序我们很早之前就已经了解过了我这里就不多赘述了如果有疑问的话就看我之前的文章 https://blog.csdn.net/Lehjy/article/details/132266676相信以你的聪明才智一定可以完美的解决。 最后感谢大家一如既往的支持谢谢大家
