Java教程

【数据结构】十大排序算法的分析与实现

本文主要是介绍【数据结构】十大排序算法的分析与实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

排序算法

排序算法可以分为内部排序和外部排序。内部排序即在内存中完成,不需要额外的空间;也可以分为比较排序和非比较排序。下图是常见的十种排序算法的性能对比。稳定性是基于排序是否改变原始元素的相对位置做判断的。

1,冒泡排序

冒泡排序采用相邻元素两两对比,如果顺序有误就交换他们的顺序,这样一轮下来,最大或最小元素就会交换到最顶端。由于形式极其像一次次的冒泡,我们称之为冒泡排序。下面演示从小到大排序的情况:

/**
     * 冒泡排序:优化:如果一趟排序中没有发生冒泡,说明数组已经有序即可退出循环
     * @param arr
     */
    public static int[] bubbleSort(int[] arr) {
        boolean flag = false;
        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]) {
                    flag = true;
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
           //优化代码
            if (!flag) {
                break;
            } else {
                System.out.println("第" + (i + 1) + "次冒泡" + Arrays.toString(arr));
                flag = false;
            }
        }
        return arr;
    }

2,选择排序

即在每轮比较时,选择当前元素作为该轮可能的最值,如果大小有误,即更新交换这个最值。这样每轮下来就能确定一个数的位置。

/**
     * 选择排序
     * @param arr
     * @return
     */
    public static int[] selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = arr[i]; //选择一个作为最小值
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min) {
                   arr[j] = arr[j] + arr[i];
                    arr[i] = arr[j] - arr[i];
                    arr[j] = arr[j] - arr[i];
                }
                min = arr[i];
            }
        }
        return arr;
    }

3,插入排序

从第二个元素开始,逐个和第一个元素比较,如果合适,将该元素插入第一个位置;依次找到合适的元素插入第二个第三个位置。。

类似插入扑克牌的方式:从第二张扑克开始,依次与第一个位置的牌进行比较,顺序合适,即将元素插入第一个位置,别比较元素则相当于后移。

比较过程中,前部元素开始有序,后部元素是无序的。

/**
     * 插入排序
     * @param arr
     * @return
     */
    public static int[] insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            //当前需要插入的元素
            int current = arr[i];
            //被插入的位置,即当前数的前一个
            int preIndex = i - 1;
            while (preIndex >= 0 && current < arr[preIndex]) {
                //被插入位置的元素后移
                arr[preIndex +1] = arr[preIndex];
                //索引向前移动
                preIndex--;
            }
            //当前值插入的位置
            arr[preIndex + 1] = current;
        }
        return arr;
    }

4,希尔排序

希尔排序是在原有简单插入排序的基础上进行了改进,也称为缩小增量排序。比如对于1个已经有序的序列,在进行插入时,可能不必要的进行多次移动,影响效率。

思路:将序列按照某种增量gap(一般采用length/2)进行分割成组,对每组数据进行简单的插入排序;然后按照gap/=2的方式继续分组,重复上述方式。直到gap=1时,即剩下一组时,希尔排序的效果已经达到,此时序列已经大部分有序了,再进行简单的排序即可。

分组的目的是使得组内都有序,整体尽可能有序。

思考:为什么分组适合插入排序,可以看到这里的分组并不是简单的二分,而是按照间距分割,以往的插入排序两个位置交换,会移动位置间距里个元素,按照分组排序,只需一次移动间距个距离即可。

  /**
     * 希尔排序
     *
     * @param arr
     * @return
     */
    public static int[] shellSort(int[] arr) {
        //控制每次的步长
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //按照步长分组
            for (int i = gap; i < arr.length; i++) {
                //对每次分组的元素进行比较
                int preIndex = i - gap; //组内的前一个元素位置
                int current = arr[i];   //当前值
                //比较组内的所以元素,并移动位置
                while (preIndex >= 0 && arr[preIndex] > current) { 
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex -= gap;
                }
                //退出循环后,位置找到插入
                arr[preIndex + gap] = current;
            }
        }
        return arr;
    }

5,快速排序

快排原理:找一个元素作为基准值(一般选择第一个元素),将比其小的元素都放在右边,比其大的元素都放在左边。然后在左右序列中递归的执行此做法,直到每个左右序列中剩下一个元素,此时整个序列已经有序了。

思想:基于基准值将序列分为左右相对其有序的两部分,直到每个序列长为1。

做法:在每次的分组中,用基准值和最后一个元素比较,从后往前,直到找出一个比基准值小的元素,交换位置;然后从前往后,直到找到一个比基准值大的元素,交换位置。直到前后索引的相对位置发生改变,说明一轮结束,此时就可以确定一个基准值序列。然后依次在各左右序列中进行快排。

 /**
     * 交换数组内的两个元素
     * @param a
     * @param n
     * @param m
     */
    private void swap(int[] arr, int a, int b) {
//        异或交换,可能存在相等时的零值情况
        if(a==b){
            return;
        }else{
            arr[a] = arr[a] ^ arr[b];
            arr[b] = arr[a] ^ arr[b];
            arr[a] = arr[a] ^ arr[b];
        }
    }

    /**
     * 快速排序
     * @param arr
     * @param start 起始位置
     * @param end 终点位置
     * @return
     */
    public static void quickSort(int[] arr,int start,int end){
        //标记索引,记录当前位置
        int low = start;
        int high = end;
        int key = arr[low]; //基准值一般选择序列第一个元素
        while(start<end){
            //从后往前遍历,直到找到较小值
            while(start<end && arr[end]>=key){
                end--;
            }
            //退出时如果找到,即交换位置
            if(arr[end]<=key){
                swap(arr,start,end);
            }
            //从前往后遍历,直到找到较大值
            while(start<end && arr[start]<=key){
                start++;
            }
            if(arr[start]>=key){
                swap(arr,start,end);
            }
        }
        //一遍排序结束,基准值位置就确定了,即左边均小于它,右边均大于它
      
        //如果当前起始位置大于标记,说明左边序列仍有元素,对左序列递归进行快速排序
        if(start>low){
            quickSort(arr,low,start-1);
        }
        //如果当前终点位置小于标记,说明右边序列仍有元素,对右序列递归进行快速排序
        if(end<high){
            quickSort(arr,end+1,high);
        }
    }

6,归并排序

根据分治法的思想,:将序列等分成两个序列,分别对其进行归并排序,直到子序列长度为1;:对每个子序列进行合并,这里额外增加一个序列用于存放合并的结果。合并规则:分别从序列起始位置比较,小的即填充到结果集中;如果某一序列遍历完毕,直接将另一序列填充到结果集。

/**
     * 归并排序:分治思想,先分再治
     * @param arr
     * @return
     */
    public static int[] mergeSort(int[] arr) {
        //“分”结束的条件
        if (arr.length < 2) {
            return arr;
        }
        int mid = arr.length / 2;
        //均分成两个数组序列
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    /**
     * “治”:将"分"好的数组序列组合起来
     * @param left
     * @param right
     * @return
     */
    public static int[] merge(int[] left, int[] right) {
        //返回拼装好的结果数组
        int[] result = new int[left.length + right.length];
        //i,j,分别为左右序列的索引,index为结果集的索引
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length) //当序列的索引超过其长度时说明序列已经排完,只需将另一序加入结果集中即可
                result[index] = right[j++];
            else if (j >= right.length)
                result[index] = left[i++];
            else if (left[i] > right[j]) //左右序列的数据依次进行比较,小的加入到结果集中
                result[index] = right[j++];
            else
                result[index] = left[i++];
        }
        return result;
    }

总结:

顾名思义:

冒泡排序:相邻位置元素比较交换,最值会被交换到顶端形如冒泡;

选择排序:两轮for,每一轮选择一个目标值,比较交换;

插入排序:从第一个位置开始选择合适元素插入交换,序列前部有序;

希尔排序:分组的插入排序,在每个序列内进行插入排序;

归并排序:等分序列,使得序列内部有序;然后组合,使得序列整体有序。

快速排序:基于基准值将序列分为左右相对其有序的两部分,直到每个序列长为1。

这篇关于【数据结构】十大排序算法的分析与实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!