苏州建网站的公司平台收费标准,澄迈住房和城乡建设局网站,wordpress igoogle,房屋装修设计方案常见的各种排序算法复杂度快速排序1.原理假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数。为了方便#xff0c;就让第一个数6作为基准数吧。接下来#xff0c;需要将这个序列中所有比基准数大的数放在6的右边就让第一个数6作为基准数吧。接下来需要将这个序列中所有比基准数大的数放在6的右边比基准数小的数放在6的左边类似下面这种排列3 1 2 5 4 6 9 7 10 8在初始状态下数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置假设这个位置是k。现在就需要寻找这个k并且以第k位为分界点左边的数都小于等于6右边的数都大于等于6递归对左右两个区间进行同样排序即可。想一想你有办法可以做到这点吗这就是快速排序所解决的问题。快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略通常称其为分治法(Divide-and-ConquerMethod)。它的平均时间复杂度为O(nlogn)最坏时间复杂度为O(n^2).从图中我们可以看到left指针right指针base参照数。其实思想是蛮简单的就是通过第一遍的遍历(让left和right指针重合)来找到数组的切割点。第一步首先我们从数组的left位置取出该数(20)作为基准(base)参照物。(如果是选取随机的则找到随机的哨兵之后将它与第一个元素交换开始普通的快排)第二步从数组的right位置向前找一直找到比(base)小的数如果找到将此数赋给left位置(也就是将10赋给20)此时数组为1040501060 left和right指针分别为前后的10。第三步从数组的left位置向后找一直找到比(base)大的数如果找到将此数赋给right的位置(也就是40赋给10)此时数组为1040504060 left和right指针分别为前后的40。第四步重复“第二,第三“步骤直到left和right指针重合最后将(base)放到40的位置 此时数组值为1020504060至此完成一次排序。第五步此时20已经潜入到数组的内部20的左侧一组数都比20小20的右侧作为一组数都比20大 以20为切入点对左右两边数按照第一第二第三第四步骤进行最终快排大功告成。2.算法实现//快速排序随机选取哨兵放前面void QuickSort(int* h, int left, int right){ if(hNULL) return; if(leftright) return; //防止有序队列导致快速排序效率降低 srand((unsigned)time(NULL)); int lenright-left; int kindexrand()%(len1)left; Swap(h[left],h[kindex]); int keyh[left],ileft,jright; while(i { while(h[j]key i if(i while(h[i] if(i } h[i]key; //QuickSort(h[left],0,i-1); //QuickSort(h[j1],0,right-j-1); QuickSort(h,left,i-1); QuickSort(h,j1,right);}冒泡排序1.原理冒泡排序在扫描过程中两两比较相邻记录如果反序则交换最终最大记录就被“沉到”了序列的最后一个位置第二遍扫描将第二大记录“沉到”了倒数第二个位置重复上述操作直到n-1 遍扫描后整个序列就排好序了。2.算法实现//冒泡排序void BubbleSort(int* h, size_t len){ if(hNULL) return; if(len1) return; //i是次数j是具体下标 for(int i0;i for(int j0;j if(h[j]h[j1]) Swap(h[j],h[j1]); return;}选择排序1.原理选择排序也是一种简单直观的排序算法。它的工作原理很容易理解初始时在序列中找到最小(大)元素放到序列的起始位置作为已排序序列然后再从剩余未排序元素中继续寻找最小(大)元素放到已排序序列的末尾。以此类推直到所有元素均排序完毕。注意选择排序与冒泡排序的区别冒泡排序通过依次交换相邻两个顺序不合法的元素位置从而将当前最小(大)元素放到合适的位置而选择排序每遍历一次都记住了当前最小(大)元素的位置最后仅需一次交换操作即可将其放到合适的位置。2.算法实现//选择排序void SelectionSort(int* h, size_t len){ if(hNULL) return; if(len1) return; int minindex,i,j; //i是次数也即排好的个数;j是继续排 for(i0;i { minindexi; for(ji1;j { if(h[j] } Swap(h[i],h[minindex]); } return;}插入排序1.原理直接插入排序(straight insertion sort)有时也简称为插入排序(insertion sort)是减治法的一种典型应用。其基本思想如下对于一个数组A[0,n]的排序问题假设认为数组在A[0,n-1]排序的问题已经解决了。考虑A[n]的值从右向左扫描有序数组A[0,n-1]直到第一个小于等于A[n]的元素将A[n]插在这个元素的后面。 很显然基于增量法的思想在解决这个问题上拥有更高的效率。直接插入排序对于最坏情况(严格递减的数组)需要比较和移位的次数为n(n-1)/2对于最好的情况(严格递增的数组)需要比较的次数是n-1需要移位的次数是0。当然对于最好和最坏的研究其实没有太大的意义因为实际情况下一般不会出现如此极端的情况。然而直接插入排序对于基本有序的数组会体现出良好的性能这一特性也给了它进一步优化的可能性。(希尔排序)。直接插入排序的时间复杂度是O(n^2)空间复杂度是O(1)同时也是稳定排序。下面用一个具体的场景直观地体会一下直接插入排序的过程场景现有一个无序数组共7个数89 45 54 29 90 34 68。使用直接插入排序法对这个数组进行升序排序。89 45 54 29 90 34 6845 89 54 29 90 34 6845 54 89 29 90 34 6829 45 54 89 90 34 6829 45 54 89 90 34 6829 34 45 54 89 90 6829 34 45 54 68 89 902.算法实现//插入排序void InsertSort(int* h, size_t len){ if(hNULL) return; if(len1) return; int i,j; //i是次数也即排好的个数;j是继续排 for(i1;i for(ji;j0;--j) if(h[j]-1]) Swap(h[j],h[j else break; return;}归并排序1.原理归并排序(MERGE-SORT)是利用归并的思想实现的排序方法该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解而治(conquer)的阶段则将分的阶段得到的各答案修补在一起即分而治之)。分而治之2.算法实现//归并排序void MergeArray(int* arr, size_t left, size_t mid, size_t right, int* temp){ if(arrNULL) return; size_t ileft,jmid1,k0; while(imid jright) { if(arr[i]arr[j]) { temp[k]arr[i]; continue; } temp[k]arr[j]; } while(imid) temp[k]arr[i]; while(jright) temp[k]arr[j]; memcpy(arr[left],temp,k*sizeof(int)); return;}void MMergeSort(int* arr, size_t left, size_t right, int* temp){ if(left { size_t mid(leftright)/2; MMergeSort(arr, left, mid, temp); MMergeSort(arr, mid1,right, temp); MergeArray(arr,left, mid, right, temp); }}void MergeSort(int* h, size_t len){ if(hNULL) return; if(len1) return; int* temp(int*)calloc(len,sizeof(int)); MMergeSort(h, 0, len-1, temp); memcpy(h,temp,sizeof(int)*len); free(temp); return;}希尔排序1.原理希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序它是简单插入排序经过改进之后的一个更高效的版本也称为缩小增量排序同时该算法是冲破O(n2)的第一批算法之一。本文会以图解的方式详细介绍希尔排序的基本思想及其代码实现。基本思想 希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至1时整个文件恰被分成一组算法便终止。 简单插入排序很循规蹈矩不管数组分布是怎么样的依然一步一步的对元素进行比较移动插入比如[5,4,3,2,1,0]这种倒序序列数组末端的0要回到首位置很是费劲比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略通过某个增量将数组元素划分为若干组然后分组进行插入排序随后逐步缩小增量继续按组进行插入排序操作直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序小的基本在前大的基本在后。然后缩小增量到增量为1时其实多数情况下只需微调即可不会涉及过多的数据移动。 我们来看下希尔排序的基本步骤在此我们选择增量gaplength/2缩小增量继续以gap gap/2的方式这种增量选择我们可以用一个序列来表示{n/2,(n/2)/2...1}称为增量序列。希尔排序的增量序列的选择与证明是个数学难题我们选择的这个增量序列是比较常用的也是希尔建议的增量称为希尔增量但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。2.算法实现//希尔排序void ShellSort(int* h, size_t len){ if(hNULL) return; if(len1) return; for(int divlen/2;div1;div/2) for(int k0;k for(int idivk;i for(int ji;jk;j-div) if(h[j] else break; return;}堆排序1.原理堆排序实际上是利用堆的性质来进行排序的要知道堆排序的原理我们首先一定要知道什么是堆。 堆的定义 堆实际上是一棵完全二叉树。 堆满足两个性质: 1、堆的每一个父节点都大于(或小于)其子节点 2、堆的每个左子树和右子树也是一个堆。 堆的分类 堆分为两类 1、最大堆(大顶堆)堆的每个父节点都大于其孩子节点 2、最小堆(小顶堆)堆的每个父节点都小于其孩子节点 堆的存储 一般都用数组来表示堆i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i 1和2 * i 2。如下图所示 堆排序 由上面的介绍我们可以看出堆的第一个元素要么是最大值(大顶堆)要么是最小值(小顶堆)这样在排序的时候(假设共n个节点)直接将第一个元素和最后一个元素进行交换然后从第一个元素开始进行向下调整至第n-1个元素。所以如果需要升序就建一个大堆需要降序就建一个小堆。 堆排序的步骤分为三步: 1、建堆(升序建大堆降序建小堆) 2、交换数据 3、向下调整。 假设我们现在要对数组arr[]{8,5,0,3,7,1,2}进行排序(降序) 首先要先建小堆 堆建好了下来就要开始排序了 现在这个数组就已经是有序的了。2.算法实现//堆排序/*大顶堆sort之后数组为从小到大排序*///调整void AdjustHeap(int* h, int node, int len) //----node为需要调整的结点编号从0开始编号;len为堆长度{ int indexnode; int child2*index1; //左孩子第一个节点编号为0 while(childlen) { //右子树 if(child1len h[child]1]) { child; } if(h[index]h[child]) break; Swap(h[index],h[child]); indexchild; child2*index1; }}//建堆void MakeHeap(int* h, int len){ for(int ilen/2;i0;--i) { AdjustHeap(h, i, len); }}//排序void HeapSort(int* h, int len){ MakeHeap(h, len); for(int ilen-1;i0;--i) { Swap(h[i],h[0]); AdjustHeap(h, 0, i); }}
