如何分析排序算法

排序算法的执行效率

分析算法的执行效率可以从下面三个方面进行分析：

• 最好、最坏和平均情况时间复杂度

  在分析最好、最坏和平均情况时间复杂度时，还需要给出每种情况对应的原始数据，这样方便进行对比，同时也可以知道排序算法在不同数据下的执行效率；

• 时间复杂度的系数、常数和低阶

  在使用大O表示法计算时间复杂度时通常会忽略系数、常数和低阶，但在比较相同时间复杂度的排序算法是，我们可以通过系数、常数和低阶来比较算法的执行效率；

• 比较次数和移动次数

  排序算法都会涉及到两种操作，一种是大小比较，一种是进行交换，所以在分析算法执行效率时也可以把这两种操作的中心

排序算法的内存消耗

算法的内存消耗主要看空间复杂度，但是排序算法还需要关注是否是原地排序；原地排序就是特指空间复杂度是O(1)的排序算法，也就是在排序过程中开辟内存是常量级的算法；

排序算法的稳定性

稳定性是只针对排序算法的指标，就是两个相同元素在排序前后的位置是否发生变化，保持一致的称为稳定排序，发生变化的就是不稳定排序；

常见的几种排序算法

冒泡排序

冒泡排序原理

冒泡排序的排序过程可以分解为冒泡操作和比较操作，其中一次冒泡操作包含多次比较操作，每次比较操作就是对相邻两个元素进行比较，不满足大小要求就对这两个元素进行交换；这样一次冒泡操作就至少让一个元素确定它所在的位置；如果有n的元素，那么执行n次冒泡操作就可以完成排序；代码如下：

void SortMain::bubbleSort(int array[], int len)
{if(len <= 0){return;}for(int i = 0; i < len; i++)       {	//一次完整的冒泡操作for(int j = 0; j < len - i - 1; j++){//一次比较操作if(array[j] > array[j+1]){int temp = array[j];array[j] = array[j+1];array[j+1] = temp;}}}
}

上面是冒泡排序的最基础的实现，还可以对上面的代码进行优化，就是当一次冒泡操作中没有进行数据交换时，代表当前进行排序的这部分元素已经是有序的了，说明排序已经全部完成了；优化代码如下：

void SortMain::bubbleSort(int array[], int len)
{if(len <= 0){return;}for(int i = 0; i < len; i++)       {	//用来标志本次冒泡操作是否进行了交换bool flag = false;//一次完整的冒泡操作for(int j = 0; j < len - i - 1; j++){//一次比较操作if(array[j] > array[j+1]){int temp = array[j];array[j] = array[j+1];array[j+1] = temp;flag = true;}}//没有交换数据表示排序完成if(flag == false){break;}}
}

冒泡排序算法分析

最好、最坏和平均情况时间复杂度

• 最好情况：当前数组是有序的，那么只要进行一次冒泡操作就可以完成排序，那么最好情况时间复杂度就是O(1);

• 最坏情况：当前数组与排序大小要求是反向有序的，那么则需要len次冒泡操作，每次冒泡操作也都要进行(n-i)次比较操作,所以最坏情况时间复杂度就是O($n^2$);

• 平均情况：由于冒泡排序在不同数组排列情况下有不同的时间复杂度，而数组排列方式总共有$n!$种，使用概率论方法进行计算比较复杂，所以使用有序度和逆序度来进行计算平均情况时间复杂度；
  有序度就是数组中有序元素对的个数；举例数组{8, 3, 5, 2, 1, 9}的有序度为6，有序对如下：
  $(8, 9), (3,5), (3, 9), (5, 9), (2, 9), (1, 9)$
  那么当数组是有序的时候，也就是满有序度，有序度就是$\frac{n(n-1)}{2}$；数组顺序完全相反时，有序度为0；逆序度就是等于满有序度减去有序度；

  那么对于冒泡操作每进行一次交换数组的有序度就加1，而对于一个数组进行冒泡排序时，交换次数一定是固定的；那么对n个元素的数组进行排序，最好情况交换次数是0次，最坏情况是$\frac{n(n-1)}{2}$次，那么取平均值就是$\frac{n(n-1)}{4}$次；而比较操作一定是大于等于交换操作的，并且冒泡排序算法的时间复杂度上限是O($n^2$),所以平均情况时间复杂度就是O($n^2$)；

内存消耗

通过代码可以看出冒泡排序的空间复杂度是O(1),所以冒泡排序也是原地排序；

稳定性

由于冒泡排序的比较操作的是相邻的两个元素，所有相同的元素在比较操作之后的位置是不会发生变化的，所以冒泡排序是稳定排序；

插入排序

插入排序原理

插入排序原理就是将数组分为已排序区间和未排序区间，初始已排序区间只包含一个元素，就是数组的第一个元素，之后从未排序区间每次取出一个元素，和已排序区间的元素进行比较，插入满足大小要求的位置，保证已排序区间一直有序，直到未排序区间元素为空；代码如下：

void insertSort(int[] array, int len)
{if(len <= 0>){return;}for(int i = 1; i < len; i++){int key = array[i];int j = i - 1;while(j >= 0 && array[j] > key){array[j+1] = array[j];j--;}array[j+1] = key;}
}

插入排序算法分析

最好、最坏和平均情况时间复杂度

• 最好情况：最好情况是数组有序，那么每次从未排序区间取出的元素都可以直接插入已排序区间最后的位置，所以需要执行n比较操作就可以完成排序，那么最好情况时间复杂度就是O(n);
• 最坏情况：当前数组与排序大小要求是反向有序的，那么每次从未排序区间取出的元素都要遍历已排序区间插入第0个位置，所以除了需要执行n比较操外，每次比较操作之后还要执行(n-i)次移动操作才可以完成排序，那么最坏情况时间复杂度就是O($n^2$);
• 平均情况：在一个数组中插入一个元素的平均情况时间复杂度是O(n)，而插入排序就是遍历未排序区间的每个元素插入到已排序区间，所以插入排序的平均情况时间复杂度是O($n^2$)；

内存消耗

通过代码可以看出，在插入排序算法中只有常量级的临时变量，所以空间复杂度是O(1)，插入排序也是原地排序；

稳定性

由于在执行插入操作时，会按照原来的顺序对数组元素进行移动，这样插入操作就不会改变原有相同元素的位置，所以插入排序是稳定排序；

选择排序

选择排序原理

选择排序和插入排序做法类似，也是分为已排序区间和未排序区间，不同的地方是选择排序是在未排序区间中找到符合大小要求的元素(最大或最小元素)直接插入到已排序区间，直到未排序区间为空；代码如下：

void selectSort(int[] array, int len)
{if(len <= 0){return;}for(int i = 0; i < len; i++){int min = i;for(int j = i+1; j < len; j++){if(array[min] > array[j]){min = j;}}if(min != i){int temp = array[i];array[i] = array[min];array[min] = temp;}}
}

选择排序算法分析

最好、最坏和平均情况时间复杂度

• 最好情况：最好情况是数组有序，那么每次从未排序区间取出最小元素还是需要遍历未排序区间，所以最好情况时间复杂度是O($n^2$);
• 最坏情况：最坏情况和最好情况相同，也是O($n^2$);
• 平均情况：由于最坏情况和最好情况都是O($n^2$)， 所以平均情况时间复杂度也是O($n^2$);

内存消耗

通过代码可以看出，在选择排序排序算法中只有常量级的临时变量，所以空间复杂度是O(1)，选择排序也是原地排序；

稳定性

由于插入已排序区间的元素是在未排序区间中找到的最小元素，当对这个元素执行交换操作时有可能改变原有相同元素的位置，所以选择排序是稳定排序；

归并排序

归并排序原理

归并排序的核心思想就是将一个数组分成两部分，分别进行排序，最后合到一起就完成了排序；这里用到的就是分治思想，就是把一个大问题分成若干个小问题，小问题解决了，大问题也就解决了，而分治一般都用递归来实现；代码如下：

void SortMain::mergeSortFunc(int* array, int start, int end)
{if(start >= end){return;}int minIndex = start + (end - start)/2;mergeSortFunc(array, start, minIndex);mergeSortFunc(array, minIndex+1, end);//mergemergeFunc(array, start, end, minIndex);
}void SortMain::mergeFunc(int* array, int start, int end, int minIndex)
{int tempArray[end-start+1];int tempIndex = 0;int p = start;int q = minIndex+1;while (p <= minIndex && end >= q) {if(array[p] < array[q])tempArray[tempIndex++] = array[p++];elsetempArray[tempIndex++] = array[q++];}int x = p;int y = minIndex;if(q <= end){x = q;y = end;}for(int i = x; i <= y; i++)tempArray[tempIndex++] = array[i];for(int i = 0; i <= end - start; i++)array[start+i] = tempArray[i];
}

归并排序算法分析

最好、最坏和平均情况时间复杂度

从上面的代码可以看出，不管是最好情况、还是最坏情况，归并排序的时间复杂度不会受到数组顺序的影响，所以我们只要分析代码执行复杂度，不需要考虑数组的情况；

按照归并排序的原理，我们要计算大问题的时间复杂度，那我们只要计算出解决小问题的时间复杂度以及将小问题合并的时间复杂度就可以了；
假设对一个大小为n的数组进行排序需要时间T(n),那么将这个数组拆分成两个数组进行排序需要的时间就是$2*T(\frac{n}{2})$，如果再对这两个数组继续拆分，我们可以得到下面这个公式：
$第一次：2*T(\frac{n}{2})$
$第二次：4*T(\frac{n}{4})$
$第三次：8*T(\frac{n}{8})$
$......$
$第k次：2^k*T(\frac{n}{2^k})$
通过合并代码，可以看出合并代码的时间复杂度是n，也就是说拆分k次，就需要$k*n$的时间来合并；
那么我们就可以得到计算归并排序执行时间的公式：
$T(n) = 2^k*T(\frac{n}{2^k}) + k*n$
由于归并排序是分解到无法再拆分为止，所以最终应该是n个数组，所以得到$T(\frac{n}{2^k})=T(1)$，我们可以计算出$k=\log_2n$，带入上面的公式得到：$T(n) = n*T(1) + \log_2n*n$，这里T(1)是常量级，所以用大O表示法得到归并排序的时间复杂度是O(n*logn);

内存消耗

通过代码可以看出，在执行合并操作时，每次都会申请一个长度为n的数组，所以归并排序的空间复杂度就是O(n)，那么归并排序也就不是原地排序；

稳定性

归并排序在合并操作时；是按照两个子数组的顺序进行比较，再放入临时变量中，那么数组中相同大小的元素的位置是不会发生变化的，所以归并排序是稳定排序；

快速排序

快速排序原理

快速排序的核心思想也是分治思想，但是和归并排序不同；它是先选择数组中任意一个值作为中间值将数组分为两部分，之后将数组中比中间小的放在一边，大的放在另外一边，这样就将数组分为两个部分，再对这两个子数组进行同样的操作，直到子数组中只有一个值，这样就完成了排序；代码如下：

void SortMain::quickSort(int array[], int len)
{if(len <= 0){return;}quickSortFunc(array, 0, len-1);
}void SortMain::quickSortFunc(int array[], int start, int end)
{if(start >= end){return;}int midIndex = end;int p = start;for(int i = start; i < end; i++){if(array[i] < array[midIndex]){if(i != p){int temp = array[i];array[i] = array[p];array[p] = temp;}p++;}}if(p != midIndex){int temp = array[p];array[p] = array[midIndex];array[midIndex] = temp;}quickSortFunc(array, 0, p-1);quickSortFunc(array, p+1, end);
}

快速排序算法分析

最好、最坏和平均情况时间复杂度

由于快速排序和归并排序都是使用分治思想，并且都用递归实现，所以计算时间复杂度的方法和归并排序是一样的，同样最终计算出平均情况时间复杂度是O(nlogn);但是快速排序不一样的地方是有最坏情况下的时间复杂度，当数组是有序的情况下，根据代码看在进行比较操作的时候还是会对当前要操作的数组分区的所有的元素进行遍历，这样时间复杂度就退化到O($n^2$);

内存消耗

通过代码可以看出，快速排序的过程中只使用到了常量级的临时变量，所以快速排序的空间复杂度是O(1)，快速排序是原地排序。（这里有人认为由于使用递归，所以栈里会有临时变量没有释放，所以空间复杂度是O(logn))）

稳定性

通过分析代码可以看出在进行快速排序时，当进行比较操作时如果相同的元素都比中间值小的情况下，通过交换会使元素的顺序发生变化，所以快速排序是不稳定排序。