有哪些网站做的比较好的,站内优化怎么做,模板网站官网,免费咨询法律目录
前言
1.直接插入排序
2.希尔排序
3.选择排序
4.堆排序
5.冒泡排序
6.快速排序
6.1Hoare版本
6.2挖坑法
6.3前后指针法
6.4快速排序的递归实现
6.5快速排序的非递归实现
7.归并排序
8.计数排序#xff08;非比较排序#xff09;
9.补充:基数排序
10.总结…目录
前言
1.直接插入排序
2.希尔排序
3.选择排序
4.堆排序
5.冒泡排序
6.快速排序
6.1Hoare版本
6.2挖坑法
6.3前后指针法
6.4快速排序的递归实现
6.5快速排序的非递归实现
7.归并排序
8.计数排序非比较排序
9.补充:基数排序
10.总结排序算法的复杂度及稳定性分析 前言 排序 排序就是使一串记录按照其中某个或某些关键字的大小递增或者递减的排列起来的操作 内部排序数据元素全部存放在内存中的排序 外部排序数据元素太多而不能同时放在内存中根据排序过程的要求不断在内外存之间移动数据的排序 常见的排序算法 以上排序算法都是比较排序还有计数排序这类非比较排序算法一下我们对各个排序算法进行代码实现 1.直接插入排序 直接插入排序是一种简单的插入排序算法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 过程当插入第ii1个元素时前面的array[0]...array[i-1]已经有序此时用array[i]的排序码与array[i-1]array[i-2]...的排序码依次比较找到插入位置后将原来位置上的元素顺序后移将array[i]插入 Note: 对于数组中的第一个数据不需要进行比较因此第一步操作的是a[1]处的数据区间[0,0]上的数据即a[0]这一个数据是有序的因此外层循环只需要对n-1次对a[1]到a[n-1]共n-1个数据进行处理 对于要处理的a[i]依次与a[i-1]a[i-2]比较如果大于a[i]则交换升序排列的情况 优化备份i处的数据依次与a[i-1]a[i-2]比较大于a[i]则向后移动一个位置否则在小于a[i]的数据元素的后一个位置插入a[i] 时间复杂度与空间复杂度 插入排序是在存放原数据的数组上进行操作所以直接插入排序算法的空间复杂度是O(1) 1️⃣当原数据的序列是逆序时为最坏情况此时直接插入排序算法的时间复杂度是O(N^2) 如上图序列逆序时数据的挪动次数为123...n-1 n(n-1)/2 所以时间复杂度为O(N^2) 2️⃣当原数据的序列有序时为最好情况此时直接插入排序算法的时间复杂度是O(N) 如上图序列顺序排列时总共进行了n-1次比较没有数据的挪动 因此时间复杂度为O(N 总结元素集合越接近有序直接插入排序算法的时间效率越高 //直接插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){// [0,end]有序end1处的数据找到正确位置后[0, end1]有序int end i;int tmp a[end 1];while (end 0){//升序排列if (a[end] tmp){a[end 1] a[end];--end;}else{break;}}//此时a[end]tmpa[end 1] tmp;}
}
2.希尔排序 希尔排序又称为缩小增量排序希尔排序的基本思想先选定一个整数gap把待排序文件中的所有记录分成n/gap个组每一组内的记录进行排序然后更新缩小gap重复上述分组和排序的操作当gap1时所有记录在同一组内排序即使所有记录有序 以下以初始增量为3为例 第一次分组如下图 每一组内的记录进行排序使用直接插入排序算法 缩小gap1即对序列5 1 2 5 6 3 8 7 4 9进行排序 每一组记录使用直接插入排序算法当gap不为1时每组记录的数据元素并不是连续排列的而是间隔gap因此需要对直接插入排序算法进行改造 for (int i 0; i n - gap; i)
{int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;
} 优化for循环调整部分为i时每次直接插入排序排一组记录当改为igap时可以实现多组记录同时排序 Note 希尔排序是对直接插入排序的优化当gap1时都是预排序目的是使数据集合接近有序当数据集合接近有序时直接插入排序的时间效率较高 gap的选择 gap的取法有多种最初Shell提出取gap n/2gap gap/2直到gap 1后来Knuth提出取gap gap/3 1。我们采用Knuth提出的方式取值。 gap越大大数可以越快的跳到后面gap越小跳的越慢但数据集合越接近有序 时间复杂度和空间复杂度 希尔排序算法不额外开辟空间其空间复杂度为O(1) 对希尔排序的时间复杂度分析很困难在特定情况下可以准确估算关键码的比较次数和对象移动次数但想要弄清楚关键码的比较次数和对象移动次数与增量选择之间的依赖关系目前还没有较完整的数学分析Knuth在《计算机程序设计技巧》中的结论是在n很大时关键码的平均比较次数和对象平均移动次数大约在n^1.25到1.6*n^1.25范围内这是在利用直接插入排序作为子序列排序方法的情况下得到的。 //希尔排序
void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 1;//更新增量//for (int i 0; i n - gap; i)for (int i 0; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}
3.选择排序 选择排序的基本思想每一次从待排的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到所有待排序的数据元素排完 直接选择排序的步骤 1️⃣在元素集合array[i]到array[n-1]中选择关键码最大小的数据元素 2️⃣若它不是这组元素中的最后一个或第一个元素则将它与这组元素中的最后一个或第一个元素交换 3️⃣在剩余的array[i]到array[n-2]array[i1]到array[n-1]集合中重复上述步骤直到集合剩余一个元素 简单来说直接选择排序将数据集合分成两部分有序部分和无序部分 以排升序为例每次选取待排数据集合即无序部分中的最大数放到无序部分的第一个位置即有序部分之后的第一个位置就完成了一个数据元素的排序 优化选择元素时选取最大元素和最小元素的操作同时进行一趟比较选出最大的元素放在a[end]位置选出最小的元素放在a[begin]位置beginend--重复上述操作 优化之后数组的两端有序部分中间为无序部分 时间复杂度和空间复杂度 直接选择排序算法不额外开辟空间其空间复杂度为O(1) 1️⃣当原数据的序列是逆序时为最坏情况此时选择排序算法的时间复杂度是O(N^2) 遍历待排数据元素集合共n个数据选出最大值和最小值需要比较n-1次 遍历待排数据元素集合共n-2个数据选出最大值和最小值需要比较n-3次 综上所述当原序列的数据元素逆序时总共比较的次数为 n-1n-3...1 (n/2) *n / 2 所以直接选择排序的时间复杂度为O(N^2) 2️⃣当原数据的序列有序时为最好情况此时直接插入排序算法的时间复杂度是O(N^2) 对于直接选择排序算法来说逆序和顺序的时间复杂度相同因为进行数据选择的操作是相同的都是进行遍历选数因此效率不高】 void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
//选择排序
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){// 选出最小的放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]);// 修正maxi:特殊情况begin和maxi重叠时执行一次交换maxi记录的是最小值if (maxi begin)maxi mini;Swap(a[end], a[maxi]);begin;--end;}
}
4.堆排序
冒泡排序详解可以参考CSDN
5.冒泡排序
冒泡排序详解可以参考CSDN
6.快速排序 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法快速排序的基本思想为任取待排元素序列中的某个元素作为基准值按照该排序码将待排序集合分割成两个子序列左子序列中的所有元素均小于基准值右子序列中的所有元素均大于基准值然后左右序列重复该过程直到所有元素都排列在相应的位置上为止 快速排序递归实现与二叉树的前序遍历规则类似需要注意的是如何按照基准值来对区间中数据进行划分常见的方式有以下几种 6.1Hoare版本 单趟排序选定一个基准值key一般情况下为第一个或最后一个元素设置两个变量left和right分别指向数据元素集合的头和尾left向后找大数right向前找小数找到则交换直到二者相遇将相遇位置的数与key交换。 单趟排序结束后数据元素的排列为小数 key 大数其中小大数是指小大于key的数。key的位置已经确定不需要再更改分割出了两个子区间若这两个子区间有序则整体有序因此递归对两个子区间进行排序即可使整体有序。 以下为单趟排序的参考代码 int keyi left;//选取第一个数作为关键值while (left right){//right找小数while (left right a[right] a[keyi]){--right;}//left找大数while(left right a[left] a[keyi]){left;}//判断left和right的关系防止错过if (left right){Swap(a[left], a[right]);}}//left和right相遇交换相遇位置的值和关键值Swap(a[left], a[keyi]); Note 1️⃣与关键值比较大小时需要注意与关键值相等的特殊情况 对left找大数遇到小于key的值时继续向后走遇到等于key的值时也应该向后继续寻找如果不过滤等于key的值则会产生死循环 当数据元素集合中为单值时如果不过滤等于的情况right找小数的循环将会是一个死循环或者当key a[right]时也会陷入死循环 2️⃣当选取第一个数据元素作为keyleft与right相遇时交换相遇位置的数据与key如何保证相遇的位置比key小key是第一个数据元素属于小数区间 left和right相遇有两种情况 right停下来left撞到right相遇相遇位置比key小right找小数所以right停下来的位置为小于key的数即相遇位置为小于key的数属于小数区间。因此若选取第一个数据元素做key则right先走left停下来right撞到left相遇相遇位置比key大left找大数所以left停下来的位置为大于key的数即相遇位置为大于key的数属于大数区间。因此若选取最后一个数据元素做key则left先走 // Hoare
int PartSort1(int* a, int left, int right)
{//取第一个数据元素为关键值int keyi left;while (left right){// R找小while (left right a[right] a[keyi]){--right;}// L找大while (left right a[left] a[keyi]){left;}if (left right)Swap(a[left], a[right]);}//相遇位置为meetiint meeti left;Swap(a[meeti], a[keyi]);return meeti;
} 快速排序的优化主要是对关键值key选取的优化 key的选择有三种方法 随机选key针对有序序列先key为最中间位置的数据三数取中即第一个元素中间位置元素最后一个位置元素三数取中位数 三数取中的函数接口如下 int GetMidIndex(int* a, int left, int right)
{int mid left (right - left) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}// a[left] a[mid]else{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
} 对key的选择优化之后可以减少递归的层数有效避免栈溢出 关键值key的选择优化之后Hoare版本的单趟排序可以优化通过三数取中的方法确定关键值key后将key与第一个数据交换此时关键值key仍为第一个数据因此其他地方不需要修改 // Hoare
int PartSort1(int* a, int left, int right)
{// 三数取中int mid GetMidIndex(a, left, right);Swap(a[left], a[mid]);int keyi left;while (left right){// R找小while (left right a[right] a[keyi]){--right;}// L找大while (left right a[left] a[keyi]){left;}if (left right)Swap(a[left], a[right]);}//相遇位置为meetiint meeti left;Swap(a[meeti], a[keyi]);return meeti;
}
6.2挖坑法 挖坑法是对Hoare版本的改进确定关键值key之后将其备份并将其作为一个坑位数据集合中的第一个元素right先走找小数找到则将该小数填到坑位中并更新该小数的位置为新的坑位left再走找大数找到后将该大数填到坑位中并更新该大数的位置为新的坑位重复上述操作直到left和right相遇相遇位置为一个坑位填入关键值key 具体过程如下图所示 // 挖坑法
int PartSort2(int* a, int left, int right)
{// 三数取中int mid GetMidIndex(a, left, right);Swap(a[left], a[mid]);int key a[left];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;
}
6.3前后指针法 前后指针法也是对Hoare版本的改进确定关键值key数据元素集合的第一个元素并备份设置两个指针prev和cur,prev初始化为第一个数据元素cur初始化为prev的下一个数据元素当cur没有越界时cur向后找小数找到则交换prev指向的数据和cur指向的元素prevcur重复上述操作直到cur越界时交换prev指向的数据元素和关键值key Noteprev的操作在交换操作之前cur的操作在交换操作之后 在cur找到小数时prev指向的也为小数其下一个位置为大数所以prev需要先加1再交换 具体过程如下图所示 特殊情况prev cur时会产生自己和自己交换的情况因此需要过滤 // 前后指针法
int PartSort3(int* a, int left, int right)
{// 三数取中int mid GetMidIndex(a, left, right);Swap(a[left], a[mid]);int keyi left;int prev left;int cur left 1;while (cur right){// cur找小if (a[cur] a[keyi] prev ! cur)Swap(a[cur], a[prev]);cur;}Swap(a[keyi], a[prev]);return prev;
}
6.4快速排序的递归实现 快速排序的递归实现 单趟排序结束后数据元素的排列为小数 key 大数 小数区间为[begin ,keyi -1]大数区间为[keyi1end] 按照单趟排序的方法递归对这两个区间排序即可 递归结束的条件区间中只有一个值时递归调用结束beginend或者beginend区间无效时递归调用结束 //快速排序
void QuickSort(int* a, int begin, int end)
{if (begin end){return;}//每趟排序区间的划分Hoare挖坑法前后指针法//调用相应接口即可int keyi PartSort1(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}
6.5快速排序的非递归实现 函数的调用需要在开辟栈帧如果递归调用的层数太深可能会造成栈溢出 我们可以借助数据结构中的栈来优化快速排序数据结构中的栈是在堆区开辟空间堆区的空间要远远大于栈区空间 实际上快速排序的非递归是借助数据结构中的栈模拟递归的过程 非递归实现思路每次将区间的左右区间压栈当栈不为空时取栈顶两个元素分别作为一趟排序的区间的左右端点进行排序 Note: 如果先定义right则需要区间左端点begin要先入栈区间右端点end后入栈这样才能保证right被区间右端点赋值,left被区间左端点赋值 //快速排序的非递归实现
void QuickSortNonR(int* a, int begin, int end)
{ST st;StackInit(st);StackPush(st, begin);StackPush(st, end);while (!StackEmpty(st)){//区间右端点int right StackTop(st);StackPop(st);//区间左端点int left StackTop(st);StackPop(st);//区间划分单趟排序int keyi PartSort3(a, left, right);//右区间if (keyi 1 right){StackPush(st, keyi 1);StackPush(st, right);}//左区间if (left keyi - 1){StackPush(st, left);StackPush(st, keyi - 1);}}StackDestroy(st);
}
7.归并排序 归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法的典型应用。将已经有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序若将两个有序表合并成一个有序表称为二路归并。 二路归并排序的步骤如下图 由如下动态图可以更好的理解二路归并排序的过程 归并排序的递归实现类似于二叉树的后续遍历采用二叉树的后续遍历框架递归结束的条件是beginend区间的划分为 [begin, mid] 和 [mid1, end]mid为中间位置 归并排序的时间复杂度和空间复杂度 归并排序需要额外开辟一个长度为N的数组因此其空间复杂度为O(N) 归并排序的时间复杂度为O(N*logN) void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)return;int mid (end begin) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid 1, end, tmp);// 两两归并成有序序列取小的尾插// [begin, mid] [mid1, end]int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}//左区间中还有数据while (begin1 end1){tmp[i] a[begin1];}//右区间中还有数据while (begin2 end2){tmp[i] 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, 0, n - 1, tmp);free(tmp);tmp NULL;
}
8.计数排序非比较排序 计数排序又称为鸽巢原理是对哈希定址法的直接应用 计数排序的操作步骤 统计相同元素出现的次数根据统计的结果将序列回收到原来的序列中 Note: 计数排序中的相对映射 1.统计个数得到个数记录数组C 2.将数组C转换成C[i]中存放的是值小于等于i的数据的个数 3.为A数组从前向后的每个元素找到对应的B中的位置每次从A中复制一个元素到B中C中相应的计数减一 4.当A中的所有数据都复制到B之后B中存放的就是有序的数据 总结计数排序在数据范围集中时效率很高但其适用范围有限 void CountSort(int* a, int n)
{int max a[0], min a[0];for (int i 1; i n; i){if (a[i] max){max a[i];}if (a[i] min){min a[i];}}int range max - min 1;//统计计数int* countA (int*)malloc(sizeof(int) * range);if (countA NULL){perror(malloc fail);return;}memset(countA, 0, sizeof(int) * range);for (int i 0; i n; i){countA[a[i] - min];//映射的相对位置}//排序int j 0;for (int i 0; i range; i){while (countA[i]--){a[j] i min;j;}}
}
9.补充:基数排序 基数排序也属于非比较排序 基数排序的操作步骤 分发数据回收数据 多关键字排序有两种方式MSD最高位优先和LSD最低位优先 基数排序的步骤如下图 10.总结排序算法的复杂度及稳定性分析 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中a[i] a[j]且a[i] 在 a[j]之前而在排序后的序列中a[i] 仍在 a[j]之前则称这种排序算法是稳定的否则称之为不稳定的 1️⃣直接插入排序稳定 关键码相同则不调整继续向后排序 2️⃣希尔排序不稳定 预排序时相同的数据可能分到不同的组不能保证稳定性 3️⃣选择排序:不稳定 4️⃣堆排序不稳定 当一个堆为单值时向下调整会影响该值的稳定性因此堆排序不稳定 5️⃣冒泡排序稳定 关键码相同则不调整继续向后排序 6️⃣快速排序不稳定 7️⃣归并排序稳定 关键码相同则不调整继续向后排序 时间复杂度与空间复杂度总结 算法平均情况最好情况最坏情况辅助空间稳定性冒泡排序O(N^2)O(N)O(N^2)O(1)稳定简单选择排序O(N^2)O(N^2)O(N^2)O(1)不稳定直接插入排序O(N^2)O(N)O(N^2)O(1)稳定希尔排序O(N*logN)~O(N^2)O(N^1.3)O(N^2)O(1)不稳定堆排序O(N*logN)O(N*logN)O(N*logN)O(1)不稳定归并排序O(N*logN)O(N*logN)O(N*logN)O(N)稳定快速排序O(N*logN)O(N*logN)O(N^2)O(logN)~O(N)不稳定
