网站关键词连接符,电子商务网站建设与维护方法分析不包括,游戏推广拉人渠道,wordpress做了个站没流量目录 1. 排序的概念及其作用
1.1 排序的概念
1.2 排序运用
1.3 常见的排序算法
2. 常见排序算法的实现
2.1 插入排序
2.1.1 基本思想
2.1.2 直接插入排序
2.1.3 希尔排序#xff08;缩小增量排序#xff09;
2.2 选择排序
2.2.1 基本思想
2.2.2 直接选择排序
2.2…目录 1. 排序的概念及其作用
1.1 排序的概念
1.2 排序运用
1.3 常见的排序算法
2. 常见排序算法的实现
2.1 插入排序
2.1.1 基本思想
2.1.2 直接插入排序
2.1.3 希尔排序缩小增量排序
2.2 选择排序
2.2.1 基本思想
2.2.2 直接选择排序
2.2.3 堆排序
2.3 交换排序
2.3.1 基本思想
2.3.2 冒泡排序
2.3.3 快速排序
2.3.3.1 快速排序优化
2.3.3.2 快速排序非递归
2.4 归并排序
2.5 非比较排序
3. 排序算法复杂度及稳定性分析 1. 排序的概念及其作用
1.1 排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。
稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r [ i ] r [ j ]且 r [ i ] 在 r [ j ] 之前而在排序后的序列中r [ i ] 仍在 r [ j ] 之前则称这种排序算法是稳定的否则称为不稳定的。
内部排序数据元素全部放在内存中的排序。
外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 排序运用 1.3 常见的排序算法 // 排序实现的接口// 插入排序
void InsertSort(int* a, int n);// 希尔排序
void ShellSort(int* a, int n);// 冒泡排序
void BubbleSort(int* a, int n);// 堆排序
void HeapSort(int* a, int n);// 选择排序
void SelectSort(int* a, int n);// 快速排序 递归实现
void QuickSort(int* a, int begin, int end);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int begin, int end);// 归并排序 递归实现
void MergeSort(int* a, int n);
// 归并排序 非递归实现
void MergeSortNonR(int* a, int n);// 计数排序
void CountSort(int* a, int n);
2. 常见排序算法的实现
2.1 插入排序
2.1.1 基本思想
直接插入排序是一种简单的插入排序法其基本思想是
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。
实际中我们玩扑克牌时就用了插入排序的思想 2.1.2 直接插入排序
当插入第 ii 1个元素时前面的 array[0]array[1]…array[i-1] 已经排好序此时用 array[i] 的排序码与 array[i-1]array[i-2], … 的排序码顺序进行比较找到插入位置即将 array[i] 插入原来位置上的元素顺序后移。 // 直接插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];}else{break;}--end;}a[end 1] tmp;}
}
直接插入排序的特性总结 元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定 2.1.3 希尔排序缩小增量排序
希尔排序Shell Sort是插入排序的一种。也称缩小增量排序是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。希尔排序是记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至1时整个文件恰被分成一组算法便终止。
我们分割待排序记录的目的是减少待排序记录的个数并使整个序列向基本有序发展。而如上面这样分完组后就各自排序的方法达不到我们的要求。因此我们需要采取跳跃分割的策略将相距某个“增量”的记录组成一个子序列这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。 // 希尔排序
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 tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}
希尔排序的特性总结 1. 希尔排序是对直接插入排序的优化。 2. 当 gap 1 时都是预排序目的是让数组更接近于有序。当 gap 1 时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 3. 希尔排序的时间复杂度不好计算因为 gap 的取值方法很多导致很难去计算因此在好些树中给出的希尔排序的时间复杂度都不固定 《数据结构(C语言版)》--- 严蔚敏 《数据结构-用面相对象方法与C描述》--- 殷人昆 因为咋们的gap是按照Knuth提出的方式取值的而且Knuth进行了大量的试验统计我们暂时就按照 到 来算。 4. 稳定性不稳定 2.2 选择排序
2.2.1 基本思想
每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。
2.2.2 直接选择排序
在元素集合 array[ i ] -- array[ n-1 ] 中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个第一个元素则将它与这组元素中的最后一个第一个元素交换在剩余的 array[ i ] -- array[ n-2 ]array[ i1 ] -- array[ n-1 ]集合中重复上述步骤直到集合剩余1个元素 // 直接选择排序
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int mini begin, maxi begin;for (int i begin 1; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}Swap(a[begin], a[mini]);// max如果被换走了修正一下if (maxi begin){maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
}
直接选择排序的特性总结 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定 2.2.3 堆排序
堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 // 向下调整
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 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 parent * 2 1;}else{break;}}
}// 堆排序
void HeapSort(int* a, int n)
{// 向下调整建堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}
堆排序的特性总结 堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定 2.3 交换排序
2.3.1 基本思想
所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
2.3.2 冒泡排序 // 冒泡排序
void BubbleSort(int* a, int n)
{for (int j 0; j n; j){int exchange 0;for (int i 1; i n - j; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange 1;}}if (exchange 0)break;}
}
冒泡排序的特性总结 冒泡排序是一种非常容易理解的排序时间复杂度O(N^2)空间复杂度O(1)稳定性稳定 2.3.3 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
// 假设按照升序对a数组中[begin, end]区间中的元素进行排序
void QuickSort(int* a, int begin, int end)
{if (begin end)return;// 按照基准值对a数组的[begin, end]区间中的元素进行划分int keyi PartSort1(a, begin, end);// 划分成功后以keyi为边界形成了左右两部分[begin, keyi-1]和[keyi1, end]// 递归排[begin, keyi-1]QuickSort(a, begin, keyi - 1);// 递归排[keyi1, end]QuickSort(a, keyi 1, end);
}
上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像大家在写递归框架时可想想二叉树前序遍历规则即可快速写出来后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
将区间按照基准值划分为左右两半部分的常见方式有 1. hoare版本 // 快速排序Hoare版本
int PartSort1(int* a, int left, int right)
{// 三数取中优化下面会讲int midi GetMidi(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;
} 2. 挖坑法 // 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int key a[left];// 保存key的值后左边形成第一个坑int hole 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;
} 3. 前后指针版本 // 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int prev left;int cur prev 1;int keyi left;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);return prev;
}
2.3.3.1 快速排序优化
三数取中法选key递归到小的子区间时可以考虑使用插入排序
// 三数取中
int GetMidi(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]) // mid是最大值{return left;}else{return right;}}else // a[left] a[mid]{if (a[mid] a[right]){return mid;}else if (a[left] a[right]) // mid是最小值{return left;}else{return right;}}
}
// 添加小区间优化的快速排序
void QuickSort1(int* a, int begin, int end)
{if (begin end)return;// 小区间优化小区间不再递归分割排序降低递归次数if ((end - begin 1) 10){int keyi PartSort3(a, begin, end);QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi 1, end);}else{InsertSort(a begin, end - begin 1);}
}
2.3.3.2 快速排序非递归
void QuickSortNonR(int* a, int begin, int end)
{ST st;STInit(st);STPush(st, end);STPush(st, begin);while (!STEmpty(st)){int left STTop(st);STPop(st);int right STTop(st);STPop(st);int keyi PartSort1(a, left, right);if (keyi 1 right){STPush(st, right);STPush(st, keyi 1);}if (left keyi - 1){STPush(st, keyi - 1);STPush(st, left);}}STDestroy(st);
}
快速排序的特性总结 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序时间复杂度O(N*logN)空间复杂度O(logN)稳定性不稳定 2.4 归并排序
基本思想
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 // 子函数 方便递归
void _MergeSort(int* a, int* tmp, int begin, int end)
{if (end begin)return;int mid (end begin) / 2;// [begin, mid] [mid 1, end]_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid 1, end);// 归并到tmp数组再拷贝回去int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int index begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}while (begin1 end1){tmp[index] a[begin1];}while (begin2 end2){tmp[index] a[begin2];}// 拷贝回原数组memcpy(a begin, tmp begin, (end - begin 1) * sizeof(int));
}// 归并排序 递归实现
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);
}
// 归并排序 非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;// [begin1, end1] [begin2, end2] 归并// 如果第二组不存在这一组不用归并了if (begin2 n){break;}// 如果第二组的右边界越界修正一下if (end2 n){end2 n - 1;}int index i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}while (begin1 end1){tmp[index] a[begin1];}while (begin2 end2){tmp[index] a[begin2];}// 拷贝回原数组memcpy(a i, tmp i, (end2 - i 1) * sizeof(int));}gap * 2;}free(tmp);
}
归并排序的特性总结 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定 2.5 非比较排序
思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤
统计相同元素出现次数根据统计的结果将序列回收到原来的序列中 // 计数排序
void CountSort(int* a, int n)
{int min a[0], max a[0];for (int i 0; i n; i){if (a[i] min)min a[i];if (a[i] max)max a[i];}int range max - min 1;int* count (int*)malloc(sizeof(int) * range);printf(range:%d\n, range);if (count NULL){perror(malloc fail);return;}memset(count, 0, sizeof(int) * range);// 统计数据出现次数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;}}
}
计数排序的特性总结 计数排序在数据范围集中时效率很高但是适用范围及场景有限。时间复杂度O(MAX(N, 范围))空间复杂度O(范围)稳定性稳定 3. 排序算法复杂度及稳定性分析 排序方法平均情况最好情况最坏情况辅助空间稳定性冒泡排序稳定简单选择排序不稳定直接插入排序稳定希尔排序不稳定堆排序不稳定归并排序稳定快速排序不稳定 本文完
