排序算法(一)

排序算法(一)

学排序算法不知道有多少次了,都是过两天就忘记,我觉得我真的学不好算法(太笨了)。这一次花点时间把几个经典的排序算法好好学习一下吧,也不要求非常明白原理...至少要知道好吧...

冒泡排序

这个排序似乎每次都是放在第一个讲,我个人觉得它不是最简单的也不是最常用的。道是最先发明的?所以才作为入门排序算法的第一个吗?哎...这个算法着实不怎么样,很慢,也没有多少的优化空间。

public void sort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        // 假设比较前数组已经有序
        boolean sorted = true;	

        for (int j = 0; j < array.length - i - 1; j++) {
            // 如果前一个元素大于后一个元素则交换(升序)
            if (array[j] > array[j + 1]) {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;

                // 如有交换则说明数组仍然无序
                sorted = false;
            }
        }

        // 如果数组已经有序则结束排序
        if (sorted) break;
    }
}

可以认为这个排序算法正常情况下是稳定的,这里说的稳定是相同的元素值排序前后相对位置不变。然后其时间复杂度为O(n2),最好的情况就是数组本来就有序为O(n)....排序两万个乱序数字大概为如下情况:

[BubbleSort]
	Time: 2.56s
	Swap: 100313055
	Compare: 199975635

选择排序

我觉得这个排序算法才是最简单也是最容易想到的,而且性能也不错,反正比冒泡排序好....

public void sort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        // 初始化最小值的下标为当然元素的下标
        int minIndex = i;

        // 找到 [i + 1, array.length) 区间内的最小值的下标
        for (int j = i + 1; j < array.length; j++) {
            if (array[minIndex] > array[j]) minIndex = j;
        }

        // 交换将最小值和当前元素
        int tmp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = tmp;
    }
}

理论上来说这个算法并不怎么样,但是和冒泡排序比较起来就很明显了,同样是两万个数据排序,冒泡排序花费太多的时间在交换上面了,而选择排序只用交换两万次...所以换来了更好的性能,但是其时间复杂度还是O(n2),没有最好的情况。

[SelectionSort]
	Time: 675ms
	Swap: 19999
	Compare: 199990000

插入排序

这个算法基础的有两种写法,一个是交换元素、还有一个是挪动元素,差别并不是很大...

public void sort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int cur = i;

        while (cur > 0 && array[cur - 1] > array[cur]) {
            // 当然元素和前一个元素交换
            int tmp = array[cur];
            array[cur] = array[cur - 1];
            array[--cur] = tmp;
        }
    }
}

反正比冒泡排序好就完事了:

[InsertionSort]
	Time: 1.09s
	Swap: 100313055
	Compare: 100333040

改成挪动元素的方式之后交换次数为0,这样基本上和选择排序效率差不多了,还是很不错的。

public void sort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int curIndex = i;
        int curValue = array[i];

        while (curIndex > 0 && array[curIndex - 1] > array[curIndex]) {
            array[curIndex] = array[--curIndex];
        }

        array[curIndex] = curValue;
    }
}
[InsertionSort]
	Time: 777ms
	Swap: 0
	Compare: 100333040

还有一个是基于二分搜索的写法,这个提升还是挺大的,不过也复杂了很多。

public void sort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        insert(array, i, search(i));
    }
}

private void insert(int[] array, int source, int target) {
    int v = array[source];
    
    if (source - target >= 0) 
        System.arraycopy(array, target, array, target + 1, source - target);
    
    array[target] = v;
}

private int search(int index) {
    int begin = 0;
    int end = index;

    while (begin < end) {
        int mid = (begin + end) >> 1;
        if (array[index] < array[mid]) {
            end = mid;
        } else {
            begin = mid + 1;
        }
    }

    return end;
}

这样无论是交换还是对比都减少了很多,因此效率就高起来了:

[InsertionSort]
	Time: 17ms
	Swap: 0
	Compare: 258087

希尔排序

很有意思的一个排序算法,可以把它当作是插入排序的超级进阶版。不是很好理解,反正就代码而言理解有点难,我也不知道要怎么去描述这个奇妙的过程,总之妙就完事了!

public void sort(int[] array) {
    for (int step = array.length >> 1; step > 0; step >>= 1) {
        for (int i = 0; i < step; i++) {
            for (int j = i + step; j < array.length; j += step) {
                int cur = j;
                int tmp = array[cur];
                while (cur > i && array[cur - gap] > tmp) {
                    array[cur] = array[cur - gap];
                    cur -= gap;
                }
                array[cur] = tmp;
            }
        }
    }
}
[ShellSort]
	Time: 32ms
	Swap: 0
	Compare: 433915

归并排序

这是一个分治思想的应用,很有意思。即将一个序列分成两个,然后再分成四个,直到单个序列只有一个元素,然后往上合并,这就是归并排序,很优秀的一个算法。

private void sort(int[] arr, int start, int end) {
    if (end - start > 1) {
        int mid = (start + end) >> 1;
        sort(arr, start, mid);
        sort(arr, mid, end);
        merger(arr, start, mid, end);
    }
}

private void merger(int[] arr, int start, int mid, int end) {
    int[] leftArray = Arrays.copyOfRange(arr, start, mid);

    for (int i = 0; i < leftArray.length;) {
        if (mid < end && arr[mid] < leftArray[i]) {
            arr[start++] = arr[mid++];
        } else {
            arr[start++] = leftArray[i++];
        }
    }
}
[MergeSort]
	Time: 38ms
	Swap: 0
	Compare: 260930

可以看一个 python 实现,还挺有意思的,而且更好理解:

 def merge_sort(arr: list, left: int, right: int) -> None:
    if right - left > 1:
        mid = (left + right) >> 1
        merge_sort(arr, left, mid)
        merge_sort(arr, mid, right)
        merge(arr, left, mid, right)


def merge(arr: list, left: int, mid: int, right: int):
    tmp = list()
    i, j = left, mid
    while i < mid and j < right:
        if arr[i] < arr[j]:
            tmp.append(arr[i])
            i += 1
        else:
            tmp.append(arr[j])
            j += 1

    start = i if i < mid else j
    end = mid if i < mid else right
    tmp.extend(arr[start:end])
    arr[left:right] = tmp

快速排序

其实这个我并不是很清楚,怎么写出来以及排序的思想我确实明白了,但是就是有一种情况是已经排序好了然后栈溢出...也就是基点的选择还是有考究的,现在我就没有讲究那么多啊,直接返回原本的了。反正就是说这种写法是比较简单的,个人觉得数据规模比较大的话还是别用这个了,递归实在搞不定呀...有时间再看一下怎么用迭代实现吧。

public int[] sort(int[] arr) {
    if (SortUtils.sorted(arr)) return arr;
    sort(0, arr.length - 1);
    return arr;
}

private void sort(int[] arr, int idx, int idy) {
    if (idx < idy) {
        int pivot = partition(arr, idx, idy);
        sort(arr, idx, pivot - 1);
        sort(arr, pivot + 1, idy);
    }
}

private int partition(int[] arr, int idx, int idy) {
    int tmp = arr[idx];

    while (idx < idy) {
        while (idx < idy) {
            if (arr[idy] > tmp) {
                idy--;
            } else {
                arr[idx++] = arr[idy];
                break;
            }
        }

        while (idx < idy) {
            if (arr[idx] < tmp) {
                idx++;
            } else {
                arr[idy--] = arr[idx];
                break;
            }
        }
    }

    arr[idx] = tmp;
    return idx;
}

睡眠排序

就图一乐呵。它确实是“宇宙第一强排序算法”,所花的时间依据于数组中的最大值,中途不需要交换不需要比较....

import java.util.ArrayList;
import java.util.concurrent.CountDownLatch;

public class SleepSort {
    public static Integer[] sort(Integer[] randoms) throws InterruptedException {
        CountDownLatch countDownLatch = new CountDownLatch(randoms.length);
        ArrayList<Integer> arr = new ArrayList<>();

        for (Integer r : randoms) {
            new Thread(() -> {
                try {
                    Thread.sleep(r * 100);
                    arr.add(r);
                    countDownLatch.countDown();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }).start();
        }
        countDownLatch.await();
        return arr.toArray(new Integer[0]);
    }
}

计数排序

典型的以空间换时间,只能排序整数,而且数组的最大值需要限制。这个我就只看了最简单的实现,事实上它还有其它的优化版本,但是如果是为了学排序算法而去学不同的排序算法将得不偿失,很多算法都只需要了解即可,比如说冒泡、选择、插入这三个 O(n2) 的算法,就算再怎么去优化也完全不如希尔、归并、快速这种 O(nlogn)的算法呀。所以说很多排序算法都只需要了解即可,最好用的应该就是快速排序了,所以想要了解更多的话不如去琢磨怎么优化快速排序。

public class CountingSort {

    public static void sort(Integer[] randoms) {
        int[] counting = new int[getMaxValue(randoms) + 1];
        for (Integer r : randoms) {
            counting[r]++;
        }

        int sortedIndex = 0;
        for (int i = 0; i < counting.length; i++) {
            while (counting[i]-- > 0) {
                randoms[sortedIndex++] = i;
            }
        }
    }

    private static Integer getMaxValue(Integer[] arr) {
        Integer max = arr[0];
        for (Integer r : arr) {
            max = r > max ? r : max;
        }
        return max;
    }
}

在排序200万个数,最大值为200万的时候这个排序算法速度非常快,当然它也不是很稳定,这个情况下比那三个 O(nlogn) 还是要快一些的,就比如快速排序在我的电脑上需要将近 1s 的时间才能排序完成。

[CountingSort]
Times: 193ms

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://blog.imoyb.com/archives/sort-algorithm-1