No IF 排序

news/2025/2/22 15:56:18/

一、前言

排序是一个基础算法，也是一个常用方法，显式排序和隐式排序遍布在代码的各个角落，甚至是没有代码的地方。排序算法的一个核心语句就是判断语句IF，使用IF成为排序语句的关键点。笔者在很久以前接触过一个题目，大意是：不使用IF语句比较两个数大小（当时的编程语言是Basic）。这在当时我的看来，成了一个巨大的挑战。后来，终于经过一段时间的思考，找到了问题的解法。年初，ChatGPT横空出世，本人就尝试使用这个题目对ChatGPT进行了测试。ChatGPT 3.5 测试失败，但是后来的ChatGPT4 经过笔者的引导，测试成功了。进而，笔者萌生了一个想法，能不能将两数的比较，扩展为三个数，乃至多个数，即不使用IF语句能否完成一般意义的排序呢？经过思考和尝试，证明是可以的。本文将通过两数比较和三数比较的过程分析给出一个不使用IF语句进行一般意义排序的方法。

另：本文代码使用的是C#。

二、不使用IF语句的两数排序

当我把这个题目抛给ChatGPT的时候，ChatGPT给出了一个使用三目运算符的方法，由于原始题目的语言是Basic，而Basic语言中是没有三目运算的，因此这不符合要求。为此，我们将题目进行限定，即不使用IF语句以及三目运算符等明显具有比较含义的语句比较两个数的大小。
思路如下：假设需要比较的两个数是 A和B， 不能使用比较语句，因此只能通过对A和B实施某种运算才有可能达到目的。显然最先想的的是减法运算，即A-B，如果A-B大于0 ，则 A>B ，A-B=0 则A=B， A-B 小于0 则是A<B。这个鲜明的特点，使我想到了符号函数。符号函数的值可以表征AB的大小。在不考虑相等的情况下，函数只有两个值 即 -1 和 1。如果将这两个值和AB对应起来，立刻就想到了数组。可以将 -1 和 1 通过某种变换，转换成数组的下标，这样就可以利用数组和下标的映射关系把AB值按照顺序输出，从而达到排序的目的。然后就有了下面的代码：

		   var A=100;var B=90;int[]  x = new int[] { A, B};// 需要比较的两个数 A 和 Bint [] rslt = new int[2] ;//比较结果var big  = x[(1 - Math.Sign(x[0] - x[1])) / 2];//大数var small = x[(1 - Math.Sign(x[1] - x[0])) / 2];//小数var result = string.Format("big = {0}, small = {1}", big,small);

分析如下：
假设 A>B,则 Math.Sign(x[0] - x[1])=1，因而(1 - Math.Sign(x[0] - x[1])=0 ， 所以
x[(1 - Math.Sign(x[0] - x[1])) / 2]=x[0/2]=x[0] = A, 即大数；
同样的 x[(1 - Math.Sign(x[1] - x[0])) / 2]=x[(1 - Math.Sign(B-A)) / 2]=x[(1 -（-1）) / 2] = x[1]=B,是小数；

如果 A<B , 则 Math.Sign(x[0] - x[1])= -1，因而(1 - Math.Sign(x[0] - x[1])=2, x[(1 - Math.Sign(x[0] - x[1])) / 2]=x[1] =B, 是大数；
而 x[(1 - Math.Sign(x[1] - x[0]))/2] = x[0] = A 是小数。

综上分析，上面的方法实现了两个数的比较，并可以将结果按从大到小的顺序输出。上述方法将大数保存到big中，将小数保存到small中， 这样big 和small就构成一个有序序列。进一步的思考是：我们能否利用某种方法扩充这个有序序列，如果可以，那么排序就可以实现了。

如果两数相等，则[(1 - Math.Sign(x[1] - x[0])) / 2=0（整数运算的特点），因此结果是x[0],这个显然是没有关系， 因此上述方法可以实现对两个数的比较。

三、不使用IF的多数排序

1、三数比较和排序

我们以整数为例进行数据的比较。假定，已经存在一个两数的有序数组，表示如下

	 int[] ints = new int[] {1, 2,};

现在我们思考，如何将第三个数插入到这个数组中。
分析上面两数比较的过程，可知

(1 - Math.Sign(x[0] - x[1])) / 2

表示的是大数数组元素的下标 ，

(1 - Math.Sign(x[1] - x[0])) / 2

是小数组元素的下标，据此不妨首先实现一个两数的比较函数，如下：

     public int[] Compare2Number(int[] n){int[] rsult = new int[2];var n1 = n[0];var n2 = n[1];var idxA = (1 - Math.Sign(n1 - n2)) / 2;// 大数下标var idxB = (1 - Math.Sign(n2 - n1)) / 2;// 小数下标rsult[0] = n[idxA];rsult[1] = n[idxB];return rsult;}

该函数返回一个有序数组，是一个两个数的降序排列的数组。利用该函数，我们思考如何将第三个数放到这个有序队列中，为了描述方便，将这个有序数组命名为 baseN 。我们将第三个数与baseN 的第一个元素比较，生成一个新的有序数组 r1， 再将r1的第二个元素与baseN的第二个数进行比较，生成另一个有序数组r2。此时
r1[0], r2[0], r2[1] 就是三个元素的排序结果。

代码如下：

            int[] baseN = new int[] { 1,2};int x3 = 3;var r0 = Compare2Number(baseN);int[] x1 = new int[2];x1[0] = r0[0];x1[1] = x3;var r1 = Compare2Number(x1);int[] x2 = new int[2];x2[0] = r1[1];x2[1] = r0[1];var r2 = Compare2Number(x2);int[] rslt = new int[3];rslt[0] = r1[0];rslt[1] = r2[0];rslt[2] = r2[1];

上述代码将结果整合到一个新的数组中，这样就得到了一个三个数的降序排列的数组。

2、多个数据比较和排序

三数的比较是将第三个数与baseN 的第一个元素比较，得到一个新数组r1，再将r1的第二个元素与baseN的第二个元素比较，再得到一个新数组r2，这样得到新的一个三元有序数组：[r1[0], r2[0], r2[1]] 。可以看出，将这个三元数组作为已知数组，就可以比较第四个数。这样推而广之，就可以进行多个数的比较。综上分析，可以写出一个数newX和n个有序数 nSorted 进行比较排序的代码：

	    public int[] GetNewOrderSeq(int newX, int[] nSorted,int nSLen){int[] rsult = new int[nSLen+1];var x = newX;for(int i = 0; i < nSLen; i++){int[] cn = new int[2];cn[0] = x;cn[1] = nSorted[i];var new2Cn = Compare2Number(cn);rsult[i] = new2Cn[0];x=new2Cn[1];}rsult[nSLen] = x;return rsult;}

该函数的功能，将一个新数newX和已知有序数组nSorted进行比较，并且生成一个新的有序数组rsult，nSLen 是已知有序数组的长度。

在该函数的基础上，我们对需要排序的数组进行遍历，将元素从头到尾一个一个地插到这个数组中，最终这数组就是一个排好序的有序数组，从而实现对一组数的排序功能。

代码如下：

            int[] ints = new int[] {1, 2, 4, 3, 5, };int[] nSorted = new int[ints.Length];nSorted[0]=ints[0];for (int i = 1; i < ints.Length; i++){var newX = ints[i];nSorted = GetNewOrderSeq(newX, nSorted,i);}

上面代码使用两个数组，第一个数组保存需要排序的数据，第二个数组保存排序好的数据。

这样我们在不使用IF语句的限制下，完成了一个数组的排序。完整的C#代码附后。

3、复杂度

分析上面代码的执行过程，我们可以看出这个排序属于插入排序，因此其时间复杂度是o(n^2)。就存贮空间而言，上面程序使用了两个相同大小的数组。能不能进一步减少存贮空间，笔者没有深入思考。

四、总结

算法世界纷繁奇妙，有的方法经典简洁，有的方法新奇晦涩。前者固然是我们追求的终极目标，但是后者也能拓展思路，在算法的画布上添上一抹令人注目的一笔。不使用IF语句比较两个数的大小乃至排序或许就是这一笔吧，希望本文的方法和思路能给各位喜欢算法的朋友一个小小的启迪。

附：No IF 排序代码

using System;namespace DataStructureEx
{internal class NoIFSort{/// <summary>///  两数排序，输出降序排列的一个数组/// </summary>/// <param name="n">两个数的数组</param>/// <returns></returns>static public int[] Compare2Number(int[] n){int[] rsult = new int[2];//for (int i = 0; i < cn.Length; i++)//{//    rsult[i] = cn[i];//}var n1 = n[0];var n2 = n[1];var idxA = (1 - Math.Sign(n1 - n2)) / 2;// the index of greater one var idxB = (1 - Math.Sign(n2 - n1)) / 2;// the index of the less onersult[0] = n[idxA];rsult[1] = n[idxB];return rsult;}/// <summary>///  将新数据插入到已知排序数组中，返回一个降序数组/// </summary>/// <param name="newX">需要排序的新数据</param>/// <param name="nSorted">已知降序数组</param>/// <param name="nSLen">降序数组长度</param>/// <returns></returns>static public int[] GetNewOrderSeq(int newX, int[] nSorted,int nSLen){int[] rsult = new int[nSLen+1];var x = newX;for(int i = 0; i < nSLen; i++){int[] cn = new int[2];//cn[0] = new CNumberLink();//cn[1] = new CNumberLink();cn[0] = x;cn[1] = nSorted[i];var new2Cn = Compare2Number(cn);rsult[i] = new2Cn[0];x=new2Cn[1];}rsult[nSLen] = x;return rsult;}}
}

测试代码

        private void btn_NoIFSort_Click(object sender, EventArgs e){int[] ints = new int[] {1, 2, 4, 3, 5, };int[] nSorted = new int[5];nSorted[0]=ints[0];for (int i = 1; i < ints.Length; i++){var newX = ints[i];nSorted = NoIFSort.GetNewOrderSeq(newX, nSorted,i);}}

nSorted 是排好顺序的数组。

PS： 上述代码在Microsoft Visual Studio Community 2022 (64 位) - Current 版本中17.2.6 中 调试通过。


http://www.ppmy.cn/news/82677.html

相关文章

前端系列15集-watch，watchEffect，eventBus

前端系列15集-watch，watchEffect，eventBus

watchEffect&#xff0c;它立即执行传入的一个函数&#xff0c;同时响应式追踪其依赖&#xff0c;并在其依赖变更时重新运行该函数。 换句话说&#xff1a;watchEffect相当于将watch 的依赖源和回调函数合并&#xff0c;当任何你有用到的响应式依赖更新时&#xff0c;该回调函数…
阅读更多...
Nginx实现ChatGPT API代理

Nginx实现ChatGPT API代理

文章目录 一、前言说明二、前置准备三、nginx配置三、代理域名用途 一、前言说明 本篇文章可以直接用于公司生产级的使用&#xff0c;所需要的资源直接改为公司级的即可平替使用文章均已通过实践应用&#xff0c;保证文章准确性&#xff0c;但因不同环境的不同可能效果不一致可…
阅读更多...
PyTorch学习笔记

PyTorch学习笔记

1.item() → number 方法: item() 返回一个数 只能用于只包含一个元素的张量。对于其他的张量&#xff0c;请查看方法tolist(). 该操作是不可微分的,即不可求导. (译者注:返回的结果是普通Python数据类型, 自然不能调用backward()方法来进行梯度的反向传播) Example: 例子:>…
阅读更多...
Spring Boot 配置文件

Spring Boot 配置文件

文章目录 1.配置文件作用2.配置文件的格式3.properties 配置文件3.1 properties 基本语法3.2 读取配置文件3.3 properties 优缺点分析 4. yml 配置文件的说明4.1 yml 基本语法4.2 yml 进阶配置1) 配置不同的数据类型2) 配置对象 5. propertise VS yml6.设置不同的配置环境6.1 创…
阅读更多...
oracle：NLSSORT函数简介及使用方法

oracle：NLSSORT函数简介及使用方法

oracle&#xff1a;NLSSORT函数简介及使用方法 在Oracle数据库中&#xff0c;NLSSORT函数是一个用于排序和比较非英语字符的重要函数。本文将对NLSSORT函数进行简要概述&#xff0c;并介绍其使用方法。 什么是NLSSORT函数&#xff1f; NLSSORT函数是Oracle数据库中的一个函数…
阅读更多...
【STC8】热启动串口指令下载

【STC8】热启动串口指令下载

前言 在目标开发板没有装载自动下载电路的时候&#xff0c;往往需要冷启动&#xff0c;也就是需要手动开关电源&#xff0c;来达到单片机复位下载。当然还有一种方法是热启动&#xff0c;通过串口接收到自定义的指令后&#xff0c;软件执行复位下载。这就是本文介绍的内容。 材…
阅读更多...
Flutter 局部刷新

Flutter 局部刷新

flutter的局部刷新的几种方式 第一种 &#xff1a;使用 GlobalKey 父组件中声明 GlobalKey<_局部刷新对象类型State> textKey GlobalKey(); textKey.currentState.局部刷新的方法(); 第二种 使用&#xff1a;StatefulBuilder 第三种 使用 StreamBuilder Stream…
阅读更多...
【Leetcode】697. 数组的度

【Leetcode】697. 数组的度

[哈希表] Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements. Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the sa…
阅读更多...
最新文章

Copyright @ 2022~2023