排序第一记——交换排序(冒泡、快排)

今天开始复习一下排序,其实这个最近都有再捡起来练,毕竟太久远拿起来还挺不容易的。
简单说一下——自己复习排序的时候理解是这样的:基本的排序分为三类:交换排序、选择排序、插入排序。用一张图表示一下:


基本的排序

不得不说,我画的图简直太丑了......
将就看一下吧,大概是这样的。前面的话有点多了,直接进入今天的正题——交换排序。


冒泡排序:BubbleSort

冒泡排序应该是最简单的了吧?额,至少我个人觉得应该是最好理解的一种排序。
百度百科的原理:

1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤,除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

说起原理来感觉好难懂是吧???
其实可以简单去思考:为啥叫冒泡排序呢?
不知道有没有注意过水里的气泡,大的气泡会浮到上面去。冒泡排序也是:每一轮的排序,在这一轮中参与比较的元素中最大的数将会浮到最后。
时间复杂度之类的分析,我写在了备注中~~~
So,直接上代码:
请注意第二层for循环,循环次数会越来越小,简单思考一下就会发现:毕竟每轮过后相对来说最大的数都会排到应该在的地方去,所以如果再多比较那几次也没啥意义~

/**
 * Created by AceCream on 2017/3/19.
 * 冒泡排序BubbleSort(属于交换排序)
 * 时间复杂度: 平均:O(n^2)   最佳:O(n)   最坏:O(n^2)
 * 空间复杂度: O(1)
 * 稳定性: 稳定
 */
public class BubbleSort {

    public static void bubbleSort(int[] values){
        for (int i=0;i<values.length;i++){
            for (int j=i;j<values.length;j++){
                if (values[i]>values[j]){
                    int temp = values[i];
                    values[i] = values[j];
                    values[j] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int value[] = {1,7,5,8,3};
        bubbleSort(value);
        for (int result : value) {
            System.out.print(result+" ");
        }

    }
}


快速排序:Quicksort

为啥叫快速排序?因为他比别的排序快啊!当然这是一般情况下,也就是平均情况下,快速排序的时间复杂度是O(nlogn),这速度真的不要太快!
!!!但是!!!
“快速排序是最快的排序”,这句话是正确的吗???
答案是:“不准确!”

因为按照平均速度来说,它确实很快,但是如果“枢纽元”为最大或者最小数字,那这个时候简直就是灾难!对!灾难!它就直接成为了——冒泡排序(Ps:冒泡:“靠!这个锅,我不背!”)
具体这个“枢纽元”是啥?还是从快速排序的原理说起来:

快排原理

原理:

  • 确定一个基准值
  • 一次循环:从后往前比较,用基准值和最后一个值比较,
  • 如果比基准值小的交换位置,如果没有继续比较下一个,
  • 直到找到第一个比基准值小的值才交换。
  • 找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,
  • 如果没有继续比较下一个,直到找到第一个比基准值大的值才交换。
  • 直到从前往后的比较索引>从后往前比较的索引,结束第一次循环。
  • 此时,对于基准值来说,左右两边就是有序的了。
  • 接着分别比较左右两边的序列,重复上述的循环。

行了,看了原理,我相信基本上都懵逼了,我当初也是被快排折磨是不行,找了大量的文档,没看懂。后来自己每一步都在纸上写一遍,终于发现了其精髓所在!
简单来说,快速排序其实是冒泡排序的加强版!从成熟体化身为完全体!至于究极体,还得在其基础上继续优化~~
我们第一次循环中,确定的这个“基准值”,就是上文所述的“枢纽元”。
借用一下百科的图片:

快速排序

这个图挺好,但是“初始”和“一次划分”中间省略了很多步,我来补充一下:想象一下挖坑~
1.首先把第一个值,也就是49作为key值,取出来存坑里
2.从右边开始向左边,依次和key值比较,一旦发现比它小的了也就是27,就把27挖出来,填在它曾经的坑里(第一个位置)。这时候变成了这个样子:

27,38,65,97,76,13,27,49

3.那么这时候,出现了俩27,这第二个27,人已经走了,但是它的坑还在,很尴尬,咋办?我们继续走下一步,从左边开始比较(注意!就不要从第一个开始了,已经比较完了,就从38开始吧),比较谁?还是依次与key(49)比较,直到发现比key大的数,也就是65,这时候就把65,放到刚刚那个尴尬的坑里,把“坑里的值”更新掉~于是变成了这样:

27,38,65,97,76,13,65,49

然后把最开始挖出来的那个49填坑里

27,38,49,97,76,13,65,49

但是这样就结束第一此划分了吗?并没有,因为从start开始的left值和end开始的right值,还没有碰到一起(left<right),所以继续走,重复刚才的动作,直到他们相遇,这个时候:49左边的数都小于49,右边的数都大于或等于49。也就完成了第一次划分。
这之后我们看一下上面的图,以49为中心,分成了两个部分,这里就体现了“分治”的思想。将一个问题,分解成两个小的部分,分别做相同的操作。将两个部分做同样的操作,你想到了什么方式?对!递归!快速排序,体现了算法的两大思想:递归和分治。所以快速排序才这么重要。
这里多说一句,前面说过如果这个"枢纽元"选的不好,那就很尴尬了,比如说,这组数,我第一个值如果不是49而是13呢?那第一次划分后,13放在了最左边,我们再看第二个值,如果第二个值是27呢?以此类推,如果我的这串数字刚开始就比较有序,那么快排反而成为了冒泡啊!时间复杂度变为了N(n^2),所以说,快速排序并不稳定。
但是!我们不能因为这个就否定它,毕竟在大量的测试中,快速排序的速度是要优与堆排序和shell排序的。

是不是听起来很晕。自己动手(请在纸上)写一遍流程其实就懂得了~~

接下来,直接手敲代码:

/**
 * Created by AceCream on 2017/3/19.
 * 快速排序QuickSort (属于交换排序)
 * 原理:
 * 一次循环:从后往前比较,用基准值和最后一个值比较,
 * 如果比基准值小的交换位置,如果没有继续比较下一个,
 * 直到找到第一个比基准值小的值才交换。
 * 找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,
 * 如果没有继续比较下一个,直到找到第一个比基准值大的值才交换。
 * 直到从前往后的比较索引>从后往前比较的索引,结束第一次循环。
 * 此时,对于基准值来说,左右两边就是有序的了。
 * 接着分别比较左右两边的序列,重复上述的循环。
 *
 * 时间复杂度: 平均:O(nlog2n)   最佳:O(nlog2n)   最坏:O(n^2)
 * 空间复杂度: O(1)
 * 稳定性: 不稳定
 *
 */
public class QuickSort {

    private static void quickSort(int[] value, int start, int end) {
        int left = start;
        int right = end;
        int key = value[start];
        while (left<right){
            while (left<right&&value[right]>=key){
                right--;
            }
            if (left<right){
                value[left] = value[right];
                left++;
            }

            while (left<right&&value[left]<key){
                left++;
            }
            if (left<right){
                value[right] = value[left];
                right--;
            }

            value[left] = key;

            if (left>start) quickSort(value,start,left-1);
            if (right<end) quickSort(value,right+1,end);
        }
    }

    public static void main(String[] args) {
        int[] value = {49,38,65,97,76,13,27,49};
        int start = 0;
        int end = value.length-1;
        quickSort(value,start,end);

        //打印出来
        for (int result : value) {
            System.out.print(result+" ");
        }
    }
}

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

推荐阅读更多精彩内容

  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,222评论 0 52
  • 概述:排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    每天刷两次牙阅读 3,746评论 0 15
  • 一、 单项选择题(共71题) 对n个元素的序列进行冒泡排序时,最少的比较次数是( )。A. n ...
    貝影阅读 9,254评论 0 10
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,285评论 0 2
  • 这段时间反复的在思考一个问题,人一生的状态该是什么样呢?和闺蜜聊天,闺蜜说二胎吧!多子多福!于是围绕主题讨论了一翻...
    兰花子阅读 83评论 0 0