0 对比
In-place:占用常数内存,不占用额外内存
Out-place:占用额外内存
稳定性:排序后 2 个相等键值的顺序和排序之前它们的顺序相同
本文所有排序代码都是以从小到大排序来举例。
1 冒泡排序
原理:比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
第一轮冒泡后,数组的最后一个数字是最大的,第二轮确定出第二大的。每一轮冒泡结束,都会在数组的尾部确定下来一个数字,这个数字在以后的冒泡中是无需再进行访问的。
实现:一共需要进行len-1
轮冒泡,所以外层循环次数是len-1
;内层循环枚举未排好的数字,如果当前数字大于右边的数字,则进行交换。
时间复杂度O(n*n)
上面的代码是从左到右冒泡,每次确定一个最大的。还可以从右到左冒泡,每次确定一个最小的,代码如下。
2 选择排序
原理:每次遍历一遍数组,寻找一个最小(或最大)的数字,然后将它和目标位置交换。
实现:一共需要遍历n-1
次,所以外层循环次数为n-1
;内层循环遍历没有排好的数字,找出最小(或最大)值;找到最值后将它和目标位置交换。
时间复杂度O(n*n)
上面的代码是每次寻找最大值,放在数组的尾部。还可以每次寻找最小值,放在数组的头部,代码如下。
3 插入排序
原理:从下标1开始遍历x,x左边是有序的。每次向有序数列中插入一个数字x,在x左边从右向左遍历,如果arr[j]
大于x
,将arr[j]
向右移动一个位置,直到找出最左边的大于x
的位置,将x
放到这个位置即可。
时间复杂度O(n*n)
也可以从右向左枚举x
,使得右边是有序的,代码如下。
4 希尔排序
待更新。
5 归并排序
原理:将数组分为左右两个小数组,对小数组进行归并排序,然后合并两个数组。
使用递归实现。递归的出口是数组元素等于1或2.
时间复杂度O(n*log(n))
6 快速排序
原理:找一个目标值x,一般是第一个或最后一个数。使用两个指针从两头到中间进行遍历,把小于x的和大于x的进行交换。当两个指针相遇的时候左边都小于x,右边都大于x。最后把x插入到中间(就是找个数交换一下位置),然后分别对两边进行快速排序。
时间复杂度`O(n*log(n))
对快排进行改进,直接每次寻找中间那个数作为target
,不必考虑target
的位置是否发生变化,最后target
会被移动到中间。
代码如下:
7 堆排序
待更新。
8 计数排序
原理:开一个很大的计数数组,标记每个数字出现的次数。之后遍历计数数组即可。
9 桶排序
待更新。
10 基数排序
待更新。