必须掌握的八种排序(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)代码实现

/**
 * 快速排序是其基本思想是基本思想是,通过一趟排序将待排记录分隔成独立的两部分,
 * 其中一部分记录的关键字均比另一部分的关键字小,
 * 则可分别对这两部分记录继续进行排序,以达到整个序列有序。
 * 步驟:
 *   1、从数列中挑出一个元素,称为 "基准"(pivot),
     2、重新排序数列,所有元素比基准值小的摆放在基准前面,
        所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,
        该基准就处于数列的中间位置。这个称为分区(partition)操作。
     3、递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。  
 * @author Administrator
 *
 */
public class QuickSort {

    public  void sort(){
        int a[] = { 11, 33, 44, 2, 0, 1, 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, 90 };

        quickSort(a,0,a.length-1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+"  ");
        }

    }
    /**
     * 
     * @param a  待排序数组
     * @param low  可以看做低位助手  
     * @param high 可以看做高位助手
     * 低助手是用来找比基准位大的数
     * 高助手是用来找比基准位小的数   这样就可以看做两个助手在活动
     */
    private  void quickSort(int[] a, int low, int high) {
        int start=low;//起始位置 0;
        int end=high; //结束位置
        int base=a[low]; //基准数 :一般是第一位
        int tempIndex=low; //找到的符合要求的位置:因为要把它的值付给基准数所在位置 所以要记录该位置 可以看做是助手移动到的位置
        while(low<high){
            //高助手从右向左找一个比基准位小的数 找到后给到低助手当前所在位置
            //没有找到的话 高助手向前移动一位
            while(low<high&&base<=a[high]){
                high--;
            }
            //找到时 把找到的数赋值给低助手所在位置
            a[low]=a[high];
            tempIndex=high;//记录当前助手位置

            //然后低助手从左向右找一个比基准数大的数 ,找到后给到高助手当前所在位置
            //没有找到的话 低助手向后移动一位
            while(low<high&&base>=a[low]){
                low++;
            }
            //找到后赋值给高助手当前所在位置
            a[high]=a[low];
            tempIndex=low;//记录当前助手位置

            //直到循环结束  -->低助手和高助手重叠 就把基准数赋到当前中轴重叠位置
            a[tempIndex]=base;

        }
        //以上第一次排序结束  把数列分成了前后两个部分
        //最后在对上面前后两个部分数列 分别递归
        if(low-start>1){//前部分至少有两个数据
            quickSort(a,0,low-1);
        }
        if(end-high>1){
            quickSort(a,high+1,end);
        }
    }

    public static void main(String[] args) {
        QuickSort q=new QuickSort();
        q.sort();
    }

}
目录
相关文章
|
7月前
|
算法 搜索推荐
排序——选择排序
排序——选择排序
70 0
|
算法 搜索推荐 索引
排序篇(二)----选择排序
排序篇(二)----选择排序
37 0
|
机器学习/深度学习 人工智能 搜索推荐
P1177 【模板】快速排序(二分排序)
P1177 【模板】快速排序(二分排序)
81 0
|
存储 算法 搜索推荐
【排序】排序这样写才对Ⅰ --插入排序与选择排序
常见的排序算法有这些.将会分成几个章节讲完,感兴趣的uu们可以关注下我的排序专栏,方便和后期观看.
61 0
|
算法 搜索推荐
排序——冒泡排序
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
|
搜索推荐
排序(2)之选择排序
继插入排序后,今天小编就给大家另一个模块,选择排序的学习,那么话不多说,我们直接进入正题。
117 0
|
索引
掌握常见的几种排序-选择排序
选择排序是一种简单的排序,时间复杂度是O(n^2),在未排序的数组中找到最小的那个数字,然后将其放到起始位置,从剩下未排序的数据中继续寻找最小的元素,将其放到已排序的末尾,以此类推,直到所有元素排序结束为止。
121 0
掌握常见的几种排序-选择排序
|
搜索推荐 算法 Java
排序:冒泡排序(算法)
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。
286 0
排序:冒泡排序(算法)
|
算法
排序——快速排序
排序——快速排序
120 0
排序——快速排序
|
算法 搜索推荐 Java
排序系列之冒泡排序
排序系列之冒泡排序
109 0