天天看点
返回

非递归的快速排序、归并排序

本文主要内容：

1.非递归的快速排序

2.归并排序

3.非递归的归并排序

4.简单的排序总结

5.简单的排序实验

- 快速排序

Arrays.sort（基本数据类型的数组）,基本使用快排

优化点：（1）基准值的选择

（2）做partition过程中是否考虑基准值相等的问题

（3）快排更适合对数据量比较大的场景使用，往往数据量比较小时，使用插入排序

  • 如何用非递归实现快速排序？

自己使用栈记录待排序区间的左右边界（栈）

首先定义一个栈，将数组末尾元素及数组首元素一次放入栈中，当栈不为空时循环继续，找到基准值，再依次往栈中放入元素。

  • 归并排序[左闭右开]

合并两个有序数组的过程:首先将数组分为两个区间然后分别排序，将两个有序数组合并的过程。

（0）平均切分待排序区间，如果带排序区间的左右两个小区间已经有序，则按照合并有序数组的方式，使最终区间有序

（1）先找到中间位置，划分左右两个小区间

（2）分治的思想，先排序左右两个小区间

（3）合并有序数组

时间复杂度：O(n*log(n))

空间复杂度：O(n)[申请一个额外的数组]

稳定性：稳定

优化点：（1）减少搬移的次数

（2）判断左边的最大的数与右边最小的数

应用：Arrays.sort(引用数据类型的排序) 归并排序

归并排序是一种最常见的外部排序：不是所有的操作都需要借助内存的排序，如果数据量大到内存放不下了，用归并排序来处理

内存有256M，现有10G的数据需要排序，怎么处理？

（1）排序好256M的数据，10G数据可以分成40G的有序小文件

（2）多路归并（40路归并）

归并排序的非递归

  • 排序总结

时间复杂度的角度：

（1）O(n^2) 插排/选择/冒泡

（2）O(n*log(n))堆排/快排/归并

（3）O(n^1.2) 希尔

空间复杂度的角度：

（1）O（1）：插排/选择/冒泡/希尔/堆排

（2）O（log（n））：快排

（3）O（n）：归并

稳定：插排/冒泡/归并

数据不敏感：选择/堆排/归并

分治：快排/归并 减治：插排/选择/冒泡/堆排

简单的排序实验

代码演示

public class Solution1 {
    //随机创建一个长度为10的数组
    public static int[] createArray(){
        Random random = new Random(20190829);
        int[] a = new int[10];
        for(int i = 0;i<a.length;i++){
            a[i] = random.nextInt(100);
        }
        return a;
    }
    //打印数组元素
    public static void showArray(int[] array){
        for(int i = 0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
    }
    //将数组中的两个下标所代表的元素交换
    public static void swap(int[] array,int a,int b){
        int t = array[a];
        array[a] = array[b];
        array[b] = t;
    }
    public static int partition(int[] array,int left,int right){
        //首先定义基准值为数组最后一个元素
        int indexPartition = array[right];
        //定义low指向数组首元素，定义high指向数组尾元素，当low小于high时循环继续
        int low = left;
        int high = right;
        while (low<high){
            while (low<high&&array[low]<=indexPartition){
                low++;
            }
            while (low<high&&array[high]>=indexPartition){
                high--;
            }
            //当两边都停止时，互相交换
            swap(array,low,high);
        }
        //low或high就为基准值
        swap(array,right,low);
        return low;
    }
    //快速排序非递归
    public static void quickSortNDG(int[] array){
        Stack<Integer> stack = new Stack<>();
        stack.push(array.length-1);
        stack.push(0);
        while (!stack.isEmpty()){
            int left = stack.pop();
            int right = stack.pop();
            if(left>right){
                continue;
            }
            int indexPartition = partition(array,left,right);
            //区间为：[left,indexPartition-1][indexPartition+1,right]
            stack.push(indexPartition-1);
            stack.push(left);

            stack.push(right);
            stack.push(indexPartition+1);
        }
    }
    //归并排序
    public static void mergeSort(int[] array){
        //左闭右开
        mergeSortInternal(array,0,array.length);
    }

    public static void mergeSortInternal(int[] array,int left,int right){
        //数组中只剩一个元素，或者没有元素
        if(left+1>=right){
            return;
        }
        //[left,mid)[mid,right)
        int mid = (left+right)/2;
        mergeSortInternal(array,left,mid);
        mergeSortInternal(array,mid,right);
        //合并有序数组
        merge(array,left,mid,right);
    }

    public static void merge(int[] array,int left,int mid,int right){
        int length = right-left;
        int[] extra = new int[length];
        int pLeft = left;
        int pRight = mid;
        int pExtra = 0;
        while (pLeft<mid&&pRight<right) {
            if (array[pLeft] <= array[pRight]){
                extra[pExtra++] = array[pLeft++];
            } else {
                extra[pExtra++] = array[pRight++];
            }
        }
        while (pLeft < mid) {
            extra[pExtra++] = array[pLeft++];
        }
        while (pRight < right) {
            extra[pExtra++] = array[pRight++];
        }
        for (int i = 0; i < length; i++) {
            array[left+i] = extra[i];
        }
    }
    //归并排序非递归
    public static void mergeFDG(int[] array){
        for(int i = 1;i<array.length;i = i*2){
            for(int j = 0;j<array.length;j = j+2*i){
                int low = j;
                int mid = j+i;
                int high = mid+i;
                if(mid>array.length){
                    continue;
                }
                if(high>array.length){
                    high = array.length;
                }
                merge(array,low,mid,high);
            }
        }
    }

    public static void main(String[] args) {
        int[] array = createArray();
        showArray(array);
        System.out.println();
        quickSortNDG(array);
        showArray(array);
        System.out.println();
        System.out.println("================================");
        mergeSort(array);
        showArray(array);
        System.out.println();
        mergeFDG(array);
        showArray(array);
        System.out.println();
    }
}

运行结果：

15 92 56 30 7 80 63 72 14 42 
7 14 15 30 42 56 63 72 80 92 
================================
7 14 15 30 42 56 63 72 80 92 
7 14 15 30 42 56 63 72 80 92 
           
//简单的排序实验
//需要写一个接口、实现接口的类、主类
//注意在idea中填入参数
public interface Sorts {
    String name();
    void sort(int[] array);
}

public class insertSort implements Sorts {
    @Override
    public String name() {
        return "直接插入排序";
    }

    @Override
    public void sort(int[] array) {
        for(int i = 0;i<array.length-1;i++){
            //有序：[0,i] 无序：[i+1,array.length-1]
            int key = array[i+1];
            int j = 0;
            for(j = i;j>=0;j--){
                if(key>=array[j]){
                    break;
                }
                array[j+1] = array[j];
            }
            array[j+1] = key;
        }
    }
}

public class selectSort implements Sorts {
    @Override
    public String name() {
        return "选择排序";
    }

    @Override
    public void sort(int[] array) {
        for(int i = 0;i<array.length;i++){
            //无序：[0,array.length-i) 有序：[array.length-i,array.length)
            int max = 0;
            for(int j = 1;j<array.length-i;j++){
                if(array[max]<array[j]){
                    max = j;
                }
                swap(array,max,array.length-i-1);
            }
        }
    }

    public static void swap(int[] array,int a,int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

public class Runner {
    private static final Sorts[] sorts = {new insertSort()};
    public static void main(String[] args) {
        if(args.length<2){
            System.out.println("需要指定序列的顺序以及数据量的大小");
            return;
        }
        String order = args[0];
        int size = Integer.parseInt(args[1]);
        int[] array;
        if(order.equals("顺序")){
            array = buildOrderArray(size);
        }else if(order.equals("逆序")){
            array = buildReverseArray(size);
        }else {
            array = buildRandomArray(size);
        }
        testSort(array);
    }
    public static int[] buildOrderArray(int size){
        int[] array = new int[size];
        for(int i = 0;i<size;i++){
            array[i] = i;
        }
        return array;
    }
    public static int[] buildReverseArray(int size){
        int[] array = new int[size];
        for(int i = size;i>0;i--){
            array[i] = i;
        }
        return array;
    }
    public static int[] buildRandomArray(int size){
        int[] array = new int[size];
        Random random = new Random(20190903);
        for(int i = 0;i<size;i++){
            array[i] = random.nextInt(100);
        }
        return array;
    }
    public static void testSort(int[] origin){
        for(Sorts sort:sorts){
            int[] array = Arrays.copyOf(origin,origin.length);
            long begin = System.nanoTime();
            sort.sort(array);
            long end = System.nanoTime();
            int[] second = Arrays.copyOf(origin,origin.length);
            Arrays.sort(second);
            if(!Arrays.equals(array,second)){
                System.out.println("排序错误");
            }
            System.out.printf("%s: 排序消耗的时间是: %.4f 毫秒%n",
                    sort.name(), (end - begin) * 1.0 / 1000 / 1000);
        }
    }
}
           
//直接插入排序的运行结果为：
直接插入排序: 排序消耗的时间是: 0.0085 毫秒
//选择排序的运行结果为：
选择排序: 排序消耗的时间是: 0.0165 毫秒
非递归快速排序 归并排序 非递归归并排序 简单的排序实验
上一篇: 归并排序—递归&amp;非递归 归并排序
下一篇: ros_control + ros + gazebo

继续阅读