笔试中各种排序算法的复杂度
“噼里啪啦喵”通过精心收集，向本站投稿了6篇笔试中各种排序算法的复杂度，以下是小编帮大家整理后的笔试中各种排序算法的复杂度，仅供参考，欢迎大家阅读。
篇1：笔试中各种排序算法的复杂度
，
从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。
(1) 如果不多于1个数据，直接返回。
(2) 一般选择序列最左边的值作为支点数据。
(3) 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。
(4) 对两边利用递归排序数列。
快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。
2 归并排序(MergeSort)
归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。
3 堆排序(HeapSort)
堆排序适合于数据量非常大的场合(百万数据)。
堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的'时候，可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
4 Shell排序(ShellSort)
Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。
Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。
5 插入排序(InsertSort)
插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。
6 冒泡排序(BubbleSort)
冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较大的数据下沉，较小的数据上升。它是O(n^2)的算法。
7 交换排序(ExchangeSort)和选择排序(SelectSort)
这两种排序方法都是交换方法的排序算法，效率都是 O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段，在实际中使用较少。
8 基数排序(RadixSort)
基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法，但是它只能用于整数的排序，如果我们要把同样的办法运用到浮点数上，我们必须了解浮点数的存储格式，并通过特殊的方式将浮点数映射到整数上，然后再映射回去，这是非常麻烦的事情，因此，它的使用同样也不多。而且，最重要的是，这样算法也需要较多的存储空间。
相关笔试题目推荐：
运营维护工程师笔试题 房地产销售代理人员笔试题 申银万国校园招聘笔试题目
篇2：各种排序方法复杂度总结
各种排序方法复杂度总结
一、冒泡排序
主要思路是：
通过交换相邻的两个数变成小数在前大数在后，这样每次遍历后，最大的数就“沉”到最后面了。重复N次即可以使数组有序。
代码实现
void bubble_sort（int arr[]， int len）
{
for （int i = 0; i < len — 1; i++）
{
for （int j = len — 1; j >= i; j——）
{
if （arr[j] < arr[j — 1]）
{
int temp = arr[j];
arr[j] = arr[j — 1];
arr[j — 1] = temp;
}
}
}
}
冒泡排序改进1：
在某次遍历中，如果没有数据交换，说明整个数组已经有序，因此通过设置标志位来记录此次遍历有无数据交换就可以判断是否要继续循环。
冒泡排序改进2：
记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序。因此设置标志位记录每次遍历中最后发生数据交换的位置可以确定下次循环的范围。
二、直接插入排序
主要思路是：
每次将一个待排序的数组元素，插入到前面已排序的序列中这个元素应该在的位置，直到全部数据插入完成。类似扑克牌洗牌过程。
代码实现
void _sort（int arr[]， int len）
{
for （int i = 1; i < len; i ++）
{
int j = i — 1;
int k = arr[i];
while （j >—1 && k < arr[j] ）
{
arr[j + 1] = arr[j];
j ——;
}
arr[j + 1] = k;
}
}
三、直接选择排序
主要思路是：
数组分成有序区和无序区，初始时整个数组都是无序区，每次遍历都从无序区选择一个最小的元素直接放在有序区最后，直到排序完成。
代码实现
void select_sort（int arr[]， int len）
{
for （int i = 0; i < len; i++）
{
int index = i;
for （int j = i + 1; j < len; j++）
{
if （arr[j] < arr[index]）
index = j;
}
if （index ！= i）
{
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
}
四、快速排序
主要思路是：
“挖坑填数 + 分治法”，首先令i = L;j = R；将a[i]挖出形成打一个坑，称a[i]为基准数。然后j——从后向前找到一个比基准数小的数，挖出来填到a[i]的坑中，这样a[j]就形成了一个新的坑，再i++从前向后找到一个比基准数大的数填到a[j]坑中。重复进行这种挖坑填数，直到i = j。这时a[i]形成了一个新的坑，将基数填到a[i]坑中，这样i之前的数都比基准数小，i之后的数都比基准数大。因此将数组分成两部分再分别重复上述步骤就完成了排序。
代码实现
void quick_sort（int arr[]， int left， int right）
{
if （left < right）
{
int i = left， j = right， target = arr[left];
while （i < j）
{
while （i < j && arr[j] >target）
j——;
if （i < j）
arr[i++] = arr[j];
while （i < j && arr[i] < target）
i++;
if （i < j）
arr[j] = arr[i];
}
arr[i] = target;
quick_sort（arr， left， i — 1）;
quick_sort（arr， i + 1， right）;
}
}
五、希尔排序
主要思路是：
先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的'元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。由于希尔排序是对相隔若干距离的数据进行直接插入排序，因此可以形象的称希尔排序为“跳着插”。
六、归并排序
主要思路是：
当一个数组左边有序，右边也有序，那合并这两个有序数组就完成了排序。如何让左右两边有序了？用递归！这样递归下去，合并上来就是归并排序。
代码实现
void merge（int arr[]， int temp_arr[]， int start_index， int mid_index， int end_index）
{
int i = start_index， j = mid_index + 1;
int k = 0;
while （i < mid_index + 1 && j < end_index + 1）
{
if （arr[i] >arr[j]）
temp_arr[k++] = arr[j++];
else
temp_arr[k++] = arr[i++];
}
while （i < mid_index + 1）
{
temp_arr[k++] = arr[i++];
}
while （j < end_index + 1）
temp_arr[k++] = arr[j++];
for （i = 0， j = start_index; j < end_index + 1; i ++， j ++）
arr[j] = temp_arr[i];
}
void merge_sort（int arr[]， int temp_arr[]， int start_index， int end_index）
{
if （start_index < end_index）
{
int mid_index = （start_index + end_index） / 2;
merge_sort（arr， temp_arr， start_index， mid_index）;
merge_sort（arr， temp_arr， mid_index + 1， end_index）;
merge（arr， temp_arr， start_index， mid_index， end_index）;
}
}
七、堆排序
堆排序的难点就在于堆的的插入和删除。
堆的插入就是——每次插入都是将新数据放在数组最后，而从这个新数据的父结点到根结点必定是一个有序的数列，因此只要将这个新数据插入到这个有序数列中即可。
堆的删除就是——堆的删除就是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点开始将一个数据在有序数列中进行“下沉”。
因此，堆的插入和删除非常类似直接插入排序，只不是在二叉树上进行插入过程。所以可以将堆排序形容为“树上插”。
篇3：排序算法（一）
进入找工作倒计时状态了，计划好好复习一下数据结构和相关算法，预计用两天时间把见过的排序算法整理下，首先看一下时间复杂度为O（n2）的算法，
首先参考大话数据结构定义一个链表类：
#include 冒泡排序法： /** *冒泡排序即相邻的两者相互比较，根据需求把较大的或较小的前移或后移 *记住，两两相邻的比较是冒泡排序的特点之一 */void BubbleSort1(SqList* list){//每次遍历时把较大者后移 int length=list->length; while(length>0) { for(int i=0;i 选择排序法： /** *选取排序即每次在未排序队列当中选取一个最小值，然后与第i个值进行交换，直至i为length为止； *当然，也可以选取最大值把到后面，根据需求而定 */void selectSort(SqList* list){ for (int i = 0; i < list->length; ++i) { int min = list->data[i]; int pos = i; for (int j = i+1; j < list->length; ++j) { if (list->data[j] < min) { min = list->data[j]; pos = j; } } if (pos != i) { swap(list->data[i], list->data[pos]); } }} 简单插入排序法： /** *遍历链表，把每个元素插入到正确位置 */void InsertSort1(SqList *list){ for (int i = 1; i < list->length; ++i) { int j = i - 1; for (; j >=0; j--) { if (list->data[i] >list->data[j]) break; } int tmp = list->data[i]; for (int k = i; k >j+1; --k) { list->data[k] = list->data[k - 1]; } list->data[j + 1] = tmp; }}void InsertSort2(SqList *list){ for (int i = 1; i < list->length; ++i) { if (list->data[i] < list->data[i - 1]) { int tmp = list->data[i]; int j = i-1; for (; j >= 0 && list->data[j] >tmp; --j) {//查找的同时，进行后移操作 list->data[j + 1] = list->data[j]; } list->data[j + 1] = tmp; } }} 希尔排序法（简单插入排序的改进）： /** *希尔排序是插入排序的一种改进，可以理解为把一个数组分成几个小的数组进行插入排序，再合并使原数组基本有序， *希尔排序一个很关键的步骤是增量的选取，合适的增量能够提高排序效率，但不合适的增量可能会导致程序崩溃或结果错误。 *其次，希尔排序也不是一个稳定的排序算法，因为它是跳跃插入排序的。 *希尔排序只是比前面几种O(n2)的效果稍好，并不会优于后面要提到的快速排序等算法。 */void ShellSort(SqList* list){ int increment = list->length; do{ increment = increment / 3 + 1; for (int i = increment + 1; i < list->length; ++i) { if (list->data[i] < list->data[i - increment]) { int tmp = list->data[i]; int j = i - increment; for (; j >= 0 && list->data[j] >tmp; j -= increment) { list->data[j + increment] = list->data[j]; } list->data[j + increment] = tmp; } } } while (increment >1);}
篇4：python实现排序算法
-03-03python局部赋值的规则
-02-02python发布模块的步骤分享
2014-03-03Python 列表(List)操作方法详解
2014-02-02go和python调用其它程序并得到程序输出
2014-04-04python中的实例方法、静态方法、类方法、类变量和实例变量浅析
2014-05-05Python random模块（获取随机数）常用方法和使用例子
-12-12python cookielib 登录人人网的实现代码
-09-09Python httplib，smtplib使用方法
2013-11-11pyramid配置session的方法教程
2014-03-03python实现k均值算法示例(k均值聚类算法)
篇5：python实现排序算法
最近更 新
用python实现的去除win下文本文件头部BOM
Python实现的金山快盘的签到程序
python操作MySQL数据库具体方法
python操作日期和时间的方法
删除目录下相同文件的python代码(逐级优化
python 中的列表解析和生成表达式
Python实例分享：快速查找出被挂马的文件
python列表去重的二种方法
python查找第k小元素代码分享
Python 网络编程说明
热 点 排 行
Python入门教程 超详细1小时学会
python 中文乱码问题深入分析
比较详细Python正则表达式操作指
Python字符串的encode与decode研
Python open读写文件实现脚本
Python enumerate遍历数组示例应
Python 深入理解yield
Python+Django在windows下的开发
python 文件和路径操作函数小结
python 字符串split的用法分享
篇6：选择排序算法总结
这里实现了选择数组里面最小值的代码，读者可以以此类推自己写出选择最大值的算法
/** * 找到最小的元素 * @param array 输入的数组 * @param arraySize 数组大小 * @param minNumber 输出最小值 * @return 最小值在数组里面的位置 */size_t findMin(int array[] , int arraySize , int * minNumber){ if(array == NULL || arraySize <= 0 || minNumber == NULL) return -1; int minPos = -1; int minNumberTemp=INT_MAX; for (int i = 0; i < arraySize; ++i) { if(array[i] < minNumberTemp) {minNumberTemp=array[i];minPos = i; } } *minNumber = minNumberTemp; return minPos;}
运行结果：
input array is :
48 18 97 27 13 85 8 38 95 31
find the min number 8 at pos 7
我们从代码里面可以看出for循环运行n次，每次都要进行一次比较if(array[i] < minNumberTemp)，如果我们标记的最小值大于当前的数组元素，就重新标记当前数组元素为最小值。因为这个代码比较简单，这里不再赘述。
选择算法之选取最大数和最小数
条件改变，现在要选择一个序列里面的最大数和最小数，这里和上面讲述过的选择最大数或者最小数有所不同，上面的要做的只是选择最大值或者最小值，而现在我们要同时选择最大值和最小值。
博主第一次看见这个题目时，和只选择最小数的情形一对比，这不是一样的么，只要在循环里面多加一个最大数的比较不就行了？的确是可以，我们来看一下部分代码实现
【笔试中各种排序算法的复杂度】相关文章：
1.排序算法总结
2.选择排序算法总结
6.句子排序
7.《排序》小班教案
8.中软融鑫笔试题目
10.《算法初级》教案设计
文档为doc格式
