快速排序算法详解

吃猫的鱼
2023-02-16 / 0 评论 / 215 阅读 / 正在检测是否收录...

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一
部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序
过程可以递归进行,以此达到整个数据变成有序序列。

需求

排序前:{6, 1, 2, 7, 9, 3, 4, 5, 8}

排序后:{1, 2, 3, 4, 5, 6, 7, 8, 9}

排序原理

  1. 首先将默认第一个元素为关键值key,设置好关键值key后基于key进行排序。
  2. 将大于或等于key的元素放到到数组右边,小于key的元素放到数组的左边。此时左边部分中各元素都小于
    或等于key,而右边部分中各元素都大于或等于key;
  3. 然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个key,将该部分数据分成左右两
    部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
  4. 重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当
    左侧和右侧两个部分的数据排完序后,整个数组的排序也就完成了。

快速排序示例详解图

示例代码

public class Quick {
    /*
  比较v元素是否小于w元素
*/
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
    /*
   数组元素i和j交换位置
    */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    /*
    对组内元素进行排序
     */
    public static void sort(Comparable[] a){
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);
    }
    //对数组a中从索引lo到索引hi之间的元素进行排序
    private static void sort(Comparable[] a, int lo, int hi) {
        if(lo>=hi){
            return;
        }
        //需要对数组中lo索引到hi索引处的元素进行分组(左子组和右子组);
        int partition = partition(a, lo, hi);//返回的是分组的分界值所在的索引,分界值位置变换后的索引

        //让左子组有序
        sort(a,lo,partition-1);

        //让右子组有序
        sort(a,partition+1,hi);
    }
    private static int partition(Comparable[] a, int lo, int hi) {
        int key = lo;
        int begin = lo;
        int end = hi+1;
        while(true){
            while(less(a[key],a[--end])) {              //如果右边的元素小于key
                if (end == lo) {
                    break;
                }
            }
            while(less(a[++begin],a[key])){          //从左边开始轮
                if(begin==hi){
                    break;
                }
            }
            //判断 left>=right,如果是,则证明元素扫描完毕,结束循环,如果不是,则交换元素即可
            if (begin>=end){
                break;
            }else{
                exch(a,begin,end);
            }
        }
        exch(a,key,end);
        return end;
    }

快速排序时间复杂度

快速排序是冒泡排序的的基础上改进的,但是效率比冒泡排序要高很多,因其跳跃性大,而冒泡排序只是相邻的两个数,每次排序只能和旁边交换,跳跃性比较小,因此效率相对比较低。

在一般情况下,快速排序的时间复杂度为O(log n),而在最差情况下则是每次交换只交换一个元素,此时的时间复杂度为O(n)。

快速排序是一个不稳定的算法,在经过排序之后,可能会对相同值的元素的相对位置造成改变。

快速排序基本上被认为是相同数量级的所有排序算法中,平均性能最好的。


3

评论 (0)

取消
友情链接 文章阅读: 网站地图