快排

一、(1)
假如有一个数组 [8,10,2,3,6,1,5] ,我们拿出5作为参考,将小于5的数放到它的左边,大于5的数放到它的右边,经过这一轮操作之后,数组就变成了[2,3,1,5,6,8,10]。

接下来我们可以运用上面的方法对左右两边进行操作了。
左边:[2,3,1] 拿出来1,小的放左边,大的放右边,[1,2,3]
右边:[6,8,10] 拿出来10,小的放左边,大的放右边,[6,8,10]

其实每一轮操作就相当于让这个参考数字回到正确位置的操作,它的前面有几个数,后面有几个数,在后面的操作中是不会变的。

(2)
实际操作中,为了节省内存,在将元素拿到参考数字两边的时候会采用交换元素的方式。分别从两边开始找符合条件的元素,等两边都找到之后进行交换。

[8,10,2,4,3,6,1,5]  --> 符合条件的,左:8,右:1,进行交换--> [1,10,2,4,3,6,8,5]
[1,10,2,4,3,6,8,5]  --> 符合条件的,左:10,右:3,进行交换--> [1,3,2,4,10,6,8,5]
....

二、代码:

    public static void sort(int a[], int low, int hight) {
        int i, j, index;
        if (low > hight) {
            return;
        }
        i = low;
        j = hight;
        index = a[i]; // 用子表的第一个记录做基准
        while (i < j) { // 从表的两端交替向中间扫描
            while (i < j && a[j] >= index) {
                j--;
            }
            if (i < j) {
                // a[i++] = a[j];// 用比基准小的记录替换低位记录
                a[i] = a[j];
            }
            while (i < j && a[i] < index) {
                i++;
            }
            if (i < j) { // 用比基准大的记录替换高位记录
                // a[j--] = a[i];
                a[j] = a[i];
            }
        }
        a[i] = index;// 将基准数值替换回 a[i]
        sort(a, low, i - 1); // 对低子表进行递归排序
        sort(a, i + 1, hight); // 对高子表进行递归排序

    }

    public static void quickSort(int a[]) {
        sort(a, 0, a.length - 1);
    }

三、通过稳定性、时间复杂度、空间复杂度三个方面分析一下归并排序:
1、稳定性
显然,在进行元素交换的时候,相同元素的前后顺序会发生变化,所以快排是不稳定的。

2.时间复杂度
//www.greatytc.com/p/6cf2cf701c57
和归并算法都采用了分治思想,所以他们的复杂度是一样的,都为O(nlogn)

3.空间复杂度
前面已经论述过为了降低空间复杂度采用了交换的方法,之后的复杂度为O(1)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,423评论 6 491
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,147评论 2 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,019评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,443评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,535评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,798评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,941评论 3 407
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,704评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,152评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,494评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,629评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,295评论 4 329
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,901评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,742评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,978评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,333评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,499评论 2 348

推荐阅读更多精彩内容

  • 本文摘自https://blog.csdn.net/yzllz001/article/details/509828...
    WorldPeace_hp阅读 511评论 0 0
  • 一、快速排序1、定义快速排序是对冒泡排序的一种改进。其基本思想是:通过一趟排序将待排序记录分割成独立的两部分,其中...
    Qi0907阅读 1,822评论 0 1
  • 思想: 快排法主要是运用二分法的思想来对一批数字进行排序,这种排序方法好处是比冒泡排序节省时间,因为冒泡排序是两两...
    逍然阅读 1,708评论 0 1
  • 快速排序的三个步骤: 选择基准:在待排序列中,按照某种方式挑出一个元素,作为 "基准"(pivot) 分割操作:以...
    萧何爱英语阅读 1,139评论 0 0
  • 转:微信公众号:程序员小灰 快排算法 是按分治算法的思路进行排序的。 选定参照元素后,每次比较都按分治算法将小的移...
    markDownMan阅读 1,272评论 0 0