西安做网站陕西必达,中国网络安全公司排名,四平做网站佳业首页,软件项目管理流程图目录
1.排序的概念及应用
1.1 排序的概念
1.2 排序的应用
1.3 常见的排序算法
2.常见排序算法的实现
2.1 直接插入排序
2.1.1 基本思想
2.1.2 动图解析
2.1.3 排序步骤#xff08;默认升序#xff09;
2.1.4 代码实现
2.1.5 特性总结
2.2 希尔排序
2.2.1 基本思…
目录
1.排序的概念及应用
1.1 排序的概念
1.2 排序的应用
1.3 常见的排序算法
2.常见排序算法的实现
2.1 直接插入排序
2.1.1 基本思想
2.1.2 动图解析
2.1.3 排序步骤默认升序
2.1.4 代码实现
2.1.5 特性总结
2.2 希尔排序
2.2.1 基本思想
2.2.2 排序步骤
2.2.3 代码实现
2.2.4 动图解析
2.2.5 特性总结
2.3 选择排序
2.3.1 基本思想
2.3.2 排序步骤升序
2.3.3 代码实现
2.3.4 动图解析
2.3.5 特性总结
2.4 堆排序
2.5 冒泡排序
2.5.1 基本思想
2.5.2 代码实现
2.5.3 动图解析
2.5.4 特性总结
2.6 快速排序
2.6.1 基本思想
2.6.2 排序步骤
2.6.3 代码实现
区间划分算法hoare初始版本
主框架
2.6.4 区间划分算法
hoare法
挖坑法
前后指针法
2.6.5 快排优化
取key方面的优化
递归方面的优化
2.6.6 快排非递归实现
栈实现代码图解
队列实现
2.6.7 特性总结
2.7 归并排序
2.7.1 基本思想
2.7.2 排序步骤
2.7.3 代码实现
2.7.4 动图解析
2.7.5 非递归实现
2.7.6 特性总结
2.8计数排序
2.8.1 基本思想
2.8.2 排序步骤
2.8.3 代码实现
2.8.4 特性分析
3.排序算法复杂度及稳定性分析 1.排序的概念及应用 1.1 排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。
稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。
内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 排序的应用
排序算法在计算机科学和实际应用中有广泛的应用。以下是一些常见的排序算法的应用示例 数据库查询在数据库中经常需要根据某个字段对数据进行排序以便更快地进行查询和检索。排序算法可以用于对数据库中的数据进行排序从而提高查询效率。 搜索算法许多搜索算法的实现需要对数据进行排序。例如在二分查找算法中要求待搜索的数据必须是有序的。因此使用排序算法对数据进行排序可以提高搜索算法的效率。 负载均衡在分布式系统中负载均衡是一种优化策略通过将工作负载均匀地分配给各个节点以提高系统的性能和吞量。排序算法可以用于对请求或任务进行排序以便将工作负载均匀地分布给各个节点。 数据压缩在数据压缩算法中排序算法可以用于对数据进行预处理以便更好地利用压缩算法的特性。例如在哈夫曼编码中可以根据字符频率对字符进行排序以便构建最优的编码树。 排序和统计在统计分析中需要对数据进行排序以便进行数据的聚合、分组和分析。排序算法可以用于对数据进行排序从而更方便地进行统计分析。 任务调度在任务调度算法中排序算法可以用于对任务进行排序以便根据任务的优先级、截止时间或其他标准进行合理的任务调度和分配。
总之排序算法在各个领域中都有广泛的应用。通过对数据进行排序可以提高系统的性能、搜索算法的效率以及优化各种应用场景中的数据处理和分析。
1.3 常见的排序算法 2.常见排序算法的实现 2.1 直接插入排序
2.1.1 基本思想
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。
直接插入排序和希尔排序都属于插入排序。
我们在实际生活中的摸扑克牌用的就是这个思想。
当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置后将array[i]插入原来位置以及后面的元素后移。
2.1.2 动图解析 要点 待插入数组已经排好序的。 待插入数据依次与数组中的元素比较找到合适的位置。 该位置及其后面的元素全部后移待插入数据插入该位置。 数组中除了第一个元素array[0]默认有序所有元素都看做待插入数据依次插入数组中完成排序。
2.1.3 排序步骤默认升序 从第一个元素开始该元素可以被认为已经有序。 取下一个元素tmp待插入元素从已排序好的数组待插入数组中从后往前扫描。 如果tmp小于该元素该元素向后挪动一位。 重复步骤3直到tmp大于等于已排序数组中的某个元素。 tmp插入到该元素的后面如果tmp小于该数组中的所有元素则tmp插入到下标为0的位置。 重复2~5。
2.1.4 代码实现
我们先写单趟插入
void Insert(int* a, int n)
{//一次插入int end 0;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];}else{break;}
end--;}
a[end 1] tmp;
}
代码解析 end变量已排序好的数组中最后一个元素的下标第一次插入从0开始数组中只有一个元素array[0] tmp变量待插入数据防止被a[end]覆盖单独用一个变量保存起来。 tmp依次和数组中的元素比较如果tmp a[end]则a[end]向后移如果tmp a[end]则找到了插入位置break退出循环。
整个数组插入最终版本
void Insert(int* a, int n)
{//一组插入for(int i 0; i n - 1; i){//i用于控制endend待插入数组中最后一个元素的下标int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];}else{break;}
end--;}a[end 1] tmp;}
}
用一个循环控制end即可完成整个数组的插入初始end 0数组中一个元素array[0]末尾end n - 2(数组中有n - 1个元素)。
2.1.5 特性总结
1.空间复杂度O(1)
2.时间复杂度
最坏情况假设升序数组逆序时间复杂度O(N^2)
最好情况数组升序时间复杂度O(N)
综合来看时间复杂度O(N^2)
我们可以看出元素集合越接近有序直接插入排序算法的时间效率越高。
2.2 希尔排序
前面我们分析得出元素集合越接近有序直接插入排序的时间效率越高那么我们是不是可以利用某种算法让数组不断接近有序然后再进行直接插入排序这里就要介绍希尔排序了。 2.2.1 基本思想
希尔排序法又称缩小增量法。希尔排序法的基本思想是将待排记录序列分割成为若干子序列分别进行插入排序待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
2.2.2 排序步骤 选定一个整数gap作为第一增量。 间隔为gap的元素为一组数据把整个数组分成gap组。 每一组数据都进行直接插入排序gap组数据排完之后数组就接近有序。 取一个比第一增量小的数作为第二增量重复2~3。 gap 1时整个数组为一组进行直接插入排序完成排序。 间隔为gap数组就被分成gap组每组有n/gap个元素。 以gap为间隔进行一趟排序数组就更加接近有序。 gap 1就是直接插入排序。
2.2.3 代码实现 间隔为gap的一组数据进行直插排序
void ShellSort(int* a, int n)
{int gap n / 2;//间隔为gap的一组元素进行直插排序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]; }else{break;}
end - gap; }
a[end gap] tmp;}
}
这里for循环控制的end变量应该控制成i n - gap因为tmp的下标为end gap要保证end gap n,所以end n - gap。或者可以类比直接插入排序直插的循环控制成i n - 1 ,gap为1所以i n - gap
gap组数据分开排序
void ShellSort(int* a, int n)
{int gap n / 2;//gap组数据分开排序for (int j 0; j gap; j){//间隔为gap的一组元素进行直插排序for (int i j; 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];}else{break;}
end - gap;}
a[end gap] tmp;}}
}
这里代码有了三层循环再加上对gap的缩减就要有四层循环相对比较复杂所以我们进行优化 gap组数据并排
void ShellSort(int* a, int n)
{int gap n / 2;//gap组数据并排for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];}else{break;}
end - gap;}
a[end gap] tmp;}
}
这里的代码的循环变量迭代从 i gap 变成了 i从三层循环优化成了两层循环但是达到的效果是一样的。
gap组并排和的分开排序不同的是并排在一组数据还没有插完的情况下又去插入另一组数据而分开排序是插完一组后才接着插入下一组。
控制gap进行多次直插:(最终版)
void ShellSort(int* a, int n)
{int gap n;while (gap 1) {gap gap / 3 1;//gap组数据并排for (int i 0; i n - gap; i) {int end i; int tmp a[end gap]; while (end 0) {if (tmp a[end]) {a[end gap] a[end]; }else{break;}
end - gap; }
a[end gap] tmp; }}
}
注意这里多gap的控制要保证最后gap 1 进行直接插入排序可以是gap gap / 2,也可以是gap gap / 3 1一般使用后者这样增量缩小的快。
2.2.4 动图解析
2.2.5 特性总结 空间复杂度O(1 时间复杂度
希尔排序的时间复杂度计算相当麻烦要用到专业的数学知识官方复杂度为O(N^1.3)比ON*logN差一点。
但是我们可以定性分析一下数组中n个元素 gap很大比如gap n / 3数组分为n / 3组每组3个数据每组比较3次合计(n / 3) * 3 n次。 gap很小比如gap 1:数组接近有序直接插入合计n次。 gap取中间的值如n / 9每组比较12...836次合计36 * (n / 9) 4n次。
里面的比较次数是逐渐变化的两端比较次数少越往中间比较次数越多。 2.3 选择排序
2.3.1 基本思想
每一次从待排序的数据元素中选出最小和最大的元素存放在序列的起始位置和末尾位置直到全部待排序的数据元素排完 。
选择排序和堆排序都属于选择排序。
2.3.2 排序步骤升序 选取一个基准值作为最大值和最小值默认array[begin] 遍历array[begin 1]~array[end]选出最大值max和最小值min array[begin]和min交换array[end]和max交换 beginend-- 重复1~4
2.3.3 代码实现
步骤相对简单我们直接写代码
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int minI begin, maxI begin; for (int i begin 1; i end; i){if (a[i] a[minI]){minI i; }if (a[i] a[maxI]){maxI i;}}Swap(a[begin], a[minI]);
if (maxI begin){maxI minI;}Swap(a[end], a[maxI]); begin;end--;}
}
注意
Swap(a[begin], a[minI])时下标maxI可能就是beginmax提前被换走所以就要调整一下maxI的下标。
2.3.4 动图解析
2.3.5 特性总结 时间复杂度O(N^2) 空间复杂度O(1)
2.4 堆排序
详见堆排序
2.5 冒泡排序
交换排序所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
冒泡排序和快速排序都属于交换排序。 2.5.1 基本思想
知名度最高的排序不多做解释。
如果右边 左边交换左右的值一直往后交换每一躺下来最大的数据在右边。
2.5.2 代码实现
void BubbleSort(int* a, int n)
{for (int i 0; i n; i){int exchange 0; for (int j 1; j n - i; j){if (a[j] a[j - 1]){Swap(a[j], a[j - 1]);exchange 1;}}//一趟下来没有交换if (exchange 0)break;}
}
代码优化
每一趟冒泡排序设置一个exchange变量为0
如果一趟冒泡发生了交换exchange置1
如果一趟冒泡下来exchange还为0说明没有交换已经有序直接break
2.5.3 动图解析
2.5.4 特性总结 时间复杂度O(N^2) 空间复杂度O(1)
2.6 快速排序
2.6.1 基本思想
快速排序采用分治法任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
2.6.2 排序步骤 选取基准值通过区间划分算法把待排序序列分割成左右两部分。 左右序列中递归重复1。
2.6.3 代码实现
区间划分算法hoare初始版本
区间划分算法有三个版本hoare法挖坑法前后指针法这里介绍hoare法也是快排的初始划分法。
三种划分方法的结果可能不同但都是让小的值往前靠拢大的值往后靠拢让整个序列逐渐趋于有序。
步骤 默认序列最左边的元素为基准值key设置leftright指针 left找大right找小right要先找都找到后交换a[left]和a[right] 重复步骤3 当left right时交换key和相遇位置的元素完成分割。 走完这一趟后key值左边都不比key大key值右边都不比key小key值到了他排序后应该在的位置不需要挪动这个元素了。
图解
算法分析 为什么能保证相遇位置的值一定比key值小然后交换 关键点就是让right先找 相遇有两种情况 left往right靠拢与right相遇right先找到了小的元素相遇后的值一定比key小。 right往left靠拢与left相遇left指针指向的元素是上一波交换过后的元素该元素比key小。 假如我们让left先找的话相遇位置比key值大不能交换。
代码
int Partion(int* a, int left, int right)
{int keyI left;//left right两个指针相遇退出循环while (left right){//right先找right找小while (left right a[right] a[keyI]){right--;}//left找大while (left right a[left] a[keyI]){left;}//都找到了交换Swap(a[left], a[right]);}//left和right相遇交换key和相遇位置元素Swap(a[keyI], a[left]);return left;
}
划分方法一般不用hoare是因为这种算法实现的代码很容易出现bug比如 right找小和left找大的过程中要保证left right否则可能出现数组越界比如1,9,6,4,2,7,8,2 右边的值都比key大会导致越界。 a[right] a[keyI]或者a[left] a[keyI]时才能--right或者left如果是a[right] a[keyI]或者a[left] a[keyI]可能出现死循环比如a[left] a[right] key时交换完后不进入内部while外部while陷入死循环。
主框架
void _QuickSort(int* a, int begin, int end)
{if (begin end)return;//根据基准值把数组划分成左右序列int keyI Partion(a, begin, end);//左右序列递归划分下去_QuickSort(a, begin, keyI - 1);_QuickSort(a, keyI 1, end);
}void QucikSort(int* a, int n)
{_QuickSort(a, 0, n - 1);
}
上述为快速排序递归实现的主框架与二叉树前序遍历规则非常像。
二叉树的递归终止条件是空树快排的终止条件是数组只有一个元素leftright或者数组区间不存在leftright。
浅画一下展开图 2.6.4 区间划分算法
前面所说hoare划分法有一定的缺陷我们下面重点介绍其他两种常用的划分方法。
hoare法
int Partion(int* a, int left, int right)
{int keyI left;//left right两个指针相遇退出循环while (left right){//right先找right找小while (left right a[right] a[keyI]){right--;}//left找大while (left right a[left] a[keyI]){left;}//都找到了交换Swap(a[left], a[right]);}//left和right相遇交换key和相遇位置元素Swap(a[keyI], a[left]);return left;
}
挖坑法 步骤 默认序列最左边的元素为基准值key把值挖走用key变量保存该位置为一个坑。 右边找小找到后把值填给坑位该位置成为新的坑位。 左边找大找到后把值填给坑位该位置成为新的坑位。 重复步骤2~3。 左右相遇相遇位置也是个坑位key值填入坑位。
图解
代码
int Partion2(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;
}
与前面代码不同的是这里的key值我们不存下标用一个变量保存。
前后指针法 步骤 默认序列最左边的元素为基准值key设置prev指针 leftcur指针 left1。 cur找小找到后preva[prev]和a[cur]交换。 重复步骤2。 cur走完以后a[prev]和key交换。
图解
代码
int Partion3(int* a, int left, int right)
{int keyI left;int prev left, cur prev 1;while (cur right){if (a[cur] a[keyI] prev ! cur)Swap(a[prev], a[cur]);cur;}Swap(a[prev], a[keyI]);return prev;
}
为了避免自己和自己交换prev先判断和cur是否相等相等就不交换。
很明显这种分割方法的代码相比前面两种简单了许多这种划分法也是最常用的。
2.6.5 快排优化
取key方面的优化
最理想的情况就是key值每次都是中间的值快排的递归就是一个完美的二分。
快排在面对一些极端数据时效率会明显下降就比如完全有序的序列这种序列的基准值key如果再取最左边或者最右边的数key值就是这个序列的最值复杂度会变成ON^2 这时候就可以用三数取中法来解决这个弊端三个数为a[left],a[mid],a[right],这样就可以尽量避免key值选到最值的情况。
//三数取中法选key值
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; elsereturn right; }else //mid left{if (a[left] a[right])return left;else if (a[mid] a[right])return mid; elsereturn right; }
}//前后指针划分
int Partion3(int* a, int left, int right)
{//中间值的下标为midIa[left]替换为此中间值int midI GetMidIndex(a, left, right); Swap(a[left], a[midI]); int keyI left;int prev left, cur prev 1;while (cur right){if (a[cur] a[keyI] prev ! cur)Swap(a[prev], a[cur]);cur;}Swap(a[prev], a[keyI]);return prev;
}
递归方面的优化
我们知道递归深度太深并不是一件好事所以我们可以针对递归方面来进行优化减少绝大多数的递归调用。
如何优化呢当递归到区间内元素个数10时调用直接插入排序。
void _QuickSort(int* a, int begin, int end)
{if (begin end)return;//区间内元素个数 10调用直接插入排序if (end - begin 1 10){InsertSort(a begin, end - begin 1);//注意起始地址是a begin,不是a}else{//根据基准值把数组划分成左右序列int keyI Partion3(a, begin, end); //左右序列递归划分下去_QuickSort(a, begin, keyI - 1); _QuickSort(a, keyI 1, end); }
}
这种优化其实可以减少绝大多数的递归调用我们把快排的递归划分想象成一颗二叉树区间长度小于10的数组大概在这棵二叉树的最后三层而最后三层占了整棵树结点个数的80%多最后一层50%倒数第二层25%...类比快排的递归来看我们省去了80%多的递归调用并且对于数据规模较小的情况下直插和快排的效率差不了多少所以这是一个极大的优化算法库中的sort函数也大多是这种优化。
2.6.6 快排非递归实现
快排的非递归我们可以使用一个栈深度优先遍历或者一个队列实现广度优先遍历
栈实现代码图解
void QuickSortNonRByStack(int* a, int n)
{Stack st; StackInit(st);int begin 0, end n - 1;//先Push右边界在Push左边界//记住push顺序取top的时候左右不要取反了StackPush(st, end);StackPush(st, begin);while (!StackEmpty(st)){int begin StackTop(st); StackPop(st); int end StackTop(st); StackPop(st); int keyI Partion3(a, begin, end);//[begin, keyI - 1] keyI [keyI 1, end]//先递归到左区间所以右区间先入栈if (keyI 1 end) {//先Push右边界在Push左边界StackPush(st, end); StackPush(st, keyI 1); }if (begin keyI - 1){//先Push右边界在Push左边界StackPush(st, keyI - 1); StackPush(st, begin);}}StackDestory(st);
}
队列实现
void QuickSortNonRByQueue(int* a, int n)
{Queue q;QueueInit(q);int begin 0, end n - 1; QueuePush(q, begin); QueuePush(q, end); while (!QueueEmpty(q)){int begin QueueFront(q);QueuePop(q);int end QueueFront(q); QueuePop(q); int keyI Partion3(a, begin, end); if (begin keyI - 1) {QueuePush(q, begin); QueuePush(q, keyI - 1);}if (keyI 1 end) {QueuePush(q, keyI 1); QueuePush(q, end); }}QueueDestory(q);
}
2.6.7 特性总结 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 时间复杂度O(NlogN)
最好情况每次key都在中间位置正好二分
最坏情况每次key都是最值复杂度O(N^2)
平均情况带优化复杂度O(NlogN) 空间复杂度O(logN)
2.7 归并排序
2.7.1 基本思想
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。
2.7.2 排序步骤
归并排序和快速排序一样采用的是分治法 将待排序序列分成两个子序列。 递归两个子序列使两个子序列有序。 合并两个子序列使整个序列有序。 左右子序列的排序重复1~3.
2.7.3 代码实现
几个注意点 我们使用归并排序能在原数组上进行归并吗当然不能假如后一个值小于前一个那么就对前一个值进行了覆盖。所以我们要开辟一个临时空间数据归并到这个临时空间里然后再拷贝到原数组。这也是归并排序的一个缺点需要额外空间。 tmp数组的数据拷贝到原数组时注意两个空间的起始地址tmp left a left
void _MergeSort(int* a, int* tmp, int left, int right)
{if (left right)return;int mid (left right) / 2;//[left, mid] [mid 1, right]_MergeSort(a, tmp, left, mid);_MergeSort(a, tmp, mid 1, right);int begin1 left, end1 mid;int begin2 mid 1, end2 right;int index left;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1]; }else{ tmp[index] a[begin2]; }}while (begin1 end1){ tmp[index] a[begin1]; }while (begin2 end2){tmp[index] a[begin2]; }//tmp局部排好的数据拷贝到a中//注意这里两个空间的起始地址不要传tmp和a了memcpy(a left, tmp left, sizeof(int) * (right - left 1));
}void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(Merge:);exit(-1);}_MergeSort(a, tmp, 0, n - 1);free(tmp);
}
2.7.4 动图解析 2.7.5 非递归实现
归并排序的非递归在逻辑上不难理解但是他在边界上的控制却相当麻烦我们先看一种不麻烦的情况数组size为2^n的情况下。
假设数组个数为8我们可以先一个数据和一个数据归并然后两个数据和两个数据归并然后四个数据和四个数据归并完成排序。
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(MergeSortNonR:);exit(-1);}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;int index begin1; //[begin1, end1] [begin2, end2]两个区间进行归并while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}while (begin1 end1){tmp[index] a[begin1];}while (begin2 end2){tmp[index] a[begin2];}memcpy(a i, tmp i, sizeof(int) * (end2 - i 1)); }gap * 2;}free(tmp);
}
但是我们并不能保证[begin1, end1] [begin2, end2]这两个区间都存在可能会有越界我们可以肯定的是begin1一定不会越界因为begin1 i而i n我们就是用i来控制一组数据归并的起始地址。所以可能越界的只会有end1,begin2,end2
这三种越界我们根据右区间存不存在分两种谈论 end1和begin2越界这种情况下第二个区间都不存在了我们就不用归并了。 end2越界这种情况下第二个区间还存在我们只需修正一下end2 n - 1即可。
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(MergeSortNonR:);exit(-1);}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;int index begin1;//[begin1, end1] [begin2, end2]两个区间进行归并//可能越界的位置end1,begin2,end2//end1和begin2越界右区间不存在直接不用归了//end2越界右区间还存在修正一下end2 n - 1接着归if (begin2 n) //end1越界begin2肯定越界{break;}if (end2 n){end2 n - 1;}//printf([%d, %d][%d, %d] , begin1, end1, begin2, end2); while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){ tmp[index] a[begin1]; }else{tmp[index] a[begin2]; }}while (begin1 end1){tmp[index] a[begin1]; }while (begin2 end2){tmp[index] a[begin2]; }//一组归完直接拷贝方便控制memcpy(a i, tmp i, sizeof(int) * (end2 - i 1)); }gap * 2;//printf(\n);}free(tmp);
}
代码还有两点注意 一组数据归并时begin1是一直的所以归并完后左区间的左边界并不是begin1而是i。 这里tmp数组拷贝到原数组的时候我们并不是拷贝整个数组而是一组归并完后就直接拷贝这样方便控制不然我们不好控制拷贝的数据个数如果整个tmp都拷贝会带有随机值覆盖原数组所以不建议整个拷贝。
2.7.6 特性总结 时间复杂度O(N*logN) 完美的二分 空间复杂度O(N)
2.8计数排序
2.8.1 基本思想
计数排序相比于前面的所有排序都有所不同因为这是一种非比较排序也是一种哈希思维的应用。
哈希思维就是健值和他的存储位置构成一种映射关系也就是数组的值和他的下标存在一种映射关系。
2.8.2 排序步骤
排序步骤 创建一个计数的数组数组的值初始化为0。 遍历待排序数组根据数组的值映射到计数数组的下标让该下标的值。 根据统计的结果计数数组的数据覆盖到原数组中完成排序。
这里有两点注意 但是我们不能进行直接映射就是数组的值 映射的下标这样很容易造成空间浪费。这里就要进行相对映射先找到数组中的最小值min映射下标 数组的值 - min。 计数数组的大小我们也不能随便开辟大小应该为max - min 1。
最终排序步骤 找出数组的min和max。 创建一个计数的数组大小为max - min 1数组的值初始化为0。 遍历待排序数组根据数组的值映射到计数数组的下标让该下标的值。 根据统计的结果计数数组的数据覆盖到原数组中完成排序。 2.8.3 代码实现
void CountSort(int* a, int n)
{//找到max和minint max a[0], min a[0];for (int i 1; i n; i){if (a[i] min){min a[i];}if (a[i] max){max a[i];}}//创建计数数组并初始化为0int range max - min 1;int* countArr (int*)malloc(sizeof(int) * range);if (countArr NULL){perror(CountSort:);exit(-1);}memset(countArr, 0, sizeof(int) * range); //统计数组数据for (int i 0; i n; i){countArr[a[i] - min];}//根据统计结果拷贝到原数组int index 0; for (int i 0; i range; i){while (countArr[i]--){a[index] i min; }}free(countArr);
}
2.8.4 特性分析 计数排序在数据范围集中时效率很高但是适用范围及场景有限。 时间复杂度O(Nrange) 空间复杂度O(range)
3.排序算法复杂度及稳定性分析
稳定性概念
假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。
下面我们研究一下七大排序的稳定性 直接插入排序
待插入数据(tmp) a[end] 插入到该数据的后面前后关系不变直插排序是个稳定的排序。 希尔排序
假如两个相同的数据被分到了不同组我们不能保证这两个数据的前后关系所以希尔排序是个不稳定的排序。
例如 选择排序最容易错的
假如被交换的元素就是相同的元素前后关系改变所以选择排序是个不稳定的排序。
例如 第一个3与最小元素1交换后相同元素3的顺序发生了改变。 堆排序
如果堆顶数据和他的一个孩子相同前后关系改变所以堆排序是个不稳定的排序。
例如 冒泡排序
如果左边和右边相等就不交换这样前后关系不变所以冒泡排序是个稳定的排序。 快速排序
假如一个值和key相等并且相遇位置在这个值的右边这样交换后前后关系改变所以快速排序是个不稳定的排序。
例如 归并排序
如果左区间的数 右区间的数时把左区间的数归并下来这样前后关系不变所以归并排序是个稳定的排序。 //[begin1, end1] [begin2, end2]两个区间进行归并while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}while (begin1 end1){tmp[index] a[begin1];}while (begin2 end2){tmp[index] a[begin2];}
排序方法时间复杂度空间复杂度稳定性直接插入排序O(N^2)O(1)Y希尔排序O(N^1.3)O(1)N选择排序O(N^2)O(1)N堆排序O(NlogN)O(1)N冒泡排序O(N^2)O(1)Y快速排序O(NlogN)O(logN)N归并排序O(NlogN)O(N)Y计数排序O(Nrange)O(range)N
