网站建站之后需要维护吗,郑州网络推广报价,vi设计公司排行榜,免费网站app下载汅api直接插入排序
直接插入排序是一种简单的插入排序法#xff0c;其基本思想是#xff1a;
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中#xff0c;直到所有的记录插入完为止#xff0c;得到一个新的有序序列 。
实际中我们玩扑克牌时#xff…直接插入排序
直接插入排序是一种简单的插入排序法其基本思想是
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。
实际中我们玩扑克牌时就用了插入排序的思想 就是第一次摸牌我们把它放在第一张第二次就和第一张比较比它大就放在他的后面否则就放在他的前面摸第三张的时候先和后面大的一张牌开始比较依次向前。 总结来说就是 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移
直接插入排序的特性总结
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定
下面我们对直接插入排序进行代码的实现 插入排序很简单 我们将第二个元素开始向后遍历i1令endi-1并且保存a[i]的值 当a[end]大于此前i下标的元素的值时将其调整将end位置的值移动到end后面一个位置同时end–如果是小于的那就直接跳出循环就代表了前面的所有值都是升序的
void insertsort(int* a, int n)
{for (int i 1; i n; i){int end i - 1;int temp a[i];while (end 0){if (a[end] temp){a[end 1] a[end];end--;}else{break;}}a[end 1] temp;}
}希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。 下面为代码实现 我们开始令gap为n的三分之一1加一是因为gap不能等于0一般情况下gap是数组长度的三分之一是比较合适的 后面的逻辑就和插入排序差不多了 后面的for循环时各个分组的数字同时进行排序
void shellsort(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int temp a[end gap];while (end 0){if (a[end] a[temp]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] temp;}}
}希尔排序的特性总结
希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的希尔排序的时间复杂度都不固定
选择排序
选择排序的思想就是每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 代码实现 第一次找出最大值最小值的下标然后放在首尾 交换值然后begin和end分别被前进和后退
void SelectSort(int* a, int n)
{assert(a);int begin 0, end n - 1;while (begin end){int min begin, max begin;for (int i begin; i end; i){if (a[i] a[max])max i;if (a[i] a[min])min i;}Swap(a[begin], a[min]);//如果最大的位置在begin位置//说明min是和最大的交换位置//这个时候max的位置就发生了变换//max变到了min的位置//所以要更新max的位置if (begin max)max min;Swap(a[end], a[max]);begin;--end;}快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为 任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止
总结下来就是 我们将小于中间位置的值的放在左边大于的放在右边然后再对左边进行一样的划分右边也是用递归实现即可
在实现快排前我们先定义一个找中间下标的函数 也就是常说的三数取中有利于更好更快得完成快排
int getmidindex(int* a, int left, int right)
{int midi (left right) / 2;if (a[left] a[midi]){if (a[midi] a[right]){return midi;}else if (a[left] a[right]){return right;}elsereturn left;}else//a[left] a[midi]{if (a[midi] a[right]){return midi;}else if (a[left] a[right]){return right;}elsereturn left;}
}快速排序一共有三种方法
hoare版本 这种方法我们统称为霍尔法 就是我们将数组的第一个元素的值赋值给key然后分别从左右 开始遍历右边先走一旦找到比key小的就停下来然后左边开始走左边找到大的就停下来然后两个位置的值互换知道二者相遇将key位置的值和他们相遇位置的值交换最后返回这个位置的下标 代码实现
int partsort1(int* a, int left, int right)
{int midi getmidindex(a, left, right);swap(a[left], a[midi]);int keyi left;while (left right){while (left right a[right] a[keyi]){right--;}while (left right a[left] a[keyi]){left;}swap(a[left], a[right]);}swap(a[keyi], a[left]);return left;
}
void quicksort(int* a, int begin, int end)
{if (begin end)return;int midi partsort1(a, begin, end);quicksort(a, begin, midi - 1);quicksort(a, midi 1, end);
}挖坑法版本 挖坑法就是把第一个元素存放到临时变量key中形成一个坑位然后右边先走右边遇到比key小的就把它给此位置的值放入坑位中此位置就是新的坑位然后左边开始找大的如果出现大的就把值填入坑位中然后此位置就是新的坑位一直到left和right相遇时就把挖出来的key值填入坑位中并且返回这个坑位的下标 过程如下图 最后省略了一部分依次类推即可
代码实现如下
int partsort2(int* a, int left, int right)
{int midi getmidindex(a, left, right);swap(a[left], a[midi]);int hole left;int key a[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 midi partsort1(a, begin, end);quicksort(a, begin, midi - 1);quicksort(a, midi 1, end);
}前后指针版本 我们首先令第一个位置的下标为prev他的下一个位置为cur并且记录第一个位置的值为key 然后cur先后遍历当cur遇到小于key的值时将prev和cur位置的值交换并且再prev1不等于cur的情况下prev进行1操作如果是等于的话就是自己和自己交换没有什么意义同时cur当遍历完成时最后交换prev位置的值和key的值返回prev位置的下标 遍历过程如下
代码实现
int partsort3(int* a, int left, int right)
{int midi getmidindex(a, left, right);swap(a[left], a[midi]);int prev left;int cur left 1;int keyi left;while (cur right){if (a[keyi] a[cur] prev ! cur){swap(a[prev] ,a[cur]);}cur;}swap(a[prev] ,a[keyi]);keyi prev;return keyi;
}
void quicksort(int* a, int begin, int end)
{if (begin end)return;int midi partsort1(a, begin, end);quicksort(a, begin, midi - 1);quicksort(a, midi 1, end);
}归并排序
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 他的大概步骤如下 归并排序的递归很简单 就是将区间逐一划分 并且得开辟一块新的空间最后将temp直接全部memcpy到目标空间a中
void _mergesort(int* a, int begin, int end, int* temp)
{if (begin end)return;int midi (begin end) / 2;_mergesort(a,begin, midi,temp);_mergesort(a,midi 1, end,temp);int begin1 begin;int begin2 midi 1;int end1 midi;int end2 end;int i begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){temp[i] a[begin1];}else{temp[i] a[begin2];}}while (begin1 end1){temp[i] a[begin1];}while (begin2 end2){temp[i] a[begin2];}memcpy(a begin, temp begin, sizeof(int) * (end - begin 1));
}
void mergesort(int* a, int n)
{int* temp (int*)malloc(sizeof(int)*n);_mergesort(a, 0, n-1, temp);free(temp);
}非递归就有点难了
void mergesortnonr(int* a, int n)
{int* temp (int*)malloc(sizeof(int) * n);if (temp NULL){perror(malloc);}int gap 1;while (gap n){int j 0;for (int i 0; i n; i 2*gap){int begin1 i;int begin2 i gap;int end1 i gap-1;int end2 i 2 * gap - 1;if (end1 n || begin2 n){break;}if (end2 n){end2 n - 1;//修正}while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){temp[j] a[begin1];}else{temp[j] a[begin2];}}while (begin1 end1){temp[j] a[begin1];}while (begin2 end2){temp[j] a[begin2];}//每归并完一组就拷贝一组memcpy(a i, temp i, sizeof(int) * (end2 - i 1));}gap * 2;}free(temp);
}归并排序的特性总结
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定
计数排序
思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤
统计相同元素出现次数根据统计的结果将序列回收到原来的序列中 其实计数排序就是用到了数组的映射当数组元素过多时就不适用了但是效率很高
void countsort(int* a, int n)
{int i 0;int j 0;int max a[0];int min a[0];for (i 0; i n; i){if (a[i] max){max a[i];}if (a[i] min){min a[i];}}int range max - min 1;int* count (int*)malloc(sizeof(int) * n);memset(count, 0, sizeof(int) * range);for (i 0; i n; i){count[a[i] - min];}int k 0;for (j 0; j range; j){while (count[j]--){a[k] j min;}}
}计数排序的特性总结
计数排序在数据范围集中时效率很高但是适用范围及场景有限。时间复杂度O(MAX(N,范围))空间复杂度O(范围
相关文章：
