算法Training——排序

摘要：对于不稳定的排序算法，只需要举出实例，就能证明其不稳定性。而对稳定排序算法，必须对算法进行分析才能判断其是否稳定排序算法是否稳定是由具体算法决定的，稳定算法也可以在某种条件下变为不稳定算法。

排序算法主要分为两大类

比较排序，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等

非比较排序，主要有：计数排序，基数排序，桶排序等

排序算法的稳定性定义：
如果序列中有a=b，排序前a在b之前，排序后a还在b之前，则称这种排序算法是稳定的。

对于不稳定的排序算法，只需要举出实例，就能证明其不稳定性。而对稳定排序算法，必须对算法进行分析才能判断其是否稳定

排序算法是否稳定是由具体算法决定的，稳定算法也可以在某种条件下变为不稳定算法。例如冒泡排序中，把交换两数的条件变为A[i]>=A[i+1]（原本是>号）

上例告诉我们，算法是由具体的人来写的，写的垃圾，稳定算法也能写的不稳定

重复地走访过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数

针对所有的元素重复以上的步骤，除了已经排序完成的数

给一组整数，按照升序排序，使用选择排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法

对于数组 [3, 2, 1, 4, 5], 排序后为：[1, 2, 3, 4, 5]

无需分析

fun sortInteger(a : IntArray)
{
    val len = a.size - 1
    var alreadyNum =  0
    var sortFinish = false

    while (alreadyNum <= len - 1 && !sortFinish)
    {
        var perSortFinish = true

        for (i in 1..(len - alreadyNum))
        {
            if (a[i-1] > a[i])
            {
                val temp = a[i-1]
                a[i-1] = a[i]
                a[i] = temp
                perSortFinish = false
            }
        }

        sortFinish = perSortFinish
        alreadyNum += 1
    }
}

public void sortIntegers(int[] A) {
    int len = A.length - 1;
    int alreadyNum = 0;
    boolean sortFinish = false;

    while (alreadyNum <= len - 1 && !sortFinish)
    {
        boolean perSortFinish = true;

        for (int i=1; i <= len-alreadyNum; i++)
        {
            if (A[i-1] > A[i])
            {
                int temp = A[i-1];
                A[i-1] = A[i];
                A[i] = temp;
                perSortFinish = false;
            }
        }

        sortFinish = perSortFinish;
        alreadyNum += 1;
    }
}

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

先从数列中取出一个数（为方便通常会选第一个数）作为基准数

逐个比较，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边

再对左右区间重复第二步，直到各区间只有一个数

直接沿用上一题的实例，为便于阅读，将该例子再写一遍

给一组整数，按照升序排序，使用选择排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法

对于数组 [3, 2, 1, 4, 5], 排序后为：[1, 2, 3, 4, 5]

无需分析