公司网站非响应式模板,wordpress 增加作者,嘉兴网站关键词推广,wordpress 删除主题作者前言
本篇博客将为大家介绍各类排序算法#xff0c;大家知道#xff0c;在我们生活中#xff0c;排序其实是一件很重要的事#xff0c;我们在网上购物#xff0c;需要根据不同的需求进行排序#xff0c;异或是我们在高考完报志愿时#xff0c;需要看看院校的排名#…前言
本篇博客将为大家介绍各类排序算法大家知道在我们生活中排序其实是一件很重要的事我们在网上购物需要根据不同的需求进行排序异或是我们在高考完报志愿时需要看看院校的排名等等这些都离不开排序今天我们就来看计算机语言中几类常见的排序算法如果你对本文感兴趣欢迎留言交流下面进入正文部分。 Comparison Sorting Visualization
大家可以通过这个网址来查看各种排序的动图以便于大家理解。
1.直接插入排序
这个顾名思义就是将数据取出来比较然后再插入合适的位置以达到有序的效果这个就类似于我们玩的扑克牌当我们摸到拍时我们需要按照扑克牌的规则对其进行有效的排序这里其实就是运用了插入排序的思想。
上面介绍了什么是插入排序下面大家来看看具体代码。
void InsertSort(int* a, int n)
{int i 0;for (i 0; i n - 1; i)//这里循环的结束条件需要注意我们最后一组是a[n-1]a[n-2]{int end i;//假设[0,end]有序现在将end1位置的值插入到[0,end]保持有序int tmp a[end 1];//这里需要先保存end1位置的值否则挪动的时候就会覆盖掉后面的数据while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
} 直接插入排序的特性总结
1. 元素集合越接近有序直接插入排序算法的时间效率越高
2. 时间复杂度O(N^2)最坏情况O(N)最好情况
3. 空间复杂度O(1)它是一种稳定的排序算法
4. 稳定性稳定
插入排序比起我们之前学过的冒泡排序效率是要高不少的在实践中我们会用到插入排序所以大家需要掌握插入排序的写法。
2. 希尔排序
希尔排序是一种比较复杂的排序方法但是它的效率是比较高的可以说它是选择排序的一种优化所以我们必须先理解好插入排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是先进行预排序然后再进行插入排序。 预排序阶段我们会先定义一个gap表示一次跳过的间隔这里其实大家可以根据插入排序去理解gap当gap等于1时其实就变成了插入排序。
这里大家需要明确
gap越大大数可以越快跳到前面小数可以越快跳到后面但是结果越不接近有序
gap越小则反之。所以我们需要让gap成为一个变量。
#includestdio.h
void ShellSort(int* a,int n)
{int gap n;while (gap 1){gap gap / 3 1;//这里1是为了让gap最终等于1//当gap1时执行的是预排序//当gap1时执行的就是插入排序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];end - gap;}else{break;}}a[end gap] tmp;}}
} 这里大家注意与插入排序进行对比代码的逻辑和插入排序是类似的这里还有一点需要大家注意就是希尔排序的时间复杂度O(n^1.3)这个结果大家记忆即可。
3. 选择排序
这个排序属于比较简单的一种排序基本思想就是找出最大的放后面找出最小的放前面然后重复上述过程即可从这里大家其实就可以感受到这个算法的效率是比较低的在实践中我们一般是不用它来进行排序的。
void SelectSort(int* a, int n)
{int begin 0;int end n - 1;while (begin end){int mini begin;int maxi begin;for (int i begin 1; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}Swap(a[begin], a[mini]);if (maxi mini){maxi mini;}Swap(a[end], a[maxi]);begin;end--;}
} 直接选择排序的特性总结
1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用
2. 时间复杂度O(N^2)
3. 空间复杂度O(1)
4. 稳定性不稳定
4.快速排序
说到快速排序这里有三种方法hoare、挖坑法前后指针法我主要为大家介绍前后指针的方法因为这个方法相对于其他两个好理解一些。 前后指针顾名思义有两个指针具体怎么工作呢刚cur位置的值小于key时那么prev然后将prev位置的值和cur位置的值互换然后cur指针继续往后走当cur位置的值大于key时cur直接往后走一直到cur越界为止。本质上实现key左边都是比key小的key右边都是比key大的。
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}int PartSort(int* a, int left, int right)
{int keyi left;int prev left;int cur prev 1;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[cur], a[prev]);}cur;}Swap(a[keyi], a[prev]);return prev;
}
void QuickSort(int* a, int left, int right)
{if (left right){return;}int keyi PartSort(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);
}
这里大家看快排的代码这里运用了递归的思想在单趟排序中我们得到的就是key的位置然后在不同的区间进行快排这里运用递归很快可以实现快排但是递归还是存在一定的缺陷当深度过深时递归可能会引发栈溢出的问题所以我们能不能不用递归来实现快排呢答案当然是可以的。
如果我们想写非递归的快排那么我们就需要用到栈这个数据结构本质上是将存在栈帧中的区间放在了栈这个数据结构中来模拟实现递归的过程
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
int PartSort2(int* a, int left, int right)
{int keyi left;int prev left;int 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;
}
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(st);//入两个整数先入右再入左形成一个区间STPush(st, right);STPush(st, left);while (!STEmpty(st)){int begin STTop(st);//这里出栈就是先出左再出右STPop(st);int end STTop(st);STPop(st);int keyi PartSort2(a, begin, end);if (keyi 1 end){STPush(st, end);STPush(st, keyi1);}if (begin keyi - 1){STPush(st, keyi-1);STPush(st, begin);}}STDestroy(st);
}
这里大家来看非递归的代码循环每走一次就取出栈顶区间然后还是先入右再入左如此循环下去就模拟了递归的过程。
快速排序的特性总结
1. 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序
2. 时间复杂度O(N*logN)
3. 空间复杂度O(logN)
4. 稳定性不稳定
5. 堆排序
堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。
需要注意的是排升序要建大堆排降序建小堆。
堆排序之所以叫做堆排是因为需要结合堆中的向上调整和向下调整两个算法具体大家可以看下面代码或者去二叉树那篇文章中查看。
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void AdjustUp(int* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}
void AdjustDown(int* a, int n, int parent)
{//这里先假设左孩子小int child parent * 2 1;while (child n)//childn时说明已经调整到叶节点了{//找出小的那个孩子if (a[child 1] a[child] child 1 n){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}
void HeapSort(int* a, int n)
{int i 0;for (i 1; i n; i){AdjustUp(a, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
} 这里我举的例子是建大堆排升序升降序可以在向下调整和向上调整中进行切换。
堆排的工作原理在于我们要先根据需要建堆这里就用到向上调整的算法帮助我们建成大堆或小堆建好堆后我们需要将首尾位置的数据进行交换然后让根部位置的数据向下调整这里拿建大堆排升序来说我们第一次交换将最大的数放到了最后然后第二次将次大的数放到倒数第二个位置以此类推到最后我们就可以得到一组升序的数据排降序是同理。
上面所介绍的是堆排的第一种写法这种写法是比较容易理解的但是我们还有另一种写法可以在其基础上再提高效率——向下调整建堆。这里大家需要明确一个问题向下调整算法有一个前提左右子树必须是一个堆才能调整。所以我们必须保证左右子树都是堆才可以然而这样显然不太现实于是我们就采取一种倒着建堆的方式我们从倒数第一个非叶子节点开始调一直到根节点这样也能实现同样的建堆效果。
这里大家还需要注意一点无论哪种写法时间复杂度都为O(NlogN)。但是实际上还是第二种方法能快一些它们时间复杂度一样只是说它们属于同一个量级但是具体详细地来看还是第二种快建议大家堆排就写下面这种。
void AdjustDown(int* a, int n, int parent)
{//这里先假设左孩子小int child parent * 2 1;while (child n)//childn时说明已经调整到叶节点了{//找出小的那个孩子if (a[child 1] a[child] child 1 n){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}
void HeapSort(int* a, int n)
{int i 0;for (i (n-2)/2; i 0; i--){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}
堆排序的特性总结
1. 堆排序使用堆来选数效率就高了很多。
2. 时间复杂度O(N*logN)
3. 空间复杂度O(1)
4. 稳定性不稳定
堆排序是一种效率很高的排序方法尤其是在数据比较多的情况下它的运行效率和快排是一个档次的所以这个排序是具有实际意义的。
6. 归并排序 大家可以直接来看这张图展现了归并排序的核心思想我们要采用分治法保证两边区间都有序后进行归并
void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin end)return;int mid (begin end) / 2;//递归使左右区间都有序_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid1, end);//进行归并int begin1 begin, end1 mid;int begin2 mid1, end2 end;int i begin;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));
}
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp NULL;
} 上面就是归并排序的代码其实大家可以结合二叉树中的后序遍历来进行理解这要提醒一下大家在我们分割区间的时候要按照上面的方式进行分割不能分割成[begin,mid-1]和[mid,end]这样会导致程序陷入死循环。
上面我们学习快排的时候介绍了两种方法一种是运用递归一种是运用非递归那么在这里亦有异曲同工之妙归并排序也是可以用非递归来实现的。
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);exit(1);}//gap为每组归并数据的个数int gap 1;int i 0;while (gap n){for (i 0; i n; i 2 * gap){//进行归并int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;if (begin2 n){break;}if (end2 n){end2 n - 1;}int j i;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 i, tmp i, (end2 - i 1) * sizeof(int));}gap * 2;}free(tmp);tmp NULL;
}
这里大家来看一下非递归的归并排序核心思想就是一组一组归并这里大家要注意我们需要归并一段拷贝一段区别于上面递归版的归并。
归并排序的特性总结
1. 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度O(N*logN)
3. 空间复杂度O(N)
4. 稳定性稳定
这里大家可以发现归并排序也是一种效率很高的排序方法它的效率和堆排快排是一个档次的所以具有一定实践意义。
7. 冒泡排序
关于冒泡排序这里就不赘述了再前面C语言的文章介绍循环的文章中有大家有需要的可以自行去我的主页查看。为什么里不详细介绍冒泡呢原因有二
其一冒泡排序比较简单属于交换排序的一种如果是初学者可以学习一下冒泡排序感受一下循环的嵌套。
其二冒泡排序确实是上不了台面因为它太慢了和其他几个不是一个量级的所以没啥实际意义只有一定的教学意义。
8. 计数排序
void CountSort(int* a, int n)
{int min a[0];int max a[0];int i 0;for (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* count (int*)calloc(range, sizeof(int));if (count NULL){perror(calloc fail);exit(1);}//统计次数for (i 0; i n; i){count[a[i] - min];}//排序int j 0;for (i 0; i range; i){while (count[i]--){a[j] i min;}}free(count);count NULL;
}
这里需要为大家强调几点计数排序只适用于整数适合范围集中的数据但是计数排序在特定情况下的效率是很高的甚至比堆排还要快所以具有实践意义我们可以在日常中使用它来进行排序。 9. 各类排序算法分析
这里主要就是来总结一下各类排序的时间复杂度、空间复杂度、稳定性等因素首先大家需要明确一下稳定性的一个概念相同的值相对位置不变。满足这个要求才可以算得上稳定。 10.总结
本篇博客为大家介绍了各种排序算法其中有一些算法的实践意义不大有些是可以在实践中进行运用的大家需要理解每一种排序的思路并且掌握对应的代码了解每种排序的特点排序这块儿内容还是比较重要的后面我们在面试中排序是一个常考的点所以大家需要重点掌握最后希望本篇博客可以为大家带来帮助感谢阅读
