salesforce零基础学习(七十九)简单排序浅谈 篇一

我们在程序中经常需要对数据列表进行排序,有时候使用SOQL的order by 不一定能完全符合需求,需要对数据进行排序,排序可以有多种方式,不同的方式针对不同的场景。篇一只是简单的描述一下选择排序,插入排序以及插入排序优化版--希尔排序。

一.选择排序

选择排序的中心思想为第一轮找到数组中最小的值,将最小值和第一个元素交换位置,第二轮找到剩余数组的最小值,将其和第二个元素交换,以此类推。

选择排序的特点如下:

1.比较次数:n * (n-1) / 2 2.交换次数:N 4.运行时间和输入无关 5.数据移动次数是最小的,每次移动都只会改变两个数组的值

apex不像java,基础类型类似Integer,String等均没有实现Comparable接口,所以方法中均已Integer类型进行处理,有兴趣的可以自行修改成Comparable或者其他类型。

 1 public static Integer[] selectionSort(Integer[] datas) {
 2    Integer dataLength = datas.size();
 3    for(Integer i = 0;i < dataLength;i++) {
 4      Integer min = i;
 5      for(Integer j = i + 1;j < dataLength;j++) {
 6         if(datas[min] > datas[j]) {
 7            min = j;
 8         }
 9      }
10      Integer temp = datas[i];
11      datas[i] = datas[min];
12      datas[min] = temp;
13    }
14    return datas;
15 }

实现Comparable接口的代码:

 1 public static Comparable[] selectionSort1(Comparable[] datas) {
 2     Integer dataLength = datas.size();
 3     for(Integer i = 0;i < dataLength;i++) {
 4         Integer min = i;
 5         for(Integer j = i;j < dataLength;j++) {
 6             if(datas[min].compareTo(datas[j]) > 0) {
 7                 min = j;
 8              }
 9          }
10          Comparable temp = datas[i];
11          datas[i] = datas[min];
12          datas[min] = temp;
13      }
14      return datas;
15  }    

二.插入排序

插入排序的中心为对左边的第i(i在1~n之间)项进行排序,保证前i项是有序的,等排到最右边一位,则整个数组变为有序的数列。

插入排序特点:

 比较次数:N^2/4  交换次数:N^2/4  所需时间取决于数组元素的初始顺序,如果初始顺序相对有序,排序会快很多  插入排序适用情景:  1.数组中的每个元素距离他的最终位置不远  2.一个有序的大数组接一个小数组  3.数组中只有几个元素位置不正确  实现规则:每一轮都对左边的i项数据进行排序,保证前i项有序 代码如下:

 1     public static Integer[] insertionSort(Integer[] datas) {
 2         Integer dataLength = datas.size();
 3         for(Integer i = 1;i < dataLength;i++) {
 4             for(Integer j = i; j > 0 && datas[j] < datas[j-1];j--) {
 5                 Integer temp = datas[j-1];
 6                 datas[j-1] = datas[j];
 7                 datas[j] = temp;
 8             }
 9         }
10         return datas;
11     }

三.希尔排序

插入排序适用于数组中只有几个元素不正确,但是如果最小的一位如果在数组的最后一位,相当于需要移动N个位置。希尔排序可以用于快速交换不相邻的元素以对数组的局部进行排序,思想为使数组中任意间隔为H的元素都是有序的。一个H有序数组就是H个互相独立的有序数组放在一起形成的一个数组。如果H很大,我们就可以将元素一次移动到很远的地方。H取值可以取2,3,4...n

关于希尔排序可以查看:https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F/3229428?fr=aladdin

下面代码描述为当H为3的排序  元素的间隔规律为a[n+1] = a[n] + 3 ^ n

public static String[] shellSort(String[] datas) {
        Integer dataLength = datas.size();
        Integer h = 1;
        while(h < dataLength/3) {
            h = 3 * h + 1;//1,4,13,40 ...
        }
        System.debug(LoggingLevel.INFO, '*** h: ' + h);
        System.debug(LoggingLevel.INFO, '*** dataLength: ' + dataLength);
        while(h >= 1) {
            for(Integer i = h;i < dataLength;i++) {
                //将a[i]插入到a[i-h],a[i-2h],a[i-3h]  ....中
                for(Integer j = i;j >= h && datas[j] < datas[j-h];j -= h) {
                    String temp = datas[j-h];
                    datas[j-h] = datas[j];
                    datas[j] = temp;
                }
                System.debug(LoggingLevel.INFO, '*** i: ' + i);
            }
            System.debug(LoggingLevel.INFO, '*** datas: ' + String.valueOf(datas));
            System.debug(LoggingLevel.INFO, '*** h: ' + h);
            h = h / 3;
            
        }
        return datas;
    }

当数组为 S H E L L S O R T E X A M P L E 情况下,使用H为3的每次运行如下图,图不全,内容自己补充。

运行后,可以将数组排成升序的有序列表。

总结:此三种排序方式,单纯效率考虑的话,可以使用希尔排序,优化了插入排序的不足,同时没有特别的占用内存。篇二会描述一下其他排序方式。额,题外话,还是不太希望今天有人看到这篇博客的,祝大家七夕快乐。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏浪淘沙

关于数组的算法

3.给定一个数组和一个数num,把小于num的书放在数组左边,大于num的书放在数组右边

1046
来自专栏C/C++基础

数组的全排列

学过数学的人都知道,全排列的意思是什么。现在如何用计算机的编程语言实现数组的全排列呢?

751
来自专栏算法channel

深度优先搜索和回溯结合后的终极模板

昨天 这5道算法题 都可以套用这个模板 推送了一个深度搜索和回溯结合的题目和另4道类似题,今天,逐个分析后4道题,最后提炼出模板。

810
来自专栏决胜机器学习

PHP数据结构(二十) ——其他插入排序

PHP数据结构(二十)——其他插入排序 (原创内容,转载请注明来源,谢谢) 注:本文是衔接直接插入排序的,因此直接插入排序的相关内容请点击——PHP...

3127
来自专栏Redis源码学习系列

Redis源码学习之跳表

跳跃链表简称为跳表(SkipList),它维护了一个多层级的链表,且第i+1层链表中的节点是第i层链表中的节点的子集。跳表作为一种平衡数据结构,经常和平衡树进行...

420
来自专栏机器学习从入门到成神

数据结构之Trie树

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

802
来自专栏奔跑的蛙牛技术博客

Java中实现的简单算法 && 计算二分查找次数

如果采用其他方式对列表进行排序可以使用List接口的sort方法传入一个Comarable的一个对象

682
来自专栏牛客网

校招面试手撕算法汇总

所有题目都是从面经中提取而来,持续更新。 本人也是菜鸟一枚,帖子也会相应的发布自己对于题目的解法和看法,但是可能想得不够,也希望大家能够一起讨论,一起进步。 1...

34411
来自专栏Golang语言社区

用Golang写一个搜索引擎

本篇较长较枯燥,请保持耐心看完。 前面两章介绍了一下倒排索引以及倒排索引字典的两种存储结构,分别是 跳跃表 和 哈希表 ,本篇我们介绍另一种数据结构,他也被大量...

3667
来自专栏有趣的Python

玩转算法面试:(四)LeetCode查找类问题

查找问题 两类查找问题 查找有无:元素’a’是否存在?set;集合 查找对应关系(键值对应):元素’a’出现了几次?map;字典 通常语言的标准库中都内置set...

3116

扫码关注云+社区