诚信通国际网站怎么做,网站建设教程pdf百度云,网站备案幕布尺寸,平面设计大赛网站1 选择排序选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是#xff1a;第一次从待排序的数据元素中选出最小(或最大)的一个元素#xff0c;存放在序列的起始位置#xff0c;然后再从剩余的未排序元素中寻找到最小(大)元素#xff0c;然后放到已排序的序… 1 选择排序选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是第一次从待排序的数据元素中选出最小(或最大)的一个元素存放在序列的起始位置然后再从剩余的未排序元素中寻找到最小(大)元素然后放到已排序的序列的末尾。以此类推直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。稳定性不稳定时间复杂度空间复杂度void SelectSort(int r[],int n){//简单选择 int index,i; for(i0;i index i; for(int ji1;j if(r[j] index j; } } if(index!i){ int temp r[i]; r[i] r[index]; r[index] temp; } }}2 插入排序直接插入排序每一趟将一个待排序的记录按其关键字的大小插入到已经排好序的一组记录的适当位置上直到所有待排序记录全部插入为止。void InsertSort(int r[],int n){//直接插入排序 int j0; for(int i2;i r[0]r[i]; //哨兵 for(ji-1;r[0] r[j1]r[j]; } r[j1]r[0]; }}稳定性稳定时间复杂度空间复杂度折半插入排序折半插入排序(binary insertion sort)是对插入排序算法的一种改进由于排序算法过程中就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列这样我们不用按顺序依次寻找插入点可以采用折半查找的方法来加快寻找插入点的速度。void BinSort(int r[],int n){//折半插入排序 int low,high,mid; for(int i2;i r[0]r[i]; low1; highi-1; while(lowhigh){ mid (lowhigh)/2; if(r[0] high mid-1; }else{ low mid1; } } for(int ji-1;jhigh1;j--){ r[j1]r[j]; } r[high1]r[0]; }}稳定性稳定时间复杂度空间复杂度3 冒泡排序冒泡排序(Bubble Sort)是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列依次比较两个相邻的元素如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列)就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样故名“冒泡排序”。稳定性稳定时间复杂度空间复杂度void BubbleSort(int r[],int n){//冒泡排序 int temp; for(int i0;i-1;i){for(int j0;j-1;j){if(r[j]r[j1]){ temp r[j]; r[j]r[j1]; r[j1]temp; } } }}4 希尔排序希尔排序(Shells Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort)是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至 1 时整个文件恰被分成一组算法便终止。稳定性不稳定时间复杂度到空间复杂度void ShellSort(int r[],int n){//希尔排序 int j0; for(int d n/2;d1;dd/2){//以增量为d进行直接插入排序 for(int id1;i r[0]r[i]; for(ji-d;j0r[0] r[jd]r[j]; } r[jd]r[0]; } }}5 归并排序归并排序(Merge Sort)是建立在归并操作上的一种有效稳定的排序算法该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。稳定性稳定时间复杂度空间复杂度void merge(int a[],int n,int left,int mid,int right){ int n1mid-left,n2right-mid; int *L new int[n11]; int *R new int[n21]; for(int i0;i L[i]a[lefti]; for(int i0;i R[i]a[midi]; L[n1]10000000; R[n2]10000000; int i0,j0; for(int kleft;k { if(L[i]R[j]) a[k]L[i]; else a[k]R[j]; } delete[] L; delete[] R;}void MergeSort(int a[],int n,int left,int right){ if(left1 { int mid(leftright)/2; MergeSort(a,n,left,mid); MergeSort(a,n,mid,right); merge(a,n,left,mid,right); }}6 快速排序快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略。该方法的基本思想是1先从数列中取出一个数作为基准数。2分区过程将比这个数大的数全放到它的右边小于或等于它的数全放到它的左边。3再对左右区间重复第二步直到各区间只有一个数。稳定性不稳定时间复杂度空间复杂度int Partition(int r[],int first,int end){//快速排序一次划分算法 int ifirst,jend; int temp; while(i while(i j--; if(i temp r[i]; r[i] r[j]; r[j] temp; } while(i i; if(i temp r[i]; r[i] r[j]; r[j] temp; j--; } } return i;}void QuickSort(int r[],int first,int end){ if(first int pivot Partition(r,first,end); QuickSort(r,first,pivot-1); QuickSort(r,pivot1,end); }}7 堆排序堆排序是利用堆这种数据结构而设计的一种排序算法堆排序是一种选择排序它的最坏最好平均时间复杂度均为它也是不稳定排序。首先简单了解下堆结构。堆排序的基本思想是将待排序序列构造成一个大顶堆。此时整个序列的最大值就是堆顶的根节点。将根节点与末尾元素进行交换此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个大顶堆这样会得到n个元素的次小值。如此反复执行便能得到一个有序序列。稳定性不稳定时间复杂度空间复杂度// 堆排序void HeapAdjust(int a[],int s,int m)//一次筛选的过程{ int rc,j; rca[s]; for(j2*s1;jm;jj*21)//通过循环沿较大的孩子结点向下筛选 { if(j1]) j;//j为较大的记录的下标if(rca[j]) break; a[s]a[j];sj; } a[s]rc;//插入}void HeapSort(int a[],int n){int temp,i,j;//找最接近的点int s 0;while(2*s1 s; }for(is;i0;i--)//通过循环初始化顶堆 { HeapAdjust(a,i,n); }for(in;i0;i--) { tempa[0]; a[0]a[i]; a[i]temp;//将堆顶记录与未排序的最后一个记录交换 HeapAdjust(a,0,i-1);//重新调整为顶堆 }}8 基数排序基数排序(radix sort)属于“分配式排序”(distribution sort)又称“桶子法”(bucket sort)或bin sort顾名思义它是透过键值的部份资讯将要排序的元素分配至某些“桶”中藉以达到排序的作用基数排序法是属于稳定性的排序其时间复杂度为O (nlog(r)m)其中r为所采取的基数而m为堆数在某些时候基数排序法的效率高于其它的稳定性排序法。稳定性稳定时间复杂度其中r为所采取的基数而m为堆数空间复杂度//获取数字的位数int getLoopTimes(int num){ int count 1; int temp num / 10; while(temp ! 0){ count; temp / 10; } return count;}//查询数组中的最大数int findMaxNum(int *p, int n){ int max p[0]; for(int i 0; i if(p[i] max){ max p[i]; } } return max;}//将数字分配到各自的桶中然后按照桶的顺序输出排序结果void sortSingle(int *p, int n, int loop){ //建立一组桶此处的20是预设的根据实际数情况修改 int buckets[10][20] {}; //求桶的index的除数 //如798个位桶index(798/1)%108 //十位桶index(798/10)%109 //百位桶index(798/100)%107 //tempNum为上式中的1、10、100 int tempNum (int)pow(10, loop - 1); int i, j; for(i 0; i int row_index (p[i]/tempNum) % 10; for(j 0; j 20; j){ if(buckets[row_index][j] NULL){ buckets[row_index][j] p[i]; break; } } } //将桶中的数倒回到原有数组中 int k 0; for(int i 0; i 10; i){ for(int j 0; j 20; j){ if(buckets[i][j] ! NULL){ p[k] buckets[i][j]; buckets[i][j] NULL; k; } } }}void BucketSort(int *p, int n){ //获取数组中的最大数 int maxNum findMaxNum(p, n); //获取最大数的位数次数也是再分配的次数。 int loopTimes getLoopTimes(maxNum); //对每一位进行桶分配 for(int i 1; i loopTimes; i){ sortSingle(p, n, i); }}9 线性查找在常规无序数组中设数组项个数为N则一个数组项平均查找长度为N/2。极端情况下查找数据项在数组最后则需要N步才能找到。时间复杂度空间复杂度int findLinear(int* p,int n,int k){ for(int i0;i if(p[i]k){ return i; } } //查找失败返回-1 return -1;}10 折半查找二分查找也称折半查找(Binary Search)它是一种效率较高的查找方法。但是折半查找要求线性表必须采用顺序存储结构而且表中元素按关键字有序排列。首先假设表中元素是按升序排列将表中间位置记录的关键字与查找关键字比较如果两者相等则查找成功否则利用中间位置记录将表分成前、后两个子表如果中间位置记录的关键字大于查找关键字则进一步查找前一子表否则进一步查找后一子表。重复以上过程直到找到满足条件的记录使查找成功或直到子表不存在为止此时查找不成功。时间复杂度空间复杂度看实现方式递归非递归// 折半查找int BinarySearch(int* p ,int n,int k) { int low 0; int high n - 1; int cur; while(lowhigh){ // 取中间值 cur (low high) / 2; // 待查找的值与中间值匹配则返回 if (p[cur] k) { return cur; }else{ // 如果中间值小于待查找的值则将查找的最小下限值设为中间值下标1 if (p[cur] low cur 1; } else {// 如果中间值大于待查找的值则将查找的最大上限值设为中间值下标-1 high cur - 1; } } }}
