数据结构复习之排序算法复习(快排and希尔)Java版

五、快速排序

快速排序：通过一趟排序将要排序的数据分割成两个独立的部分，其中一部分比基准数据要小，另一部分比基准数据要大。整个切分过程递归执行，以此使整个数据变成有序序列

步骤：

• 设定一个分界值（一般为数据的第一个元素）
• 设置左右两个指针，右指针寻找小于分界值的元素，左指针寻找大于分界值的元素
• 当其中一方找到后停在那里等另一方，都找到后两人将元素交换位置
• 重复以上步骤
• 当左右指针指向同一元素时，将该元素与分界值元素交换位置
• 重复以上步骤

例：两个小朋友在有数字的格子上玩游戏，取第一个格子上的数为标准值，两人一块向中间走，右边的小朋友脚下的数字比标准值小就停下，之后左边小朋友走，走到脚下数字比标准值大的就停下，与另一个小朋友换位置。当小朋友相遇，将标准值与当前格子数字交换

图示：

当左右指针相遇后便从此处将数组分割为左右两部分

代码如下：

package SortTest;

import java.util.Random;

public class FastSortTest {
    public static void main(String[] args) {
        FastSortTest fastSortTest = new FastSortTest();
        int[] buildelement = fastSortTest.buildelement();
        fastSortTest.printSort(buildelement);
        System.out.println();
        fastSortTest.fast_split(buildelement,0,buildelement.length-1);
        fastSortTest.printSort(buildelement);
    }
    //建立长度为10的测试数组
    public int[] buildelement(){
        int[] element = new int[10];
        Random random = new Random();
        for (int i=0;i<10;i++){
            //生成0-10之间的随机数
            element[i] = random.nextInt(10);
        }
        return element;
    }
    //快速排序_拆分
    public void fast_split(int[] element,int lo,int hi){
        if(hi<=lo){
            return ;
        }
        int partition = fast_Sorted(element,lo,hi);
        fast_split(element,lo,partition-1);
        fast_split(element,partition+1,hi);
    }
    //快速排序算法
    public int fast_Sorted(int[] element,int lo,int hi){
        int base = element[lo];
        //左指针放在数组第一个元素处
        int left = lo;
        //右指针放在数组最后一个元素后一位
        int right = hi+1;
        while (true){
            //从右向左遍历，找到比基准元素小的元素
            while(base<=element[--right]){
                //右指针移动到最左边或左右指针已经相遇
                if(right==lo || left == right){
                    break;
                }
            }
            while (base>=element[++left]){
                //左指针移动到最右边或左右指针已经相遇
                if(left==hi || left == right){
                    break;
                }
            }
            if(left>=right){
                System.out.println(" 左指针："+left+",右指针："+right);
                break;
            }
            int temp = element[right];
            element[right] = element[left];
            element[left] = temp;
        }
        element[lo] = element[right];
        element[right] = base;
        return right;
    }
    //结果输出
    public void printSort(int[] element){
        for (int i=0;i<element.length;i++){
            System.out.print(element[i]+" ");
        }
    }
}

快速排序总结：

• 时间复杂度：O(nlogn)、最好时间复杂度O(nlogn)、最坏时间复杂度（每次都遍历全部数据，在最后一个元素处分组）为O(n^2)
• 空间复杂度：O(1)
• 稳定性：不稳定。例：6 8 7 6 3 5 9 4.第一次快排后6与3交换，两个6的相对位置变化

• 六、希尔排序

希尔排序：是一种缩小增量排序，是插入排序的改良版

步骤：

• 选定一个增长量、按照增长量对数据进行分组
• 分别对组进行插入排序
• 减小增长量，重复第二步操作

package SortTest;

import java.util.Random;

public class ShellSortTest {
    public static void main(String[] args) {
        ShellSortTest shellSortTest = new ShellSortTest();
        int[] buildelement = shellSortTest.buildelement();
        int[] ints = shellSortTest.shellSorted(buildelement);
        shellSortTest.printSort(ints);
    }
    //建立长度为10的测试数组
    public int[] buildelement(){
        int[] element = new int[10];
        Random random = new Random();
        for (int i=0;i<10;i++){
            //生成0-10之间的随机数
            element[i] = random.nextInt(10);
        }
        return element;
    }
    //插入排序算法
    public int[] shellSorted(int[] element){
        //确定增量 固定形式
        int h = 1;
        while (h<=element.length/2){
            h = 2*h+1;
        }
        //停止分组的条件为h=1 固定形式,while循环控制h每次缩小
        while (h>=1){
            //进行排序 从第二个元素开始i+1即进入下一个组
            for(int i = h;i<element.length;i++){
                //判断元素将元素放入当前组的有序区
                for (int j = i; j>=h;j-=h){
                    //如果该元素小于有序区中元素，进行位置交换
                    if (element[j]<element[j-h]){
                        int temp = element[j];
                        element[j] = element[j-h];
                        element[j-h] = temp;
                    }else{  //如果该元素大于有序区中元素，则将该元素直接加入有序区即可
                        //退出循环，去插入下一个元素，相当于每组元素交替插入
                        break;
                    }
                }
            }
            h=h/2;
        }
        return element;
    }
    //结果输出
    public void printSort(int[] element){
        for (int i=0;i<element.length;i++){
            System.out.print(element[i]+" ");
        }
    }
}

希尔排序总结：

• 时间复杂度：O(n^1.3)-O(n2)。无法具体得知。可以通过程序运行时间测试是优于插入排序的
• 空间复杂度：O(1)
• 稳定性：不稳定，组之间相同元素顺序可能被打乱