镇海淘宝网站建设,html网页表格制作,销售网页制作,郑州营销型网站设计本章我们来学习一下数据结构的排序算法#xff01;
目录
1.排序的概念及其运用
1.1排序的概念
1.2 常见的排序算法
2.常见排序算法的实现
2.1 插入排序
2.1.1基本思想#xff1a;
2.1.2直接插入排序#xff1a;
2.1.3 希尔排序( 缩小增量排序 )
2.2 选择排序
2.2…本章我们来学习一下数据结构的排序算法
目录
1.排序的概念及其运用
1.1排序的概念
1.2 常见的排序算法
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 快速排序
1. hoare版本
2. 挖坑法
3. 前后指针版本 编辑
2.3.2 快速排序优化 2.3.3 快速排序非递归
2.4 归并排序
2.5 非比较排序
3.排序算法复杂度及稳定性分析 1.排序的概念及其运用
1.1排序的概念
1排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。
2稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中 r [ i ] r [ j ]且 r [ i ] 在 r [ j ] 之前而在排序后的序列中 r [ i ] 仍在 r [ j ]之前则称这种排序算法是稳定的否则称为不稳定的。
3内部排序数据元素全部放在内存中的排序。
4外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 常见的排序算法 2.常见排序算法的实现
2.1 插入排序
2.1.1基本思想
直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 实际中我们玩扑克牌时就用了插入排序的思想 2.1.2直接插入排序 当插入第i(i1) 个元素时前面的 array[0],array[1],…,array[i-1] 已经排好序此时用 array[i] 的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将 array[i] 插入原来位置上的元素顺序后移 代码案例 // 时间复杂度O(N^2) 逆序
// 最好的情况O(N) 顺序有序
void InsertSort(int* a, int n)
{// [0, end] end1for (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];--end;}else{break;}}a[end 1] tmp;}
} 直接插入排序的特性总结 1. 元素集合越接近有序直接插入排序算法的时间效率越高。 2. 时间复杂度 O(N^2) 3. 空间复杂度 O(1) 它是一种稳定的排序算法。 4. 稳定性稳定 2.1.3 希尔排序( 缩小增量排序 ) 希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个 组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工 作。当到达 1 时所有记录在统一组内排好序 。 代码案例
// 平均O(N^1.3)
void ShellSort(int* a, int n)
{int gap n;// gap 1时是预排序目的让他接近有序// gap 1是直接插入排序目的是让他有序while (gap 1){//gap gap / 2;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 个元素。 代码案例 // 时间复杂度O(N^2)
// 最好的情况下O(N^2)
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[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}Swap(a[begin], a[mini]);if (maxi begin){maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
}直接选择排序的特性总结 1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用。 2. 时间复杂度 O(N^2) 3. 空间复杂度 O(1) 4. 稳定性不稳定 2.2.3 堆排序 堆排序(Heapsort) 是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 代码案例
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){// 假设左孩子小如果解设错了更新一下if (child 1 size 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)
{// O(N)// 建大堆for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
} 堆排序的特性总结 1. 堆排序使用堆来选数效率就高了很多。 2. 时间复杂度 O(N*logN) 3. 空间复杂度 O(1) 4. 稳定性不稳定 2.3 交换排序 基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。 2.3.1冒泡排序 代码案例
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}// 时间复杂度O(N^2)
// 最好情况是多少O(N)
void BubbleSort(int* a, int n)
{for (int j 0; j n; j){bool exchange false;for (int i 1; i n-j; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange true;}}if (exchange false)break;} 冒泡排序的特性总结 1. 冒泡排序是一种非常容易理解的排序 2. 时间复杂度 O(N^2) 3. 空间复杂度 O(1) 4. 稳定性稳定 2.3.2 快速排序 快速排序是Hoare 于 1962 年提出的一种二叉树结构的交换排序方法其基本思想为 任取待排序元素序列中 的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右 子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止 。 代码案例
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{if(right - left 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div1, right)QuickSort(array, div1, right);
}int GetMidi(int* a, int begin, int end)
{int midi (begin end) / 2;// begin end midi三个数选中位数if (a[begin] a[midi]){if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}else{//...}
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int left begin, right end;int keyi begin;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[left], a[keyi]);keyi left;// [begin, keyi-1] keyi [keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi1, end);
} 上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。将区间按照基准值划分为左右两半部分的常见方式有 1. hoare版本 代码案例
int PartSort1(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int left begin, right end;int keyi begin;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[left], a[keyi]);return left;
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort1(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi1, end);
}
2. 挖坑法 代码案例
// 挖坑法
int PartSort2(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int key a[begin];int hole begin;while (begin end){// 右边找小填到左边的坑while (begin end a[end] key){--end;}a[hole] a[end];hole end;// 左边找大填到右边的坑while (begin end a[begin] key){begin;}a[hole] a[begin];hole begin;}a[hole] key;return hole;
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi1, end);
}3. 前后指针版本 代码案例
int PartSort3(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int keyi begin;int prev begin;int cur prev 1;while (cur end){if (a[cur] a[keyi] prev ! cur)Swap(a[prev], a[cur]);cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi1, end);
}2.3.2 快速排序优化 1. 三数取中法选 key 2. 递归到小的子区间时可以考虑使用插入排序 2.3.3 快速排序非递归 代码案例
void QuickSortNonR(int* a, int left, int right)
{Stack st;StackInit(st);StackPush(st, left);StackPush(st, right);while (StackEmpty(st) ! 0){right StackTop(st);StackPop(st);left StackTop(st);StackPop(st);if(right - left 1)continue;int div PartSort1(a, left, right);// 以基准值为分割点形成左右两部分[left, div) 和 [div1, right)StackPush(st, div1);StackPush(st, right);StackPush(st, left);StackPush(st, div);}StackDestroy(s);
} 快速排序的特性总结 1. 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫 快速 排序 2. 时间复杂度 O(N*logN) 3. 空间复杂度 O(logN) 4. 稳定性不稳定 2.4 归并排序 基本思想 归并排序MERGE-SORT 是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法 Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 代码案例
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)return;int mid (begin end) / 2;// [begin, mid][mid1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid1, 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, sizeof(int) * (end - begin 1));
}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);
}//非递归法
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){printf(gap:%2d-, gap);for (size_t 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] 归并//printf([%2d,%2d][%2d, %2d] , begin1, end1, begin2, end2);// 边界的处理if (end1 n || begin2 n){break;}if (end2 n){end2 n - 1;}//printf([%2d,%2d][%2d, %2d] , begin1, end1, begin2, end2);int j begin1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}memcpy(a i, tmp i, sizeof(int) * (end2-i1));}printf(\n);gap * 2;}free(tmp);
} 归并排序的特性总结 1. 归并的缺点在于需要 O(N) 的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度 O(N*logN) 3. 空间复杂度 O(N) 4. 稳定性稳定 2.5 非比较排序 思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤 1. 统计相同元素出现次数 2. 根据统计的结果将序列回收到原来的序列中 代码案例
// 基数排序/桶排序// 计数排序
// 时间O(Nrange)
// 空间O(range)
void CountSort(int* a, int n)
{int min a[0], max a[0];for (int i 1; 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*)calloc(range, sizeof(int));if (count NULL){printf(calloc fail\n);return;}// 统计次数for (int i 0; i n; i){count[a[i] - min];}// 排序int i 0;for (int j 0; j range; j){while (count[j]--){a[i] j min;}}
} 计数排序的特性总结 1. 计数排序在数据范围集中时效率很高但是适用范围及场景有限。 2. 时间复杂度 O(MAX(N, 范围 )) 3. 空间复杂度 O( 范围 ) 4. 稳定性稳定 3.排序算法复杂度及稳定性分析 注 1算法稳定性是指待排序列中相同的值在排序后相对顺序不变这就是算法稳定。 2辅助空间是指在排序的过程中开辟了新的空间。 本篇完
