网站建设的基本知识,资料网站怎么做,什么网站上做推广,中国建设银行钓鱼网站经典七大比较排序算法 上1 选择排序1.1 算法思想1.2 代码实现1.3 选择排序特性2 冒泡排序2.1 算法思想2.2 代码实现2.3 冒泡排序特性3 堆排序3.1 堆排序特性#xff1a;4 快速排序4.1 算法思想4.2 代码实现4.3 快速排序特性5 归并排序5.1 算法思想5.2 代码实现5.3 归并排序特性…
经典七大比较排序算法 ·上1 选择排序1.1 算法思想1.2 代码实现1.3 选择排序特性2 冒泡排序2.1 算法思想2.2 代码实现2.3 冒泡排序特性3 堆排序3.1 堆排序特性4 快速排序4.1 算法思想4.2 代码实现4.3 快速排序特性5 归并排序5.1 算法思想5.2 代码实现5.3 归并排序特性1 选择排序
1.1 算法思想
选择排序每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 大致操作步骤如下
第一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置然后再从剩余的未排序元素中寻找到最小大元素然后放到已排序的序列的末尾重复第二步操作直到全部待排序的数据元素的个数为零。 选择排序视频演示1.2 代码实现
选择排序还是很好理解的。但这里的实现会对直接选择排序做一些小的改进。 既然直接选择排序遍历一遍可以找出最小的数据那遍历一遍同样可以找出最大的元素。这样每遍历一次待排序数据元素的起始位置就变成最小的了结束位置就变成最大的了。 参考代码如下
//n - 数据个数
void SelectSort(int* a, int n)
{int begin 0; //待排序数据起始位置下标int end n - 1;//待排序数据结束位置下标int minIndex 0;//记录最小数据的下标int maxIndex 0;//记录最大数据的下标//待排序数据大于1时进入循环while (begin end){//假设一开始最小元素和最大元素下标都是第一个待排序数据下标minIndex begin;maxIndex begin;//遍历一遍for (int i begin 1; i end; i){//选出最小元素下标if (a[i] a[minIndex]){minIndex i;}//选出最大元素下标if (a[i] a[maxIndex]){maxIndex i;}}//将最小元素和待排序序列的起始位置交换Swap(a[begin], a[minIndex]);//将最大元素和待排序序列的结束位置交换Swap(a[end], a[maxIndex]);//缩小待排序区间重复上述过程begin;--end;}
}很多老铁在敲完上面代码之后觉得已经没有问题了。 但实际上像遇到上面情况。如果[maxIndex]指向的是[begin]中存放的内容[minIndex]的内容先和[begin]交换之后[maxIndex]指向的就不在是待排序序列中的最大元素了。需要做相应的修改。 Swap(a[begin], a[minIndex]);//如果begin和maxIndex重叠那么修正maxInedxif (begin maxIndex){maxIndex minIndex;}Swap(a[end], a[maxIndex]);1.3 选择排序特性
选择排序作为一种简单直观的排序算法虽然好理解但效率并不高。 无论是在面对什么样的排序序列时间复杂度都是稳定的O(n2)O(n^2)O(n2)量级实际中很少使用。
2 冒泡排序
2.1 算法思想
冒泡排序作为一种交换排序它会重复地走访要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到不再需要交换也就是说该数列已经排序完成。 大致操作步骤如下
比较相邻的两个元素。如果第一个和第二个大元素的顺序不符合要求就交换他们两个。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 冒泡排序视频演示2.2 代码实现
//n - 数据个数
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i){for (int j 0; j n - 1 - i; j){//排升序if (a[j] a[j 1]){Swap(a[j], a[j 1]);}}}
}冒泡排序还有一种优化的方法就是立一个 flag当在一趟序列遍历中元素没有发生交换则证明该序列已经有序不需要再继续进行冒泡排序了。
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i){int flag 1;for (int j 0; j n - 1 - i; j){if (a[j] a[j 1]){flag 0;Swap(a[j], a[j 1]);}}if (1 flag){break;}}
}但这种改进优化在实际上对于提升性能来说并没有什么作用并不是很大。
2.3 冒泡排序特性
冒泡排序也是一种非常简单直观的排序。 在最好的情况下(序列接近有序)冒泡排序的时间复杂度是O(n)O(n)O(n)量级的 在最坏的情况下(序列逆序)冒泡排序的时间复杂度是O(n2)O(n^2)O(n2)量级的。
3 堆排序
关于堆排序的算法思想和代码实现相关内容可以参考阿顺的堆结构的两个应用这篇博客里面有比较详细的介绍。这里就不在赘述了。
3.1 堆排序特性
堆排序使用堆的结构来选数效率就高了很多。 堆排序的平均时间复杂度是O(n∗log2n)O(n*log_2n)O(n∗log2n)量级的。
4 快速排序
4.1 算法思想
快速排序是Hoare提出的一种二叉树结构的交换排序方法。 其基本思想为 任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两个子序列其中左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后对左右子序列重复该过程直到所有元素都排列在相应位置上为止。 算法步骤
从序列中挑出一个元素作为基准排序数列将所有比基准值小的元素摆放在基准前面所有比基准值大的元素摆放在基准后面相同的数可以在任一边。在这个分区排完之后该基准就处于数列的中间位置递归地把小于基准值元素的子数列和大于基准值元素的子数列排序 快速排序视频演示4.2 代码实现
快速排序在发展的过程中涌现出了很多种不同的版本但核心思想是不会变的。这里会介绍3种常见版本以供大家参考。
//a - 待排序序列
//begin - 待排序序列起始位置
//end - 待排序序列结束位置
void QuickSort(int* a, int begin, int end)
{//序列只有一个值或没有值就不再排序if (begin end){return;}//对区间进行快速排序并返回排序后的基准值位置int keyIndex QuickPartSort(a, begin, end);//[begin, keyIndex - 1] keyIndex [keyIndex 1, end]//左区间排序QuickSort(a, begin, keyIndex - 1);//右区间排序QuickSort(a, keyIndex 1, end);}上面代码就是快速排序实现的主框架QuickPartSort函数有不同的实现方式。 其实从主框架上可以看出快速排序的递归实现和二叉树的前序遍历还是很像的。
hoare版本
//以排升序为例
int QuickPartSort1(int* a, int begin, int end)
{int left begin;int right end;//取序列第1个数据做基准值int keyIndex left;while (left right){//右边先走找小while (left right a[right] a[keyIndex]){--right;}//左边再走找大while (left right a[left] a[keyIndex]){left;}//左大右小-交换Swap(a[left], a[right]);}//left和right相遇此时将基准值和相遇值交换Swap(a[keyIndex], a[left]);//基准值下标跟着改变keyIndex left;return keyIndex;
}观察hoare版本的代码发现选择的是最左边的值做基准值。此时却是让右边的索引先走那能不能让左边的值先走呢又为什么选择右边的值先走呢 答案是左边的值先走也可以但是处理起来细节上更复杂一些。 选择右边先走的原因是为了保证相遇位置的值比基准值小(或者就是基准位置的值)。 右边先走的情况无非就是
right先走right遇到比基准值小的right停下来让left走left去遇到了right。 这种情况相遇位置就是right停下来的位置right停的位置也就是比基准值要小的位置。right先走right没有遇到比基准值要小的值right去遇到了left。 这种情况下相遇位置是left上一轮停下来的位置该位置要么是基准值的位置要么就是比基准值小的位置。 这时反过来想一下如果选最左边为基准值left先走的话相遇位置的值就是大于基准值的这样相遇位置的值就不能和基准值交换这里需要做一些处理来让基准值交换到合适的位置去最终徒劳增加了麻烦。 所以一般建议是 左边做基准值让右边先走 右边做基准值让左边先走。
挖坑版本 在面对上面hoare版本比较不好理解的左边做基准值右边先走的问题时挖坑法的版本能让快速排序更好理解一点点。
int QuickPartSort2(int* a, int begin, int end)
{//最左边做基准值int key a[begin];//坑位给到基准值位置int pitIndex begin;int left begin;int right end;while (left right){//右边找小填到左边的坑里面去。这个位置形成新的坑。while (left right a[right] key){--right;}a[pitIndex] a[right];pitIndex right;//左边找大填到右边的坑里面去。这个位置形成新的坑。while (left right a[right] key){left;}a[pitIndex] a[left];pitIndex left;}//坑位再填上基准值a[pitIndex] key;return pitIndex;
}因为坑位的存在左边有坑右边就走然后填坑右边有坑左边就走然后填坑。这个过程就更好理解了。但是挖坑法在算法性能上相比hoare版本并没有什么大的改进。 3. 前后指针版本 前后指针的使用和前两个版本的排序方式就有较大的区别了。
int QuickPartSort3(int* a, int begin, int end)
{//基准值选择int keyIndex begin;int prev begin;//前指针int cur begin 1;//后指针while (cur end){//cur位置的值小于keyIndex位置的值if (a[cur] a[keyIndex]){prev;Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyIndex]);keyIndex prev;return keyIndex;
}前后指针方法中两个指针都是从左向右的方向在走直到cur走完整个序列。 但是在走的过程中prev的位置1后如果和cur位置相等因为指向同一个位置就不需要交换了代码进一步优化如下
if (a[cur] a[keyIndex] prev ! cur)
{Swap(a[prev], a[cur]);
}前后指针版本不仅好理解而且代码也很简洁是几个版本中最推荐的了。 但是以上方法选基准值还是存在一定问题的。 鉴于以上几个版本都选择的是最左边作为基准值如果是排已经有序的序列的话如下图所示 序列有多少的数据就递归多少次很容易栈溢出。 所以为了让每次选择基准值避免选择到序列中的最值有的地方给出用随机数的方法选择基准值但这里主要介绍三数取中选择基准值的方法。 所谓三数取中不过是在序列的起止位置中间位置末位位置选择这三个数出来通过比较找到不是最大也不是最小的一个数让这个数做基准值。
int GetMidIndex(int* a, int begin, int end)
{int mid begin (end - begin) / 2;if (a[begin] a[mid]){if (a[mid] a[end]){return mid;}else if (a[begin] a[end]){return end;}else{return begin;}}else//beginmid{if (a[mid] a[end]){return mid;}else if (a[begin] a[end]){return begin;}else{return end;}}
}找到基准值之后可以将基准值和序列的起始位置进行一个交换这样就和之前排序的代码一样仍是选择序列的起始位置做基准值了。代码也不需要更多的修改了。
//三数取中优化
int mid GetMidIndex(a, begin, end);
Swap(a[keyIndex], a[mid]);因为三数取中的优化使的每次递归左右子序列更加的二分代码效率自然就得到了提高。 当然我们知道递归需要是创建销毁和销毁栈帧的具体参考阿顺的这篇博文你也能看懂的的函数栈帧创建与销毁 因为快速排序的递归和二叉树前序递归很像如果快速递归的划分接近二分的话就会像满二叉树的遍历一样最后一层的数量(2h−12^{h-1}2h−1)会是整棵树数量(2h−12^h-12h−1)的一半也就是快速排序最后一层的递归次数是整个过程递归次数的一半。在面对小数据量时还要递归这么多次进行栈帧的开销确实会影响到程序的效率。 所以可以对小区间进行优化当递归划分小区间区间比较小的时候就不再递归划分去排序这个小区间。而是可以考虑直接用其它排序对小区间进行处理。 这里就给出对小区间元素小于10时的插入排序处理。
if (end - begin 10)
{//int keyIndex PartSort1(a, begin, end);//int keyIndex PartSort2(a, begin, end);int keyIndex QuickPartSort3(a, begin, end);QuickSort(a, begin, keyIndex - 1);QuickSort(a, keyIndex 1, end);
}
else
{InsertSort(a begin, end - begin 1);
}通过计算可以得出以上代码在采用小区间优化后函数调用次数可以减少80%80\%80%左右这种提升还是很明显的。 以上都是对快速排序的递归版本的介绍。但是递归有一个死穴就是递归太深栈溢出程序会崩溃。所以也要能够对快速排序进行非递归的实现。 可以借助栈数据结构或者队列数据结构进行非递归实现。这里就选择栈数据结构来进行实现。借助栈来实现的运行逻辑是可以和递归实现的递归逻辑达成一致的。 因为是C语言实现所以对于栈数据结构的需要可以参考阿顺的这篇博文顺序表实现栈(C语言)
void QuickSortNonR(int* a, int begin, int end)
{Sk stack;StackInit(stack);StackPush(stack, end);StackPush(stack, begin);while (!StackEmpty(stack)){int left StackTop(stack);StackPop(stack);int right StackTop(stack);StackPop(stack);int keyIndex QuickPartSort3(a, left, right);// [left, keyIndex-1] keyIndex [keyIndex1, right]if (keyIndex 1 right){StackPush(stack, right);StackPush(stack, keyIndex 1);}if (left keyIndex - 1){StackPush(stack, keyIndex - 1);StackPush(stack, left);}}StackDestroy(stack);
}代码结合画图就很容易理解快速排序的非递归了。
4.3 快速排序特性
快速排序一听到这个名字你就知道它存在的意义l。而且快速排序整体的综合性能和使用场景都是比较好的所以也才敢叫快速排序。 快速排序的一次划分算法从两头交替搜索直到left和right重合因此其时间复杂度是O(n)O(n)O(n)而整个快速排序算法的时间复杂度与划分的趟数有关。 理想的情况是每次划分所选择的中间数恰好将当前序列几乎等分经过log2nlog_2nlog2n趟划分便可得到长度为1的子表。这样整个算法的时间复杂度为O(n∗log2n)O(n*log_2n)O(n∗log2n)。 最坏的情况是每次所选的中间数是当前序列中的最大或最小元素这使得每次划分所得的子表中一个为空表另一子表的长度为原表的长度-1。这样长度为n的数据表的快速排序需要经过n趟划分使得整个排序算法的时间复杂度为O(n2)O(n2)O(n2)。 从空间性能上看尽管快速排序只需要一个元素的辅助空间但快速排序需要一个栈空间来实现递归。最好的情况下即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表所需栈的最大深度为log2(n1)log_2{(n1)}log2(n1)但最坏的情况下栈的最大深度为n。
5 归并排序
5.1 算法思想
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并得到完全有序的序。若将两个有序表合并成一个有序表称为二路归并。 算法步骤
申请空间使其大小为两个已经排序序列之和该空间用来存放合并后的序列设定两个指针最初位置分别指向两个已经排序序列的起始位置比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置重复步骤 3 直到某一指针到达序列尾将另一序列剩下的所有元素直接复制到合并序列尾。 归并排序视频演示5.2 代码实现
作为一种典型的分而治之思想的算法应用归并排序的实现有两种方法
自上而下的递归
//n - 数据个数
void MergeSort(int* a, int n)
{//开辟归并空间int* tmp (int*)malloc(n * sizeof(int));assert(tmp ! NULL);//归并排序_MergeSort(a, 0, n - 1, tmp);free(tmp);
}void _MergeSort(int* a, int begin, int end, int* tmp)
{//递归区间不足1个数据就不再递归//因为1个数据即有序if (begin end){return;}int mid begin (end - begin) / 2;// [begin, mid][mid1, end] 分治递归让子区间有序//左区间递归_MergeSort(a, begin, mid, tmp);//又去见递归_MergeSort(a, mid1, end, tmp);//归并过程int begin1 begin;int end1 mid;int begin2 mid 1;int end2 end;int i begin1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}//把归并数据拷贝回原数组memcpy(a begin, tmp begin, (end - begin 1) * sizeof(int));
}自下而上的迭代。 所谓自下而上的迭代不过是最开始从1个和1个开始归并(因为1个数据即有序)。 之后每次归并数据都扩2倍直到最后一组的数据已经大于等于整个序列的数据为止就完成归并了。可以用循环来解决。
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(n * sizeof(int));assert(tmp ! NULL);//最开始一组只有一个数据int gap 1;//一组的数据要小于序列长度while (gap n){for (int i 0; i n; i 2 * gap){//[i,igap-1]和[igap, i2*gap-1]区间的数据进行归并int begin1 i;int end1 i gap - 1;int begin2 i gap;int end2 i 2 * gap - 1;int j begin1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}}//一趟归并结束进行拷贝memcpy(a, tmp, n * sizeof(int));//一组数据扩2倍gap * 2;}free(tmp);
}但是上面代码有一个致命的bug就是只能适用于2n2^n2n个数据的归并。否则就存在越界的错误。 所以需要对归并区间进行界线的判断和修正。 因为begin1i不会越界而end1 begin2 end2都可能越界。 所以存在三种情况下的修正
//修正边界
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;
}上述是修正的一种方法。还可以采用更省事的策略在遇到越界的区间时就不再归并了。
if (end1 n || begin1 n)
{break;
}
else if (end2 n)
{end2 n - 1;
}但这种方法需要每归并一次就拷贝一次而不是等到一趟归并完在拷贝。memcpy函数应该放在for循环之内。
5.3 归并排序特性
归并排序的时间复杂度是稳定的O(n∗log2n)O(n*log_2n)O(n∗log2n)而因为要开辟额外的归并数组所以空间复杂度是O(n)O(n)O(n)。 归并排序速度仅次于快速排序一般用于对总体无序但是各子项相对有序的数列排序。 归并排序的比较次数小于快速排序的比较次数移动次数一般多于快速排序的移动次数。 虽然归并排序比较占用内存但却是一种效率高且稳定的算法。
