排序算法 - 耐心排序

基本思想

耐心排序充分集合了桶排序和插入排序的优点，首先使用桶排序，排序之后每个桶中数据相对有序，这样再使用插入排序，简化了问题，速度变的更快。

建桶规则:如果没有桶,新建一个桶;如果不符合入桶规则那么新建一个桶。

入桶规则:只要比桶里最上边的数字小即可入桶,如果有多个桶可入,那么按照从左到右的顺序入桶即可。

举个例子：待排序数组[6 4 5 1 8 7 2 3]

第一步：因为此前还没有桶，则建立一个桶，我们命名为桶1,从上面取出第一个数字 6，然后将6放入到桶中。

第二步：我们使用第二个值4，然后遍历现有的桶，遍历的工程中先遇到桶1，我们发现桶1中最上面的元素是6,4比6大，则6下沉，有桶【4,6】。

第三步：我们使用第三个值5，然后遍历现有的桶，因为第一个桶第一个元素是4，比5小，所以重新开一个桶【5】，之后共有两个桶【4,5】【5】。

第四部：我们使用第四个值1，然后遍历现有的桶，因为第一个桶第一个元素是4，比1大，所以放到桶1【4,6】最前面，从而形成【1,4,6】【5】。

第五步：我们使用第五个元素，然后遍历现有的桶，第一个桶第一个元素是1，第二个桶第一个元素是5，都比8小，所以需要重新开一个桶【8】，此时共有桶【1,4,6】【5】【8】。

第六步：使用同样的方法，之后桶是【1,4,6】【5】【7，8】。

第七步：使用同样的方法，之后桶是【1,4,6】【2，5】【7，8】。

第八步：使用同样的方法，之后桶是【1,4,6】【2，5】【3，7，8】。

注意：遍历的数组，只跟各个桶的第一个元素做比较，这样保证各个桶元素有序。

代码

package main.java.com.study.sortingAalgorithm;

import main.java.com.study.utils.CommonUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: whb
 * @description: 耐心排序
 */
public class PatienceSort {
    public static int[] patienceSort(int[] unsorted) {
        List new_list = new ArrayList();
        for (int i = 0; i < unsorted.length; i++) {
            List bucket_list = new ArrayList();
            if (i == 0) {
                bucket_list.add(unsorted[i]);
                new_list.add(bucket_list);
            } else {
                boolean is_ok = false;
                for (int j = 0; j < new_list.size(); j++) {
                    if (unsorted[i] < (int) ((List) new_list.get(j)).get(0)) {
                        ((List) new_list.get(j)).add(0, unsorted[i]);
                        is_ok = true;
                        break;
                    }
                }
                if (!is_ok) {
                    bucket_list.add(unsorted[i]);
                    new_list.add(bucket_list);
                }
            }
        }
        //多维数组变成单维数组
        int[] ok_list = new int[unsorted.length];
        int q = 0;
        for (int m = 0; m < new_list.size(); m++) {
            for (int n = 0; n < ((List) new_list.get(m)).size(); n++) {
                ok_list[q] = (int) ((List) new_list.get(m)).get(n);
                q++;
            }
        }

        //插入循环
        //将数组的长度赋给n是为了防止每次for循环中判断时都调用length方法影响性能
        int n = ok_list.length;
        //用于中转数据
        int tmp;
        int j;
        //排序的次数
        for (int i = 1; i < n; i++) {
            tmp = ok_list[i];
            //取i前面的所有跟i位置元素进行比较，先比较i-1和i，如果i-1大于i，则互换位置，i-1和i-2比较，以此类推
            for (j = i - 1; j >= 0 && ok_list[j] > tmp; j--) {
                ok_list[j + 1] = ok_list[j];
            }
            ok_list[j + 1] = tmp;
        }
        return ok_list;
    }

    public static void main(String[] args) {
        int[] unsorted = {6, 4, 5, 1, 8, 7, 2, 3};
        System.out.println("**************耐心排序******************");
        System.out.println("排序前：");
        CommonUtils.display(unsorted);
        System.out.println("排序后：");
        int[] sorted = patienceSort(unsorted);
        CommonUtils.display(sorted);
    }
}

测试结果