排序算法与时间复杂度

不知诸位有没有在面试过程中 “ 遭遇 ” 灵魂提问： “ 简述下快排 ” 、 “ 写段代码吧，嗯，就冒泡算法吧 ” 、 “ 你知道哪几种排序算法、简单描述你最熟悉的一种 ” 、 “ 选择排序的时间复杂度是？ ” 诸如此类，排序算法在面试中出现的概率高的令人发指。也有不少小伙伴吐槽，真正工作中谁会琢磨这个，工作今年也没用到过自己写排序算法啊 … 好吧，跑的有点远了。排序算法耳熟能详，搞懂排序算法的实现是必须的，除非视金钱如粪土，不 care 面试结果。另一方面，排序算法孰优孰劣？就像王婆卖瓜，她自卖自夸也得有道理不是？你说瓜好瓜就好么，为啥好勒？水分足、甜度大、自然熟，摆出这些指标自然证明瓜好。那么排序算法哪家强？程序运行时考虑性能最关注啥？非 CPU 和 Memory 莫属。那么顺理成章的，算法优劣要看的便是时间复杂度 (cpu) 和空间复杂度 (memory) 咯。

二、 时间复杂度的概 念

时间复杂度准确的说是渐进时间复杂度，表示程序运行时间随着问题复杂度增加而变化的规律 。 显然，一个问题的计算时间与问题的大小有关。一方面，对 100 个数字做排序和对 10000 个数字做排序复杂度必然不同；另一方面，如果以选择排序和冒泡排序分别对 100 个和 10000 个数字做排序用以评判两算法的优劣也太不公平了。渐进时间复杂度，问题的输入大小 (n) 作为变量，随着 n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述； f(n) 的边界可以用数学上的大 O 来限制。

提个问题，把 100 张洗乱的牌排序和把 200 张的牌排序需要的耗时差别是多少， 1 倍、 2 倍、 4 倍还是 8 倍？ 首先确定咋排序，就以选择排序为例吧。选择排序简单直观稳定性好，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 代码奉上：

/*


选择排序1


*/


public static int[] selectSort(int[] numbers){


for(int i=0;i<numbers.length-1;i++){//执行n-1次


int minIndex = i;


for(int j=i+1;j<numbers.length;j++){//执行n-1 + n-2 + …+1次


if(numbers[j] <numbers[minIndex]){


minIndex = j;


}


}


int temp = numbers[minIndex];


numbers[minIndex] = numbers[i];


numbers[i] = temp;


System.out.println(Arrays.toString(numbers));


}


return numbers;


}

如上代码所示，两层循环，第一层为 n-1 次，每次进行当前最小数据位置交换；第二次为 n-1+n-2+n-3+….+1 次，用于遍历查找当前最小元素。可以将最小数据位置交换和遍历查找当前最小元素作为两个平行的操作，平行操作的次数可以按加法计算总次数。因而，排序需执行次数为 n-1+ （ n²-n)/2 = （ n² + n – 2 ） /2 。另外，当 N 趋近于无穷大时，常数比值不会影响数量级。时间复杂度的计算关键看函数的变量部分，而不关注常数因子，可以记为 O(n² + n-2);

如上图，可见 n² + n – 2 中随着 N 趋近于无穷大，增长最快的项为 n² 。 我们记选择排序的时间复杂度为 O(n²). 显然，根据时间复杂度，用 O(n²) 来计算上述洗牌问题， 200² ／ 100²=4 ，答案为 4 倍。 有兴趣的不妨看下下面的实现玩玩找茬，找找问题，加深一下对选择排序算法的认识。

/*


选择排序-error


*/


public static int[] selectSort(int[] numbers){


for(int i=0;i<numbers.length-1;i++){//执行n-1次


for(intj=i+1;j<numbers.length;j++){//执行n-1+n-2+…+1次


if(numbers[j] < numbers[i]){


int temp = numbers[i];


numbers[i] = numbers[j];


numbers[j] = temp;


}


}


System.out.println(Arrays.toString(numbers));


}


return numbers;


}

三 空 间 复 杂 度的概念

空间复杂度是度量算法所需存储空间的大小。如上的选择排序，只需要一组固定的变量用于存储，变量的数量与数据输入规模 n 无关，所以其空间复杂度为 O(1). 没有对比就没有伤害，我们看下快速排序的空间复杂度。 快速排序是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 代码奉上

/*


快速排序


*/


public static void quickSort(int[] arr,int low,int high){


int i,j,temp,t;


if(low>high){


return;


}


i=low;


j=high;


//基准位


temp = arr[low];





while (i<j) {


//先看右边，依次往左递减


while (temp<=arr[j]&&i<j){


j–;


}


//再看左边，依次往右递增


while(temp>=arr[i]&&i<j) {


i++;


}


//如果满足条件则交换


if (i<j) {


t = arr[j];


arr[j] = arr[i];


arr[i] = t;


}





}


//最后将基准为与i和j相等位置的数字交换


arr[low] = arr[i];


arr[i] = temp;


//递归调用左半数组


quickSort(arr, low, j-1);


//递归调用右半数组


quickSort(arr, j+1, high);


}

单纯看一轮快排的执行，其空间复杂度同样为 O(1) 然而，快排使用的是递归，平均递归次数是 log(n) ，鉴于递归需要的栈空间，其平均空间复杂度即为 O(log(n)) 。快排也称为优化版的冒泡算法，纳尼，冒泡算法烦请跳转 4.2 。

四 排序算法解析

4.1 选择排 序

见时间复杂度章节。

4.2 冒泡排序

冒泡排序是一种最简单常见的排序算法之一了。有同事曾说他记忆最深的便是冒泡，因为冒泡是他学习 java 时除 helloworld 之外所写的第一段程序。冒泡排序的实现即重复地走访排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来（ a1 与 a2 比较，若 a1>a2, 交换；然后 a2 与 a3 比较，以此类推）。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “ 浮 ” 到数列的顶端。 代码：

/*


冒泡排序


*/


public static void bubbleSort(int[] arr) {


if (arr.length <= 1) return;





for (int i = 0; i < arr.length; ++i) {


boolean flag = false;


for (int j = 0; j <arr.length-1-i; ++j) { //冒泡是把每轮循环中较大的数飘到后面，此处为arr.length-1-i


if (arr[j] > arr[j + 1]){ //即这两个相邻的数是逆序的，交换


int temp = arr[j];


arr[j] = arr[j + 1];


arr[j + 1] = temp;


flag = true;


}


}


if (!flag) break;//根据标志位，若一次循环没有需要交换的对象即排序完成


}


}

冒泡排序的平均时间复杂度为 O(n²) ，空间复杂度为 O(1) 。 快速排序实际是冒泡算法基于分治法原理的优化版，快速排序的平均时间复杂度为 O(nlog(n)) ，最差时间复杂度是退化为等同冒泡排序的 O(n²) 引申一下分治法： 所谓分治法即分而治之，将敌人分割成块各个击破之。对于求解问题，将问题分解成若干相似但更小的子问题，反复进行分解操作，直至问题变得易于求解，而后将各子问题的解合并在一起并得到原始问题的解。快速排序便是如此，将代排序的数据一分为二得到两个带排序的子集，依次递归子集排序。

4.3 快速排序

见空间复杂度章节。

4.4 希 尔 排序

希尔排序也称为缩小增量排序，是简单插入排序的优化版。它是把记录按照下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，排序完成。平均时间复杂度为 O(nlog(n)) ，空间复杂度为 O(1)

private void shellSort(int[] a){


int n=a.length;


int gap=n/2;


while(gap>=1){


for(int i=gap;i<a.length;i++){


int j=0;


int temp = a[i];


for(j=i-gap;j>=0 &&temp<a[j];j=j-gap){


a[j+gap] = a[j];


}


a[j+gap] = temp;


}


printResult(a,a.length);


gap = gap/2;


}


}

五 关于复 杂 度的思考

大多数童鞋在日常工作中很少会考虑到时间复杂度，甚至感觉复杂度对工作没有意义。了解复杂度的概念当然不应该仅仅为了应付面试。平时工作的时候，多思考多关注，复杂度会对我们的处理问题思路和解决性能问题的能力给予很大的帮助。 比如，在工作中需要使用集合类的时候，你会不会考虑该用 ArrayList 还是 LinkedList ？如果考虑，你会拿什么作为选择的依据呢？大家都会说，链表适合插入、删除较多的场景，数组适合查找操作较多的场景。对你而言，这结论的依据是什么呢？归根结底还是时间复杂度所决定的。 对于查找： 数组是用一组连续的内存空间来存储一组具有相同类型数据的一种线性表结构。因而需要随机按下标查找数组中的某个元素时，以公式：第 i 个元素地址 = 首地址 + i * 每个元素的大小，即可获得元素地址。时间复杂度为 O(1) ； 对于链表，其数据并非连续存储，而是在非连续内存块由指针串联。当要随机查找某个元素，并没有像数组一样的计算公式可以直接获取地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。其时间复杂度为 O(n). 因为随机查找的场景更适合使用数组。 对于插入、删除： 因为数组是连续的内存空间，假设要在长度为 n 的数组中第 i 个位置插入元素，我们需要将第 k ～ n 的元素都顺序地往后挪一位。最好时间复杂度为插入数组末尾不需要移动元素时，为 O(1) ；最坏时间复杂度为插入数组开头需要全部元素移动，为 O(n); 平均情况时间复杂度为 (1+2+…n)/n=O(n). 删除元素同理，为了保证数据连续性，为平均时间复杂度为 O(n). 而链表，插入或者删除一个数据，并不需要为了保持内存的连续性而移动数据，只需要改变指标即可，如下图描述插入 x 元素。时间复杂度为 O(1). 删除同理。