快速排序(Java)

快速排序(Quicksort)是对冒泡排序的一种改进。

其主要思路是:

①首先选择一个基准元素,元素可以在待排序序列中随机选取

②把基准元素当做当做一把标尺,对待排序集合进行一遍筛选,使得基准元素左边的元素均小于自身,右边元素均大于自身,由此便将待排序集合分成了两个子区间。

③左右两个子区间分别独立的进行排序,两区间内再选取一个基准元素......以此递归,当左右两边都排好序之后,整个集合也就排好顺序。

实现代码如下

public class QuickSort {//不稳定排序
    public void quick(int[] a){
        if(a.length>0){
            quickSort(a,0,a.length-1);
        }
    }

    /**
     * 快速排序
     * @param a
     */
    private void quickSort(int[] a,int low,int high) {
        if(low<high){
            int middle = getMiddle(a,low,high);//找基准元素
            quickSort(a,0,middle-1);//递归,排列基准元素左边的子区间
            quickSort(a,middle+1,high);//递归,排列基准元素右边的子区间

        }
    }

    /**
     * 获取基准元素的下标
     * @param a
     * @param low
     * @param high
     * @return
     */
    private int getMiddle(int[] a, int low, int high) {
        int tep = a[low];//基准元素
        while (low<high){
            while (low<high&&a[high]>=tep){
                high--;
            }
            a[low] = a[high];
            while (low<high&&a[low]<=tep){
                low++;
            }
            a[high] = a[low];

        }

        a[low] = tep;//插入到排序后正确的位置
        return low;
    }
//测试代码!
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] a= {12,1,52,63,26,49,-1,59,100,-2,29,87,55,63,77};
        quickSort.quick(a);
        for (int num:a) {
            System.out.println(" "+num);
        }
    }
}

运行结果

TIM截图20191110200926.png

性能分析

快速排序的一次划分算法从两头交替搜索,直到low和high重合,因此其时间复杂度是O(n);而整个快速排序算法的时间复杂度与划分的趟数有关。

理想的情况是,每次划分所选择的中间数恰好将当前序列几乎等分,经过log2n趟划分,便可得到长度为1的子区间。这样,整个算法的时间复杂度为O(nlog2n),其实,快速排序的平均时间复杂度也是O(nlog2n)。

最坏的情况是,每次所选的中间数是当前序列中的最大或最小元素,这使得每次划分所得的子区间中一个为空,另一子区间的长度为原区间的长度减1。这样,长度为n的集合的快速排序需要经过n趟划分,使得整个排序算法的时间复杂度为O(n2)。

从空间性能上看,尽管快速排序只需要一个基准元素的辅助空间,但快速排序需要一个栈空间来实现递归。最好的情况下,即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子区间,所需栈的最大深度为log2(n+1);但最坏的情况下,栈的最大深度为n。这样,快速排序的空间复杂度为O(log2n))。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 一、 单项选择题(共71题) 对n个元素的序列进行冒泡排序时,最少的比较次数是( )。A. n ...
    貝影阅读 9,245评论 0 10
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,220评论 0 52
  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可...
    意识流丶阅读 3,206评论 2 9
  • 经典的排序算法 冒泡排序(O(n2)):排序区间按N、N - 1、N - 2、……、2的规律变化,有序区间按1、2...
    雨住多一横阅读 674评论 0 0
  • 俗话说“台上一分钟,台下十年功”,每一个好的表演者都是经过漫长的努力练就的一身功夫。 那一天,她站在台上,我坐在台...
    清茶伴酒阅读 660评论 1 0