目录1.堆排序2.快速排序1.hoare版本2.挖坑法3.前后指针法4.非递归实现快排注意点3.归并排序1.递归版本2.非递归版本1.堆排序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 (child 1 n a[child 1] a[child]) { child; } if (a[parent] a[child]) { Swap(a[parent], a[child]); } else { break; } parent child; child parent * 2 1; } } void heapsort(int* a, int n) { for (int i (n - 1 -1) / 2; i 0; i--) { adjustdown(a, n, i); } for (int i n-1; i 0; i--) { Swap(a[0], a[i]); adjustdown(a, i, 0); } } void printarr(int* a, int n) { for (int i 0; i n; i) { printf(%d , a[i]); } printf(\n); } void heaptest() { int arr[] { 4,7,1,9,3,6,5,8,3,2,0 }; printarr(arr, sizeof(arr)/sizeof(int)); heapsort(arr, sizeof(arr)/sizeof(int)); printarr(arr, sizeof(arr)/sizeof(int)); }我们先用向下调整算法建堆。使用向下调整算法建堆的前提是该节点的子树都是堆。那么我们从最后一个节点的父节点开始向下调整算法这样因为两个子树都是叶子节点因此满足条件。从后往前一直遍历到父节点为根节点那么就建好堆了。然后只需要不断将第一个和最后一个节点的值交换把最大值放到末尾然后不断从根节点向下建堆即可每次都挑选出最大值我们依次把他们放到末尾即可。2.快速排序主逻辑递归1.hoare版本void Swap(int* a, int* b) { int tmp *a; *a *b; *b tmp; } void printarr(int* a, int n) { for (int i 0; i n; i) { printf(%d , a[i]); } printf(\n); } int partsort(int* a, int left, int right) { int keyi left; while (left right) { while (left right a[left] a[keyi]) { left; } while (left right a[right] a[keyi]) { right--; } Swap(a[left], a[right]);//如果是因为leftright结束交换值也并不影响结果 } Swap(a[keyi], a[left]); return left; } void quicksort(int* a, int begin, int end) { if (begin end)return; int keyi partsort(a, begin, end); quicksort(a, begin, keyi-1); quicksort(a, keyi 1, end); } void quicktest() { int arr[] { 4,7,1,9,3,6,5,8,3,2,0 }; printarr(arr, sizeof(arr) / sizeof(int)); quicksort(arr,0, sizeof(arr) / sizeof(int)-1); printarr(arr, sizeof(arr) / sizeof(int)); }我们以左边第一个下标为keyi因此先从右边开始找1.先从右往左找到比a【keyi】小的值2.再从左往右找到比a【keyi】大的值交换这两个值。3.不断重复以上过程直到相遇left right4.交换a【keyi】和a【left】注意点1.我们在移动下标时判断条件是a[left] a[keyi]lefta[right] a[keyi] right--这是为了防止遇到与a【keyi】相等的值的时候陷入死循环2.我们在寻找下标的小循环中也加入leftright的判断是因为防止极端情况。如果不判断就会越界而且如果是因为leftright结束交换值也并不影响结果同时因为这个极端情况原因我们遍历是从最左边keyi处开始遍历不然会忽略掉这种情况。也是注意点1中判断条件需要加的原因3.我们再来谈谈为什么从一边开始调整要从另一边开始找起以上面的情况为例子因为这样可以保证他们相遇时候所处在的值一定比a【keyi】小情况1、left不动right先移动与left相遇此时a【keyi】还在原位情况2. right移动后找到小值left移动后与right相遇此时该位置的值比a【keyi】小情况3left与right先各自移动并且交换一次然后right再移动和left相遇此时因为已经交换过a【left】处储存的值小于a【keyi】因此也符合综上2.挖坑法int partsort(int* a, int left, int right) { int key a[left]; while (left right) { while (left right a[right] key) { right--; } a[left] a[right]; while (left right a[left] key) { left; } a[right] a[left]; } a[left] key; return left; }把a【keyi】的位置先挖走记录这个key值。1.从右边往左找小把这个值填入坑中同时这个位置形成一个新的坑2.从左边往右找大 把这个值填入坑中同时这个位置形成一个新的坑3.重复以上操作直到leftright然后把key值填入这个坑中此时这个位置一定是坑因为left和right永远有一个是坑3.前后指针法int partsort(int* a, int left, int right) { int prev left; int cur left 1; int keyi left; while (cur right) { if (a[cur] a[keyi] prev ! cur)//这里直接判断一下相等就不交换并且在判断条件 //的地方就更新prev { Swap(a[prev], a[cur]); } cur;//cur就是一直往前走直到结束遇到相应位置才有操作因此直接放到循环中 } Swap(a[keyi], a[prev]); keyi prev; return keyi; }cur一直向后找小于key的位置如果a【cur】 keyprev然后交换a【prev】和a【cur】如果cur所在位置的值都比key小那么cur和prev拉不开差距.prev后和cur交换就是自身交换如果遇到比key大的值就会拉开差距此时如果cur遇到比key小的值这个值就会和一个比key大的值交换因为prev和cur原本中间隔着的都是大于key的值prev后再交换就会是这样的结果这样相当于把大的往右推小的往左推cur走出数组结束key与a【prev】交换即可4.非递归实现快排stack.h#pragma once #include malloc.h #include stdio.h #include cassert #define INITSIZE 20 // 支持动态增长的栈 typedef int STDataType; typedef struct Stack { STDataType* _a; int _top; // 栈顶 int _capacity; // 容量 }Stack; // 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空如果为空返回非零结果如果不为空返回0 int StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps);stack.cpp#define _CRT_SECURE_NO_WARNINGS 1 #includestack.h void CheckCapacity(Stack* ps) { if (ps-_top 1 ps-_capacity) return; STDataType* tmp (STDataType*)realloc(ps-_a, ps-_capacity * 2 * sizeof(STDataType)); if (tmp NULL) { perror(CheckCapacity); return; } ps-_a tmp; ps-_capacity ps-_capacity * 2; } // 初始化栈 void StackInit(Stack* ps) { STDataType* tmp (STDataType*)malloc(INITSIZE * sizeof(STDataType)); if (tmp NULL) { perror(StackInit); return; } ps-_a tmp; ps-_capacity INITSIZE; ps-_top -1; } // 入栈 void StackPush(Stack* ps, STDataType data) { CheckCapacity(ps); ps-_top; ps-_a[ps-_top] data; } // 出栈 void StackPop(Stack* ps) { if (ps-_top -1)return; ps-_top--; } // 获取栈顶元素 STDataType StackTop(Stack* ps) { assert(!StackEmpty(ps)); return ps-_a[ps-_top]; } // 获取栈中有效元素个数 int StackSize(Stack* ps) { return ps-_top 1; } // 检测栈是否为空如果为空返回非零结果如果不为空返回0 int StackEmpty(Stack* ps) { if (ps-_top -1)return 1; return 0; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps-_a); ps-_a NULL; ps-_capacity 0; ps-_top -1; }void QuickSortNonR(int* a, int begin, int end)//非递归快排 用栈模拟递归过程 { Stack st; StackInit(st); StackPush(st, end);//我们需要一个区间这里直接让两个数入栈只是顺序需要注意 StackPush(st, begin);//因为栈是先进后出 因此先进end int left, right, keyi; while (!StackEmpty(st)) { left StackTop(st); StackPop(st); right StackTop(st); StackPop(st); keyi PartSort(a, left, right);//由于栈后进先出的性质我们每次先把右半部分入栈 if (keyi 1 right) { StackPush(st, right); StackPush(st, keyi 1); } if (keyi - 1 left) { StackPush(st, keyi - 1); StackPush(st, left); } } StackDestroy(st); }注意点以上三种方法只是实现形式不同时间复杂度是完全相同的并且主逻辑的代码不需要更改就是一个递归只需要把部分排序修改即可3.归并排序将已有序的子序列合并得到完全有序的序列。下图可以形象说明其过程不断向下分解知道每个子区间都有序将两个子区间合并不断重复即可得到最终的结果。1.递归版本void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin end)return; if (end - begin 1 10)//小区间优化 区间很小的时候就不继续递归而是采用一种相对效率较高的排序。因为递归时最下面的几层要进行的调用是最多的 { InsertSort(a begin, end - begin 1); return; } int mid begin (end - begin) / 2; _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid 1, end, tmp); int left begin; int right mid 1; int n begin; while (left mid right end) { if (a[left] a[right]) { tmp[n] a[left]; } else { tmp[n] a[right]; } } while (left mid) { tmp[n] a[left]; } while (right end) { tmp[n] a[right]; } for (int i begin; i end; i) { a[i] tmp[i]; } } void MergeSort(int* a, int n) { int* tmp (int*)malloc(sizeof(int) * n); _MergeSort(a, 0, n - 1 , tmp); free(tmp); }小区间优化优化后排序效率会增高一些但是是锦上添花并没有产生质变2.非递归版本思路其实很简单就是每组一个进行排序然后每组两个四个八个进行排序使用循环即可void MergeSortNonR(int* a, int n) { int gap 1; int* tmp (int*)malloc(sizeof(int) * (n 1)); while (gap n) { int begin1, end1, begin2, end2; for (begin1 0; begin1 n; begin1 gap * 2) { end1 begin1 gap - 1; begin2 begin1 gap; end2 begin1 gap * 2 - 1; if (end1 n || begin2 n)break; if (end2 n)end2 n; int left begin1; int right begin2; int index begin1; while (left end1 right end2) { if (a[left] a[right]) { tmp[index] a[left]; } else { tmp[index] a[right]; } } while (left end1) { tmp[index] a[left]; } while (right end2) { tmp[index] a[right]; } for (int i begin1; i end2; i)//排一段赋一段 越界就break { a[i] tmp[i]; } } gap * 2; } } void MergeSortNonR2(int* a, int n)//这个2只是换一种方式处理边界问题 { int gap 1; int* tmp (int*)malloc(sizeof(int) * (n 1)); while (gap n) { int begin1, end1, begin2, end2; for (begin1 0; begin1 n; begin1 gap * 2) { end1 begin1 gap - 1; begin2 begin1 gap; end2 begin1 gap * 2 - 1; if (end1 n) { end1 n - 1; begin2 n; end2 n - 1; } else if (begin2 n) { begin2 n; end2 n - 1; } else if (end2 n) { end2 n; } int left begin1; int right begin2; int index begin1; while (left end1 right end2) { if (a[left] a[right]) { tmp[index] a[left]; } else { tmp[index] a[right]; } } while (left end1) { tmp[index] a[left]; } while (right end2) { tmp[index] a[right]; } } for (int i 0; i n; i)//一次性都排好越界修改边界如果边界失效就让begin end,这样数组a就不会把它的值赋给tmp了 { a[i] tmp[i]; } gap * 2; } }4.计数排序时间复杂度N range空间复杂度range在某些情况下计数排序其实是效率非常高的一种排序但是它有两个比较大的弊端第一即它依赖数据范围适用于范围集中的数组第二即它依赖下标对应即它只能排序整型void CountSort(int* a, int n) { int min a[0]; int 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* tmp (int*)malloc(sizeof(int) * range); memset(tmp, 0, sizeof(int) * range); for (int i 0; i n; i) { tmp[a[i] - min]; } int count 0; for (int i 0; i range; i) { while(tmp[i] 0) { a[count] i min; tmp[i]--; } } }5.稳定性稳定性简而言之可以用一下例子简单介绍稳定性一般用于以某种标准确定某些相同数的排序比如比赛时相同分数时时间花费少的排名考前又或者例如考试成绩同分时按语文成绩排序我们可以先将名次按照语文成绩排序再按照总分排序这样即可顺利划分下面是一些常见排序的稳定性比较值得注意的是选择排序选择排序可以在选数的时候保证稳定性但是在交换数据的时候就不能保证了