团购网站模板免费下载wordpress漂亮手机网站模板

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

团购网站模板免费下载,wordpress漂亮手机网站模板,企业网站的建设哪家比较好,怎么建立一个平台目录 七大排序的时间复杂度和稳定性 排序 插入排序 简单插入排序 希尔排序 选择排序 简单选择排序 堆排序 交换排序 冒泡排序 快速排序 快排的递归实现
hoare版本的快排 挖坑法的快排 双指针法的快排 快排的非递归 归并排序 归并的递归实现 归并的非递归实现…目录 七大排序的时间复杂度和稳定性 排序 插入排序 简单插入排序 希尔排序 选择排序 简单选择排序 堆排序 交换排序 冒泡排序 快速排序 快排的递归实现  hoare版本的快排 挖坑法的快排 双指针法的快排 快排的非递归 归并排序 归并的递归实现 归并的非递归实现 补充 快排的三路划分 七大排序的时间复杂度和稳定性 排序时间的复杂度和稳定性-CSDN博客关于七大排序的时间复杂度和稳定性的总结帮助读者迅速掌握各各排序的优劣在不同情况下如何选择。https://blog.csdn.net/2401_87944878/article/details/145404375 排序 排序就是将一组数据按照递增或递减的方式将其排列。 排序包含两种 内部排序数据元素全部放在内存中的排序。 外部排序数据太多不能同时放在内存中根据排序的过程不能在内外存之间移动的排序。外部排序要对文件进行操作。 排序包含有四大实现插入排序选择排序交换排序归并排序。根据这四个实现又可以分支出一共7个排序思想简单插入排序希尔排序选择排序堆排序冒泡排序快速排序归并排序。下面我们对这七种排序进行讲解。 插入排序 插入排序包含两种简单插入排序希尔排序。 简单插入排序 如图简单插入怕排序就是遍历原数组将每一个元素放在其指定位置。先拿出一个元素向前找看比它大的先后移直到找到比它小的。 //简单插入排序 void InsertSort(int* a, int n) {//插入排序向前找到元素的指定位置for (int i 1; i n; i){int end i;int cur a[end];while(end0){if (a[end - 1] cur){a[end] a[end - 1];end–;}elsebreak;}a[end] cur;} } 希尔排序 希尔排序实际上是对简单插入排序的一种优化。简单插入排序每次与其相邻的元素进行比较而希尔排序是将一个数组分成多个组将每个组进行简单插入排序这样可以让大的数迅速到前面去小的数迅速到后面去。 可以看到第一次gap是5时将下标0和5比较1和6比较2和7比较….这样可以迅速将大的数移到前面去将小的数移到后面去这样就使的数组更加趋于有序的状态。 通过gap从大到小的变化使得当gap较小的时候可以快速向前找到它的位置更快的让每次循环break掉让效率更快。 //希尔排序 void ShellSort(int* a, int n) {//希尔排序与插入排序的区别在于其先进行预排序int gap n;while (gap 1){gap / 2;for (int i 0; i gap; i){for (int m i gap; m n; m gap){int end m;int cur a[end];while (end 0){if (a[end - 1] cur){a[end] a[end - 1];end–;}elsebreak;}a[end] cur;}}} } 选择排序 选择排序包含两种简单选择排序和堆排序 简单选择排序 简单选择排序就是遍历原数组直接找到最大值或最小值将其放在尾和首可以一次只找出一个最值也可以将最大值和最小值同时找到。 以上是遍历未排序的数组每次找出最下的元素交换下面演示遍历未排序的数组每次找打最小和最大的元素。  //交换函数 void Swap(int* a, int* b) {int tmp *a;*a *b;b tmp; }//简单选择排序 void SelectSort(int a, int n) {//一次遍历选出最大值和最小值int left 0;int right n - 1;while (left right){int min left;int max left;for (int i left; i right; i){if (a[min] a[i])min i;if (a[max] a[i])max i;}//交换Swap(a[left], a[min]);//注意此处如果left对应的值就是最大值的时候//将min和left交换后max就在min的位置了if (left max)Swap(a[right], a[min]);elseSwap(a[right], a[max]);left, right–;} } 堆排序 堆排序就是利用二叉树的性质通过建大堆或小堆将最大的数据或最小的数据放在指定位置。在二叉树中已经详细讲过堆了这里就直接贴代码。 二叉树C语言-CSDN博客文章浏览阅读1.3k次点赞19次收藏18次。帮助读者快速掌握树这一数据结构了解堆的功能能够实现堆排序以及如何再大量数据中快速找到前K个最大元素如何处理普通二叉树普通二叉树的遍历等知识。https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931 //向下调整 void AdjustDown(int* a, int n, int parent) {int child 2 * parent 1;while (child n){if (child1na[child] a[child 1])child;if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child 2 * parent 1;}elsebreak;} }//堆排序 void HeapSort(int* a, int n) {//先建大堆for (int i (n - 2) / 2; i 0; i–){//向下调整AdjustDown(a, n, i);}//将堆顶的最大值和堆低交换int sz n - 1;Swap(a[0], a[sz]);sz–;while (sz 0){AdjustDown(a, sz 1, 0);Swap(a[0], a[sz]);sz–;} } 交换排序 交换排序分为冒泡排序和快速排序。 冒泡排序 冒泡排序简单没有实际作用这里直接贴代码。 //冒泡排序 void BubbleSort(int* a, int n) {for (int i 0; i n - 1; i){for (int m 0; m n - 1 - i; m){if (a[m] a[m 1])Swap(a[m], a[m 1]);}} } 快速排序 快速排序是将一个元素key作为基准先找到这个key的准确位置将小于key的放在key的左边将大于key的放在右边。 快排的递归实现  hoare版本的快排 如图将数组首元素作为key通过左右指针让R指针先走找到小于key的值停L指针再走大于key的时候停将L位置和R位置交换直到L和R相遇时停止这个位置就是key排序后的位置。 思考为什么要让R指针想走能否让L指针想走  关于key的选择有三种方法选择最左边的随机选择比较数组左右中间这三个值选出次小的值。此处选择三数取中最好可以尽量避免只出现一个递归函数。 //快排Hoare版本 void QuickSort(int* a, int begin,int end) {if (begin end)return;//快排就是将key放在正确位置上去。//三数取中int mid Mid(begin, end);Swap(a[begin], a[mid]);int keyi begin;int left begin;int right end;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]);keyi left;QuickSort(a, begin, keyi - 1);QuickSort(a, keyi1, end); } 挖坑法的快排 利用挖坑法可以直接不用思考数组那一边的指针先走的问题。 挖坑法就是将keyi的位置值保留R指针找比key小的将其填在keyi的位置R指针处变为坑直到L指针和R指针相遇将其位置的key填入坑。 //快排挖坑法 void HoleSort(int* a, int begin, int end) {if (begin end)return;int mid Mid(begin, end);Swap(a[mid], a[begin]);int hole begin;int left begin;int right end;int key a[hole];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;int keyi hole;HoleSort(a, 0, keyi - 1);HoleSort(a, keyi1, end); } 双指针法的快排 分别利用两个指针一个向前面走如果cur对用的值比key小就交换两个指针都向前移动如果cur对应的值大就不交换cur向前移动。 //快排双指针法 void DPoint(int* a, int begin, int end) {if (begin end)return;int mid Mid(begin, end);Swap(a[begin], a[mid]);int keyi begin;int cur begin;int pre begin;while (cur end){if (a[cur] a[keyi]){if (cur ! pre)Swap(a[cur], a[pre]);cur;pre;}else{cur;}}Swap(a[keyi], a[pre - 1]);keyi pre - 1;DPoint(a, begin, keyi - 1);DPoint(a, keyi1, end); } 快排的非递归 快排的非递归就是利用栈将其begin和end的值储存起来再利用栈的“后入先出”的性质每一次拿出一个范围再放入子范围直到栈的空间为空时停止。 此处以Hoare的非递归为例。 typedef struct Stack {int* a;int size;int capacity; }Stack;//栈的初始化 void StackInit(Stack* sp) {sp-capacity 4;sp-a (int*)malloc(sizeof(int) * (sp-capacity));if (sp-a NULL)perror(malloc failed);sp-size 0; }//入栈 void StackPush(Stack* sp, int x) {//检查空间够不够if (sp-size sp-capacity){sp-capacity * 2;int* tmp (int*)realloc(sp-a, sizeof(int) * (sp-capacity));if (tmp NULL)perror(realloc failed);sp-a tmp;}sp-a[sp-size] x;sp-size; }//出栈 void StackPop(Stack* sp) {sp-size–; }//返回栈顶元素 int StackTop(Stack* sp) {return sp-a[sp-size - 1]; }//检查栈空间是否为空 bool IsStackEmpty(Stack* sp) {if (sp-size 0)return true;elsereturn false; } //快排非递归 void QuickNon(int* a, int begin, int end) {//快排的非递归就是将快排的左右间距存储在栈中Stack s;StackInit(s);StackPush(s, end);StackPush(s, begin);while (!IsStackEmpty(s)){int begin StackTop(s);StackPop(s);int end StackTop(s);StackPop(s);int left begin;int keyi left;int right end;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;if (begin keyi - 1){StackPush(s, keyi - 1);StackPush(s, begin);}if (keyi 1 end){StackPush(s, end);StackPush(s, keyi 1);}} } 归并排序 归并排序的实现就是先对小范围排序再对大范围排序。如图相对两个元素进行排序再对4个元素进行排序依次依次2向后排序。 归并的递归实现 //归并排序 void Merge(int a, int begin, int end) {if (begin end)return;int mid (begin end) / 2;Merge(a, begin, mid);Merge(a, mid 1, end);int begin1 begin;int end1 mid;int begin2 mid 1;int end2 end;int* tmp (int*)malloc(sizeof(int) * (end - begin 1));int j 0;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(a begin, tmp, sizeof(int) * (end - begin 1));free(tmp); } 归并的非递归实现 归并的非递归实现就不能用栈来存储18首尾的范围了可以直接从2个元素排序开始依次2直到排完为止。 //归并的非递归实现 void MergeNon(int a, int begin, int end) {int gap 1;while (gap end){for (int i 0; i end; i 2 * gap){int begin1 i;int end1 i gap - 1;int begin2 i gap;int end2 i 2 * gap - 1;if (begin2 end){break;}if (end2 end)end2 end;int* tmp (int*)malloc(sizeof(int) * (end2 - begin1 1));int j 0;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(a i, tmp, sizeof(int) * (end2-i1));free(tmp);}gap * 2;} } 补充 关于快排当有大量重复的数据出现的时候快排的key的位置可能就是最左边导致向下递归后还是只有一组当大量出现这种情况的时候就会导致快排变成简单选择排序时间复杂度大大增加导致效率降低。此处可以采用三路划分的快排解决。 快排的三路划分 三路划分与普通快排的区别普通快排将数组分成两个部分大于key和小于key的而三路划分将快排分成三个部分大于key小于key和等于key的。 分为左右两个指针以及一个遍历数组的指针将大于key的调到右边将小于key的调到左边将等于key的放在中间。 //快排的三路划分 void TQuickSort(int* a, int begin, int end) {if (begin end)return;int mid Mid(begin, end);Swap(a[begin], a[mid]);int keyi begin;int key a[begin];int left begin;int cur begin;int right end;while (cur right){if (a[cur] key){if (cur ! left)Swap(a[left], a[cur]);left, cur;}else if (a[cur] key){Swap(a[cur], a[right]);right–;}elsecur;}keyi left;TQuickSort(a, begin, keyi - 1);TQuickSort(a, keyi 1, end); }