前言

本文主要讲的是归并排序，堆排序和快速排序的原理与实现。当然我的实现不一定不是最好的，如果有更好的实现大家也可以在评论区贴出更好的实现代码。

时间复杂度的计算：时间复杂度大概的意思是以每一条执行的语句为单位，一个排序算法在随着数据的增大时间上会以什么形式去增长（这里一个算法可能根据数据情况的不同会有多个时间复杂度比如我排序的数据是1,2,3,4,5和1,3,2,5,4 使用快速排序的话就会产生不同的时间复杂度，一般我们取最常见的数据情况即可，即平均时间复杂度）。一般情况下我们关注时间复杂度关注到数量级即可比如某个算法的执行代码量是n2 + logn那么我们一般就记做O(n2)。

常见的时间复杂度有:

常数阶O(1),对数阶O(  ),线性阶O(n),

线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3)

更详细的请参考：https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/1894057

归并排序

归并排序是一种稳定排序，时间复杂度为O(nlogn)。适用于:数据量不大，需要稳定排序的情况。

算法原理：

归并排序的思想，有点像MapReduce，是一种分治的思想，就是将一个大的数组分成许多的小数组，小数组间进行排序之后再进行多个小数组的聚合，聚合时根据小数组内值得大小从新生成一个新的小数组，直到聚合完毕。感觉这种算法可以写个多处理器的版本速度应该会更快。

算法实现：

private static void mergeSort(int[] arr) {
        int step = 2;
        int[] temps = new int[arr.length];

        while (step < arr.length * 2) {
            for (int i = 0; i < arr.length; i += step) {
                int left = i, right = i + step / 2 < arr.length ? i + step / 2 : arr.length - 1;
                int index = i;

                while (index < i + step && index < arr.length) {
                    if (arr[left] > arr[right]) {
                        temps[index] = arr[right];
                        right++;
                        if (right == i + step || right == arr.length) {
                            index++;
                            break;
                        }
                    } else {
                        temps[index] = arr[left];
                        left++;
                        if (left == i + step / 2) {
                            index++;
                            break;
                        }
                    }

                    index++;
                }
                while (left < i + step / 2 && index < arr.length) {
                    temps[index] = arr[left];
                    left++;
                    index++;
                }
                while (right < i + step && index < arr.length) {
                    temps[index] = arr[right];
                    right++;
                    index++;
                }
            }
            step *= 2;

            int[] trans = arr;
            arr = temps;
            temps = trans;
        }
    }

堆排序

堆排序是一种稳定排序，平均时间复杂度为O(n * logn).适用于：数据量比较大（速度不一定快但是省空间），需要稳定排序的情况。其实堆排序的算法更适用于查找数组内最大最小值。

算法原理：

算法实现：

 private static void heapSort(int[] arr) {
        int length = arr.length;
        while (length > 0) {
            int temp;
            for (int i = length / 2 - 1; i > -1; i--) {
                int k = i * 2;
                if (arr[i] < arr[k + 1]) {
                    temp = arr[i];
                    arr[i] = arr[k + 1];
                    arr[k + 1] = temp;
                }
                if (k + 2 < length && arr[i] < arr[k + 2]) {
                    temp = arr[i];
                    arr[i] = arr[k + 2];
                    arr[k + 2] = temp;
                }
            }
            temp = arr[--length];
            arr[length] = arr[0];
            arr[0] = temp;
        }
    }

快速排序

快速排序是一种不稳定排序，时间复杂度O(nlogn)。适用于：不需要稳定排序的前提下，大多数情况都是可以满足的。快排同样使用的是分治的思路，也是有多种快速排序算法可以再多cpu或者多主机的情况下执行的。

算法原理：

算法实现：

private static void quickSort(int[] arr, int left, int right) {
        if(left >= right)
            return;

        int reference = arr[left], l = left, r = right;
        while(l != r) {
            while(arr[r] >= reference && l != r)
                r--;

            while(arr[l] <= reference && l != r)
                l++;

            if(l < r){
                int temp = arr[r];
                arr[r] = arr[l];
                arr[l] = temp;
            }
        }

        arr[left] = arr[l];
        arr[l] = reference;

        quickSort(arr, left, l - 1);
        quickSort(arr, l + 1, right);
    }

总结

每种算法都有着各自最适合的情况，个人认为不要求稳定排序的情况下使用快速排序，要求稳定且数据量不是特别大的时候使用归并排序，数据量的的时候堆排序感觉速度很慢也不是很合适的算法。。感觉堆排序的优点还是能迅速的找出极大极小值吧。