我喜欢的排序算法

鸡尾酒排序（双重冒泡排序）

public static int[] cocktailSort(int[] src)
{
    //将最小值排到队尾
    for(int i = 0 ; i < src.length/2 ; i++)
    {
        for(int j = i ; j < src.length-i-1 ; j++)
        {
            if(src[j] < src[j+1])
            {
                int temp = src[j];
                src[j] = src[j+1];
                src[j+1] = temp;
            }
            System.out.println("交换小"+Arrays.toString(src));
        }
        //将最大值排到队头
        for(int j = src.length-1-(i+1); j > i ; j--)
        {
            if(src[j] > src[j-1])
            {
                int temp = src[j];
                src[j] = src[j-1];
                src[j-1] = temp;
            }
            System.out.println("交换大"+Arrays.toString(src));
        }
        System.out.println("第"+i+"次排序结果："+Arrays.toString(src));
    }
    return src;
}

希尔排序

希尔排序严格来说是基于插入排序的思想，又被称为缩小增量排序。
　　具体流程如下：
　　1、将包含n个元素的数组，分成n/2个数组序列，第一个数据和第n/2+1个数据为一对…
　　2、对每对数据进行比较和交换，排好顺序；
　　3、然后分成n/4个数组序列，再次排序；
　　4、不断重复以上过程，随着序列减少并直至为1，排序完成。

　对于插入排序而言，如果原数组是基本有序的，那排序效率就可大大提高。另外，对于数量较小的序列使用直接插入排序，会因需要移动的数据量少，其效率也会提高。因此，希尔排序具有较高的执行效率。
　　希尔排序并不稳定，O(1)的额外空间，时间复杂度为O(N*(logN)^2)。

public void sort(int[] arr) {
        // i表示希尔排序中的第n/2+1个元素（或者n/4+1）
        // j表示希尔排序中从0到n/2的元素（n/4）
        // r表示希尔排序中n/2+1或者n/4+1的值
        int i, j, r, tmp;
        // 划组排序
        for(r = arr.length / 2; r >= 1; r = r / 2) {
            for(i = r; i < arr.length; i++) {
                tmp = arr[i];
                j = i - r;
                // 一轮排序
                while(j >= 0 && tmp < arr[j]) {
                    arr[j+r] = arr[j];
                    j -= r;
                }
                arr[j+r] = tmp;
            }
            System.out.println(i + ":" + Arrays.toString(arr));
        }
    }

快速排序

算法思想：基于分治的思想，是冒泡排序的改进型。首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法），然后分别从数组的两端扫描数组，设两个指示标志（lo指向起始位置，hi指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换lo和hi位置的值，然后从前半部分开始扫秒，发现有元素大于基准点的值，就交换lo和hi位置的值，如此往复循环，直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。

public static int partition(int []array,int lo,int hi){
        //固定的切分方式
        int key=array[lo];
        while(lo<hi){
            while(array[hi]>=key&&hi>lo){//从后半部分向前扫描
                hi--;
            }
            array[lo]=array[hi];
            while(array[lo]<=key&&hi>lo){从前半部分向后扫描
                lo++;
            }
            array[hi]=array[lo];
        }
        array[hi]=key;
        return hi;
    }
    
    public static void sort(int[] array,int lo ,int hi){
        if(lo>=hi){
            return ;
        }
        int index=partition(array,lo,hi);
        sort(array,lo,index-1);
        sort(array,index+1,hi); 
    }