/*1、冒泡排序
思路：外层循环从1到n-1，内循环从当前外层的元素的下一个位置开始，依次和外层的元素比较，出现逆序就交换，通过与相邻元素的比较和交换来把小的数交换到最前面。
*/
for(int i=0; i<arr.length-1; i++) //外层循环控制排序趟数
{
    for(int j=0; j<arr.length-1-i; j++) //内层循环控制每一趟排序多少次
    {
        if(arr[j]>arr[j+1])
        {
            int temp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;
            　　　　　　　　
        }
        　　　　　　
    }
    　　　　
}
/*2、选择排序
思路：冒泡排序是通过相邻的比较和交换，每次找个最小值。选择排序是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
*/
private static void sort(int[] array)
{
    int n = array.length;
    for (int i = 0; i < n-1; i++)
    {
        int min = i;
        for (int j = i+1; j < n; j++)
        {
            if (array[j] < array[min]) //寻找最小数
            {
                min = j;                      //将最小数的索引赋值
            }
        }
        int temp = array[i];
        array[i] = array[min];
        array[min] = temp;
    }
}
/*3、插入排序
思路：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。可以理解为玩扑克牌时的理牌；
*/
private static void sort(int[] array)
{
    int n = array.length;
    /**
    *从第二位数字开始，每一个数字都试图跟它的前一个比较并交换，并重复；直到前一个数字不存在或者比它小或相等时停下来
    **/
    for (int i = 1; i < n; i++)  //从第二个数开始
    {
        int key = array[i];
        int j = i -1;
        while (j >= 0 && array[j]>key)
        {
            array[j + 1] = array[j];     //交换
            j--;                                //下标向前移动
        }
        array[j+1] = key;
    }
}
/*4、希尔排序
思路：希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。
先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
问题：增量的序列取法？
关于取法，没有统一标准，但最后一步必须是1；因为不同的取法涉及时间复杂度不一样，具体了解可以参考《数据结构与算法分析》；一般以length/2为算法。（再此以gap=gap*3+1为公式）
 */
private static void sort(int[] array)
{
    int n = array.length;
    int h = 1;
    while (h<n/3)   //动态定义间隔序列
    {
        h = 3*h +1;
    }
    while (h >= 1)
    {
        for (int i = h; i < n; i++)
        {
            for (int j = i; j >= h && (array[j] < array[j - h]); j -= h)
            {
                int temp = array[j];
                array[j] = array[j - h];
                array[j-h]= temp;
            }
        }
        h /=3;
    }
}
/*5、归并排序
思路：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。它使用了递归分治的思想；相当于：左半边用尽，则取右半边元素；右半边用尽，则取左半边元素；右半边的当前元素小于左半边的当前元素，则取右半边元素；右半边的当前元素大于左半边的当前元素，则取左半边的元素。
*/

//自顶向下：

private static void mergeSort(int[] array)
{
    int[] aux = new int[array.length];
    sort(array, aux, 0, array.length - 1);
}

private static void sort(int[] array, int[] aux, int lo, int hi)
{
    if (hi<=lo) return;
    int mid = lo + (hi - lo)/2;
    sort(array, aux, lo, mid);
    sort(array, aux, mid + 1, hi);
    merge(array, aux, lo, mid, hi);
}

private static void merge(int[] array, int[] aux, int lo, int mid, int hi)
{
    System.arraycopy(array,0,aux,0,array.length);
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++)
    {
        if (i>mid) array[k] = aux[j++];
        else if (j > hi) array[k] = aux[i++];
        else if (aux[j]<aux[i]) array[k] = aux[j++];
        else array[k] = aux[i++];
    }
}

//自底向上：

public static void sort(int[] array)
{
    int N = a.length;
    int[] aux = new int[N];
    for (int n = 1; n < N; n = n+n)
    {
        for (int i = 0; i < N-n; i += n+n)
        {
            int lo = i;
            int m  = i+n-1;
            int hi = Math.min(i+n+n-1, N-1);
            merge(array, aux, lo, m, hi);
        }
    }
}

private static void merge(int[] array, int[] aux, int lo, int mid, int hi)
{
    for (int k = lo; k <= hi; k++)
    {
        aux[k] = array[k];
    }
    // merge back to a[]
    int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++)
    {
        if      (i > mid)              array[k] = aux[j++];  // this copying is unneccessary
        else if (j > hi)               array[k] = aux[i++];
        else if (aux[j]<aux[i]) array[k] = aux[j++];
        else                           array[k] = aux[i++];
    }
}

/*归并排序的缺点：因为是Out-place sort，因此相比快排，需要很多额外的空间。

为什么归并排序比快速排序慢？

　　答：虽然渐近复杂度一样，但是归并排序的系数比快排大。

对于归并排序有什么改进？

　　答：就是在数组长度为k时，用插入排序，因为插入排序适合对小数组排序。在算法导论思考题2-1中介绍了。复杂度为O(nk+nlg(n/k)) ，当k=O(lgn)时，复杂度为O(nlgn)
*/

/*6、快速排序
思路：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
*/
private static void sort(int[] array)
{
    shuffle(array);
    sort(array, 0, array.length - 1);
}
private static void sort(int[] array, int lo, int hi)
{
    if(hi<=lo+M)
    {
        Insert.sort(a,lo,hi);
        return;
    }
    int lt = lo, gt = hi;
    int v = array[lo];
    int i = lo;
    while (i <= gt)
    {
        if      (array[i]<v) exch(array, lt++, i++);
        else if (array[i]>v) exch(array, i, gt--);
        else              i++;
    }
    // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
    sort(array, lo, lt-1);
    sort(array, gt+1, hi);
}

private static void exch(int[] a, int i, int j)
{
    int swap = a[i];
    a[i] = a[j];
    a[j] = swap;
}

/**
 *打乱数组
 */
private static void shuffle(int[] array)
{
    Random random = new Random(System.currentTimeMillis());
    if (array == null) throw new NullPointerException("argument array is null");
    int n = array.length;
    for (int i = 0; i < n; i++)
    {
        int r = i + random.nextInt(n-i);     // between i and n-1
        int temp = array[i];
        array[i] = array[r];
        array[r] = temp;
    }
}

/*7、堆排序
思路：堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
*/
public static void sort(int[] a)
{
    int N = a.length;
    int[] keys = new int[N+1];
    //注意，堆的数据结构是从1开始的，0不用
    for (int i = 1; i < keys.length; i++)
    {
        keys[i] = a[i-1];
    }
//      //构造堆,使得堆是有序的
    for(int k = N/2; k>=1; k--) sink(keys,k,N);
    //排序，相当于毁掉堆
    while(N>1)
    {
        exch(keys,1,N--);
        sink(keys,1,N);
    }
    //重新写回数组
    for (int i = 0; i < a.length; i++)
    {
        a[i] = keys[i+1];
    }
}

private static void sink(int[] a, int k, int N)
{
    // TODO Auto-generated method stub
    while(2*k<=N)
    {
        int j = 2*k;
        if (j < N && less(a[j], a[j+1])) j++;
        if (less(a[j], a[k])) break;
        exch(a, k, j);
        k = j;
    }
}

private static boolean less(int k, int j)
{
    // TODO Auto-generated method stub
    return k < j;
}

private static void exch(int[] a, int i, int n)
{
    // TODO Auto-generated method stub
    int temp = a[i];
    a[i] = a[n];
    a[n] = temp;
}

/*8、计数排序
思路：将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

　　找出待排序的数组中最大和最小的元素；
　　统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
　　对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
　　反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
*/

/**
     * 输入数组的元素都是介于0..k之间的
     * @param data 待排序数组
     * @param k 最大元素
     * @return 排序结果
     */
public static int[] sort(int[] data, int k)
{
    // 存放临时数据的数组tmp，初始元素都是0；k为数组中最大元素
    int[] tmp = new int[k + 1];

    // 计算数组中每个元素i出现的次数，存入数组tmp中的第i项，即原数组中的元素值为tmp数组中的下标
    for (int i = 0; i <= data.length - 1; i++)
    {
        tmp[data[i]]++;
    }
    // 计算数组中小于等于每个元素的个数,即从tmp中的第一个元素开始，每一项和前一项相加
    for (int j = 1; j <= k; j++)
    {
        tmp[j] = tmp[j] + tmp[j - 1];
    }
    // result数组用来来存放排序结果
    int[] result = new int[data.length];
    for (int i = data.length - 1; i >= 0; i--)
    {
        result[tmp[data[i]] - 1] = data[i];
        tmp[data[i]]--;
    }
    return result;
}

/*9、桶排序
思路：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

　　设置一个定量的数组当作空桶；
　　遍历输入数据，并且把数据一个一个放到对应的桶里去；
　　对每个不是空的桶进行排序；
　　从不是空的桶里把排好序的数据拼接起来。
*/
public static void bucketSort(double array[])
{
    int length = array.length;
    ArrayList arrList[] = new ArrayList[length];
    for (int i = 0; i < length; i++)
    {
        //0.7到0.79放在第8个桶里,编号7；第一个桶放0到0.09
        int temp = (int) Math.floor(10 * array[i]);
        if (null == arrList[temp])
            arrList[temp] = new ArrayList();
        arrList[temp].add(array[i]);
    }
    // 对每个桶中的数进行插入排序
    for (int i = 0; i < length; i++)
    {
        if (null != arrList[i])
        {
            Collections.sort(arrList[i]);
        }
    }
    int count = 0;
    for (int i = 0; i < length; i++)
    {
        if (null != arrList[i])
        {
            Iterator iter = arrList[i].iterator();
            while (iter.hasNext())
            {
                Double d = (Double) iter.next();
                array[count] = d;
                count++;
            }
        }
    }
}
/*10、基数排序
思路：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

　　取得数组中的最大数，并取得位数；
　　arr为原始数组，从最低位开始取每个位组成radix数组；
　　对radix进行计数排序（利用计数排序适用于小范围数的特点）；
*/
private static void radixSort(int[] array,int radix, int distance)
{
    int length = array.length;
    int[] temp = new int[length];
    int[] count = new int[radix];
    int divide = 1;

    for (int i = 0; i < distance; i++)
    {

        System.arraycopy(array, 0,temp, 0, length);
        Arrays.fill(count, 0);

        for (int j = 0; j < length; j++)
        {
            int tempKey = (temp[j]/divide)%radix;
            count[tempKey]++;
        }

        for (int j = 1; j < radix; j++)
        {
            count [j] = count[j] + count[j-1];
        }
        for (int j = length - 1; j >= 0; j--)
        {
            int tempKey = (temp[j]/divide)%radix;
            count[tempKey]--;
            array[count[tempKey]] = temp[j];
        }
        divide = divide * radix;
    }
}