排序(一)冒泡排序、选择排序、插入排序

一、基础知识

排序的稳定性:

在排序的过程中,数组中相等元素的相对顺序保持不变,则排序是稳定的。

原地排序算法:

在原始输入数组上完成的排序算法,没有申请额外的空间。

二、冒泡排序

步骤:
冒泡排序.png

比较两个相邻的元素,将值大的元素交换到右边。
(1)第一次比较:首先比较第一和第二个数,将小数放在前面,将大数放在后面。
(2)比较第2和第3个数,将小数放在前面,大数放在后面。
......
(3)如此继续,直到比较到最后的两个数,将小数放在前面,大数放在后面,重复步骤,直至全部排序完成。
(4)在上面一趟比较完成后,最后一个数一定是数组中最大的一个数,所以在比较第二趟的时候,最后一个数是不参加比较的。
(5)在第二趟比较完成后,倒数第二个数也一定是数组中倒数第二大数,所以在第三趟的比较中,最后两个数是不参与比较的。
(6)依次类推,每一趟比较次数减少依次。

时间复杂度分析:

若有n个元素,第一轮比较n-1次,第二轮比较n-2次,第三轮比较n-3次... 则,一共需要比较 n-1+n-2+n-3+...+1次,共 \frac{n (n-1)}{2} 次比较。所以,时间复杂度是:O(n^2)

代码实现:
package com.douma.line;

import java.util.Arrays;

public class BubbleSorter {
    public void bubbleSort(int[] data) {
        //一定要注意边界条件
        if (data == null || data.length <= 1) return;
        for (int round = 1; round <= data.length; round++) {
            //外层循环: 控制冒泡的轮数
            int compareTimes = data.length - round;
            //每一轮比较的次数 为 数组的长度 减去 轮数
            for (int i = 0; i < compareTimes; i++) {
                // 比较相邻的两元素,只有大于,才会交换;小于或等于 就不做任何处理。
                if (data[i] > data[i+1]) {
                    int tmp = data[i];
                    data[i] = data[i+1];
                    data[i+1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] data = new int[]{12,23,36,9,24,42};
        new BubbleSorter().bubbleSort(data);
        //System.out.println(data);
        //提醒:这样打印出来的是数组的地址。
        /*
        * Arrays.toString() 的作用是用来很方便地输出数组
        * */
        System.out.println(Arrays.toString(data));
    }
}
冒泡排序的特点:
  • 空间复杂度是 O(1),是原地排序算法。
  • 冒泡排序是稳定的排序算法。
冒泡排序优化:

当在一轮中没有元素交换,就不需要交换了。这样可以减少比较次数。

public void bubbleSort(int[] data) {
    if (data == null || data.length <= 1) return;
    for (int round = 1; round <= data.length; round++) {
        boolean hasSwap = false; // 优化
        //外层循环: 控制冒泡的轮数
        int compareTimes = data.length - round;
        //每一轮比较的次数 为 数组的长度 减去 轮数
        for(int i = 0; i < compareTimes; i++) {
            // 比较相邻的两元素,只有大于,才会交换;小于或等于 就不做任何处理。
            if (data[i] > data[i+1]) {
                int tmp = data[i];
                data[i] = data[i+1];
                data[i+1] = tmp;
                hasSwap = true; // 发生交换,设为true
            }
        }
        if (!hasSwap) break;
        // 如果不发生交换,说明该数组已经有序了。
        // 既然有序了,跳出round循环,不需要进行其他轮的比较了。
        // 这样优化可以减小比较的次数
    }
}

三、选择排序

选择排序,从头至尾扫描序列,找出最小的一个元素,和第一个元素交换,此时最小的元素就到了排序后正确的位置。接着从剩下的元素中再找一个最小的元素,和第二个元素交换,此时第二小的元素也排到正确的位置。然后再在剩下的元素中选择一个最小的元素,继续这种选择和交换方式。直到剩下的数列的选择范围为0,那么得到一个有序序列。

步骤:

数组data中6个元素:23,12,42,36,9,24。
第一轮:
i= 0,将最小数值元素索引设为i,即minNumIndex=0。
j 从1 开始遍历,将data[j]与data[minNumIndex]进行比较,并更新minNumIndex 的值。
直到j遍历结束,此时minNumIndex = 4。将data[4] 与 data[i] 进行交换。

第二轮:
i= 1,最小数值元素索引(minNumIndex)=1。
j 从2 开始遍历,将data[j]与data[minNumIndex]进行比较,并更新minNumIndex 的值。
直到j遍历结束,此时minNumIndex = 1。将data[1] 与 data[i] 进行交换。

第三轮:
i= 2,最小值索引(minNumIndex)=2。
j 从3 开始遍历,将data[j]与data[minNumIndex]进行比较,并更新minNumIndex 的值。
直到j遍历结束,此时minNumIndex = 4。将data[4] 与 data[i] 进行交换。

第四轮:
i= 3,最小值索引(minNumIndex)=3。
j 从4 开始遍历,将data[j]与data[minNumIndex]进行比较,并更新minNumIndex 的值。
直到j遍历结束,此时minNumIndex = 5。将data[5] 与 data[i] 进行交换。

第五轮:
i= 4,最小值索引(minNumIndex)=4。
j 从5 开始遍历,将data[j]与data[minNumIndex]进行比较,并更新minNumIndex 的值。
直到j遍历结束,此时minNumIndex = 5。将data[5] 与 data[i] 进行交换。

第六轮:
i= 5,最小值索引(minNumIndex)=5。只有一个元素,不用比较了。

时间复杂度分析:

若有n个元素,第一轮比较n-1次,第二轮比较n-2次,第三轮比较n-3次... 则,一共需要比较 n-1+n-2+n-3+...+1次,共 \frac{n (n-1)}{2} 次比较。所以,时间复杂度是:O(n^2)

代码实现:
public void sort(int[] data) {
    if (data == null || data.length <= 1) return;
    for (int i = 0; i < data.length; i++) {
        // 控制选择排序的轮数
        // (i元素之前保证有序)找到 [i, n) 中的最小元素所在的索引
        // i 是未排序元素中的第一个,j是第二个
        int minNumIndex = i;
        for (int j = i + 1; j < data.length; j++) {
            if (data[j] < data[minNumIndex]) {
                minNumIndex = j;
            }
        }
        // 将 data[i]和最小元素进行交换
        swap(data, i, minNumIndex);
    }
}
选择排序的特点:
  • 空间复杂度是 O(1),是原地排序算法。
  • 选择排序是不稳定的排序算法。
    如:5,8,5,2,9
    当第一个5和2交换时,这两个5的相对顺序变了。
    所以选择排序是不稳定的,也因此它的使用场景非常受限。

四、插入排序

拿到未排序区间的第一个元素,将与对排序区间的每个元素进行比较,插入。直到未排序区间的元素为空。(简单来说就是将一个元素插入到已经排好的序列中,插入之后序列依然有序。)

步骤:

data数组有6个元素:34 ,8 ,64 ,51 ,32 ,21 。每轮处理一个元素,每个元素都需要处理,有6个元素,所以需要6轮。

第一轮:
从第一个元素开始,i=0 ,j=0,自己和自己比,不用交换。此轮结束。
即:34 ,8 ,64 ,51 ,32 ,21 。

第二轮:
从第二个元素开始,i=1,需要把data[1]插入到前面有序的数组中。
此时指针j:j从i开始遍历,并比较data[j] 和data[j-1],如果data[j-1] > data[j],两者交换。j向前移动,此时data[j]无法与前一个元素进行比较,不用交换,此轮结束。
即:8 ,34 ,64 ,51 ,32 ,21 。

第三轮:
从第三个元素开始,i=2,需要把data[2]插入到前面有序的数组中。
此时指针j:j从i开始遍历,并比较data[j] 和data[j-1],即比较64和34。不用交换。此轮结束。
即:8 ,34 ,64 ,51 ,32 ,21 。

第四轮:
从第四个元素开始,i=3,需要把data[3]插入到前面有序的数组中。
比较51和64,交换两者。比较51和34,不用交换。此轮结束。
即:8 ,34 ,51 ,64 ,32 ,21 。

第五轮:
从第五个元素开始,i=4,需要把data[4]插入到前面有序的数组中。
比较32和64,交换。比较32和51,交换。比较32和34,交换。比较32和8,不用交换,此轮结束。
即:8 ,32,34 ,51 ,64 ,21 。

第六轮:
从第六个元素开始,i=5,需要把data[5]插入到前面有序的数组中。
比较21和64,交换。比较21和51,交换。比较21和34,交换。比较21和32,交换。比较21和8,不交换。此轮结束。
即:8 ,21,32,34 ,51 ,64 。

时间复杂度分析:
  • 遍历一遍数组,时间复杂度为O(n)。
  • 每轮遍历需要将一个元素插入到有序数组的正确位置,这个插入过程的最坏时间复杂度为O(n)。

所以时间复杂度为:O(n^2)

public void sort1(int[] data) {
    if (data == null || data.length <= 1) return;
    // 插入排序的轮数, 可以从第二个元素开始
    for (int i = 1; i < data.length; i++) {
        // 注意这里的j不能等于0
        for (int j = i; j > 0; j--) {
            if (data[j] < data[j - 1]) {
                swap(data, j , j - 1);
            } else {
                break;
            }
        }
    }
}
选择排序的特点:
  • 空间复杂度是 O(1),是原地排序算法。
  • 插入排序是稳定的排序算法。
插入排序的优化:

将原来代码中的“交换” 变成“赋值”。来减少元素的访问次数。

public void sort(int[] data) {
    if (data == null || data.length <= 1) return;
    // 插入排序的轮数
    for (int i = 1; i < data.length; i++) {
        int tmp = data[i];
        int j;
        for (j = i; j > 0; j--) {
            if (tmp < data[j - 1]) {
                // 将较大的元素总是向右移动
                data[j] = data[j - 1];
            } else {
                break;
            }
        }
        // 找到 i 对应的元素需要插入的位置
        data[j] = tmp;
    }
}

五、 比较三种算法的性能:

public class SortCompare {
    private static Random random = new Random();

    private static int[] genData(int n) {
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = random.nextInt();
        }
        return data;
    }

    private static long time(String sortType, int[] data) {
        long start = System.currentTimeMillis();

        if (sortType.equals("bubble")) new BubbleSort().sort(data);
        else if (sortType.equals("selection")) new SelectionSort().sort(data);
        else if (sortType.equals("insertion")) new InsertionSort().sort(data);
        
        return System.currentTimeMillis() - start;
    }
    // 生成k个长度为n的数组
    private static long manyTimesSort(String sortType, int n, int k) {
        long totalTime = 0;
        for (int i = 0; i < k; i++) {
            totalTime += time(sortType, genData(n));
        }
        return totalTime;
    }

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

推荐阅读更多精彩内容