在 Java 中的冒泡排序算法对手动链表进行排序

Sarwan Soomro 2023年1月30日 2022年4月22日
  1. Java 中的冒泡排序
  2. Java 中的冒泡排序手动链表
  3. Java 中的类排序链表
在 Java 中的冒泡排序算法对手动链表进行排序

冒泡排序是用于对数据集合进行排序的最常见的数据结构算法。它通过以错误的顺序迭代和交换相邻元素直到它们正确来起作用。

我们将首先向你展示基本的排序演示。然后我们将实现两个冒泡排序算法来对 Java 中的链表进行排序。

Java 中的冒泡排序

让我们保持基本的东西,而不涉及排序的算术方面。我们将在冒泡排序中从头到尾遍历一个数组。

然后只有它可以将当前索引与下一个索引进行比较。该公式的核心概念是当当前元素的大小大于下一个元素时。

语法:

for (int A = 0; A < sort - 1; A++)
for (int B = 0; B < sort - A - 1; B++)
if (DEMO[B] > DEMO[B + 1]){
// Swapping of array
	int temp = DEMO[B];
DEMO[B] = DEMO[B + 1];
DEMO[B + 1] = temp;
}
注意
我们通过应用上面的公式使用循环来遍历元素。它在这个阶段交换和遍历。

现在让我们在 Java 中执行一个简单的冒泡排序算法。但首先,看看数组未排序索引的初始状态。

数组:{43, 65, 21, 64, 12, 6, 1}

以下代码块将通过应用此基本排序算法对此数组索引执行冒泡排序。

值得一提的是,我们总是可以根据自己的要求修改这个公式。但是,此时核心应该保持基本以形成清晰。

代码:

//In this program, we will sort an array DEMO using the bubble sort algorithm
//Main class
public class BubbleSortLinkListExample1
{
	//Main function
	private void bubbleSort(int DEMO[])
	{
		//Using .length to determine entire length of array's index
		int sort = DEMO.length;
		//If array's length is less than int sort, increase it by 1
		for (int A = 0; A < sort-1; A++)
			//Formula 1
			for (int B = 0; B < sort-A-1; B++)
				if (DEMO[B] > DEMO[B+1])
				{
					// Swapping of array
					int temp = DEMO[B];
					DEMO[B] = DEMO[B+1];
					DEMO[B+1] = temp;
				}
	}
	/* Now we are going to print DEMO array*/
	void printArray(int DEMO[])
	{
		int sort = DEMO.length;
		for (int A=0; A<sort; ++A)
			System.out.print(DEMO[A] + " ");
		System.out.println();
	}
	// We are going to implement a driver algorithm for sorting our DEMO array
	public static void main(String args[])
	{
		BubbleSortLinkListExample1 ob = new BubbleSortLinkListExample1();
		int DEMO[] = {43, 65, 21, 64, 12, 6, 1};
		ob.bubbleSort(DEMO);
		System.out.println("After the array has been sorted!");
		ob.printArray(DEMO);
	}
}

对这个数组进行升序排序后,我们得到 Java 的输出。

输出:

After the array has been sorted!
1 6 12 21 43 64 65

Java 中的冒泡排序手动链表

链表手动排序也是冒泡排序中一种直接的方法。

我们之前讨论过遍历数据吗?现在,我们将实践它。

节点允许我们将数据从一个节点遍历到下一个节点。

看看我们下面的演示模型。由于我们在前面的示例中确实执行了排序,因此在这里强调节点非常重要。

冒泡排序节点演示

Java 中的类排序链表

正如我们所理解的,我们应用这个类来形成 Java 中的节点。

代码:

class SortLL {
	public static class Mynode {
		int indx;
		Mynode fwdMynode;

		public Mynode(int indx) {
			this.indx = indx;
			this.fwdMynode = null;
		}
		public int getindx() {
			return this.indx;
		}
	}
注意
除了手动排序,我们还将使用 .setNextNode() 函数,它接受一个节点并相应地设置下一个实例变量。

你可以单独使用这些类并调用它们的对象,但这是一种冗长而复杂的方式。因此,我们将所有类保存在一个文件中。

同样,我们将使用 .getNextNode() 函数,它检索下一个不带参数的类元素。你必须熟悉这个概念,所以让我们执行手动冒泡排序算法,不用多说。

  1. 排序之前的链表:

    手动冒泡排序前的链表

    代码:

    class SortLL {
    	public static class Mynode {
    		int indx;
    		Mynode fwdMynode;
    
    		public Mynode(int indx) {
    			this.indx = indx;
    			this.fwdMynode = null;
    		}
    		public int getindx() {
    			return this.indx;
    		}
    	}
    	// My node class
    	private Mynode head;
    	private int size;
    	public SortLL(){
    		this.head = null;
    		this.size = 0;
    	}
    	public void add(int indx) {
    		Mynode Mynode = new Mynode(indx);
    		if (head == null) {
    			head = Mynode;
    		} else {
    			Mynode CN = head;
    			while(CN.fwdMynode != null) {
    				CN = CN.fwdMynode;
    			}
    			CN.fwdMynode = Mynode;
    		}
    		size++;
    	}
    	public void sort() {
    		if (size > 1) {
    			boolean dtr;
    			do {
    				Mynode thisMynode = head;
    				Mynode ladtMynode = null;
    				Mynode fwd = head.fwdMynode;
    				dtr = false;
    
    				while ( fwd != null ) {
    					if (thisMynode.indx > fwd.indx) {
    						dtr = true;
    						if ( ladtMynode != null ) {
    							Mynode sig = fwd.fwdMynode;
    
    							ladtMynode.fwdMynode = fwd;
    							fwd.fwdMynode = thisMynode;
    							thisMynode.fwdMynode = sig;
    						} else {
    							Mynode sig = fwd.fwdMynode;
    							head = fwd;
    							fwd.fwdMynode = thisMynode;
    							thisMynode.fwdMynode = sig;
    						}
    						ladtMynode = fwd;
    						fwd = thisMynode.fwdMynode;
    					} else {
    						ladtMynode = thisMynode;
    						thisMynode = fwd;
    						fwd = fwd.fwdMynode;
    					}
    				}
    			} while( dtr );
    		}
    	}
    	public int listSize() {
    		return size;
    	}
    	public void printindx() {
    		Mynode CN = head;
    
    		while(CN != null) {
    			int indx = CN.getindx();
    			System.out.print(indx + " ");
    			CN = CN.fwdMynode;
    		}
    		System.out.println();
    	}
    	public boolean isEmpty() {
    		return size == 0;
    	}
    }
    // indxInterface class
    class SrtBubb {
    	public static void main (String[]args) {
    		SortLL s = new SortLL();
    		s.add(12);
    		s.add(2);
    		s.add(7);
    		s.add(19);
    		s.add(23);
    		s.add(9);
    		System.out.println("Before Performing Bubble Sort");
    		s.printindx();
    		s.sort();
    		System.out.println("After Performing Bubble Sort");
    		s.printindx();
    		System.out.println("Size of the linked list is: " + s.listSize());
    	}
    }
    
  2. 执行手动冒泡排序后:

    手动冒泡排序后的链接列表

    输出:

    Before Performing Bubble Sort
    12 2 7 19 23 9
    After Performing Bubble Sort
    2 7 9 12 19 23
    Size of the linked list is: 6
    

你可以根据你的要求修改此程序。但这是初学者理解使用冒泡排序对链表进行手动排序的最实用的方法。

假设你仍然对这个话题感到困惑。我们还为你提供了文件目录中的代码。

Sarwan Soomro avatar Sarwan Soomro avatar

Sarwan Soomro is a freelance software engineer and an expert technical writer who loves writing and coding. He has 5 years of web development and 3 years of professional writing experience, and an MSs in computer science. In addition, he has numerous professional qualifications in the cloud, database, desktop, and online technologies. And has developed multi-technology programming guides for beginners and published many tech articles.

LinkedIn

相关文章 - Java List