排序算法

大O表示法：将代码的所有步骤转换为关于数据规模n的公式项，排除不会对问题的整体复杂度产生较大影响的低阶系数项和常数项。三个法则：①只关注循环执行次数最多的代码段。②加法法则：总复杂度等于两级最大的代码段复杂度。③乘法法则：嵌套代码复杂度等于内外代码复杂度的乘积。
空间复杂度：也称渐进空间复杂度，表示代码存储空间与数据规模之间的增长关系。
时间复杂度：又称“渐进式时间复杂度”，表示代码执行时间与数据规模之间的增长关系。
原地排序算法：空间复杂度为O(1)的算法。基本上不需要额外辅助空间，允许少量额外的辅助变量进行的排序，即在原来的排序数组种比较和交换的排序。
稳定排序算法：数组中出现相同数值元素时，排序是否会造成元素相对位置的改变。

插入排序算法

简单插入排序算法

插入排序(Insert Sort)的原理是，将数组分为已排序区间和未排序区间两部分，从未排序区间中依次取元素跟已排序区间的元素对比，找到适合插入的位置。即对每一个数向前检索直到大于下一个数，将其插入中间，适用于3-7个小数据量的排序。

public class InsertionSort {
    public void insertionSort(int[] arr) {
        int j;
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];//记录当前数
            for (j = i; j > 0 && tmp < arr[j - 1]; j--)
                arr[j] = arr[j - 1];//向前检索
            arr[j] = tmp;//插入
        }
    }
}

由于嵌套循环的每一个都花费N次迭代，因此插入排序的时间复杂度为为O(n^2)，它不牵涉额外得到其他空间，因此空间复杂度为O(1)，是原地排序算法。
N个互异数的数组平均逆序数是N（N-1）/4

希尔排序算法

希尔排序(Shell Sort)是插入排序的一种，又称缩小增量排序，是针对直接插入排序算法的改进。主要改进思路是减少插入排序中数据的移动次数，设置步长，在初始数组较大时取较大步长，通常初始步长为待排数组长度1/2，此时只有两个元素比较，交换一次，此时数组为部分有序数组；之后步长依次减半直至步长为1，即为插入排序，此时数组已接近有序，所以插入元素时数据移动次数会相对较少，效率得到提高。

public class ShellSort{
    public void shellSort(int[] arr) {
        int j;
        for (int gap = arr.length / 2; gap > 0; gap /= 2)//调节距离
            for (int i = gap; i < arr.length; i++) {
                int tmp = arr[i];
                for (j = i; j >= gap && tmp < arr[j - gap]; j -= gap)//对每个数向前按距离间隔检索
                    arr[j] = arr[j - gap];
                arr[j] = tmp;//插入
            }
    }
}

希尔排序的一般复杂度为O(N^3/2)。希尔排序的时间复杂度和增列序列有关，即程序实现步长，{1,2,4,8,…}这种序列并不是很好的增量序列，这个增量序列的时间复杂度(最坏情形)是O(n^2)，Hibbard提出了另一个增量序列{1,3,7，…,2^k-1}(质数增量)，时间复杂度(最坏情形)为O(n^1.5)；Sedgewick提出了几种增量序列，其最坏情形运行时间为O(n^1.3),其中最好的一个序列是{1,5,19,41,109,…}。

归并排序算法

二路归并排序算法

思想：递归的将两个排序好的数组排列组合在一个。
步骤：1.申请空间，使其大小为两个已经排序序列之和，用来存放合并后的序列；
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4.重复步骤 3 直到某一指针达到序列尾；
5.将另一序列剩下的所有元素直接复制到合并序列尾。
特点：1.归并排序的性能不受输入数据的影响，代价是需要额外的内存空间。
2.合并两个已排序的表用到线性附加内存，还需要花费时间拷贝数据到临时数组再拷贝回来。
3.在java中，进行元素比较是昂贵的（比较不容易被内嵌，动态调度的开销会减慢执行的速度），但移动元素是省时的（因为他们是引用的赋值，而不是庞大对象的拷贝）。归并排序使用排序算法中最少的比较次数，是标准java类库中范型排序使用的算法。（c++相反）
我的归并算法如下，很多地方需要改进。

public void sort(int[] arr, int[] arr1, int left, int right) {
    if (right - left == 1) {
        if (arr[left] > arr[right]) {
            arr[left] = arr[left] + arr[right];
            arr[right] = arr[left] - arr[right];
            arr[left] = arr[left] - arr[right];
        }
    } else if (right - left == 2) {
        for (int j = 0; j < 2; j++) {
            for (int i = left; i < right; i++) {
                if (arr[i] > arr[i + 1]) {
                    arr[i] = arr[i] + arr[i + 1];
                    arr[i + 1] = arr[i] - arr[i + 1];
                    arr[i] = arr[i] - arr[i + 1];
                }
            }
        }
    } else {
        merg.sort(arr, arr1, left, right / 2 + left / 2);
        merg.sort(arr, arr1, right / 2 + left / 2 + 1, right);
        for (int i = left; i < right + 1; i++) arr1[i] = arr[i];
        int le = left, ri = right / 2+left/2 + 1;
        for (int i = left; i < right + 1; i++) {
            if (le == right / 2+left/2 + 1) arr[i] = arr1[ri++];
            else if (ri == right + 1) arr[i] = arr1[le++];
            else if (arr1[le] <= arr1[ri]) {
                arr[i] = arr1[le++];
            } else {
                arr[i] = arr1[ri++];
            }
        }
    }
}

《数据结构与算法分析java语言描述》中这段代码：

public class BookMergeSort {
    private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] a, AnyType[] tmpArray, int left, int right) {
        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(a, tmpArray, left, center);
            mergeSort(a, tmpArray, center + 1, right);
            merge(a, tmpArray, left, center + 1, right);
        }
    }
    //利用方法重载解决自动生成对应函数问题
    public static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] a) {
        AnyType[] tmpArray = (AnyType[]) new Comparable[a.length];
        mergeSort(a, tmpArray, 0, a.length - 1);
    }
    private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] a, AnyType[] tmpArray, int leftPos, int rightPos, int rightEnd) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;
        while (leftPos <= leftEnd && rightPos <= rightEnd)
            if (a[leftPos].compareTo(a[rightPos]) <= 0)
                tmpArray[tmpPos++] = a[leftPos++];
            else
                tmpArray[tmpPos++] = a[rightPos++];//灵活设置循环，减少资源浪费
        while (leftPos <= leftEnd)
            tmpArray[tmpPos++] = a[leftPos++];
        while (rightPos <= rightEnd)
            tmpArray[tmpPos++] = a[rightPos++];
        for (int i = 0; i < numElements; i++, rightEnd--)//使用现成的指针
            a[rightEnd] = tmpArray[rightEnd];
    }
}

在java中，进行元素比较是昂贵的（比较不容易被内嵌，动态调度的开销会减慢执行的速度），但移动元素是省时的（因为他们是引用的赋值，而不是庞大对象的拷贝）。归并排序使用排序算法中最少的比较次数，是标准java类库中范型排序使用的算法。（c++相反）

多路归并排序算法

交换排序算法

冒泡排序算法

冒泡排序(Bubble Sort)，是一种最基础的交换排序，每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。
原理：每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。

public class BubbleSort {
    public int[] bubSort(int arr[]) {
        int e, isEmpty = 1;
        while (isEmpty == 1) {
            isEmpty = 0;
            for (int i = 1; i < arr.length; i++) {
                int empty = 0;
                if (arr[i - 1] > arr[i]) {
                    e = arr[i];
                    arr[i] = arr[i - 1];
                    arr[i - 1] = e;
                    isEmpty = 1;
                }
            }
        }
        return arr;
    }
}

冒泡排序的时间复杂度为O(N^2)，空间复杂度为O(1)。

快速排序算法

快速排序使用分治策略来把一个串行分为两个子串行。从本质上看，是冒泡排序基础上的递归分治法。

基础步骤：

1.如果输入个数是0或1，则返回。
2.取数列S中任一元素v，称为“基准”或“枢纽元”(来自《数据结构与算法分析Java语言描述》，都译作pivot）。
3.将S-{v}（S中其余元素）划分成两个不相交的集合：小于等于v的集合S1，大于等于v的集合S2（相同的数可以放到任一边）。
4.返回{quickSort(S1)后跟v，继而返回quickSort(S2)}。

枢纽元

对于等于枢纽元的元素，第3步分割的描述不是唯一的，因此这就成了一种设计决策，把等于枢纽元的元素更平均的分到S1和S2中，类似于二叉查找树的平衡。
一种错误的方法：
通常的、无知的选择是将第一个元素用作枢纽元，如果输入是预排序或反序，就会产生一个劣质的分割（在所有递归调用中，所有元素都被划入S1或S2）。实际上，如果数列是预排序的，快速排序将花费二次的时间而不干任何事。
安全的做法：
随机选取枢纽元非常安全，但随机数的生成开销很大，无法减少算法其余部分的平均运行时间。
三数中值分割法：
枢纽元最好的选择是数组的中值，但计算会明显减慢快速排序的速度。因此一般的做法是使用左端、右端和中心位置上三个元素的中值。

    public static <AnyType extends Comparable<? super AnyType>> AnyType median3(AnyType[] a, int left, int right) {
        int center = (left + right) / 2;
        if (a[center].compareTo(a[left]) < 0) swapReferences(a, left, center);
        if (a[right].compareTo(a[left]) < 0) swapReferences(a, left, right);
        if (a[right].compareTo(a[center]) < 0) swapReferences(a, center, right);
        swapReferences(a, center, right - 1);
        return a[right - 1];
    }

分割策略

通过将枢纽元与最后的元素交换使枢纽元离开要被分割的数据段，从第一个元素和倒数第二个元素，要做的就是把所有小元素（相对枢纽元）移到数组左边而把大元素移到右边。
设立两个指针left和right，分别指向第一个元素和倒数第二个元素，当left在right左边时，我们将left右移经过小元素，并将right左移经过大元素，当left和right同时分别指向一个大元素和小元素而停止时，将两个元素互换，即把一个大元素推向右边而把小元素推向左边。重复该过程直到指针彼此交错为止。
分割的最后一步是将枢纽元与left所指向的元素交换。
一个重要的细节是如何处理等于枢纽元的元素，当指针遇到等于枢纽元的元素时是否应该停止。直观的看，right和left应该做相同的工作，否则分割将出现偏向一方的倾斜。
考虑数组中所有元素都相等的情况。如果指针停止并进行交换，虽然将有很多次无意义交换，但left和right将在中间交错并成功建立子数组。如果指针不停止，left最后到过的位置可能偏向一端，从而产生两个非常不均衡的子数组，增加运行时间。因此，进行不必要的交换建立两个均衡的子数组要比蛮干冒险得到两个不均衡的子数组好。

小数组

对于很小的数组，快速排序不如插入排序。因为快速排序是递归的，所以这样的情形经常发生。通常的解决方法是对于计算中的小数组不再使用递归的快速排序，代之以对小数组有效的排序算法。好的截至范围是N=10（虽然在5到20间都可能产生类似的效果）。这样做也避免了一些有害的退化情形，如取三个元素的中值而只有一个或两个元素的情况。

快速排序例程

以下快速排序未使用截止替换小数组的方法，对一个元素、两个元素和三个元素的情况分别进行判断处理。

public class MyQuickSort {
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    public static void quickSort(int[] arr, int left, int right) {
        if(right-left>1) {
            if (arr[left] > arr[right]) swap(arr, left, right);
            if (arr[right] > arr[right / 2 + left / 2]) swap(arr, right, right / 2 + left / 2);
            if (arr[left] > arr[right]) swap(arr, left, right);
            int leftIndex = left, rightIndex = right - 1;
            while (leftIndex < rightIndex) {
                if (arr[leftIndex] >= arr[right] && arr[rightIndex] <= arr[right]) swap(arr, leftIndex, rightIndex);
                if (arr[leftIndex] < arr[right]) leftIndex++;
                if (arr[rightIndex] > arr[right]) rightIndex--;
            }
            swap(arr, leftIndex, right);
            quickSort(arr,left,rightIndex);
            quickSort(arr,leftIndex+1,right);
        }else if(right-left==1){
            if(arr[left]>arr[right])swap(arr,right,left);
        }
    }
    public static void swap(int[] arr, int left, int right) {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
}

快速排序每次的交换是跳跃式的，将小于等于基准点的数全部放到左边，将大于等于基准点的数全部放到右边。这样在每次交换时就不会像冒泡排序只能在相邻的数之间交换，因此总的比较和交换次数就少了。
快速排序的平均运行时间是O(NlogN)，得益于精炼和高度优化的内部循环。
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
通过将快速排序和堆排序结合，由于堆排序的O(NlogN)最坏情况运行时间，可以对几乎所有的输入都达到快速排序的快速运行时间。

选择排序算法

简单选择排序算法

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是：首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

    public static  void selectionSort(int[] arr) {
        int index = 0;
        int tmp;
        for (int i = 0; i < arr.length-1; i++) {
            index=i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j]<arr[index]) index = j;
            }
            tmp = arr[i];
            arr[i] = arr[index];
            arr[index] = tmp;
        }
    }

对于长度为n的数组，代码执行的时间都花费在内层for循环中的比较语句和外层for循环里的交换语句，时间复杂度为O(n^2)，空间复杂度为O(1)。如果用数组实现选择排序算法，由于选择元素之后会发生交换操作，有可能把前面的元素交换到后面，所以选择排序不是稳定的排序，如下图所示。如果用链表实现，只会插入元素而不会交换未排序元素的位置，是稳定算法。

堆排序算法

分配排序

基于分配和收集，先将数据分配到不同的桶中，再将桶中的数据收集到一起。

桶排序

基于比较排序的一种分配排序，是单关键字排序。
基本思想：将待排序序列，按照序列值的大小划分成几个桶，分别对每组进行排序，排完序之后再按照一定的顺序合并所有的桶，即排序完成。
步骤：1.根据待排序序列的大小设定桶值，即划分多少个桶。
2.遍历待排序序列，将每个元素放入不同的桶中。
3.在向桶中添加元素时，使用插入排序或其他排序方法，将桶内元素排序
4.按桶的顺序合并桶。
不分区基础实现：

public class BuckSortTwo {
    public static void bucketSort(int[] arr){
        if (arr==null||arr.length<2){
            return;
        }
        //常用写法
        int max = Integer.MIN_VALUE;
        for (int i =0;i<arr.length;i++){
            max = Math.max(max,arr[i]);
        }
        int[] bucket = new int[max+1];
        for (int i =0;i<arr.length;i++){
            //桶数组此下标有数据，数值就加一
            bucket[arr[i]]++;
        }
        int i = 0;
        for (int j = 0;j<bucket.length;j++){
            while (bucket[j]-->0){
                arr[i++]=j;
            }
        }
    }
}

分区合并实现：

public class BucketSort {
    public static void bucketSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int len = arr.length;
        // 根据原始序列的长度，设置桶的数量。这里假设每个桶放最多放4个元素
        int bucketCount = len / 4;
        // 遍历原始序列，找出最大值和最小值
        int min = 0, max = 0;
        for (int i = 0; i < len; i++) {
            if (arr[i] > max) {
                max = arr[i];
            } else if (arr[i] < min) {
                min = arr[i];
            }
        }
        // 每个桶的数值范围
        int range = (max - min + 1) / bucketCount;
        int[][] buckets = new int[bucketCount][];
        // 遍历原始序列
        for (int i = 0; i < len; i++) {
            int val = arr[i];
            // 计算当前值属于哪个桶
            int bucketIndex = (int) Math.floor((val - min) / range);
            // 向桶中添加元素
            buckets[bucketIndex] = appendItem(buckets[bucketIndex], val);
        }
        // 最后合并所有的桶
        int k = 0;
        for (int[] b : buckets) {
            if (b != null) {
                for (int i = 0; i < b.length; i++) {
                    arr[k++] = b[i];
                }
            }
        }
    }
    private static int[] appendItem(int[] bucketArr, int val) {
        if (bucketArr == null || bucketArr.length == 0) {
            return new int[]{val};
        }
        // 拷贝一下原来桶的序列，并增加一位
        int[] arr = Arrays.copyOf(bucketArr, bucketArr.length + 1);
        // 这里使用插入排序，将新的值val插入到序列中
        for (int i = bucketArr.length - 1; i >= 0; i--) {
            // 从新序列arr的倒数第二位开始向前遍历（倒数第一位是新增加的空位，还没有值）
            // 如果当前序列值大于val，那么向后移位
            if (arr[i] > val) {
                arr[i + 1] = arr[i];
            } else {
                arr[i + 1] = val;
                break;
            }
        }
        return arr;
    }
}

桶排序的平均时间复杂度为O(n+k)，最坏的情况为O(n^2)，空间复杂度为O(n+k)。

基数排序和计数排序

多关键字链式排序。
桶排序是在数组元素在某个小范围内大量数据情况下时间复杂度为O(n)的排序。假如数据的范围为0~1000我们就开一个1001大小的数组进行排序，就是假如100出现了就将100的桶b[100]++。
基数排序就是多个桶进行桶排序。以十进制为例，基数指的是数的位，如个位，十位，百位等。比如输入的数最多有两位，我们就先按十位进行桶排序，分为0~9的十个桶，b[0]存0 ~9的数，b[3]存30 ~39的数，然后对每个0-9的桶进行按个位数的桶排序，最后就是整体有序的数组。
计数排序其实就是特殊的桶排序，就是多了一个先找最大最小值开一个大小为max-min+1的数组进行桶排序，假如i(min<=i<=max)出现了，就放进桶b[i-min]++。比桶排序所需的空间有所减少。
它们都是时间复杂度为O(n)的排序，都比较适合在某个小范围内大量重复数据的排序，而且都不需要进行记录关键字间的比较。

参考

Java 基础

常用排序算法