今天开的专题是排序,排序是学过好多遍的,但是学了忘,忘了学,汗。
一种非常典型的算法,简单地说就是一组数组,通过某种操作能让它变得有序,升序or降序。
下面总地说说各种排序算法的思想以及代码,当然,它们是最基础的,也还有优化空间。
默认对int[] arr
进行升序排序。
选择排序
它的思想非常简单,就是选择一个元素,把它放在它该在的地方。
比如索引为0的元素,那它就是最小的嘛,然后剩下的元素中找到最小的元素,放到第0个位置上,依此类推。
从前往后缩小排序的范围,因为前面的已经排好的嘛,一个一个地往后。
注意噢,它是交换次数最小的一种排序方式,不过也有它的缺点,就是运行时间和输入无关,即使它已经有序了,也和完全无序的元素的运行时间一样……
时间复杂度:$O(N^2)$
空间复杂度:$O(1)$
public static void main(String[] args) {
int[] arr = new int[]{
0, 6, 4, 3, 7, 5, 2, 1, 9, 8
};
for(int i = 0;i < arr.length;i++){
// 选择一个最小的
int min = i;
// 从后面的数中找最小的
for(int j = i + 1;j < arr.length;j++){
if (arr[j] < arr[min]){
min = j;
}
}
// 把最小的放到它该在的地方
exch(arr, min, i);
}
Arrays.stream(arr).forEach(System.out::print);
}
插入排序
这个排序我马上就想起打牌时整理扑克的场景 :我总会先把一边排好,比如把最大的2、1找出来放到左边,然后再把KQJ找出来,放到2、1的后面,依此类推。
正式点的话就是:当前索引的左边都是有序的,当遇到一个新的元素时,把它“插入”到有序元素的正确的位置。
它可以很快地把一个大致有序的数据进行排序。
时间复杂度:$O(N^2)$
空间复杂度:$O(1)$
public static void main(String[] args) {
int[] arr = new int[]{
0, 6, 4, 3, 7, 5, 2, 1, 9, 8
};
for(int i = 1;i < arr.length;i++){
// 保持i的左边是有序的
for(int j = i ;j > 0 && arr[j] < arr[j - 1];j--){
// 与前一个元素交换,直到它在合适的位置
exch(arr, j, j - 1);
}
}
Arrays.stream(arr).forEach(System.out::print);
}
当然,这段代码也是可以优化的,可以看到它交换太多了,其实不应该,可以往后找到合适的位置,最后再交换一次即可。
public static void main(String[] args) {
int[] arr = new int[]{
0, 6, 4, 3, 7, 5, 2, 1, 9, 8
};
for(int i = 1 ;i < arr.length;i++){
// 把当前元素value插入有序区[0, i)的恰当位置
int value = arr[i];
int j = i;
// 与value相比!要是比它大,就放到后面
while (j > 0 && arr[j - 1] > value){
arr[j] = arr[j - 1];
j--;
}
// 插入value
arr[j] = value;
}
Arrays.stream(arr).forEach(System.out::print);
}
希尔排序
非常神奇的一个算法,是插入排序的一种优化:插入排序找恰当位置的时候,不是一步一步地移动吗?这里就绝绝子,它一次移动h步($h >= 1$)。每次排序后,让h逐渐变小,直到为1,即回到原始的插入排序,但此时元素已经“大致有序”,排序速度会很快。
其实它就是h把大数组分为了若干个小数组进行插入排序,兼顾了规模与有序性,因为插入排序非常适合短数组和部分有序的数组。渐渐地把小数组排序完,此时留下的是部分有序的大数组,这里处理就很快了。
《算法》这本书也提到,除了对于很大的N,它们(其它更高级的排序算法)可能只会比希尔排序快两倍(可能还不到),并且更复杂,我也很赞同,因为它确实简单。
好像还没有对这个排序的性能作出非常透彻的理解,下面的复杂度也是按主流所说。
平均时间复杂度:$O(NlogN)$ ?最坏情况下也达不到平方级别,最多是与N^1.5成正比。
空间复杂度:$O(1)$
public static void main(String[] args) {
int[] arr = new int[]{
0, 6, 4, 3, 7, 5, 2, 1, 9, 8
};
int h = 1;
int n = arr.length;
// 设定步长为3n+1
while (h < n / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
// 步长为h的插入排序。
for (int i = h; i < n; i += h){
int value = arr[i];
int j = i;
while(j > 0 && arr[j - h] > value){
arr[j] = arr[j - h];
j -= h;
}
arr[j] = value;
}
h /= 3;
}
Arrays.stream(arr).forEach(System.out::print);
}
看,果然是没啥区别吧,但是它却比插入排序快多了噢~
优化的话,还可以对步长h进行优化。
归并排序
原地归并
要想完成归并排序,先作以下一个小操作
把有序子数组arr[lo, mid]和arr[mid + 1, hi]归并成arr[lo, hi]。
这里采用临时数组的方法,把元素先放到临时数组中,然后再归并回原数组。
// 临时数组
private static int[] aux = new int[10];
public static void merge(int[] arr, int lo, int mid, int hi){
int i = lo, j = mid + 1;
// 复制到临时数组中保存。
for(int k = lo;k <= hi;k++){
aux[k] = arr[k];
}
for(int k = lo;k <= hi;k++){
if (i > mid){
// 左边排完了
arr[k] = aux[j++];
}else if(j > hi){
// 右边排完了
arr[k] = aux[i++];
}else if(aux[i] < aux[j]){
// 左边比右边小,放左边
arr[k] = aux[i++];
}else{
arr[k] = aux[j++];
}
}
}
自顶向下
有了上面的基础归并后,可以挖掘两个不同的归并方式。现在这种是自顶向下的,怎么说呢,它就是从上开始向下遍历,可以看看它的遍历树就知道了。
这也是我们遇到的最平常、最简单的一种写法,简单地说就是使用递归,先排左边,再排右边,然后再合并两个有序数组,听起来非常简单呢(确实是这样的!)
private static void topToBottomSort(int[] arr, int lo, int hi) {
if (hi <= lo) {
return;
}
// 找中间
int mid = lo + (hi - lo) / 2;
// 排左边
topToBottomSort(arr, lo, mid);
// 排右边
topToBottomSort(arr, mid + 1, hi);
// 合并左右
merge(arr, lo, mid, hi);
}
它排左边的时候,是一路往下遍历,直到lo > mid的时候(其实也就是前两个元素),就合并它,然后再接着第三、第四个元素,再合并它,然后再把前四个元素排好序,依此类推。。。这就是向下的过程(可以画一画它的过程,这里是说给自己看的,如果有访客来,这肯定是看不懂的【x)
自底向下
还有一种是从底下开始向上遍历的,就是我先在底下排好,然后再向上合并。
比如,我一开始两个两个地排序、归并,然后再四个四个、八个八个。。。
private static void bottomToTopSort(int[] arr) {
int n = arr.length;
// size指每个要排序的小区间的大小,两个为一组
for (int size = 1; size < n; size = size + size) {
for (int lo = 0; lo < n - size; lo += size + size) {
// [lo, lo + size - 1]就是对应上面的“排左边”
// [lo + size - 1, Math.min(lo + size + size - 1, n - 1)] 就是排右边
// 这个min,其实是怕最后越界了,比如当我八个八个地排的时候,“右边”不够8个了,这时最大就是n-1了
merge(arr, lo, lo + size - 1, Math.min(lo + size + size - 1, n - 1));
}
}
}
快速排序
顾名思义,它就是很快了!
它也是和归并一样,有一种分治的思想,具体做法是:把一个数组切分现两部分,以某个元素为轴,左部分比该元素小,右部分比该元素大。然后对左边进行排序,对右边进行排序,这样就做好了。
private static void quicksort(int[] arr, int lo, int hi) {
// 绝了,这里居然写反了
if (hi <= lo) {
return;
}
int j = partition(arr, lo, hi);
quicksort(arr, lo, j);
quicksort(arr, j + 1, hi);
}
把上面的话转成代码就是这样的……
切分算法是最重要的,下面的切分都是以第一个元素为轴。
private static int partition(int[] arr, int lo, int hi) {
int pivot = arr[lo];
while (lo < hi) {
// 从后往前找,比枢轴大的放在右边不动
while (lo < hi && pivot <= arr[hi]) {
hi--;
}
// 找到一个小的,放到最前面(枢轴已经保存,放心覆盖)
arr[lo] = arr[hi];
// 从前往后找,比枢轴小的在左边不动
while (lo < hi && arr[lo] <= pivot) {
lo++;
}
// 直到遇到一个大的,把它也覆盖到刚刚枢轴右边
arr[hi] = arr[lo];
}
// 最后把枢轴放到正确的位置上,也就是lo == hi的地方
arr[lo] = pivot;
return lo;
}
计数排序
加一个,这个排序非常特别。
是一种特殊的桶排序,每个桶中的元素都是一样的,在一个桶中,即都是有序的元素。
它的思想是这样的,比如对一个范围是1-n的数组,我就创建一个1-n的桶,然后计数比较,每个桶中元素会是多少。
然后再根据这个计数,生成一个包含前面元素的和的数组,这个数组的值就是对应元素的下标。
从后往前遍历原数组,然后从计数数组中找到对应的下标,把它放进去,依此类推,即完成排序。
(说得有点奇怪。。之后再补充吧)
public static void countingSort(int[] arr) {
int n = arr.length;
if (n <= 1) {
return;
}
// 5
int max = Arrays.stream(arr).max().getAsInt();
int[] count = new int[max + 1];
// 2 0 2 3 0 1
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// 2 2 4 7 7 8
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
int[] result = new int[n];
// 2, 5, 3, 0, 2, 3, 0, 3
for (int i = n - 1; i >= 0; i--) {
// 比如第一个元素3,从count中找,它是第7个
int index = count[arr[i]] - 1;
// 把元素放到下标为6的位置
result[index] = arr[i];
// 计数减一
count[arr[i]]--;
}
// 复制回原数组。
for (int i = 0; i < n; i++) {
arr[i] = result[i];
}
}
真题演练
来做一下leetcode上与排序有关的题目吧。
215. 数组中的第K个最大元素
给定整数数组 nums
和整数 k
,请返回数组中第 **k**
个最大的元素。
请注意,你需要找的是数组排序后的第 k
个最大的元素,而不是第 k
个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
提示:
1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
class Solution {
public int findKthLargest(int[] nums, int k) {
int lo = 0, hi = nums.length - 1;
int target = nums.length - k;
while(lo < hi){
// 刚好划分到第nums.length - k个(即第k大)
int mid = partition(nums, lo, hi);
if(mid == target){
return nums[mid];
}else if(mid > target){
hi = mid - 1;
}else{
lo = mid + 1;
}
}
return nums[lo];
}
private int partition(int[] arr, int lo, int hi){
int pivot = arr[lo];
while(lo < hi){
while(lo < hi && pivot <= arr[hi]){
hi--;
}
arr[lo] = arr[hi];
while(lo < hi && arr[lo] <= pivot){
lo++;
}
arr[hi] = arr[lo];
}
arr[lo] = pivot;
return lo;
}
}