必须掌握的八种排序(5-6)--冒泡排序,快速排序

5、冒泡排序

(1)基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

(2)理解图

(3)代码实现

/**
 * 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,
 * 如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,
 * 也就是说该数列已经排序完成。
 * 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
 * 步驟:
 *    1、比较相邻的元素。如果第一个比第二个大,就交换他们两个。
      2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
      3、针对所有的元素重复以上的步骤,除了最后一个。
      4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
 * @author Administrator
 *
 */
public class bubbleSort {
    public bubbleSort() {
        int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35,
                25, 53, 51 };
        int temp = 0;
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
        for (int i = 0; i < a.length; i++)
            System.out.println(a[i]);
    }
}

6、快速排序

(1)基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

(2)理解图

(3)代码实现

public static void quickSort(int [] a,int left,int right){
        //快速排序算法   
        //找一个基准元素,把数组分为两个部分,前面一部分比基准元素小  后面一部分比基准元素大 保证前面一部分的元素都小于后面一部分的元素
        //一般以第一个元素作为基准元素
        //找两个助手 ,低助手和高助手  ,分别位于数组的两端
        //低助手从左往右找比基准元素大的元素 找到则交换 记录该位置 找不到的话 低助手索引加1
        //高助手从右往前找比基准元素小的元素,找到则交换 ,记录该位置,找不到的话,低助手索引减1
        //直到低助手和高助手重叠 ,则记录该位置   ,数组就被分成了两个部分 再对这两部分进行递归,再分成两部分  最后合即为排好序的数组

        if(left==right){
            return;
        }
        int partition=partition(a,left,right);
        //递归
        quickSort(a,left,partition);
        quickSort(a,partition+1,right);

    }  
    /**
     * 找中间位置的方法
     * @param a 待排序数组
     * @param left :低助手   低助手从左往右找比基准元素大的元素 找到则交换 记录该位置 找不到的话 低助手索引加1
     * @param right: 高助手  高助手从右往前找比基准元素小的元素,找到则交换 ,记录该位置,找不到的话,低助手索引减1
     */
    public static int partition(int [] a,int left,int right){
        int base=a[left];
        //找两个助手 ,低助手和高助手  ,分别位于数组的两端
        left--;
        right++;
        while(left<right){
            left++;
            while(a[left]<base){
                left++;
            }
            right--;
            while(a[right]>base){
                right--;
            }

            if(left<right){
                swap(a,left,right);
            }
        }
        return right;
    }
    //交换值的函数
    public static  void swap(int [] a,int i,int j){
        int temp;
        temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏积累沉淀

线程的其他特征

睡眠: //使用sleep控制线程运行 public class Test9 { /** * @param args */ ...

2019
来自专栏ccylovehs

JavaScript之深拷贝和浅拷贝

工作中会经常遇到操作数组、对象的情况,你肯定会将原数组、对象进行‘备份’ 当真正对其操作时发现备份的也发生改变,此时你一脸懵逼,到时是为啥,不是已经备份了么,怎...

1181
来自专栏Java成长之路

【天梯-wikioi】1203 判断浮点数是否相等

心得:自己当时没做出来, 当时自己不知道这个fabs函数, 所以算了很久也没算出来。

1022
来自专栏黑泽君的专栏

java中,方法参数是基本类型和引用类型的区别

当参数是基本类型时,在调用方法时将值传递到方法中,运行方法,运行结束方法退出,对原本main中定义的变量没有任何操作(方法中没有return)。即:此时只跟栈有...

1672
来自专栏pangguoming

理解js中的new

new 操作符 在有上面的基础概念的介绍之后,在加上new操作符,我们就能完成传统面向对象的class + new的方式创建对象,在Javascript中,我们...

4064
来自专栏cs

python的顺序程序设计

赋值 同步赋值:变量1,变量2,....变量n=表达式1,表达式2,.....表达式n 同步赋值首先计算右边n个表达式的值,然后同时将表达式的值赋给左边的n...

4236
来自专栏余林丰

1.比较排序之冒泡排序

  冒泡排序可以说是在排序算法中最为入门级别的算法之一了。因为其简单易于理解,常在课堂中作为排序的入门算法。   冒泡排序见名生意,其排序过程如同水里的泡一般由...

1926
来自专栏黑泽君的专栏

如何给线程起名字呢?

2281
来自专栏chenjx85的技术专栏

leetcode-645-Set Mismatch

22211
来自专栏青玉伏案

窥探Swift之函数与闭包的应用实例

今天的博客算是比较基础的,还是那句话,基础这东西在什么时候都是最重要的。说到函数,只要是写过程序就肯定知道函数是怎么回事,今天就来讨论一下Swift中的函数的特...

1975

扫码关注云+社区

领取腾讯云代金券