企业网站建设分为那几个阶段,门户网站建站注意事项,ps网页设计培训班,查询企业营业执照怎么查总言 数据结构基础#xff1a;排序相关内容。 文章目录总言1、基本介绍2、插入排序2.1、直接插入排序#xff1a;InsertSort2.1.1、单趟2.1.2、总趟2.2、希尔排序#xff08;缩小增量排序#xff09;#xff1a;ShellSort2.2.1、预排序1.0#xff1a;单组分别排序2.…总言 数据结构基础排序相关内容。 文章目录总言1、基本介绍2、插入排序2.1、直接插入排序InsertSort2.1.1、单趟2.1.2、总趟2.2、希尔排序缩小增量排序ShellSort2.2.1、预排序1.0单组分别排序2.2.2、预排序2.0多组混合排序2.2.3、加入直接排序3.0对gap间距说明3、选择排序3.1、直接选择排序SelectSort3.2、堆排序HeapSort3.2.1、整体3.2.2、向上调整函数、向下调整函数4、交换排序4.1、冒泡排序BubbleSort4.1.1、固定类型版本4.1.2、多种类型版本4.2、快速排序QuickSort4.2.1、Hoare法4.2.1.1、单趟①思路分析②实现说明③逻辑阐述4.2.1.2、总趟递归法①相关实现与说明②结果演示4.2.2、挖坑法4.2.2.1、单趟①思路分析②相关实现4.2.2.2、总趟4.2.3、前后指针法4.2.3.1、单趟①思路分析②相关实现4.2.3.2、总趟4.2.4、快排优化1.0关于key值的选取4.2.5、快排优化2.0小区间优化4.2.6、快排针对总趟的非递归写法5、归并排序5.1、递归版5.2、非递归版5.2.1、版本1.05.2.1.1、写法5.2.1.2、问题5.2.2、版本2.05.2.2.1、写法一5.2.2.2、写法二6、计数排序1、基本介绍
常见排序 时间最坏 时间最好 空间 稳定性 插入排序 直接插入排序 O(N2) O(N) O(1) √ 希尔排序 平均 O(N1.3) O(1) × 选择排序 直接选择排序 O(N2) O(N2) O(1) × 堆排序 O(N·log) O(N·log) O(1) × 交换排序 冒泡排序 O(N2) O(N) O(1) √ 快速排序 O(N2) O(N·log) O(logN) × 其它排序 归并排序 O(N·log) O(N·log) O(N) √ 2、插入排序 整体思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。
2.1、直接插入排序InsertSort 1、基本说明 直接插入排序的核心思路 当插入第i(i1)i(i1)i(i1)个元素时前面的array[0],array[1],…,array[i−1]array[0],array[1],…,array[i-1]array[0],array[1],…,array[i−1]已经排好序此时用array[i]array[i]array[i]排序码与array[i−1],array[i−2],…array[i-1],array[i-2],…array[i−1],array[i−2],…的排序码顺序进行比较找到正确的插入位置将array[i]array[i]array[i]插入并将原来位置上的元素顺序后移。 说明 给定一个数集将其排序首先我们可以考虑对一个元素的排序即单趟再考虑对总体元素的排序即多趟。
2.1.1、单趟 1、思路分析 对于一个有序区间如何排序直接插入·单趟说明 直接插入排序中单趟是建立在原数集是有序区间的基础上的。即默认[0,end]有序新的需要插入的数在下标为end1的位置则插入后仍旧保持有序。 举例如下 假设待排序区间如下图所示假设排升序 其中经过前4趟后使得[0,4]区间有序下标为5的元素(即4)为当前趟待插入元素。那么按照直接插入排序的规则将其与前[0,4]中元素比较插入合适位置。 如下4先与9比较排升序使得原先arr[4]中的元素(即9)后移接下来4又与7比较。 4与7比较升序4小使得arr[3]中元素(即7)后移接下来4与5比较。 4与5比较使得5后移接下来4又与2比较 4与2比较此时4比2大则意味着arr[1]后位置为4的正确位置将4放入。 2、相关实现 int end;//默认[0,end]有序待插入数在下标为end1的位置int tmp a[end 1];//tmp用于保存当前趟中待插入数原因后续该位置会被覆盖while (end 0){if (tmp a[end]){a[end 1] a[end];//排升序tmp需要放到end、end1之间即a[end]≤tmp≤a[end1]end--;}elsebreak;//若不满足if条件说明当前位置找到了直接跳出}a[end 1] tmp;//再插入值关于单趟中直接跳出原因说明 当不满足if (tmp a[end])条件时说明找到待插入数正确位置此时有两种情况。 情况一待插入元素的位置在数组中间该情况下end经过上一轮判断自减一次实际插入位置为end1。 情况二数组原序列都比待插入元素大(小)此时end一直自减直到为负数跳出while循环。此时实际插入位置相当于数组首位置仍旧是end1。 综合考虑在跳出while循环后一并处理两种情况。
2.1.2、总趟 1、思路分析 对于一个无序区间如何排序直接插入·总趟数说明 我们只要定一个基准区间后续元素视为待插入数据依次迭代类推即可如下图 2、相关实现
void InsetSort(int* a, int n)
{//总趟for (int i 0; i n-1; i)//默认end nend1为插入数因此end1n即有end n-1i是用来控制end遍历总元素的。{//单趟int endi;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}elsebreak;}a[end 1] tmp;}
}3、相关验证
void Print(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void test1()
{int arr[] { 9,1,2,5,7,4,8,6,3,5 };int size sizeof(arr) / sizeof(int);Print(arr, size);InsertSort(arr, size);Print(arr, size);}2.2、希尔排序缩小增量排序ShellSort 1、基本说明 希尔排序的核心思路 对待排序文件以gapgapgap为跨步将所有数据分成nnn个组所有距离为gapgapgap的数据分在同一组内对每一组内的数据进行排序重复上述分组和排序的工作当到达gap1gap1gap1时所有记录在同一组内排好序。 整体上希尔排序可分为两步骤 1、预排序使所排元素接近有序提高了直接插入排序时的效率 2、直接插入排序使上述元素达到有序
2.2.1、预排序1.0单组分别排序 1、思路分析 这里我们先来解决预排序问题 对单组如何排序 先设置gap值将以下数据分组例如gap3。 对分在同组内的数据进行排序其方法类似于直接插入排序只不过这里我们比较的不是end和end1而是end和endgap处的数据。 //单趟其思路和直接插入排序类似只是跨步由gap1变为了任意正整数for (int i 0; i n - gap; igap){int endi;int tmp a[end gap];//此处tmp储存的是与end相距跨步为gap的元素:即同一组元素while (end 0){if (tmp a[end])//排升序当下标为endgap的元素比下标为end所指向的元素还小时将下标为end出的元素往后挪挪到endgap下标处{a[end gap] a[end];end - gap;//注意此处end的跨步也要更改为gap}elsebreak;}a[end gap] tmp;}对多组如何排序 排完一组后对下一组进行排序当所有组排完后所得序列接近有序。 因此我们只要在原先的单趟排序基础上再嵌套一层循环用于控制组数流动即可。 int gap 3;for (int j 0; j gap; j)//多组间的流动{//单趟for (int i 0; i n - gap; i gap){//……}}2、相关实现 上述思路整体实现如下
void ShellSort_1(int* a, int n)
{int gap 3;for (int j 0; j gap; j){//单趟for (int i 0; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}elsebreak;}a[end gap] tmp;}}}进行验证
void test2()
{int arr[] { 9,1,2,5,7,4,8,6,3,5 };int size sizeof(arr) / sizeof(int);Print(arr, size);ShellSort_1(arr, size);Print(arr, size);}2.2.2、预排序2.0多组混合排序 在上述代码中我们嵌套了两层循环(j、i)实际上只需要做一些调整用一次循环也能实现
void ShellSort_2(int* a, int n)
{int gap 3;for (int i 0; i n - gap; i)//若此处换为i则是多组元素轮番进行排序即交替分组插入排序{int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}elsebreak;}a[end gap] tmp;}}1.0先在组内进行排序整体排好后再到下一组进行排序。 2.0先对第一组内数据进行部分元素排序来到下一组同样进行部分排序依此类推交替进行。
2.2.3、加入直接排序3.0对gap间距说明 1、思路分析 根据上述1.0、2.0内容我们只是进行了预排序将序列变得相对有序要达到完全有序还需要对gap间距做些调整gap涉及到每次排序时的分组问题。 排升序gap越大大的数更快到后面小的数更快到前面但越不接近有序 排升序gap越小越接近有序 当gap1时就是直接插入排序。 那么如何确定gap值才能使得排序效果相对较优 以下为一种给出的方案 让gap成为一个动态的数int gap n从而达到多次预排的效果并保证最后一次gap值为1gap gap / 3 1或者gap gap / 2. int gap n;while (gap 1)//此处gap1循环继续原因是gapgap/31中保证了gap最后一次为1.{gap gap / 3 1;}2、相关实现
void ShellSort_3(int* a, int n)
{int gap n;while (gap 1)//此处gap1跳出循环原因是gapgap/31中保证了gap最后一次为1.{gap gap / 3 1;for (int i 0; i n - gap; i){//若此处换为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;}}
}相关验证gap4、gap2都在进行预排序当gap1时直接插入排序。
3、选择排序 整体思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。
3.1、直接选择排序SelectSort 1、基本思路 直接选择排序思路说明 在元素集合array[i]—array[n−1]array[i]—array[n-1]array[i]—array[n−1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换。在剩余的array[i]—array[n−2]array[i1]—array[n−1]array[i]—array[n-2]array[i1]—array[n-1]array[i]—array[n−2]array[i1]—array[n−1]集合中重复上述步骤直到集合剩余1个元素。 以上是直接选择排序的基本思路换言之在给定的数组区间[begin,end]中选出最小/最大元素根据升序或降序要求将其与首位元素交换。我们在此基础上做一些改动同时找出区间[begin,end]内最小、最大值同时与首位元素交化。这样单趟回合中我们能排序好两个数缩减[begin,end]区间范围继续新一轮选择排序。 如下单趟中在区间[begin,end]范围内找出本回合中最小、最大元素对应下标。 将最小、最大下标对应元素与begin、end下标对应元素交换让最下、最大元素分别到数组两端。 缩减区间[begin,end]在新区间中重复上述操作直至begin与end相遇(奇数时)或begin与end相错(偶数时)。 2、代码实现 不完全写法1.0
void SelectSort_1(int* a, int n)
{//begin、end代表数组下标代表每趟[begin,end]int begin 0;int end n - 1;while (begin end)//总共要走的次数{//单次操作int mini begin, maxi begin;//定义最小、最大值的下标初始默认二者统一for (int i begin; i end; i){//步骤一找出单次操作中最小、最大元素对应下标//区间[begin,end]范围内若有比下标为mini的元素更小的值则更新mini的下标同理若有比下标为maxi的元素更大的值则更新maxi的下标。if (a[i] a[mini])mini i;if (a[i] a[maxi])maxi i;}//步骤二将最小、最大下标对应元素与begin、end下标对应元素交换让最下、最大元素分别到数组两端Swap(a[begin], a[mini]);Swap(a[end], a[maxi]);//步骤三缩减区间[begin,end],在新区间中重复上述操作begin;end--;}
}上述代码存在一个问题需要注意一种特殊情况 if (maxi begin)//若maxi的下标表示的是begin下标由于上述中begin下标中的元素与mini下标中的元素交换了位置此处要对maxi进行修正maxi mini;//相当于上述Swap(a[begin], a[mini])中把begin原先元素交换到了mini位置处而begin对应的maxi指向没有随begin而变化故在这里修正修正写法2.0
void SelectSort_1(int* a, int n)
{//begin、end代表数组下标代表每趟[begin,end]int begin 0;int end n - 1;while (begin end)//总共要走的次数{//单次操作int mini begin, maxi begin;//定义最小、最大值的下标初始默认二者统一for (int i begin; i end; i){//步骤一找出单次操作中最小、最大元素对应下标//区间[begin,end]范围内若有比下标为mini的元素更小的值则更新mini的下标同理若有比下标为maxi的元素更大的值则更新maxi的下标。if (a[i] a[mini])mini i;if (a[i] a[maxi])maxi i;}//步骤二将最小、最大下标对应元素与begin、end下标对应元素交换让最下、最大元素分别到数组两端Swap(a[begin], a[mini]);if (maxi begin)//修正最大最小值在边界的情况maxi mini;Swap(a[end], a[maxi]);//步骤三缩减区间[begin,end],在新区间中重复上述操作begin;end--;}
}相关验证
void test3()
{int arr[] { 9,1,2,5,7,4,8,6,3,5 };int size sizeof(arr) / sizeof(int);Print(arr, size);SelectSort_2(arr, size);Print(arr, size);
}3.2、堆排序HeapSort
3.2.1、整体 1、基本说明 堆排序相关内容在其它博文有讲解此处不做过多说明。堆排中注意整体实现顺序1、建堆(两种方式)2、交换数据排序 二叉树相关堆排
void HeapSort(int* a, int n)
{//建堆方式一自上而下借助向上调整函数//时间复杂度O(N*logN)for (int i 1; i n; i){AdjustUp(a, i);}//建堆方式二自下而上借助向下调整函数//时间复杂度O(N)for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDwon(a, n, i);}//步骤二排序降序小堆升序大堆int end n - 1;//end数组尾元素下标为n-1while (end 0)//end0是因为堆顶自身交换及向下调整无意义{Swap(a[0], a[end]);//交换堆中首尾数据AdjustDwon(a, end, 0);//向下调整堆顶数据--end;//每次自减即可把交换后的末位数排除在下一次向下调整中}
} 3.2.2、向上调整函数、向下调整函数 1、向上调整函数
void Swap(HPDataType* n1, HPDataType* n2)
{HPDataType tmp *n1;*n1 *n2;*n2 tmp;
}void AdjustUp(HPDataType*a,int child)
{HPDataType parent (child - 1) / 2;while (child0)//不断调整{//不满足堆的性质交换此处默认小堆if (a[child] a[parent]){Swap(a[child], a[parent]);//交换//需要更改新增节点下标,进行下一轮父子关系判断child parent;parent (child - 1) / 2;}else{break;}}
}2、向下调整函数
void Swap(HPDataType* n1, HPDataType* n2)
{HPDataType tmp *n1;*n1 *n2;*n2 tmp;
}void AdjustDown(HPDataType* a, int size, int parent)
{int child parent * 2 1;//默认左孩子while (childsize){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;}}
}4、交换排序
4.1、冒泡排序BubbleSort 冒泡排序在C语言函数与数组、指针两篇博文中有介绍此处也不做过多说明。
4.1.1、固定类型版本
void BubbleSort(int* a, int n)
{for (int j 0; j n - 1; j){int exchange 1;for (int i 0; i n-j-1; i){if (a[i] a[i 1]){exchange 0;Swap(a[i], a[i 1]);}}if (exchange)break;}}4.1.2、多种类型版本
void swap(char* num1, char* num2, size_t size)
{for (size_t i 0; i size; i){//一个字符一个字符的交换char tmp *num1;*num1 *num2;*num2 tmp;//注意字符指针的迭代num1;num2;}
}void bubble_sort(void* base, size_t num, size_t size, int (*compar)(const void*, const void*))
{for (size_t i 0; i num - 1; i){for (size_t j 0; j num - 1 - i; j){//arr[j]arr[j1]if (compar((char*)base size * j, (char*)base size * (j 1)) 0)//排升序{swap((char*)base size * j, (char*)base size * (j 1),size);//交换元素}}}
} 4.2、快速排序QuickSort 一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。排出来的是升序
4.2.1、Hoare法
4.2.1.1、单趟 思路 选出一个key一般是最左边或者最右边的值。 单趟排序完成后对于升序要求达到左边比key小右边比key大对降序要求达到左边比key大右边比key小。
①思路分析 1、思路分析 对于单趟(升序) 先以最左或最右位置选出一个key设左为L右为R。 若左为key则R先向前移动找比key小的位置R找到小于key的位置保持不动。L再向后移动找比key大的位置。找到之后交换R和L位置处的数值。 R再次向前移动找比key小的位置L向后移动找比key大的位置找到之后交换R和L位置的数值。 R继续向前找比key小的值L继续向后找比key大的值当R和L相遇将该位置处的值与key的值交换结束。 此时key左边的值都比key小key右边的值都比key大。
②实现说明 2、相关实现 错误实现演示 int left 0, right n - 1;int key a[left];//选左为keywhile (left right){//右先走右找小while (a[right] key)--right;//左后走左找大while (a[left] key)left;//找到交换Swap(a[left], a[right]);}//交换最后的keySwap(key, a[left]);问题一a[right] key、a[left] key 修改如下: //右先走右找小while (a[right] key)--right;//左后走左找大while (a[left] key)left;问题二left right 修改如下 //右先走右找小while (left right a[right] key)--right;//左后走左找大while (left right a[left] key)left;问题三Swap(key, a[left]); 正确实现演示 int left 0, right n - 1;int key left;//选左为keywhile (left right){//右先走右找小while (left right a[right] a[key])--right;//左后走左找大while (left right a[left] a[key])left;//找到交换Swap(a[left], a[right]);}//交换最后的keySwap(a[key], a[left]);③逻辑阐述 3、相关问题说明 1、以升序为例如何做到左边数值比key小右边数值比key大 回答将左边比key大的值和右边比key小的值两两交换这样左边只剩下原先比key小的值和被交换过来的比key小的值右边与左边相反。 如此便达到升序的效果。如果要实现降序只需要左边找小值右边找大值即可。 2、关于左右L、R是否会错过问题? 回答不会L、R会错过的情况是二者同时一个向后一个向前遍历因奇偶数的不同而导致相错问题。
while(leftright)
{left; //从代码执行角度虽然在两行分先后--right; //但二者从逻辑角度发生在同一时刻(同语句中)
}但此处L、R并非同时进行是一个先完成它的步数另一个再完成对应步数由于二者相向故一定会有LR相遇时。 while (left right a[right] a[key])--right; //右边先走右边while结束后right不动while (left right a[left] a[key])left; //此时左边在走3、左边做key为什么要让右边先走(反之右边做key为什么要让左边先走) 回答 对于升序左边做key右边先走可保证相遇时的值比key小或者与key相等右边做key左边先走可保证相遇时的值比key大或者与key相等 分析 以升序、左边做key右边先走为例子 情形一 R先走R停下L去遇到R(L停下只有两种可能①L找到对应值停下②L与R相遇此处是②因为①的情况L停下未遇到R)。 此时相遇的位置是R停下的位置而要使R停下即有a[R]a[key]。相遇交换就使得小于key的值到左边去。 情形二 R先走R没有找到比key要小的值但R遇到了L。 子情形一最初始的一轮循环中R往前走直接到达key处即L没有机会往后走此时说明key后的数组元素都比key大LR相遇点的值即上述中与key相等的情况。 子情形二L、R经过彼此交换后的下一组循环中R往前走直接遇到了L说明在(L,R]区间内的元素都比key大而L(与R的相遇点)处的值是上一轮循环后经过交换的值即上一轮R中小于key的值此时在下一轮循环L位置处(L在R后变动)。
4.2.1.2、总趟递归法
①相关实现与说明 单趟排序完成以key为界数组被分为三个区间。[begin,key-1]区间内数据比key小 、key 、[key1,end]区间内数据比key大。 此时我们再分别对两区间数据重复上述单趟操作即可。这有点类似于二叉树的前序遍历。 这里我们将上述快排中单趟取出单独封装为一个函数 以[begin,end]作为单趟区间这样我们只用修改beginend具体指向下标就能让其达成前序遍历也就是快排中的总趟。
int PartSort(int* a, int begin, int end)
{int left begin, right end;int key left;//选左为keywhile (left right){//右先走右找小while (left right a[right] a[key])--right;//左后走左找大while (left right a[left] a[key])left;//找到交换Swap(a[left], a[right]);}//left、right相遇时将key处的数据与left处的数据交换Swap(a[key], a[left]);key left;//Swap交换了key原先下标元素return key;
}return key;返回key值是为了下述总趟排序时方便寻找各子区间位置。[begin,key-1]、key、[key1,end] 总趟如下
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int key PartSort(a, begin, end);QuickSort(a, begin, key - 1); QuickSort(a, key 1, end);
}递归的返回条件当区间不存在或区间只有一个值时此时无需再排序。
②结果演示 测试结果如下 代码如下
void test5()
{int arr[] { 6,1,2,5,7,4,8,9,3,5 };int size sizeof(arr) / sizeof(int);Print(arr, size);QuickSort(arr,0,size-1);Print(arr, size);
}int count0;
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int key PartSort(a, begin, end);printf(Quake%d:, count);Print(a, end1);QuickSort(a, begin, key - 1);QuickSort(a, key 1, end);
}4.2.2、挖坑法
4.2.2.1、单趟
①思路分析 1、思路分析 先得到第一个数据存放在临时变量key中形成一个坑位key6。 R开始向前移动找比key的值小的位置找到后将该值放入坑位中该值原先位置形成新的坑位 L开始向后移动找比key大的值找到后又将该值放入坑位中再形成新的坑位。 R再次向前移动找比key小的位置找到后将该值放入坑位该位置形成新的坑位 L紧接着向后移动找比key大的位置找到后将该值放入坑位中该位置形成新的坑位。 如此循环翻覆当L和R相遇时将key中的值放入坑位中结束循环。此时坑位左边的值都比坑位小右边的值都比坑位大。 此法相较于上一种方法在于提高了理解性不必纠结于为什么先走右边再走左边。在一轮中L、R有一个充当了坑位坑位本身是固定不能移动的因此只能移动L、R中非坑位的走向。
②相关实现 2、相关实现
int PartSort2(int* a, int begin, int end)
{int left begin, right end;int key a[left], pit left;//pit用于记录坑位下标while (left right){if (left right a[right] key)//左有坑排升序在右找小--right;a[pit] a[right];//找到后将数据填入坑中pit right;//右形成新坑if (left right a[left] key)//右为坑升序在左找大left;a[pit] a[left];//找到后填入坑中pit left;//左边形成新坑}a[pit] key;//最后坑中填入基准数keyreturn pit;
}4.2.2.2、总趟 事实上这几种方法中总趟的实现保持不变用递归法仍旧等同于二叉树的前序遍历。只是把hoare版中单趟实现方法改为这里挖坑法中单趟实现。 只是此法相较于上一种方法在于提高了理解性不必纠结于为什么先走右边再走左边。在一轮中L、R有一个充当了坑位坑位本身是固定不能移动的因此只能移动L、R中非坑位的走向。
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int key PartSort2(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key 1, end);
}相关验证如下 验证代码如下
int count0;
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int key PartSort2(a, begin, end);printf(Quake%d:, count);Print(a, end1);QuickSort(a, begin, key - 1);QuickSort(a, key 1, end);
}void test5()
{int arr[] { 6,1,2,5,7,4,8,9,3,5 };int size sizeof(arr) / sizeof(int);Print(arr, size);QuickSort(arr,0,size-1);Print(arr, size);
} 4.2.3、前后指针法
4.2.3.1、单趟
①思路分析 1、思路分析 初始时prev指针指向序列开头cur指针指向prev指针的后一个位置。 然后判断cur指针指向的数据是否小于key若小于则prev指针后移一位并让cur指向的数据与prev指向的数据交换然后cur指针自增。 当cur指针指向的数据仍旧小于key时重复上述步骤。若cur指针指向的数据大于key则cur指针自增。 此后只需要重复上述cur指向数据与key指向数据大小判断即可。 当cur指针往后走到已经越界这时我们将prev下标指向的数据与key进行交换。结束此时key左边的数据比key小key右边的数据比key大。 ②相关实现 2、相关实现
int PartSort3(int* a, int begin, int end)
{int prev begin, cur begin 1;int key begin;while (cur end)//[begin,end]下标{if (a[cur]a[key]){prev;Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[key]);//cur首次越界后,将prev下标指向的数据与key进行交换key prev;return key;
}4.2.3.2、总趟 和挖坑法一致这里的三种写法区别在于单趟的实现总趟仍旧是采取递归方法实现。 从理解角度来讲使用前后指针理解起来更容易没有那么多弯弯绕绕。
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int key PartSort3(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key 1, end);
}相关验证
int count0;
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int key PartSort3(a, begin, end);printf(Quake%d:, count);Print(a, end1);QuickSort(a, begin, key - 1);QuickSort(a, key 1, end);
}void test5()
{int arr[] { 6,1,2,5,7,4,8,9,3,5 };int size sizeof(arr) / sizeof(int);Print(arr, size);QuickSort(arr,0,size-1);Print(arr, size);
}4.2.4、快排优化1.0关于key值的选取 1、问题说明 对于上述的快排方法选择出来的基数key影响快排效率。 ①key影响递归效率的原因说明 若所选择的key接近于中位数则效率相对较优(相当于此时接近二分快排中递归类似于二叉树的前序遍历其时间复杂度和深度有关左右均衡时二叉树深度相对较小)。 ②什么情况下取端点作为key值会造成所选数极大/极小 我们一般取左右端点数为key值当所给数组原先就有序或接近有序很容易选出的key就是极小值/极大值的情况。此时快排效率相对较低 1、当数据很多时由于递归的深度很深而栈空间相对而言不是那么大容易出现栈溢出的现象。 2、此外这种最坏情况下时间复杂度O(N)NN-1N-2……1≈O(N^2) 。 因此针对上述情况我们需要对key值做出改进。 2、解决方案 解决方法如下 法一随机选择key。 法二三数取中。对数组第一个数据、下标在中间的数据、最后一个数据做比较。选择三个数的中间数作为key值这里我们将key所在下标元素与mid下标元素交换即可。这样做能保证后续遍历排序时所有数据轮番遍历到也不用做过多调整。即整体大逻辑框架不变。
int GetMidIndex(int* a, int begin, int end)
{int mid (begin end) / 2;if (a[begin] a[end]){if (a[end] a[mid])//beginendmidreturn end;else if (a[begin] a[mid])//beginmidendreturn mid;elsereturn begin;//midbeginend}else//a[begin]a[end]{if (a[begin] a[mid])//endbeginmidreturn begin;else if (a[mid] a[end])return end;elsereturn mid;}
}在单趟排序中只需要做key下标和mid下标元素位置交换即可此处以前后指针法来举例。
int PartSort3(int* a, int begin, int end)
{int prev begin, cur begin 1;int key begin;int mid GetMidIndex(a, begin, end);Swap(a[key], a[mid]);while (cur end)//[begin,end]下标{if (a[cur]a[key]){prev;Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[key]);//cur首次越界后,将prev下标指向的数据与key进行交换key prev;return key;
}相关验证如下
#includetime.h
void TestQuickSort()
{srand(time(0));const int N 50000000;int* a1 (int*)malloc(sizeof(int) * N);assert(a1);int* a2 (int*)malloc(sizeof(int) * N);assert(a2);for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];}int begin1 clock();QuickSortpro(a1, 0, N - 1);int end1 clock();int begin2 clock();QuickSort(a2, 0, N - 1);int end2 clock();printf(QuickSortpro:%d\n, end1 - begin1);printf(QuickSort:%d\n, end2 - begin2);free(a1);free(a2);}4.2.5、快排优化2.0小区间优化 1、问题说明 递归划分区间当区间比较小时就不再用递归划分去排序这个小区间可以考虑使用其它排序对小区间做处理。比如直接插入排序(希尔排序针对大量数据)如此可减少很多递归次数。 该调整在QuickSort总趟中。 解决方案如下给定一个范围当单趟排序中区间内元素数量相对少时就使用其它排序来完成。
void QuickSortpro(int* a, int begin, int end)
{if (begin end)return;if (end - begin 10){int key PartSort3(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key 1, end);}elseInsertSort(abegin, end - begin 1);
}end - begin 10给定一个适合的区间值当区间大于该值时仍旧使用递归否则就使用其它排序方法。 InsertSort(abegin, end - begin 1);注意这里的参数传递。快排中使用直接插入排序第一参数为对应小区间首元素地址(不能直接传递a)第二参数为小区间数据个数(begin、end为下标)。
4.2.6、快排针对总趟的非递归写法 1、问题说明 为什么要学习非递归方法 极端场景下如果深度太深会出现栈溢出的现象。故而此处要面对的一个问题是如何把递归改为非递归 改法一 将递归直接该为循环例如斐波那契额数列、归并排序 改法二 用数据结构栈或队列模拟递归过程 这里快排的非递归法就要使用上述法二。这里借助的是栈。 关键点如何使用栈模拟递归过程 快排中需要用到递归的是总趟故而这里单趟写法照旧不变使用上述三种写法即可。总趟中我们每次递归改变的是单趟排序的区间故而使用栈时关键点在于如何在栈中存储我们需要的区间位置以便取出用于单趟排序 结合栈后进先出的性质。我们先把左右区间[begin,end]入栈先入end再入begin这样top取栈顶元素时才能按顺序取到begin、end两值。 根据取出的区间进行单趟排序。此时我们能得到keyi值将区间分为[left,key-1] 、key、[key1,right]三部分再重复上述入栈操作对左右两区间分别入栈、取出排序如此循环直到所排区间为单元素即可。
void QuickSortNonR(int* a, int begin, int end)
{ST stack;StackInit(stack);StackPush(stack, begin);StackPush(stack, end);while (!StackEmpty(stack))//栈不为空时循环继续说明还有区间没有排完{int left StackTop(stack);//取区间左端StackPop(stack);int right StackTop(stack);//取区间右端StackPop(stack);int keyi PartSort3(a, left, right);//单趟排序得到key值//[left,key-1] key [key1,right]if (right keyi 1)//key1right时表明此时右区间中值大于一个{StackPush(stack, right);StackPush(stack, keyi 1);}if (left keyi - 1)//left key - 1时表明此时左区间中值大于一个{StackPush(stack, keyi - 1);StackPush(stack, left);}}StackDestroy(stack);
}此处若不使用栈来模拟递归(处理过程类似于二叉树的前序遍历)也可以使用队列完成(处理过程类似于二叉树的层序遍历)只不过队列的特性是先进先出入队时需要注意区间选择问题。
5、归并排序 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用。其大致思想为将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 示意图如下
5.1、递归版 1、思路说明 按照上述描述给定一个数组区间[begin,end]设中间值为mid要让其有序则需要先让其左右子区间有序即[begin,mid]、[mid1,end]只有在左右子区间有序的情况下我们才能对当前整个区间进行归并排序。这个步骤就类似于二叉树的后续遍历。 需要注意的是链式二叉树中由于其每个节点单独开辟并归时只需要改变指针指向即可。而这里数组是一段连续的物理空间若直接在原数组改动会导致数据覆盖问题因此此处我们借助了额外的数组。 2、相关实现
void _MergeSort(int* a, int begin, int end,int*tmp)
{if (begin end)return;int mid (begin end) / 2;//step1:让左右区间有序[begin,mid]、[mid1,end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid 1, end, tmp);//step2:并归类似于两个数组比较取二者max/min排序int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int cur begin1;//此处不能直接使cur赋值为0,因为子序列是从[begin,end]开始begin在不同的子序列中下标不同while (begin1 end1 begin2 end2)//两区间均有值{if (a[begin1] a[begin2])//以升序为例tmp[cur] a[begin1];elsetmp[cur] a[begin2];}while (begin1 end1)//处理剩余区间tmp[cur] a[begin1];while (begin2 end2)tmp[cur] a[begin2];//step3:将tmp中排序好的数据放回原数组相应位置memcpy(a begin, tmp begin, (end - begin 1)*sizeof(int));
}void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);assert(tmp);_MergeSort(a, 0, n - 1, tmp);//开区间还是闭区间看自己控制free(tmp);
}注意细节 1、递归返回条件begin end 2、两数组比较归并时tmp遍历下标int cur begin1; 3、如何将本回合归并结果拷贝回原数组中memcpy(a begin, tmp begin, (end - begin 1)*sizeof(int));。注意这里我们整体排序的是[begin、end]区间只是排序它时是将其分为子区间排序。
5.2、非递归版 1、思路说明 Q前面我们有介绍递归改非递归通常有两种方法这里归并排序的非递归写法是否像快排一样需要借助栈或队列 A不需要。归并非递归法不适合用借助栈在上面的快排中由于前序遍历使用栈或队列不影响排序。而此处的并归排序中属于后续遍历需要先处理其左右子区间得到有序数组才能处理本身。考虑到上述因素这里我们直接使用循环达到递归效果。 逻辑图如下 5.2.1、版本1.0
5.2.1.1、写法 这里我们以gap作为XX归并。则需要归并的两区间为[i,igap-1]、[igap,igap*2-1]。i用于确定每次需要比较的两区间中首个区间左下标其余区间下标依据i和gap来确定。 根据上述对于单趟(归并两区间比较排序)的排序逻辑仍旧保持不变此处只是不再使用递归控制总趟(这里我们使用了循环)。
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);assert(tmp);int gap 1;while (gap n){for (int i 0; i n; i 2 * gap)//2*gap一个gap代表一组间距归并一次需要两组故下次从第三组开始{//区间[i,igap-1]、[igap,igap*2-1]int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i gap * 2 - 1;int cur begin1;//此处不能直接使cur赋值为0while (begin1 end1 begin2 end2)//两区间均有值{if (a[begin1] a[begin2])//以升序为例tmp[cur] a[begin1];elsetmp[cur] a[begin2];}while (begin1 end1)//处理剩余区间tmp[cur] a[begin1];while (begin2 end2)tmp[cur] a[begin2];}memcpy(a, tmp, sizeof(int) * n);gap * 2;}free(tmp);
}可以看到对于下述举例2的倍数我们可以很好的完成排序
5.2.1.2、问题 但是对于非2的倍数的数组存在越界等情况 这里我们再打印演示看看
printf(\ngap%d时, gap);
printf([%d,%d]、[%d, %d] , begin1, end1, begin2, end2);5.2.2、版本2.0 考虑到上述问题我们需要对会发生越界的下标进行修正。以下给出两种写法总体修正方法一致这里的法一、法二区别在于何时memcpy。
5.2.2.1、写法一 修正部分代码如下 //step2:修正区间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 - 1;}相关验证如下 整体如下
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);assert(tmp);int gap 1;while (gap n){for (int i 0; i n; i 2 * gap)//2*gap一个gap代表一组间距归并一次需要两组故下次从第三组开始{//step1:分区间[i,igap-1]、[igap,igap*2-1]int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i gap * 2 - 1;int cur begin1;//此处不能直接使cur赋值为0//step2:修正区间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 - 1;}//step3归并两区间元素比较排序while (begin1 end1 begin2 end2)//两区间均有值{if (a[begin1] a[begin2])//以升序为例tmp[cur] a[begin1];elsetmp[cur] a[begin2];}while (begin1 end1)//处理剩余区间tmp[cur] a[begin1];while (begin2 end2)tmp[cur] a[begin2];}memcpy(a, tmp, sizeof(int) * n);//同gap组一次性归并gap * 2;}printf(\n);free(tmp);
}注意事项 1、if、else if这几种修正关系为互斥情况。注意需要把正常情况也考虑进去。 2、对于区间[begin1,end1]、[begin2,end2]若end1、begin2、end2越界能否将区间修正为[begin1,begin1]、[begin1,begin1]例如[8,9]、[10,11]将其修正为[8,8]、[8,8]。 回答不能。这里memcpy(a, tmp, sizeof(int) * n);我们是在每次XX归并后将整个数组拷贝回去若依照上述方法修正则会多出一个数据。故此处需要将其修正为不存在区间。 3、同理上述情况能否不修正[begin2,end2]值直接返回 else if (begin2 n || end2 n){break;}回答在这种单趟排完后才拷贝回原数组的情况下不能这样做原因会将tmp中随机数拷贝回去。 5.2.2.2、写法二 法一中我们是将单趟排序完成后将tmp中数据拷贝回原数组这里也可以每次排完序都进行拷贝
void MergeSortNonR_2(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);assert(tmp);int gap 1;while (gap n){printf(\ngap%d时, gap);for (int i 0; i n; i 2 * gap)//2*gap一个gap代表一组间距归并一次需要两组故下次从第三组开始{//step1:分区间[i,igap-1]、[igap,igap*2-1]int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i gap * 2 - 1;int cur begin1;//此处不能直接使cur赋值为0//step2:修正区间if (end1 n || begin2 n){break;}else if (end2 n)//需要修正边界{end2 n - 1;}printf([%d,%d]、[%d, %d] , begin1, end1, begin2, end2);int space end2 - begin1 1;//step3归并两区间元素比较排序while (begin1 end1 begin2 end2)//两区间均有值{if (a[begin1] a[begin2])//以升序为例tmp[cur] a[begin1];elsetmp[cur] a[begin2];}while (begin1 end1)//处理剩余区间tmp[cur] a[begin1];while (begin2 end2)tmp[cur] a[begin2];memcpy(ai, tmpi, sizeof(int) * space);//单组归并}gap * 2;}printf(\n);free(tmp);
}6、计数排序 基本思路 1. 统计相同元素出现次数 2. 根据统计的结果将序列回收到原来的序列中 局限性 1、如果是浮点数、字符串就不能使用这种方法。 2、如果数据范围很大空间复杂度很高相对不适合。这个排序不适用的是数据之间跨度比较大的情况。其相对适合范围集中重复数较多的排序。 注意事项 1、若数值很大例如数组数据为1000、1001、1002等如果使用绝对映射则数组开辟需要到一千个空间以上。故可使用相对映射法。 2、若是负数仍旧可以用元素-最小值的方法得到数值。
//时间复杂度O(max(range,N))
//空间复杂度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;//需要开辟一个能装下最大数与最小数元素差的数组[min,max]之间的数据在数组中按顺序各占一个元素位置int* count (int*)malloc(sizeof(int) * range);if (count NULL){printf(malloc:fail\n);exit(-1);}memset(count, 0, sizeof(int) * range);//先将该统计数组内元素初始化为0//统计次数for (int i 0; i n; i)//将原数组元素中出现的值做统计{count[a[i] - min];//-min是相对映射使原数组值在统计数组中从0开始也能解决负数问题}//回写排序int j 0;for (int i 0; i range; i){while (count[i]--)//统计数组中该值出现几次在原数组中映射元素就写入几次{a[j] i min;//min为映射回去}}
}
