邯郸企业做网站费用,wordpress登录注册页面,杭州哪家网站建设公司好点,怎么在网上推广产品思维导图#xff1a; 一.插入排序
1.直接插入排序#xff08;InsertSort#xff09;
①手机通讯录时时刻刻都是有序的#xff0c;新增一个电话号码时#xff0c;就是使用插入排序的方法将其插入原有的有序序列。 ②打扑克 步骤#xff1a; ①如果一个序列只有一个数 一.插入排序
1.直接插入排序InsertSort
①手机通讯录时时刻刻都是有序的新增一个电话号码时就是使用插入排序的方法将其插入原有的有序序列。 ②打扑克 步骤 ①如果一个序列只有一个数那么该序列自然是有序的。插入排序首先将第一个数视为有序序列然后把后面的元素视为要依次插入的序列。②我们通过外层循环控制要插入的数下标表示从下标为1处的元素开始插入直到最后一个元素然后用insertVal保存要插入的值。③内层循环负责交换升序降序根据需求设计。④内层循环结束继续进行外层循环插入下一个元素进行排序直到整个序列有序。动图演示 //插入排序
void InsertSort(int* arr, int n)
{int i, j, insertVal;for (i 1; i n; i) //控制要插入的数{insertVal arr[i];//先保存要插入的值//内层控制比较,j 要大于等于 0同时 arr[j]大于 insertval 时arr[j]位置元素往后覆盖for (ji-1; j 0 arr[j] insertVal; j--){arr[j 1] arr[j];}arr[j 1] insertVal;//将insertVal插入两个极端情况//1.前面的数字小于insertVal不进入内层循环直接原地不动//2.前面的数字都大于insertValx放在下标为0处}
}
效果 结论 1. 元素集合越接近有序直接插入排序算法的时间效率越高2. 时间复杂度O(N^2)3. 空间复杂度O(1)它是一种稳定的排序算法4. 稳定性稳定2.希尔排序Shellsort
希尔排序(Shells Sort)是插入排序的一种又称“缩小增量排序”Diminishing Increment Sort是直接插入排序算法的一种更高效的改进版本。
步骤 1.对待排序的序列进行预排让序列接近有序。预排也是借助直接插入排序实现具体实现方法规定一个增量gap间隔为gap的元素为一组然后分组排序直到间隔gap的所有分组排序完成增量(gap)减少继续间隔为gap的元素进行分组排序 当增量减至1时预排完成。gap越大大的数可以越快的到后面小的数可以越快的到前面。 gap越大预排完越不接近有序。 gap越小越接近有序。2.gap1直接进行直接插入排序。动图 //希尔排序
void ShellSort(int* arr, int n)
{int gapn;int i ,insertVal;while (gap 1){//每次对gap折半操作gap gap / 2;//间隔为gap的所有组进行插入排序for (i 0; i n-gap; i){//组员igap下标最大到n-1再多就越界访问了所以in-1-gap上面是开区间表示insertVal arr[igap];for (i; i 0 arr[i] insertVal; i-gap){arr[igap] arr[i];}arr[igap] insertVal;}
}
} 希尔排序的特性总结 1. 希尔排序是对直接插入排序的优化。2. 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的 了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的 对比。3. 希尔排序的时间复杂度不好计算需要进行推导推导出来平均时间复杂度 O(N^1.3— N^24. 稳定性不稳定 二.选择排序
3.选择排序SelectSort
步骤
遍历一遍从待排序列中选出一个最小值然后放在序列的起始位置再找次小的直到整个序列排完。
动图演示 但这种太慢了实际上我们可以一趟选出两个值一个最大值一个最小值然后将其放在序列开头和末尾这样可以使选择排序的效率快一倍。 void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
//选择排序
void SelectSort(int* arr, int n)
{int begin 0, end n - 1;while (begin end){int mini begin, maxi begin;//初始化让最大值和最小值起初都是自己作为一个基准for (int i begin; i end; i){if (arr[i] arr[mini]){mini i;//不断更新在此次遍历过程中遇到的最小值}if (arr[i] arr[maxi]){maxi i;//不断更新在此次遍历过程中遇到的最大值}}Swap(arr[begin], arr[mini]);//此次遍历最小的放到begin处//注意最小值已经放到了begin处但如果begin原先存的是此次遍历最大的数//那么你一交换把最大的数给交换到了mini处所以我们要修正if (begin maxi){// 如果begin跟maxi重叠需要修正一下maxi的位置maxi mini;}Swap(arr[maxi], arr[end]);//此次遍历最大的放到end处begin;end--;}
}
效果 直接选择排序的特性总结 1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用2. 时间复杂度O(N^2)3. 空间复杂度O(1)4. 稳定性不稳定4.堆排序HeapSort
堆排序即利用堆的思想来进行排序
堆的性质
• 堆中某个节点的值总是不大于或不小于其父节点的值
• 堆总是一棵完全二叉树
步骤
升序建大堆若父结点的值恒大于等于子结点的值则该堆称为最大堆max heap降序建小堆若父结点的值恒小于等于子结点的值则该堆称为最小堆min heap
①建堆: 堆的逻辑结构是一个完全二叉树存储结构是数组所以数组也可以看成一个堆但还不满足堆的性质而我们要做的就是调整数组使之建堆成最大堆或最小堆 调整方法使用向下排序算法。 向下调整算法的核心思想选出左右孩子中小的哪一个跟父亲交换,如果要建大堆则相反 向下调整算法的前提建小堆左右子树都必须是小堆才能够进行调整大堆相反。 但数组满足不了这个前提我们就换一种思想从倒数第一个非叶子结点最后一个结点的父亲开始调整。 ②排序 假设我们建的是大堆父结点的值恒大于等于子结点的值然后按照堆删的思想将堆顶和堆底的数据交换但不同的是这里不删除最后一个元素。这样最大元素就在最后一个位置然后从堆顶向下调整到倒数第二个元素这样次大的元素就在堆顶重复上述步骤直到只剩堆顶时停止。 数组确定父子关系
lchild(左孩子)parent父亲*21
rchild(右孩子)parent父亲*22 动图演示 //建堆
void AdjustDown(int* arr, int n, int root)//向下调整
{int parent root;int child parent * 2 1;while (child n){if (child 1 n arr[child 1] arr[child]){child;}if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}
}
//堆排序
void HeapSort(int* arr, int n)
{//建堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(arr, n, i);}//交换for (int i n - 1; i 0; i--){Swap(arr[i], arr[0]);AdjustDown(arr, i, 0);}
} 堆排序的特性总结 1. 堆排序使用堆来选数效率就高了很多。2. 时间复杂度3. 空间复杂度O(1)4. 稳定性不稳定 三.交换排序
5.冒泡排序BubbleSort
两两相邻元素进行比较并且可能需要交换一趟下来该趟的最大小值在最右边。
动图演示 void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
//冒泡排序
void BubbleSort(int* arr, int n)
{for (int i 0; i n; i)//控制趟数{int exchange 0;//记录交换次数for (int j 0; j n - 1 - i; j){//第一趟比较n-1次然后每走完i趟就有i个右边的位被占所以比较次数减iif (arr[j] arr[j 1]){Swap(arr[j], arr[j 1]);exchange 1;}}if (exchange 0){//交换次数为0排序直接结束break;}}
} 冒泡排序的特性总结 1. 冒泡排序是一种非常容易理解的排序2. 时间复杂度O(N^2)3. 空间复杂度O(1)4. 稳定性稳定6.快速排序QuickSort
【递归实现】
快速排序的核心是分治思想
假设我们的目标依然是按从小到大的顺序排列我们找到数组中的一个分割值把比分割值小的数都放在数组的左边把比分割值大的数都放在数组的右边这样分割值的位置就被确定。借助分割值的位置把数组一分为二前一半数组和后一半数组继续找分割值的位置 不断地进行递归最终分割得只剩一个时整个序列自然就是有序的。
重点在于怎么确定分割值的位置下面有挖坑法左右指针法和前后指针法三种方法。 6.1挖坑法
挖坑法确定分割值的位置
步骤 ①定义一个分割值key一般是将待排序序列的最左边或最右边的数据取出赋给key下面以最左面为例那么最最左边数据就可以被覆盖就是所谓的坑。②left代表待排序序列最左端right代表待排序序列最右端 ③首先坑在最左边所以我们让right先走去找比key小的值放到最左边的坑然后此时的right变成了坑所以left在走找比key大的值放到此时的right然后right再走找比key小的值放到此时的left如此进行下去直到left和right最终相遇将key放到相遇点这个坑这时相遇点就是分割值的位置。④借助分割值的位置把数组一分为二前一半数组和后一半数组继续采用这种思想 不断地进行递归最终分割得只剩一个时整个序列自然就是有序的。动图演示 //挖坑法确定分割值的位置
int PartSort1(int* arr, int left, int right)
{int key arr[left];//取出分割值int hole left;//保存坑的位置while (left right){// 右边找小放到左边while (left right arr[right] key){right--;}// 不满足上边的循环就说明右边的right有小的要放到左边的left坑里 arr[hole] arr[right];hole right;//更新坑的位置// 左边找大while (left right arr[left] key){left;}// 不满足上边的循环就说明左边begin有大的放到右边end的坑里arr[hole] arr[left];hole left;}arr[hole] key;return hole;//本次排序完成返回分割值key的下标
}
//快速排序
void QuickSort(int* arr, int left, int right)
{if (left right){//递归停止的条件return;}int keyi PartSort1(arr, left, right);//每一趟排序完成都会返回一个分割值key的下标//借助分割值的位置将序列分为左子区间[left,keyi-1]和右子区间[keyi1,right]//再用分治递归使左子区间和右子区间有序QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi 1, right);
}
效果 6.2左右指针法
左右指针法确定分割值的位置
步骤 ①选定一个分割值key一般是待排序序列的最左边或最右边。②left代表待排序序列最左端right代表待排序序列最右端 ③假设key在最左边那么right先走遇到比key小的值就停下不发生交换然后left开始走直到left遇到一个大于key的数时将left和right的内容交换right再次开始走如此进行下去直到left和right最终相遇此时将相遇点的内容与key的内容交换即可这时相遇点就是分割值的位置。④借助分割值的位置把数组一分为二前一半数组和后一半数组继续采用这种思想 不断地进行递归最终分割得只剩一个时整个序列自然就是有序的。动图演示 //左右指针法确定key的位置
int PartSort2(int* arr, int left, int right)
{int key left;//选定分割值while (left right){// 找小while (left right arr[right] arr[key]){right--;}// 找大while (left right arr[left] arr[key]){left;}Swap(arr[left], arr[right]);} Swap(arr[left], arr[key]);return left;//本次排序完成返回分割值key的下标
}
//快速排序
void QuickSort(int* arr, int left, int right)
{if (left right){//递归停止的条件return;}int keyi PartSort2(arr, left, right);//每一趟排序完成都会返回一个分割值key的下标//借助分割值的位置将序列分为左子区间[left,keyi-1]和右子区间[keyi1,right]//再用分治递归使左子区间和右子区间有序QuickSort(arr, left, keyi- 1);QuickSort(arr, keyi 1, right);
} 6.3前后指针法
前后指针版本确定分割值的位置
步骤 ①规定一个分割值key一般是最左边或是最右边的。②起始时prev指针指向序列开头cur指针指向prev1。③cur从左至右遍历若cur指向的内容小于key则prev先向后移动一位然后交换prev和cur指针指向的内容然后cur指针若cur指向的内容大于key则cur指针直接。如此进行下去直到cur到达end位置此时将key和prev指针指向的内容交换即可。4.这样做本质上就是cur指针遍历一遍待排序序列把所有小于key的数据都放到下标[1prev]这个区间然后把key和prev的内容交换。5.key将待排序序列该分成了两半左边比他小右边比他大然后再让左右序列进行上述操作直至左右序列分割得只剩一个元素时整个序列自然就是有序的。//前后指针版本确定分割值的位置
int PartSort3(int* arr, int left, int right)
{int key left;//选定分割值int curleft1;int prevleft;while(curright){while(arr[cur]arr[key]prev!cur){//只要a[cur]a[key]语句为真prev必须要进行但不一定要发生交换因为prevcur自己和自己交换没意义。Swap(arr[cur],arr[prev]);} cur; } Swap(arr[key], arr[prev]);return prev;//本次排序完成返回分割值key的下标
}
//快速排序
void QuickSort(int* arr, int left, int right)
{if (left right){//递归停止的条件return;}int keyi PartSort3(arr, left, right);//每一趟排序完成都会返回一个分割值key的下标//借助分割值的位置将序列分为左子区间[left,keyi-1]和右子区间[keyi1,right]//再用分治递归使左子区间和右子区间有序QuickSort(arr, left, keyi- 1);QuickSort(arr, keyi 1, right);
}6.4快速排序的优化 1.我们在分割值的选择上可以进行优化假如我要实现升序原待排序序列接近降序这就会造成效率太低递归次数过多导致栈溢出。所以我们可以选出一个中间值和最左右边交换。 方法三数取中
//三数取中
int MidIndex(int* a, int left, int right)
{int mid (left right) / 2;//防止mid越界//int mid left(right - left) / 2;if (a[left] a[right]){if (a[mid] a[left]){return left;}else if (a[mid] a[right]){return right;}else{return mid;}}else{if (a[mid] a[left]){return left;}else if (a[mid] a[right]){return right;}else{return mid;}}
} 2.减少递归次数方法小区间优化 以左右指针法举例
// 三数取中
int GetMidIndex(int* a, int left, int right)
{int mid (left right)/2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}else // a[left] a[mid]{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
}
//左右指针法确定key的位置
int PartSort2(int* arr, int left, int right)
{int mid GetMidIndex(arr, left, right);//将分割值调整至最左边Swap(arr[mid], arr[left]);int key left;//选定分割值while (left right){// 找小while (left right arr[right] arr[key]){right--;}// 找大while (left right arr[left] arr[key]){left;}Swap(arr[left], arr[right]);} Swap(arr[left], arr[key]);return left;//本次排序完成返回分割值key的下标
}
//快速排序
void QuickSort(int* arr, int left, int right)
{if (left right){return;}//小区间优化减少递归次数if (right - left 1 10){InsertSort(arr left, right -left 1);}else{int keyi PartSort2(arr, left, right);//每一趟排序完成都会返回一个分割值key的下标//借助分割值的位置将序列分为左子区间[left,keyi-1]和右子区间[keyi1,right]//再用分治递归使左子区间和右子区间有序QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi 1, right);}
}
【非递归版本】
我们可以借助栈的思想递归是一直递到限制条件然后开始回归最后一次调用先完然后倒数第二次……和栈的先进后出思想很像所以我们可以借助栈来实现。
6.5栈实现
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;
void StackInit(ST* ps)
{assert(ps);ps-a (STDataType*)malloc(sizeof(STDataType)* 4);if (ps-a NULL){printf(malloc fail\n);exit(-1);}ps-capacity 4;ps-top 0;
}void StackDestory(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}
// 入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);// 满了-》增容if (ps-top ps-capacity){STDataType* tmp (STDataType*)realloc(ps-a, ps-capacity * 2 * sizeof(STDataType));if (tmp NULL){printf(realloc fail\n);exit(-1);}else{ps-a tmp;ps-capacity * 2;}}ps-a[ps-top] x;ps-top;
}// 出栈
void StackPop(ST* ps)
{assert(ps);// 栈空了调用Pop直接中止程序报错assert(ps-top 0);//ps-a[ps-top - 1] 0;ps-top--;
}STDataType StackTop(ST* ps)
{assert(ps);// 栈空了调用Top直接中止程序报错assert(ps-top 0);return ps-a[ps-top - 1];
}int StackSize(ST* ps)
{assert(ps);return ps-top;
}bool StackEmpty(ST* ps)
{assert(ps);return ps-top 0;
}
//前后指针版本确定分割值的位置
int PartSort1(int* arr, int left, int right)
{int key arr[left];//取出分割值int hole left;//保存坑的位置while (left right){// 右边找小放到左边while (left right arr[right] key){right--;}// 不满足上边的循环就说明右边的right有小的要放到左边的left坑里 arr[hole] arr[right];hole right;//更新坑的位置// 左边找大while (left right arr[left] key){left;}// 不满足上边的循环就说明左边begin有大的放到右边end的坑里arr[hole] arr[left];hole left;}arr[hole] key;return hole;//本次排序完成返回分割值key的下标
}
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{//创建栈Stack st;StackInit(st);//原始数组区间入栈StackPush(st, right);StackPush(st, left);//将栈中区间排序while (!StackEmpty(st)){//注意如果right先入栈栈顶为leftleft StackTop(st);StackPop(st);right StackTop(st);StackPop(st);//得到分割值的下标int keyi PartSort1(a, left, right);// 以分割值下标分割点形成左右两部分//分别入栈if (right keyi 1){StackPush(st, right);StackPush(st, keyi 1);}if (left keyi - 1){StackPush(st, keyi - 1);StackPush(st, left);}}StackDestory(st);
} 快速排序的特性总结 1. 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序2. 时间复杂度3. 空间复杂度4. 稳定性不稳定四.归并排序
7.归并排序MergeSort 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。 将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 步骤
使用归并的前提是所有子序列都有序所以我们对待排序序列进行分割一分二二分四…………直至子序列只有一个数字一个数字总该认为他有序吧。 将已有序的子序列合并得到完全有序的序列注意两个子序列合并成一个子序列序列要进行排序确保该子序列有序以便后续合并若将两个有序表合并成一个有序表称为二路归并。 动图演示 void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left right){//子序列分割只剩一个元素停止跳到上一级归并return;}int mid (left right) 1;//分割一分二……_MergeSort(arr, left, mid, tmp);//划分左区间[left, mid]_MergeSort(arr, mid1, right, tmp);//划分右区间[mid1, right]//分割完成开始归并int begin1 left, end1 mid;//左区间int begin2 mid 1, end2 right;//右区间int index left;while (begin1 end1 begin2 end2){//注意结束条件为一个序列为空时就停止//合并的序列可能不一样长if (arr[begin1] arr[begin2]){//为了实现合并后的子序列有序我们要对要合并的两个序列的元素进行一一比较比较结果放到 //临时数组然后再把临时数组赋给原序列。tmp[index] arr[begin1];//一定是后置复制完确保指向下一个元素}else{tmp[index] arr[begin2];}}//两序列不可能同时为空可能有瘸腿的情况将剩余元素合并while (begin1 end1){tmp[index] arr[begin1];}while (begin2 end2){tmp[index] arr[begin2];}//将合并后的序列拷贝到原数组中//在这里拷贝的原因是保证返回到上一层递归后两个子序列中的元素是有序的for (int i left; i right; i){arr[i] tmp[i];}
}
//归并排序
void MergeSort(int* arr, int n)
{int* tmp (int*)malloc(sizeof(int)*n);//临时数组左右区间归并时排序要借助临时数组//防止覆盖待排序序列造成错误if (tmp NULL){perror(malloc);exit(-1);} _MergeSort(arr, 0, n - 1, tmp);//分割归并free(tmp);tmpNULL;
}
归并排序的特性总结 1. 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问 题。2. 时间复杂度3. 空间复杂度O(N)4. 稳定性稳定排序算法复杂度及稳定性分析 博主水平有限如有错误还请多多包涵。
