文档章节

排序---冒泡排序、快速排序、选择排序、插入排序、希尔排序

o
 osc_wws45aot
发布于 2019/08/20 09:20
字数 1553
阅读 13
收藏 0
dcc

精选30+云产品,助力企业轻松上云!>>>

1.冒泡排序   O(n2)

    基本思路:在要排序的一组数中,从第一个元素开始,依次对比当前元素和下一个元素,让较大的数往后沉,较小的数往前冒。即当发现相邻的两个数和排序的要求相反时,就交换它们的位置。
    
    
 int[] arr = {5,8,2,4,9,1,3,6,7};
     // 1. 冒泡排序。外层循环控制循环次数,内层循环比较数据 
     @Test
     public void fun () {
          for(int i = 0; i < arr.length - 1; i++) {
              for (int j = 0; j < arr.length-1-i; j++) {
                   if (arr[j] > arr[j+1] ) {
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                   }
              }
          }
          out();
     }
// 冒泡排序优化
     @Test
     public void fun1() {
          boolean flag;
          for(int i = 0; i < arr.length-1; i ++) {
              // 标识,用来判断数组是否发生了交换
              flag = false;
              for (int j = 0; j < arr.length-1-i; j++) {
                   if (arr[j] > arr[j+1] ) {
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                        flag = true;
                   }
              }
              // 当一轮下去之后,数组未发生任何交换,则表示排序已经完成
              if (!flag) {
                   break;
              }
          }
     }

 


 

2.快速排序

    基本思想:选择一个基准元素a(通常找第一个元素),目标是让a左边的元素都小于a,右边的元素都大于a。具体方法是:从数组两端开始探测,左边初始为哨兵i,右边为哨兵j。从左往右依次找一个大于基准数a的数,从右往左依次找一个小于基准数a的数,交换它们。当两个哨兵相遇,交换哨兵所在位置的元素和基准数,一次探测结束。接着对左右两边分别进行探测,直至排序完成。右边的哨兵要先探测,因为左哨兵所在位置是的元素是小于基准数的,而当最终左右哨兵相遇的时候需要将基准数和哨兵所在位置交换,因此这时候交换的数应该是小于基准数的,即满足基准数左边的元素都小于它。
     
int[] arr = {5,8,2,4,9,1,3,6,7};
     @Test
     public void fun2() {
          int low = 0;  // 左哨兵位置,从左向右寻找小于基准数的数
          int high = arr.length - 1;   // 右哨兵位置,从右向左寻找大于基准数的数
          quickSort(low, high);
          out();
     }
     // 2.快速排序---哨兵法
     private void quickSort(int low, int high) {
          if(low>high){
            return;
        }
          int tmp = arr[low];     // 基准数
          int i = low;
          int j = high;
          while (i < j) {
              // 先移动右哨兵,依次往左递减
              while (arr[j] >= tmp && i < j) {
                   j -- ;
              }
              // 再移动左哨兵,依次往右递增
              while  (arr[i] <= tmp && i < j) {
                   i ++ ;
              }
              // 交换
              if (i < j) {
                   int flag = arr[i];
                   arr[i] = arr[j];
                   arr[j] = flag;
              }
          }
          // 此时跳出循环,表明两个哨兵相遇,搜寻结束,交换基准数和哨兵所在位置
          arr[low] = arr[i];
          arr[i] = tmp;
          
          // 对基准数左边进行排序,基准数位置现在在j和i
          quickSort(low, j - 1);
          
          // 对右半边进行排序
          quickSort(j + 1, high);
     }  
// 快速排序,填坑法
     public void quickSort2(int low, int high) {
          while(low > high) {
              return;
          }
          int i = low;
          int j = high;
          int tmp = arr[low];     // 挖出arr[low]记为基准数,这是一个坑
          while(i < j) {
              // 从右向左寻找比基准数tmp小的数,找到后填补arr[low]的坑,这时arr[j]变为新的坑
              while(i < j && arr[j] >= tmp) {
                   j--;
              }
              // 跳出循环,说明找到比基准数小的数了
              if (i < j) {
                   arr[i] = arr[j];
                   i++;
              }
              // 从左向右寻找比基准数大的数,找到后填补arr[j]的坑,这时arr[i]变为新的坑
              while(i < j && arr[i] <= tmp) {
                   i++;
              }
              if (i < j) {
                   arr[j] = arr[i];
                   j--;
              }
          }
          //循环结束,表明i和j相遇,将最后一个坑填上
          arr[i] = tmp;
          quickSort2(low, i - 1);
          quickSort2(i + 1, high);
     }

 


 3.选择排序   O(n2)

    基本思想:在长度为n的数组中,第一次遍历n-1个数,找到最小的数与第一个元素交换;第二次遍历n-2个数,找到最小的值与第二个元素交换... ... 
/
/ 选择排序
@Test
public void fun8() {
  int tmp;
  // 最后一个元素不需要再对其进行一次排序,因为前面的元素已经完成了排序,则最后一个元素必定已排序过
  for(int i = 0; i < arr.length - 1; i++) {
    int index = i;
    // 这里需要对i之后的所有元素都比较一下,防止有漏掉的
    for (int j = i; j < arr.length; j++) {
      if (arr[j] < arr[index]) {
        index = j;
      }
    }
    if (index != i) {
      tmp = arr[i];
      arr[i] = arr[index];
      arr[index] = tmp;
    }
  }
  out();
}

 


 

4.插入排序   O(n2)

    基本思想:在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使得这n个数也是有序的。如此反复循环,直到全部排好序。
    
    相同的场景
     
//插入排序
     @Test
     public void fun13() {
          for(int i = 1; i < len; i++) {
              for(int j = i; j > 0; j--) {
                   if (arr[j] < arr[j - 1]) {
                        int tmp = arr[j];
                        arr[j] = arr[j-1];
                        arr[j-1] = tmp;
                   }
              }
          }
          out();
  }

 


5.希尔排序

    基本思想:这个排序又称为缩小增量排序。设待排序数组长度为n,取一个整数index(小于n)作为间隔将数组分为index个子序列,所有距离为index的元素放在一个子序列中,对每一个子序列分别进行直接插入排序。然后缩小index,重复上述子序列划分和排序工作。直至最后取到index=1将所有元素放在一个序列中进行排序。        由于开始时,index的取值比较大,每一个序列中的元素比较少,因此排序速度很快。到后面index逐渐增大,子序列中元素个数增加,但由于前面的工作基础,大多数元素已经是有序状态,所以排序速度依然很快。
    
// 希尔排序
     @Test
     public void fun14() {
          int index = len;
          while(true) {
              index = index/3 + 1;         // 增量,每次在当前增量的基础上除3再加1
              for(int i = 0; i < index; i++) {  // 根据增量进行分组,一共分为index个组
                   for(int k = i+index; k < len; k+=index) {   // 进行插入排序
                        for(int j = k; j > i; j-=index){
                             if (arr[j] < arr[j - index]) {
                                  int tmp = arr[j];
                                  arr[j] = arr[j-index];
                                  arr[j-index] = tmp;
                             }
                        }
                   }
              }
              if (index == 1) {
                   break;
              }
          }
          out();
     }

 

参考博客:https://www.runoob.com/w3cnote/sort-algorithm-summary.html

https://www.jianshu.com/p/40dcc3b83ddc

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
快速排序到底有多快?

上期为大家介绍了快速排序(Quicksort),有很多同学会问:快排是不是比之前几种排序都要快?它到底有多快?,那就让我们一起来做个小实验测试一下吧! 一、实验设计 目前给大家介绍过了6种排...

猪哥66
2019/04/09
9
0
快速排序到底有多快?

上期为大家介绍了快速排序(Quicksort),有很多同学会问:快排是不是比之前几种排序都要快?它到底有多快?,那就让我们一起来做个小实验测试一下吧! 一、实验设计 目前给大家介绍过了6种排...

osc_w9s1w4o0
2019/04/09
2
0
重温前端10大排序算法(长文建议收藏)

注意:文章中排序算法性能比较都以实际情况为准。 文中代码地址:github.com/collins999/… 1、冒泡排序 思路 通过相邻元素的比较和交换,使得每一趟循环都能找到未有序数组的最大值或最小值...

蜗牛的北极星之旅
01/07
0
0
python实现七大经典排序算法

本文主要使用python来实现七个经典的排序算法,分别是:冒泡排序、选择排序,插入排序,快速排序,希尔排序,堆排序和归并排序。 一、相关归纳总结 1、时间复杂度 O(N^2): 冒泡排序、选择排序...

JohnieLi
03/31
0
0
常用的数据结构和算法

1.插入排序:直接插入排序,希尔排序 2.选择排序:直接选择排序,堆排序 3.交换排序:冒泡排序,快速排序 4.归并排序 5.基数排序 > 算法 - 排序算法 简单排序:冒泡排序、选择排序、插入排序...

desaco
2018/11/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周日乱弹 —— 那么长的绳子,你这是放风筝呢

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @ 巴拉迪维:黑豹乐队的单曲《无地自容》 耳畔突然响起旋律,是那首老歌。中国摇滚有了《一无所有》不再一无所有;中国摇滚有了《无地自容》不...

小小编辑
49分钟前
55
1
《吐血整理》-顶级程序员书单集

你知道的越多,你不知道的越多 给岁月以文明,而不是给文明以岁月 前言 王潇:格局决定了一个人的梦想,梦想反过来决定行为。 那格局是什么呢? 格局是你能够看见的深度、广度和密度。 王潇认...

敖丙
2019/12/11
8
0
我可以在Android版式中加下划线吗? - Can I underline text in an Android layout?

问题: 如何在Android布局xml文件中定义带下划线的文本? 解决方案: 参考一: https://stackoom.com/question/A31z/我可以在Android版式中加下划线吗 参考二: https://oldbug.net/q/A31z/...

法国红酒甜
52分钟前
26
0
干掉ELK | 使用Prometheus+Grafana搭建监控平台

什么是Prometheus? Prometheus是由SoundCloud开发的开源监控报警系统和时序列数据库(TSDB)。Prometheus使用Go语言开发,是Google BorgMon监控系统的开源版本。 Prometheus的特点 · 多维度...

木九天
今天
34
0
拉勾网拉你上勾

预览 需求简介 拉勾网是一个互联网行业的一个招聘网站,上面有许多职位,于是乎,小编想提取指定职位的基本信息(职位名,薪水,工作经验,工作地点,教育背景),然后插入 MongoDB 数据库,...

木下瞳
2019/04/17
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部