在网站建设中遇到的问题短网址生成系统源码

当前位置： 首页 > news >正文

在网站建设中遇到的问题,短网址生成系统源码,网站建设最快多长时间,学校网站的功能文章目录 内排序一、插入排序1.1 直接插入排序1.2 折半插入排序1.3 希尔排序 二、选择排序2.1 简单选择排序2.2 堆排序 三、交换排序3.1 冒泡排序3.2 快速排序Hoare版挖坑法快速排序前后指针法快速排序的非递归 四、归并排序递归版本非递归版本 五、基数排序六、计数排序内排序… 文章目录 内排序一、插入排序1.1 直接插入排序1.2 折半插入排序1.3 希尔排序 二、选择排序2.1 简单选择排序2.2 堆排序 三、交换排序3.1 冒泡排序3.2 快速排序Hoare版挖坑法快速排序前后指针法快速排序的非递归 四、归并排序递归版本非递归版本 五、基数排序六、计数排序内排序总结 内排序 一、插入排序 插入排序包括直接插入排序和希尔排序 1.1 直接插入排序 算法思想 直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。 用一个形象的比喻摸牌与插牌。 下面进行动图演示 算法的代码实现 void insert_sort(int a[], int n) {// tmp表示要插入的元素// end表示已插入元素最后一个元素的下标int tmp, end;// 1个元素默认有序因此从1开始for (int i 1; i n; i){tmp a[i];end i - 1;while (end 0){// 1. 如果a[end] tmp 则a[end]向后移, end–// 如果a[end] tmp则a[end1] tmp// 特殊情况如果tmp是最小的数则end -1会跳出循环因此在循环体外赋值if (a[end] tmp){a[end 1] a[end];end–;}else{break;}}a[end 1] tmp;} }算法评价 元素集合越接近有序直接插入排序算法的时间效率越高 时间复杂度O(N^2) 空间复杂度O(1)它是一种稳定的排序算法 稳定性稳定
改进插入排序效率的重点减少比较的次数如何减少比较的次数2的方向 快速定位新插入的元素在已排序好的位置 – 折半查找 让原来的序列趋近于有序 – 希尔排序
1.2 折半插入排序 算法思想 直接插入排序中将无序区的开头元素Ri插入到有序区 R[0…i-1]是采用顺序比较的方法。由于有序区的元素是有序的,可以采用折半查找方法先在R0…i-1中找到插入位置,再通过移动元素进行插入,这样的插入排序称为折半插入排序(binary insertion sort)或二分插人排序 算法实现 void mid_insert_sort(int a[], int n) {int tmp, end;for(int i 1; i n; i){tmp a[i];end i-1;// 1. 折半查找位置 – 注意稳定性令 为l区域int l -1, r i;while(l1 ! r){int mid l r 1;if(a[mid] tmp) r mid;else l mid;}// 2. 后移元素[0 l] [r i-1], l1的地方插入后移[l1, i-1]一位while(end l1){a[end1] a[end];–end; }a[l1] tmp;} }算法评价 折半插入排序的元素移动次数与直接插入排序相同,不同的仅是变分散移动为集中移动。在R0…i-1中查找插入R[]的位置,折半查找的平均关键字比较次数约为log(i1)-1,平均移动元素的次数为i/22,所以平均时间复杂度为: 实际上,折半插入排序和直接插入排序相比移动元素的性能没有改善,仅仅减少了关键字的比较次数。就平均性能而言,由于折半查找优于顺序查找,所以折半插入排序也优于直接插入排序。折半插入排序的空间复杂度为(1),也是一种稳定的排序方法。 1.3 希尔排序 算法思想 希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数gap把待排序文件中所有数据分成gap个组所有距离为gap的数据分在同一组内并对每一组内的数据进行排序。然后取 gap gap/2重复上述分组和排序的工作。当到达gap1时数据将排好序. 算法实现 //单组排完在排下一组 void shell_sort(int a[], int n) {int gap n;while (gap 1){gap / 2;//gap / 3 1;//1. 分组for (int i 0; i gap; i){// 2. 单组插入排序int tmp, end;for (int j igap; j n; j gap){tmp a[j];end j - gap;while (end i){if (a[end] tmp){a[end gap] a[end];end - gap;}else break;}a[endgap] tmp;}}} } //多组并行 void shell_sort(int a[], int n) {int gap n;while (gap 1){gap / 2;//多组并行for (int i 0; i gap n; i){int tmp a[i gap];int end i;while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else break;}a[end gap] tmp;}} }算法评价 希尔排序的空间复杂度O(1) 希尔排序的时间复杂度 希尔排序法是一种不稳定的排序算法。例如,若希尔排序分为{3,10,7,8,20}和(5,8,2,1,6)两组,显然第1组的8排列在第2组的8的后面,两组采用直接插入排序后的结果为(3,7,8,10,20}和{1,2,5,6,8),这样第1组的8排列到第2组的8的前面,它们的相对位置发生了改变。 二、选择排序 2.1 简单选择排序 算法思想 每次从剩余数中选出最小的数与已排序的数组后面一个元素换位置 算法实现 //原版 – 每次选出最小 void select_sort(int a[], int n) {for (int i 0; i n; i){int Min_i i;// 1. 单趟找最小元素的下标for (int j i; j n; j){if (a[Min_i] a[j]){Min_i j;}}// 2. 与i下标对应的元素交换std::swap(a[Min_i], a[i]);} } //优化版 – 每次选出最大和最小 void select_sort(int a[], int n) {int l 0, r n - 1;while(l r){int Min_i l, Max_i r;// 1. 单趟找最小和最大元素的下标for (int j l; j r; j){if (a[Min_i] a[j]){Min_i j;}if (a[Max_i] a[j]){Max_i j;}}// 2. 与lr下标对应的元素交换std::swap(a[Min_i], a[l]);//存在情况l指向的数就是目前区间的最大值if (l Max_i){Max_i Min_i;}std::swap(a[Max_i], a[r]);l, r–;} }算法评价 显然,无论初始数据序列的状态如何,在第i趟排序中选出最小关键字的元素,内for循环需做n-1-(i1)1-n-i-1次比较,因此总的比较次数为: 另外,简单选择排序算法是一个不稳定的排序方法。例如排序序列为(5,3,2,5,4,1,8,7),第1趟排序时选择出最小关键字1,将其与第1个位置上的元素交换,得到(1,3,2,5,4,5,8,7},从中看到两个5的相对位置发生了改变。 2.2 堆排序 算法思想 堆排序(heap sort)是一种树形选择排序方法,它的特点是将 R1…n看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的位置关系在无序区中选择关键字最大(或最小)的元素。 算法实现 void AdjustDown(int a[], int n, int father) {//1. 找左孩子int left 2 * father 1;while (left n){int Maxchild left;//2. 找右孩子if (left 1 n a[Maxchild] a[left 1]) Maxchild left 1;//3. 与父亲比较if (a[Maxchild] a[father]){std::swap(a[Maxchild], a[father]);father Maxchild;left 2 * father 1;}else return;} } void heap_sort(int a[], int n) {for (int i n / 2; i 0; i–){AdjustDown(a, n, i);}for (int i 0; i n - 1; i){std::swap(a[0], a[n - 1 - i]);AdjustDown(a, n-1-i, 0);} }算法评价 堆排序的时间主要由建立初始堆和反复重建堆这两部分的时间构成 建堆O(n) 排序O(nlogn) 综上所述,堆排序的最坏时间复杂度为O(nlogn)。堆排序的平均性能分析较难,但实验研究表明,它较接近最坏性能。实际上,堆排序和简单选择排序算法一样,其时间性能与初始序列的顺序无关,也就是说,堆排序算法的最好、最坏和平均时间复杂度都是O(nlogn)。由于建初始堆所需的比较次数较多,所以堆排序不适合元素数较少的排序表堆排序只使用i、i、tmp等辅助变量,其辅助空间复杂度为(1)。另外,在进行筛选时可能把后面相同关键字的元素调整到前面,所以堆排序算法是一种不稳定的排序方法。 三、交换排序 3.1 冒泡排序 算法思想 冒泡排序(bubble sort)也称为气泡排序,是一种典型的交换排序方法,其基本思想是通过无序区中相邻元素关键字间的比较和位置的交换使关键字最小/最大的元素如气泡一般逐渐往上“漂浮”直至“水面” 算法实现 void bubble_sort(int a[], int n) {for (int i 0; i n-1; i){//单趟从左向右依次比较for (int j 0; j n - 1 - i; j){if (a[j] a[j 1]) std::swap(a[j], a[j 1]);}} }//优化1如果某趟没有发生一次交换则证明已经完成排序 void bubble_sort(int a[], int n) {for (int i 0; i n - 1; i){int exchange 0;//单趟从左向右依次比较for (int j 0; j n - 1 - i; j){if (a[j] a[j 1]){std::swap(a[j], a[j 1]);exchange 1;}}if (exchange 0) return;} } //优化2 – 双向冒泡 void two_bubble_sort(int a[], int n) {int l 0, r n - 1, flag 1;while (l r){for (int i l; i r; i){if (a[i] a[i 1]){std::swap(a[i], a[i 1]);flag i;}}r flag;for (int i r - 1; i l; i–){if (a[i] a[i 1]){std::swap(a[i], a[i 1]);flag i;}}l flag;} }算法评价 冒泡排序算法辅助空间复杂度为O(1),也就是说它是一个就地排序。另外,当ii日R[i].keyR[i].key时,两者没有逆序,不会发生交换,也就是说使R[i]和R[i]的相对位置保持不变,所以冒泡排序是一种稳定的排序方法。 3.2 快速排序 Hoare版 算法思想 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 再上递归展开图和二叉树的前序遍历差不多 算法实现 void quick_sort(int a[], int l, int r) {if (l r) return;//1. 选key 假设左边第一个为keyint keyi l;//2. 找到key的正确位置int st l, ed r;while (st ed){while (ed st a[ed] a[keyi]) –ed;while (ed st a[st] a[keyi]) st;std::swap(a[st], a[ed]);}//3. 将key交换到正确位置std::swap(a[st], a[keyi]);;keyi st;//4. 继续下分quick_sort(a, l, keyi - 1);quick_sort(a, keyi 1, r); }记住上面这三个关键点。 快速排序的时间复杂度是O(nlogn).如下
上面是Hoare大佬的原版思路但有些人认为Hoare的方法有很多小坑于是又有许多人提出了快速排序的其他实现思路如挖坑法前后指针法下面我们一一道来 挖坑法 算法思想 先将key保存将l设置为hole然后从右向左找 key的数, 找到则将其放到hole里更新hole然后从左向右找 key的数 找到则将其放到hole里更新hole直到 l r, 此时hole为key应放的位置 算法实现 void quick_sort(int a[], int l, int r) {if (l r) return;//1. 选key 假设左边第一个为keyint key a[l];int hole l;//2. 找到key的正确位置int st l, ed r;while (st ed){while (ed st a[ed] key) –ed;a[hole] a[ed];hole ed;while (ed st a[st] key) st;a[hole] a[st];hole st;}//3. 将key交换到正确位置a[hole] key;//4. 继续下分quick_sort(a, l, hole - 1);quick_sort(a, hole 1, r); }快速排序前后指针法 算法思想
算法实现 void quick_sort(int a[], int l, int r) {if (l r) return;//1. 选key 假设左边第一个为keyint cur, prev, keyi;prev keyi l;cur prev 1;while (cur r) {if (a[cur] a[keyi] prev ! cur) {std::swap(a[prev], a[cur]);}cur;}std::swap(a[keyi], a[prev]);keyi prev;quick_sort(a, l, keyi - 1);quick_sort(a, keyi 1, r); }快速排序的非递归 用栈来模拟 void quick_sort(int a[], int l, int r) {std::stackint st;st.push®;st.push(l);while (st.size()){int begin st.top();st.pop();int end st.top();st.pop();//单次快排过程int x a[begin end 1], i begin - 1, j end 1;while (i j){do i; while (a[i] x);do j–; while (a[j] x);if (i j) std::swap(a[i], a[j]);}//插入新的划分段if (j 1 end){st.push(end);st.push(j 1);}if (begin j){st.push(j);st.push(begin);}} }四、归并排序 递归版本 算法思想 基本思想归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 形象来讲就是将数组拆成一个个元素再逐渐将它们组合起来。这符合递归的特性下面我们通过递归展开图来看。 递归展开图虽然看起来像把数组里的元素拆成了一个个新数组但我们必须要清晰的认识到这些元素还是在原数组里。明白了这点让我们来好好思考一下如何归并。有人说交换一下就行了。比如上面最下面一层10 和 6归并回去的时候大的和小的交换一下位置不就有序了。但倒数第二层呢?4个数互相交换吗这就有点复杂化了。 比较好的做法是创建一个临时数组tmp将需要归并的元素通过直接插入排序插入到临时数组里面,再把临时数组拷贝回去。如下图 算法实现 void merge_sort(int a[], int l, int r, int tmp[]) {// 1. 终止条件if (l r)return;// 2. 不断递归划分int mid l r 1;merge_sort(a, l, mid, tmp);merge_sort(a, mid 1, r, tmp);// 3. 开始归并, 左区间[l, mid] 右区间[mid1, r] 起始位置 end lint l1 l, r1 mid;int l2 mid 1, r2 r;int end l;while (l1 r1 l2 r2){if (a[l1] a[l2]) tmp[end] a[l1];else tmp[end] a[l2];}// 3.1 左区间可能有剩余while (l1 r1) tmp[end] a[l1];// 3.2 右区间可能有剩余while (l2 r2) tmp[end] a[l2];// 3.2 将排序好的数组拷贝到原数组内memcpy(a l, tmp l, sizeof(int) * (r - l 1)); }非递归版本 归并过程由一一归并到二二归并再到四四归并…直到gap n void merge_sort(int* a, int l, int r) {int n r - l 1;int* tmp new int[n];int gap 1;//左右区间的大小while (gap n){for (int i 0; i n; i 2 * gap){// 开始归并, 左区间[i, igap-1] 右区间[igap, igap gap-1] 起始位置 end iint l1 i, r1 i gap-1;int l2 i gap, r2 i 2 * gap - 1;int end i;//情况1r1 越界 表明l2,r2都越界了直接break//情况2l2 越界 同上直接break//情况3: r2 越界 更改r2 n-1//情况4无越界 if (l2 n) break;if (r2 n) r2 n - 1;while(l1 r1 l2 r2){if (a[l1] a[l2]) tmp[end] a[l1];else tmp[end] a[l2];}// 左区间可能有剩余while (l1 r1) tmp[end] a[l1];// 右区间可能有剩余while (l2 r2) tmp[end] a[l2];//这里用end - i不要用2*gap 因为存在越界的情况拷贝的大小 gap*2memcpy(a i, tmp i, sizeof(int) * (end-i));}gap * 2;}delete[] tmp; }五、基数排序 算法思想 基数排序radix sort属于“分配式排序”distribution sort又称“桶子法”bucket sort或bin sort顾名思义它是透过键值的部份资讯将要排序的元素分配至某些“桶”中藉以达到排序的作用基数排序法是属于稳定性的排序其时间复杂度为O (nlog®m)其中r为所采取的基数而m为堆数在某些时候基数排序法的效率高于其它的稳定性排序法。 二种方式 最高位优先(Most Significant Digit first)法简称MSD法先按k1排序分组同一组中记录关键码k1相等再对各组按k2排序分成子组之后对后面的关键码继续这样的排序分组直到按最次位关键码kd对各子组排序后。再将各组连接起来便得到一个有序序列。 最低位优先(Least Significant Digit first)法简称LSD法先从kd开始排序再对kd-1进行排序依次重复直到对k1排序后便得到一个有序序列。 算法实现 – LSD void radix_sort(int a[], int n) {//确定基数 – 按个 十…排序因此基数 0-9 共10个const int radix 10;std::queueint q[radix];int mol 10;while (1){//1. 分配for (int i 0; i n; i){//1. 求key// 10013 取十位 模100再除10int k a[i] % mol;k / (mol / 10);//2. 入队q[k].push(a[i]);}// 如果都分配到q[0]则表示关键字序号已经超过k1if (q[0].size() n) break;//2. 回收int end 0;for (int i 0; i radix; i){while (q[i].size()){int t q[i].front();q[i].pop();a[end] t;}}//3. 开始排序kd-1位mol * 10;} }六、计数排序 算法思想 计数排序是一种非比较排序其核心是将序列中的元素作为键存储在额外的数组空间中而该元素的个数作为值存储在数组空间中通过遍历该数组排序。 算法实现 void count_sort(int a[], int n) {int Max a[0];for (int i 1; i n; i){Max std::max(Max, a[i]);}int* count new int[Max]{0};for (int i 0; i n; i){count[a[i]];}int end 0;for (int i 0; i Max; i){while (count[i]){a[end] i;count[i]–;}} }算法评价 时间复杂度O (NMax) 空间复杂度O (Max) 内排序总结 排序方法时间复杂度空间复杂度稳定性平均情况最坏情况最好情况直接插入排序O( n 2 n^2 n2)O( n 2 n^2 n2)O( n n n)O(1)稳定折半插入排序O( n 2 n^2 n2)O( n 2 n^2 n2)O( n n n)O(1)稳定希尔排序O( n 1.3 n^{1.3} n1.3)O(1)不稳定简单选择排序O( n 2 n^2 n2)O( n 2 n^2 n2)O( n 2 n^2 n2)O(1)不稳定堆排序O( n l o g 2 n nlog_2{n} nlog2​n)O( n l o g 2 n nlog_2{n} nlog2​n)O( n l o g 2 n nlog_2{n} nlog2​n)O(1)不稳定冒泡排序O( n 2 n^2 n2)O( n 2 n^2 n2)O( n 2 n^2 n2)O(1)稳定快速排序O( n l o g 2 n nlog_2{n} nlog2​n)O( n 2 n^2 n2)O( n l o g 2 n nlog_2{n} nlog2​n)O( l o g 2 n log_2{n} log2​n)不稳定归并排序O( n l o g 2 n nlog_2{n} nlog2​n)O( n l o g 2 n nlog_2{n} nlog2​n)O( n l o g 2 n nlog_2{n} nlog2​n)O( n n n)稳定基数排序O( d ( n r ) d(nr) d(nr))O( d ( n r ) d(nr) d(nr))O( d ( n r ) d(nr) d(nr))O( r r r)稳定计数排序O( n n n)O( n n n)O( n n n)O( r a n g e range range)不稳定