cdr做图时怎么找到网站的,一个网站服务器一年大概多少钱,建筑工程承包网址大全,网站开发的软件介绍目录 1. 插入排序
1.1.1 直接插入排序代码实现
1.1.2 直接插入排序的特性总结
1.2.1 希尔排序的实现
1.2.2 希尔排序的特性总结
2. 选择排序
2.1.1 选择排序
2.1.2 选择排序特性
2.2.1 堆排序
2.2.2 堆排序特性
3. 交换排序
3.1.1 冒泡排序
3.1.2 冒泡排序的特性
…目录 1. 插入排序
1.1.1 直接插入排序代码实现
1.1.2 直接插入排序的特性总结
1.2.1 希尔排序的实现
1.2.2 希尔排序的特性总结
2. 选择排序
2.1.1 选择排序
2.1.2 选择排序特性
2.2.1 堆排序
2.2.2 堆排序特性
3. 交换排序
3.1.1 冒泡排序
3.1.2 冒泡排序的特性
3.2.1 快速排序
3.2.1.1 hoare版本
3.2.1.2 挖坑法
3.2.1.3 前后指针法
3.2.2.1 快排的递归实现及优化
3.2.2.2 快排的非递归实现
3.2.2 快速排序的特性
4. 归并排序
4.1 归并递归实现
4.2 归并非递归实现
5. 非比较排序
5.1 计数排序
5.2 基数排序
5.3 桶排序
6. 排序算法复杂度及稳定性 1. 插入排序
1.1.1 直接插入排序代码实现
插入排序动图如下 思想就是把[0,end]区间变为有序让后把下一个数据进行插入下面是代码实现
我们先写一趟排序
int end ;
int tem a[end 1];
while (end 0)
{if (tem a[end]){a[end 1] a[end];end--;}else{break;}
}
a[end 1] tem; 之后我们用一个for循环控制end的值就可以了
完整代码如下所示
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tem a[end 1];while (end 0){if (tem a[end]){a[end 1] a[end];end--;}else{break;}}a[end 1] tem;}
}
1.1.2 直接插入排序的特性总结 1. 元素集合越接近有序直接插入排序算法的时间效率越高 2. 时间复杂度 O(N^2) 3. 空间复杂度 O(1) 它是一种稳定的排序算法 4. 稳定性稳定 1.2.1 希尔排序的实现 希尔排序法又称缩小增量法。希尔排序法的基本思想是 先选定一个整数gap把待排序文件中所有记录分成个 组所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工 作。当到达 1 时所有记录在统一组内排好序 。 相距为gap的数为一组这样就可以分为gap组如下所示这里以gap为3为例 如下图所示 这里我解释一下为啥gap是多少就可以分为几组因为每组的起始位置依次加一而他们相聚gap所以就是gap组。 下面我们先进行一组排序代码如下 void shellsort(int* a, int n)
{int gap 3;for (int i 0; i n - gap; i gap){int end i;int key a[end gap];while (end 0){if (key a[end]){a[end gap] a[end];end--;}else{break;}}a[end gap] key;}} 下面我们控制组数每组的开头是不一样的最后控制gap只有gap为1时是最后一趟排序其余的都是预排序完整代码如下 void shellsort(int* a, int n)
{int gap n;while (gap1){gap gap / 3 1;for (int j 0; j gap; j){for (int i j; i n - gap; i gap){int end i;int key a[end gap];while (end 0){if (key a[end]){a[end gap] a[end];end-gap;}else{break;}}a[end gap] key;}}}
} 下面是另一种写法两种写法的效率是一样的第二种写法就是进行一组两个数据的插入后直接进行下一组 就是先4,2然后1,1然后3,8第一种是一组全部弄完后再弄下一组两者的效率一样的 第二种代码如下 void shellsort(int* a, int n)
{int gap n;while (gap1){gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int key a[end gap];while (end 0){if (key a[end]){a[end gap] a[end];end-gap;}else{break;}}a[end gap] key;}}
} 1.2.2 希尔排序的特性总结 1. 希尔排序是对直接插入排序的优化。 2. 当 gap 1 时都是预排序目的是让数组更接近于有序。当 gap 1 时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 3. 希尔排序的时间复杂度不好计算因为 gap 的取值方法很多导致很难去计算因此在好些树中给出的 希尔排序的时间复杂度都不固定 《数据结构(C语言版)》--严蔚敏 希尔排序的分析是一个复杂的问题,因为它的时间是所取增量序列的函数,这涉及 些数学上尚未解决的难题。因此,到目前为止尚未有人求得一种最好的增量序列,但大 量的研究已得出一些局部的结论。如有人指出,当增量序列为dIta[k]25-61-1时,希 尔排序的时间复杂度为O(12312)其中t为排序趙数,1ktlog2(n1)」。还有人在 大量的实验基础上推出 当刀在某个特定范围内,希尔排序所需的比较和移动次数为为 n1.3,当770时,可减少到7(10g27)201。增量序列可以有各种取法1,且需注意:应使增 量序列中的值没有除1之外的公因子,并且最后一个增量值必须等于1。 《数据结构-用面相对象方法与C描述》---殷人昆 因为咋们的 gap 是按照 Knuth 提出的方式取值的而且 Knuth 进行了大量的试验统计我们暂时就按照 到 来算。 4. 稳定性不稳定 2. 选择排序 2.1.1 选择排序 思想就是便利找到一个最大一个最小最小放在起始位置最大放在最后的位置 代码实现 void SelectSort(int* a, int n)
{int begin 0;int end n - 1;while (begin end){int maxindex begin;int minindex begin;for (int i begin 1; i end; i){if (a[i] a[maxindex]){maxindex i;}if (a[i] a[minindex]){minindex i;}}Swap(a[begin], a[minindex]);//这里我们要注意如果maxindex指向与begin相等时换位之后maxindex要更新if (begin maxindex)maxindex minindex;Swap(a[end], a[maxindex]);begin;end--;}
} 2.1.2 选择排序特性 1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用 2. 时间复杂度 O(N^2) 3. 空间复杂度 O(1) 4. 稳定性不稳定 2.2.1 堆排序 堆排序就是先建堆然后按照堆的删除把堆顶数据放到数组最后让后end减减向下调整就行 代码实现如下 void AddjustDown(int* a, int n, int parent)
{int child 2 * parent 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child 2 * parent 1;}else{break;}}}
//堆排序
void HeapSort(int* a, int n)
{for (int i (n - 2) / 2; i 0; i--){AddjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AddjustDown(a, end, 0);end--;}
} 2.2.2 堆排序特性 1. 堆排序使用堆来选数效率就高了很多。 2. 时间复杂度 O(N*logN) 3. 空间复杂度 O(1) 4. 稳定性不稳定 3. 交换排序 3.1.1 冒泡排序 代码实现 void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i){int falg 1;for (int j 0; j n - 1 - i ;j){if (a[j] a[j 1]){Swap(a[j], a[j 1]);}falg 0;}if (falg 1){break;}}
} 3.1.2 冒泡排序的特性 1. 冒泡排序是一种非常容易理解的排序 2. 时间复杂度 O(N^2) 3. 空间复杂度 O(1) 4. 稳定性稳定 3.2.1 快速排序 3.2.1.1 hoare版本 这里我们写的是单趟的逻辑 int PartSort1(int* a, int left, int right)
{int keyi left;int begin left;int end right;while (begin end){while (begin end a[end] a[keyi]){end--;}while (begin end a[begin] a[keyi]){begin;}Swap(a[end], a[begin]);}Swap(a[begin], a[keyi]);return begin;
} 3.2.1.2 挖坑法 // 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{int key a[left];int keyi left;int begin left;int end right;while (begin end){while (begin end a[end] a[keyi]){end--;}a[keyi] a[end];keyi end;while (begin end a[begin] a[keyi]){begin;}a[keyi] a[begin];keyi begin;}a[keyi] key;return keyi;
} 3.2.1.3 前后指针法 // 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{int key a[left];int prev left;int cur prev 1;while (cur right){//这里当我们每次交换时prev先走是为了防止数组最左端的数据被覆盖if (a[cur] key prev!cur)Swap(a[cur], a[prev]);cur;}//这里注意要与数组的头一个序列的值交换Swap(a[prev], a[left]); return prev;
} 3.2.2.1 快排的递归实现及优化 // 三数取中
int findmidi(int* a, int left, int right)
{int midi (right - left) / 2 left;if (a[left] a[midi]){if (a[midi] a[right]){return midi;}else if (a[right] a[midi]){if (a[left] a[right]){return left;}else{return right;}}}else//a[midi]a[left]{if (a[right] a[midi]){return midi;}else if (a[right] a[midi]){if (a[right] a[left]){return right;}else{return left;}}}
}
void QuickSort(int* a, int left, int right)
{if (left right)return ;if (right - left 1 10){InsertSort(a left, right - left 1);return ;}else{int midi findmidi(a, left, right);Swap(a[midi], a[left]);int mid PartSort3(a, left, right);QuickSort(a, left, mid - 1);QuickSort(a, mid 1, right);}
} 其中的三数其中发是为了防止数据有序的情况下效率退化 而在数据足够少时不用再递归了减少了递归次数优化了效率 3.2.2.2 快排的非递归实现 //快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{Stack stack;StackInit(stack);StackPush(stack, right);StackPush(stack, left);while (!StackEmpty(stack)){int begin StackTop(stack);StackPop(stack);int end StackTop(stack);StackPop(stack);int mid PartSort3(a, begin, end);if (mid 1 end){StackPush(stack, end);StackPush(stack, mid 1);}if (begin mid - 1){StackPush(stack, mid - 1);StackPush(stack, begin);}}StackDestroy(stack);
} 就是利用栈来存每次递归的区间用栈模拟实现递归过程注意的是每次入栈应该是右区间先入再左区间 3.2.2 快速排序的特性 1. 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫 快速 排序 2. 时间复杂度 O(N*logN) 4. 归并排序 归并排序 MERGE-SORT 是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法 Divide and Conquer 的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有 序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 如果说快排是二叉树的前序则归并就是后序 4.1 归并递归实现 void _MergeSort(int *a, int *tem, int left, int right)
{if (left right){return;}int mid (right - left) / 2 left;_MergeSort(a, tem, left, mid);_MergeSort(a, tem, mid1, right);//下面要进行归并排序int j left;int begin1 left;int end1 mid;int begin2 mid 1;int end2 right;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tem[j] a[begin1];}else{tem[j] a[begin2];}}while (begin1 end1){tem[j] a[begin1];}while (begin2 end2){tem[j] a[begin2];}memcpy(a left, tem left, sizeof(int) * (right - left 1));
}
//归并排序
void MergeSort(int* a, int n)
{int* tem (int*)malloc(sizeof(int) * n);int left 0;int right n - 1;_MergeSort(a, tem, left, right);
} 注意分区间为什么是以上的分法请看下图 如果[2,3]按照第一种则会一直递归造成栈溢出。 4.2 归并非递归实现 //归并排序非递归写法
void MergeSortNonR(int *a, int n)
{int* tem (int*)malloc(sizeof(int) * n);if (tem NULL){perror(malloc faliue);return;}int gap 1;while (gap n){//gap是每组归并数据的数据个数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;//第二组全都越界if (begin2 n){break;}//第二组部分越界end2更新if (end2 n)end2 n - 1;int j begin1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tem[j] a[begin1];}else{tem[j] a[begin2];}}while (begin1 end1){tem[j] a[begin1];}while (begin2 end2){tem[j] a[begin2];}memcpy(a i, tem i, sizeof(int) * (end2 - i 1));}gap * 2;}free(tem);tem NULL;
} 这里我们注意的就是越界问题如果begin2越界说明此次归并不需要了end2越界说明第二组有部分数据需要归并end2更新。如果end1越界此时begin2一定越界直接退出for循环不用进行归并了 5. 非比较排序 5.1 计数排序 代码实现其实就是一个简单的哈希映射 // 计数排序
void CountSort(int* a, int n)
{//申请一个计数数组int max a[0];int min a[0];for (int 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*)calloc(range, sizeof(int));for (int i 0; i n; i){count[(a[i]-min)];}int j 0;for (int i 0; i range; i){while (count[i]--){a[j] i min;}}free(count);count NULL;
} 1. 计数排序在数据范围集中时效率很高但是适用范围及场景有限。 2. 时间复杂度 O(MAX(N, 范围 )) 3. 空间复杂度 O( 范围 ) 5.2 基数排序 思想就是先按照最低位按照顺序先排接着一直到最高位这里我们只需要了解一下思想就行 5.3 桶排序 思想就是我们建立一个指针数组此时数组里面的元素是一个指向链表结点的指针。 我们便利原数组把最高位对应的数放到指针数组对应的下标比如78就要放到B数组下标为7的那个数组元素里面如果再来一个76就进行尾插最后对链表排序。 6. 排序算法复杂度及稳定性 稳定性是指两个相同的数在排序前后的相对位置如果不变就是稳定反之则不稳定。 冒泡这里我们这里我们不分析了 选择排序假设662我们把6和2交换6的相对位置改变了就不稳定了 插入排序是稳定 希尔如果两个相同的数被分到不同的组就会不稳定 堆排如果都是2把2放到最后相对位置改变不稳定 归并排序就是我们在归并时如果相等我们就把左区间的那个值先放到数组中就稳定了 快速排序假设665我们把6和5交换就会不稳定了
文章转载自： http://www.morning.dmchips.com.gov.cn.dmchips.com http://www.morning.jynzb.cn.gov.cn.jynzb.cn http://www.morning.mmjyk.cn.gov.cn.mmjyk.cn http://www.morning.mkbc.cn.gov.cn.mkbc.cn http://www.morning.lxjcr.cn.gov.cn.lxjcr.cn http://www.morning.ptzbg.cn.gov.cn.ptzbg.cn http://www.morning.glpxx.cn.gov.cn.glpxx.cn http://www.morning.lmhcy.cn.gov.cn.lmhcy.cn http://www.morning.zhmgcreativeeducation.cn.gov.cn.zhmgcreativeeducation.cn http://www.morning.mkpkz.cn.gov.cn.mkpkz.cn http://www.morning.xpgwz.cn.gov.cn.xpgwz.cn http://www.morning.nkhdt.cn.gov.cn.nkhdt.cn http://www.morning.pmsl.cn.gov.cn.pmsl.cn http://www.morning.cnqwn.cn.gov.cn.cnqwn.cn http://www.morning.gsjzs.cn.gov.cn.gsjzs.cn http://www.morning.pjfmq.cn.gov.cn.pjfmq.cn http://www.morning.mkpqr.cn.gov.cn.mkpqr.cn http://www.morning.lfbsd.cn.gov.cn.lfbsd.cn http://www.morning.jtmql.cn.gov.cn.jtmql.cn http://www.morning.mrpqg.cn.gov.cn.mrpqg.cn http://www.morning.hbjqn.cn.gov.cn.hbjqn.cn http://www.morning.fgkwh.cn.gov.cn.fgkwh.cn http://www.morning.wdlyt.cn.gov.cn.wdlyt.cn http://www.morning.dsxgc.cn.gov.cn.dsxgc.cn http://www.morning.zzgtdz.cn.gov.cn.zzgtdz.cn http://www.morning.baguiwei.com.gov.cn.baguiwei.com http://www.morning.rknhd.cn.gov.cn.rknhd.cn http://www.morning.sqxr.cn.gov.cn.sqxr.cn http://www.morning.frtt.cn.gov.cn.frtt.cn http://www.morning.tfwr.cn.gov.cn.tfwr.cn http://www.morning.rbsmm.cn.gov.cn.rbsmm.cn http://www.morning.lrylj.cn.gov.cn.lrylj.cn http://www.morning.dwmtk.cn.gov.cn.dwmtk.cn http://www.morning.jjzxn.cn.gov.cn.jjzxn.cn http://www.morning.wgqtt.cn.gov.cn.wgqtt.cn http://www.morning.hrzky.cn.gov.cn.hrzky.cn http://www.morning.hpmzs.cn.gov.cn.hpmzs.cn http://www.morning.rxcqt.cn.gov.cn.rxcqt.cn http://www.morning.bydpr.cn.gov.cn.bydpr.cn http://www.morning.qzsmz.cn.gov.cn.qzsmz.cn http://www.morning.xnbd.cn.gov.cn.xnbd.cn http://www.morning.jjrsk.cn.gov.cn.jjrsk.cn http://www.morning.ympcj.cn.gov.cn.ympcj.cn http://www.morning.zbkwj.cn.gov.cn.zbkwj.cn http://www.morning.wzdjl.cn.gov.cn.wzdjl.cn http://www.morning.lqklf.cn.gov.cn.lqklf.cn http://www.morning.zlchy.cn.gov.cn.zlchy.cn http://www.morning.27asw.cn.gov.cn.27asw.cn http://www.morning.mpflb.cn.gov.cn.mpflb.cn http://www.morning.ckxd.cn.gov.cn.ckxd.cn http://www.morning.ldzss.cn.gov.cn.ldzss.cn http://www.morning.gkfwp.cn.gov.cn.gkfwp.cn http://www.morning.ykwgl.cn.gov.cn.ykwgl.cn http://www.morning.gbgdm.cn.gov.cn.gbgdm.cn http://www.morning.jhtrb.cn.gov.cn.jhtrb.cn http://www.morning.hsgxj.cn.gov.cn.hsgxj.cn http://www.morning.npgwb.cn.gov.cn.npgwb.cn http://www.morning.lwtld.cn.gov.cn.lwtld.cn http://www.morning.nbybb.cn.gov.cn.nbybb.cn http://www.morning.clkyw.cn.gov.cn.clkyw.cn http://www.morning.dwfxl.cn.gov.cn.dwfxl.cn http://www.morning.qckwj.cn.gov.cn.qckwj.cn http://www.morning.qckwj.cn.gov.cn.qckwj.cn http://www.morning.ntgjm.cn.gov.cn.ntgjm.cn http://www.morning.ftwlay.cn.gov.cn.ftwlay.cn http://www.morning.tphrx.cn.gov.cn.tphrx.cn http://www.morning.rqlbp.cn.gov.cn.rqlbp.cn http://www.morning.kpgft.cn.gov.cn.kpgft.cn http://www.morning.qglqb.cn.gov.cn.qglqb.cn http://www.morning.jbqwb.cn.gov.cn.jbqwb.cn http://www.morning.sgrwd.cn.gov.cn.sgrwd.cn http://www.morning.mtgkq.cn.gov.cn.mtgkq.cn http://www.morning.jfmyt.cn.gov.cn.jfmyt.cn http://www.morning.bfkrf.cn.gov.cn.bfkrf.cn http://www.morning.qcwrm.cn.gov.cn.qcwrm.cn http://www.morning.rcfwr.cn.gov.cn.rcfwr.cn http://www.morning.iknty.cn.gov.cn.iknty.cn http://www.morning.cwyfs.cn.gov.cn.cwyfs.cn http://www.morning.fssmx.com.gov.cn.fssmx.com http://www.morning.ygwbg.cn.gov.cn.ygwbg.cn
