排序

引言

为什么想起来最近写这一些列的文章,因为最近一个朋友吐槽面试的有67年工作经验的员工,连基本的排序都不能实现,所以想了下,如果让自己来做,能不能讲的清楚这一些列的排序。所以就动手写了这一系列的文章,也算是自己了解巩固下。

 

常用的排序算法

一、冒泡排序

二、选择排序

三、插入排序

四、快速排序

五、堆排序

六、归并排序

七、基数排序

八、希尔排序

九、桶排序

 

冒泡排序(Bubble Sort

冒泡排序也称为:沉降排序(SinkingSort),之所以有这两个名字和他的实现方法有关,因为冒泡排序的实现方式是将数据列表中的最小的数据往前移动,想水里面的气泡一样向上浮。这样也就对应着最大的数据,逐渐往后移动,对应着上浮的就是下沉。

冒泡排序每次只比较相邻的两个数字的大小,再将一个数字和后面数字继续比较大小,一轮比较完成后在比较下一轮数据。知道最终没有数据可以比较位置,排序结束。

 常见排序算法(一)插图

Java:

public class BubbleSort {

    public static void main(String[] args) {

        int[] a = new int[]{9, 2, 7, 8, 5, 6, 3, 4, 1};
        for (int i = a.length - 1; i >= 1; i--) {
            for (int j = 0; j < i; j++) {
                int temp1 = a[j];
                int temp2 = a[j + 1];
                a[j] = temp1 > temp2 ? temp2 : temp1;
                a[j + 1] = temp1 > temp2 ? temp1 : temp2;
                printArrays(a);
            }
        }

    }

    private static void printArrays(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + "、");
        }
        System.out.println();
    }

}

 

Out:

297856341

279856341

278956341

278596341

278569341

278563941

278563491

278563419

278563419

278563419

275863419

275683419

275638419

275634819

275634189

275634189

257634189

256734189

256374189

256347189

256341789

256341789

256341789

253641789

253461789

253416789

253416789

235416789

234516789

234156789

234156789

234156789

231456789

231456789

213456789

123456789

 

程序的实现逻辑很简单,变及数组,依次将两个数字做比较,如果小的在大的前面,那么换一个位置,否则位置不换,继续拿大的和后面的比较。重复实现逻辑,为什么外面循环用i--,呢,因为每次我们实现一次排序,总能得到一个最大值,这个值,一定是排在了这个数组的最后一个,所以,最后面的一个我们是不需要比较的,这样无形中也就减少了运算。

从代码实现上来看,冒泡排序的时间复杂度为:O(n2);简单的说执行速度,取决于for循环的次数,链表的大小。

选择排序(Selection sort

选择排序是一种很直观简单暴力的排序算法,简单的说,就是,先遍历一遍数据,把最小的数据找出来,交换位置,放在第一位,然后在从把后面的链表继续遍历,找出最小数据,然后在,交换位置,继续遍历后续链表。知道全部遍历完成

常见排序算法(一)插图1

    常见排序算法(一)插图2 

public static void main(String[] args) {
    int[] a = new int[]{9, 2, 7, 8, 5, 6, 3, 4, 1};


    for (int i = 0; i < a.length; i++) {
        int min = i;
        for (int j = i; j < a.length; j++) {
            if (a[min] > a[j]) {
                min = j;
            }
        }
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
        printArrays(a);

    }


}

 

从代码实现上来看,选择排序的时间复杂度为:O(n2);简单的说执行速度,取决于for循环的次数,链表的大小。

上面的排序,我们不难看出,每次排序,其实我们不仅可以找到最小值,还可以找到最大值,这种情况,我们可以将排序算法优化下

public static void main(String[] args) {
    int[] a = new int[]{4, 2, 1, 7, 5, 8, 3, 9, 6, 8, 7, 0, 9, 2, 3,10,2,23,1,2,3,2,2,2,2};

    for (int i = 0; i < a.length - i; i++) {

        int min = i;
        int max = i;
        for (int j = i; j < a.length - i; j++) {

            if (a[min] > a[j]) {
                min = j;
            }
            if (a[max] < a[j]) {
                max = j;
            }
        }
        if (min != max) {

            int maxTemp = a[a.length - i - 1];
            a[a.length - i - 1] = a[max];
            a[max] = maxTemp;

            int temp = a[i];
            if (a[i] > a[min]) {
                a[i] = a[min];
                a[min] = temp;
            }
            printArrays(a);

        }
    }

}

每次排序同时将最小的放在最前面,将最大的放在最右边,循环的时候,也不需要每次都循环到链表的最后段,每次循环都踢掉链表的两端,在进行排序操作.

实际上这两种写法,在效率上相差并不大,下面那种虽然在循环次数上变少了,但是循环类的操作变复杂了。之所以这样写,只是说明下,我么并不是只能每次找最小的数,也可以按照需要,变换写法。

插入排序(Insertion Sort)

   插入排序是一种最简单的排序算法,在数据量小的情况下,是一种非常有效的排序方式,

他的核心思想,保证轮询到的数据前面的链表部分是顺序的,将需要比较的数字和前面的排序完成的链表进行比较,插入到一个合适的位置。

常见排序算法(一)插图3

常见排序算法(一)插图4

public static void main(String[] args) {

    int[] a = new int[20];
    for (int i = 0; i < 20; i++) {
        int random = (int) (Math.random() * 10);
        a[i] = random;
    }

    for (int i = 1; i < a.length; i++) {

        int current = a[i];
        int seq = i;
        while (seq > 0) {
            int temp = a[seq - 1];
            if (current >= temp) {
                break;
            } else {
                a[seq - 1] = current;
                a[seq] = temp;
            }
            seq--;
        }
    }
    printArrays(a);

}

 

插入排序比较适合.属于稳定的排序,适合于数据量小,部分数据有序的情况排序。他比较依赖于原链表的混乱程度。

当链表是有序的,也就是最优情况下,每个数只要和前面的一个数想比较,就可以了。这时候的时间复杂度是O(n);

当然逆向来说,如果链表是有序的,但是和我们需要排序的规则是相反的,那么每个数字都要和前面的所有数字比较。这个时候,时间复杂度就变成了O(n2)

 

 

481 对 “常见排序算法(一)”的想法;

  1. Pingback: best buy cialis
  2. Pingback: sildenafil 50mg uk
  3. It’s perfect time to make a few plans for the long
    run and it’s time to be happy. I have read this publish
    and if I could I desire to recommend you few attention-grabbing issues or advice.
    Perhaps you can write subsequent articles referring to
    this article. I want to read more things about it!

  4. One thing I would like to say is always that car insurance canceling is a hated experience and if you are doing the best things as a driver you simply will not get one. Lots of people do obtain the notice that they are officially dumped by their own insurance company and many have to fight to get added insurance from a cancellation. Low cost auto insurance rates are often hard to get after the cancellation. Knowing the main reasons for auto insurance termination can help car owners prevent sacrificing one of the most essential privileges accessible. Thanks for the tips shared through your blog.

  5. Pingback: viagra savings
  6. One other issue issue is that video games are generally serious in nature with the main focus on studying rather than enjoyment. Although, there is an entertainment element to keep your sons or daughters engaged, each and every game will likely be designed to work on a specific set of skills or program, such as math or science. Thanks for your write-up.

  7. Hey there would you mind letting me know which hosting
    company you’re using? I’ve loaded your blog in 3 different browsers
    and I must say this blog loads a lot faster then most. Can you recommend a good hosting provider at a honest price?
    Thanks a lot, I appreciate it!

  8. I really love your website.. Great colors & theme. Did you
    build this amazing site yourself? Please reply back as I’m wanting to create my own site and would love to learn where you got
    this from or just what the theme is named. Appreciate it!

  9. It’s appropriate time to make some plans for the future and it’s time
    to be happy. I have read this post and if I could I want to suggest
    you some interesting things or advice. Maybe you
    can write next articles referring to this article.
    I want to read even more things about it!

  10. Its like you read my mind! You seem to grasp a lot about this, like you wrote the e book
    in it or something. I feel that you just could do with
    some p.c. to power the message home a bit, but instead of that,
    that is wonderful blog. A fantastic read. I’ll certainly
    be back.

  11. It’s appropriate time to make some plans for the long run and it is time to be happy.
    I’ve read this post and if I may just I desire
    to recommend you few fascinating things or tips.
    Perhaps you can write next articles relating to this article.
    I wish to learn even more things about it!

  12. Hello would you mind letting me know which hosting company you’re utilizing?
    I’ve loaded your blog in 3 completely different web browsers and I must say this blog loads a lot faster then most.
    Can you recommend a good web hosting provider at a honest price?
    Cheers, I appreciate it!

  13. Pingback: duloxetine hcl dr
  14. It’s perfect time to make some plans for the future and it’s time to be
    happy. I’ve read this post and if I could I wish to
    suggest you few interesting things or tips. Maybe you can write next articles referring to this article.
    I wish to read more things about it!

  15. Pingback: metformin dosage
  16. I’ve been surfing online more than 3 hours today, yet I never found any interesting article like yours.
    It’s pretty worth enough for me. In my opinion, if all site owners and bloggers made good content
    as you did, the internet will be a lot more useful than ever before.

  17. It is perfect time to make a few plans for the long run and it’s time
    to be happy. I have learn this submit and if I may I want to counsel you some attention-grabbing issues or suggestions.
    Maybe you can write subsequent articles regarding this article.
    I want to read more things approximately it!

  18. Pingback: bupropion er
  19. Pingback: finasteride generic
  20. Pingback: flagyl 500
  21. Pingback: cialis 20mg daily
  22. Pingback: cheap sildenafil
  23. Pingback: vardenafil buy
  24. Pingback: aricept 10 mg
  25. Pingback: cefdinir antibiotic
  26. Pingback: what is cephalexin
  27. Pingback: cheap zithromax
  28. Pingback: cialis on sale
  29. Pingback: cialis 20mg price uk
  30. Pingback: vardenafil cheap
  31. Pingback: cialis 40mg generic
  32. Pingback: tadalafil 10mg
  33. I have been exploring for a little for any high quality articles or weblog posts on this kind of area .

    Exploring in Yahoo I finally stumbled upon this website.
    Studying this info So i am satisfied to show that I have an incredibly
    just right uncanny feeling I found out just what I needed.
    I most indubitably will make certain to do not forget this website and give
    it a look on a continuing basis.

  34. Avantajlı Fiyatlarla Takipçi Satın Al

    Sosyal medya hesaplarında etkileşimi arttırmanın en hızlı yolu İnstagram takipçi
    satın al yada instagram beğeni satın al hizmetidir.

    Sosyal medya da bir kişiyi ya da kanalı takip etmeden önce mutlaka takipçi
    sayısına dikkat edilir. Bunun sebebi ise bu kadar çok kişi takip
    ediyor ise takip edilmeye değerdir psikolojisi yer almaktadır.

    Takipçi sayısı fazla, beğeni ya da etkileşimi yüksek her hesap doğal yoldan takipçi kazanma
    potansiyeline sahip olmaktadır.

    Bu nedenle yeni bir sosyal medya hesabı üzerinden paylaşım yapıyor ya da ürün satışı yapmak istiyorsanız çok az takipçi sayısı ile
    bunu başarmanız mümkün değildir. instagram
    Takipçi Satın Al
    işlemi yaparak kısa sürede takipçi sayısını arttırmanız mümkün olacaktır.

  35. Pingback: levitra 40 mg generic
  36. Hi there! I understand this is sort of off-topic however
    I needed to ask. Does building a well-established blog like yours
    require a large amount of work? I’m brand new to running a blog but I do write
    in my journal every day. I’d like to start a blog so I will be
    able to share my personal experience and thoughts online.
    Please let me know if you have any kind of recommendations or
    tips for brand new aspiring bloggers. Appreciate it!

  37. Unquestionably imagine that which you said.
    Your favorite reason appeared to be on the internet the easiest thing to be mindful of.
    I say to you, I certainly get annoyed whilst other people
    think about worries that they plainly do not realize about.
    You managed to hit the nail upon the highest and also defined out the whole
    thing without having side-effects , other people can take a signal.
    Will likely be again to get more. Thanks