设计网站欣赏,泰安民生网,网店推广技巧,贵州建设厅网站二建大家好#xff0c;欢迎来到“干货”小仓库#xff01;#xff01; 很高兴在CSDN这个大家庭与大家相识#xff0c;希望能在这里与大家共同进步#xff0c;共同收获更好的自己#xff01;#xff01;无人扶我青云志#xff0c;我自踏雪至山巅#xff01;#xff01;欢迎来到“干货”小仓库 很高兴在CSDN这个大家庭与大家相识希望能在这里与大家共同进步共同收获更好的自己无人扶我青云志我自踏雪至山巅 1.插入排序
1.1基本思想 直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 生活实例我们玩扑克牌时就用了插入排序思想。 1.2直接插入排序 就是将一组已经有序的数组中插入一个新的数据将其放在数组的正确位置最终使数组变成有序。 单趟图例 代码实现及解析 //插入排序
void InsertSort(int* a, int n)
{for (int i 1; i n; i){int endi-1;int tmpa[i];while (end 0){if (a[end] tmp){a[end 1] a[end];--end;}elsebreak;}a[end 1] tmp;}
} 特性总结 ① 元素集合越接近有序直接插入排序算法的时间效率越高 ② 时间复杂度O(N^2) ③ 空间复杂度O(1)它是一种稳定的排序算法 ④ 稳定性稳定 2.希尔排序
2.1基本思想 希尔排序法又称缩小增量法。 基本思想 ①将数据分组(分的组越多每组数据越少) ②对每组中的数据排好序 ③再对整体数据分组比上次分的组数要少然后再对每组进行排序依次循坏进行。 ④直到数据分成一组数据就全部有序了。 2.2实现
代码实现及图解 //希尔排序
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[i gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}elsebreak;}a[end gap] tmp;}}
} 特性总结 ①希尔排序是对直接插入排序的优化。 ② 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 ③稳定性不稳定。 3.选择排序
3.1基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 3.2实现 单趟原理 ①挑选出最大值和最小值 ②将挑选出的最大值和最小值分别与最后一个数据和起始数据交换 代码实现及图解 //交换
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
//选择排序
void SelectSort(int* a, int left, int right)
{while (left right){int minleft, maxleft;for (int i left1; i right; i){if (a[i] a[min])mini;if (a[i] a[max])maxi;}Swap(a[left], a[min]);if (max left)max min;Swap(a[right], a[max]);left;--right;}
} 特性总结 ①直接选择排序思考非常好理解但是效率不是很好。实际中很少使用 ②时间复杂度O(N^2) ③ 空间复杂度O(1) ④稳定性不稳定 4.堆排序
4.1基本思想 堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 4.2实现
代码实现及解析 //交换
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
//向下调整
void AdjustDown(int* a, int n, int parent)
{int child parent *2 1;while (child n){if (child1n a[child] a[child 1])child;if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}elsebreak;}
}
//堆排序
void HeapSort(int* a, int n)
{ //向下调整建堆for (int i (n - 2) / 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;}
} 特性总结 ①堆排序使用堆来选数效率就高了很多。(上一篇文章《C语言数据结构与算法(二叉树)》有讲TOPK问题) ②时间复杂度O(N*logN) ③空间复杂度O(1) ④稳定性不稳定 5.冒泡排序
5.1基本思想 所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。 5.2实现
代码实现及图解 //交换
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}//冒泡排序
void BubbleSort(int* a, int n)
{for (int j 0; j n; j){for (int i 1; i n-j; i){if (a[i - 1] a[i])Swap(a[i], a[i - 1]);}}} 特性总结 ①冒泡排序是一种非常容易理解的排序 ②时间复杂度O(N^2) ③空间复杂度O(1) ④稳定性稳定 6.快速排序 基本思想任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 6.1hoare版本 ①选出一个基准值一般选最左边或者最右边的那个数据也可以选中间的数据然后交换到最左边或者最右边即可。 ②左边做基准值右边先开始移动找到比基准值小就停下来然后左边找比基准值大的。 ③将左右两边找的值进行交换然后继续移动右边左边直到左边大于或大于右边则停下来将基准值和停下来的那个位置进行交换到此单趟就完成了。 ④利用递归继续执行上面步骤。 代码解析图解 //交换
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}//horea版本
int Part1(int* a, int left, int right)
{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[left], a[keyi]);keyi left;return keyi;
}
//快排
void QuickSort(int* a, int left, int right)
{if (left right)return;int keyi Part1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);
}6.2挖坑法
代码解析图解 int Part2(int* a, int left, int right)
{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;
}void QuickSort(int* a, int left, int right)
{if (left right)return;int keyi Part1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);
}6.3前后指针法
代码解析图解 //交换
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}//前后指针法
int Part3(int* a, int left, int right)
{int keyi left;int prev left;int cur left1;while (curright){if (a[cur] a[keyi])cur;else{prev;if (prev ! cur){Swap(a[prev], a[cur]);cur;}elsecur;}}Swap(a[keyi], a[prev]);keyi prev;return keyi;
}
void QuickSort(int* a, int left, int right)
{if (left right)return;int keyi Part1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);
}
6.4快速排序优化 当上面的三种快速排序方法遇到接近有序的数据的时候效率会大大降低可做如下优化 ①三数取中(选基准值)。上面三种方法都可以加上三数取中提高代码效率。 ②小区间优化(小区间用插入排序)。 代码解析及图解 //三数取中
int GetMidNum(int* a, int left, int right)
{int mid left rand() % (right - left);/*int mid (left right) / 2;*/if (a[left] a[right]){if (a[mid] a[left])return left;else if (a[mid] a[right])return right;elsereturn mid;}else{if (a[mid] a[right])return right;else if (a[mid] a[left])return left;elsereturn mid;}
}
//交换
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}//前后指针法
int Part3(int* a, int left, int right)
{int tmp GetMidNum(a, left, right);if (tmp ! left)Swap(a[tmp], a[left]);int keyi left;int prev left;int cur left1;while (curright){if (a[cur] a[keyi])cur;else{prev;if (prev ! cur){Swap(a[prev], a[cur]);cur;}elsecur;}}Swap(a[keyi], a[prev]);keyi prev;return keyi;
}
//快排
void QuickSort(int* a, int left, int right)
{if (left right)return;//小区间优化--小区间直接使用插入排序if ((right - left 1) 10){//int keyi Part1(a, left, right); //hoare版本//int keyi Part2(a, left, right); //挖坑法int keyi Part3(a, left, right); //前后指针法// [left,keyi-1] keyi [keyi1,right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);}else{InsertSort(a left, right - left 1);//插入排序}
}
6.5三路划分法 结合了三数取中、小区间优化。 特殊用途用于解决大量数据相同的情况。 原理 ①比基准值小的数据往左边放。 ②和基准值相等的数据往中间放。 ③比基准值大的数据往右边放。 代码解析及图解 void QuickSortPart4(int* a, int left, int right)
{if (left right)return;if ((right - left 1) 10){InsertSort(a left, right - left 1);//插入排序}else{int begin left;int end right;int tmp GetMidNum(a, left, right);if (tmp ! left)Swap(a[tmp], a[left]);int keyi left;int cur left 1;while (cur right){if (a[cur] a[keyi]){Swap(a[cur], a[keyi]);left;keyi;}else if (a[cur] a[keyi]){Swap(a[cur], a[right]);--right;}elsecur;}QuickSortPart4(a, begin, left - 1);QuickSortPart4(a, right 1, end);}
}
6.6总结 ①快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 ② 时间复杂度O(N*logN) ③空间复杂度O(logN) ④稳定性不稳定 7.快速排序的非递归 递归的问题 ①效率。影响不是很大 ②深度太深会导致栈溢出。 递归改非递归有两种方式: ①直接改成循环。类似斐波那契等情况。 ②使用栈辅助改循环 通过画出快排的递归展开图可以看出本质就是区间在不断的变化。 代码解析 void QuickSortNonR(int* a, int left, int right)
{//利用之前栈的实现接口函数Stack st; StackInit(st);StackPush(st, right);StackPush(st, left);while (!StackEmpty(st)){int begin StackTop(st);StackPop(st);int end StackTop(st);StackPop(st);int keyi Part3(a, begin, end);//前后指针法//[begin,keyi-1] keyi [keyi1,end]if (keyi 1 end){StackPush(st, end);StackPush(st, keyi 1);}if (begin keyi - 1){StackPush(st, keyi - 1);StackPush(st, begin);}}StackDestroy(st);
}8.归并排序
8.1基本思想 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 8.2实现 ①归并排序先递归到区间只有一个数据的时候(分解)才开始进行往回排序(合并)。 ②在合并的时候需要改变数据的位置而且又不能对其他数据造成影响故需要另外的一个数组暂时存储排好序的数据然后拷贝回原数组。 递归展开图 void _MergeSort(int* a, int left, int right, int* tmp)
{if (left right)return;int mid (left right) / 2;//[left,mid] [mid1,right]_MergeSort(a, left, mid,tmp);_MergeSort(a, mid 1, right, tmp);int begin1 left; int end1 mid;int begin2 mid 1; int end2 right;int i left;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}elsetmp[i] a[begin2];}while (begin1 end1)tmp[i] a[begin1];while (begin2 end2)tmp[i] a[begin2];memcpy(a left, tmp left, sizeof(int) * (right - left 1));
}
//归并排序
void MergeSort(int* a, int left, int right)
{int* tmp (int*)malloc(sizeof(int) * (right - left 1));if (tmpNULL)exit(2);_MergeSort(a, left, right, tmp);free(tmp);
} 归并排序的特性总结 1. 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度O(N*logN) 3. 空间复杂度O(N) 4. 稳定性稳定 9.归并排序的非递归 归并排序的递归本质上就是在改变要排序的数据的个数可以直接改成循环。 图解 //归并非递归
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * (n));if (tmp NULL)exit(2);int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){int begin1 i; int end1 i gap - 1;int begin2 i gap; int end2 i 2 * gap - 1;if (end1 n || begin2 n)break;else if (end2 n)end2 n - 1;int j i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}elsetmp[j] a[begin2];}while (begin1 end1)tmp[j] a[begin1];while (begin2 end2)tmp[j] a[begin2];//归并一部分拷贝一部分(拷贝回原组)memcpy(ai, tmpi, sizeof(int) * (end2-i1));}gap * 2;}
}
10.计数排序
10.1基本思想 ① 统计相同元素出现次数 ② 根据统计的结果将序列回收到原来的 10.2实现
代码分析
、
//计数排序
void CountSort(int* a, int n)
{int min a[0];int max a[0];for (int i 1; i n; i){if (min a[i])min a[i];if (max a[i])max a[i];}int range max - min 1;int* CountA (int*)malloc(sizeof(int) * range);//计数数组if (CountA NULL){perror(malloc fail\n);exit(2);}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;}}free(CountA);//释放
}
11.排序稳定性分析 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。(简单来说就是排好序后相同数据的相对位置保持不变则是稳定的否则不稳定)。 排序总结 快乐的时光总是短暂咱们下篇博客再见啦觉得不错的不要忘了给默默努力的自己点个赞和收藏咯感谢支持,谢谢大家
