Was sind die Sortieralgorithmen in Java?

1. Blasensortierung

import java.util.Arrays;//冒泡排序public class BubbleSort_01 {
	public static void main(String[] args) {
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		//记录比较次数
		int count=0;
		//i=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]) {
					int temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
				}
				count++;
			}
		}
		System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
		System.out.println("一共比较了："+count+"次");//一共比较了：105次
	}}

4 . Shell Sort (Shell Sort)

import java.util.Arrays;public class BubbleSort1_01 {
	public static void main(String[] args) {
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		int count=0;
		for (int i = 0; i < a.length-1; i++) {
			boolean flag=true;
			for (int j = 0; j < a.length-1-i; j++) {
				if (a[j]>a[j+1]) {
					int temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
					flag=false;
				}
				count++;
			}
			if (flag) {
				break;
			}
		}
		System.out.println(Arrays.toString(a));// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
		System.out.println("一共比较了："+count+"次");//一共比较了：95次
	}}

5

import java.util.Arrays;//选择排序:先定义一个记录最小元素的下标，然后循环一次后面的，找到最小的元素，最后将他放到前面排序好的序列。public class SelectSort_02 {
	public static void main(String[] args) {
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		for (int i = 0; i < a.length-1; i++) {
			int index=i;//标记第一个为待比较的数
			for (int j = i+1; j < a.length; j++) { //然后从后面遍历与第一个数比较
				if (a[j]<a[index]) {  //如果小,就交换最小值
					index=j;//保存最小元素的下标
				}
			}
			//找到最小值后，将最小的值放到第一的位置，进行下一遍循环
			int temp=a[index];
			a[index]=a[i];
			a[i]=temp;
		}
		System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
	}}

7. Heap-Sortierung (Heap-Sortierung)

Heap-Sortierung

Schritt 1: Erstellen Sie den anfänglichen Heap-BuildHeap, verwenden Sie sink (arr, i, length), um den Wert der Oberseite des Heaps anzupassen;

Schritt 2: Der Der Zweck des Absenkens des obersten Elements des Heaps besteht darin, das größte Element an die Spitze des Heaps zu verschieben und es dann mit sink(arr, 0,length) anzupassen;

Illustration der Heap-Sortierung: Link

import java.util.Arrays;//插入排序:定义一个待插入的数，再定义一个待插入数的前一个数的下标，然后拿待插入数与前面的数组一一比较，最后交换。public class InsertSort_03 {
	public static void main(String[] args) {
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		for (int i = 0; i < a.length; i++) {  //长度不减1，是因为要留多一个位置方便插入数
			//定义待插入的数
			int insertValue=a[i];
			//找到待插入数的前一个数的下标
			int insertIndex=i-1;
			while (insertIndex>=0 && insertValue <a[insertIndex]) {//拿a[i]与a[i-1]的前面数组比较
				a[insertIndex+1]=a[insertIndex];
				insertIndex--;
			}
			a[insertIndex+1]=insertValue;
		}
		System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
	}}

8. Zählsortierung (Count Sort)

Referenzlink

Die Schritte des Algorithmus sind wie folgt:

Finden Sie das größte Element im Array, das sortiert werden soll.
Zählen Sie die Anzahl der Vorkommen jedes Elements mit dem Wert i im Array und speichern Sie das i-te Element des Arrays count

und sammeln Sie alle Zählungen (beginnend mit dem ersten Element in count wird jedes Element zum vorherigen Element hinzugefügt)

Füllen Sie das Zielarray Umgekehrt: Fügen Sie jedes Element hinzu, das i in das Element count [i] des neuen Arrays eingefügt wird. Jedes Mal, wenn ein Element platziert wird, wird count [i] subtrahiert

Bucket Sort Es kann als eine verbesserte Version der Zählsortierung betrachtet werden. Es unterteilt die zu sortierenden Daten in mehrere geordnete Buckets. Die Daten in jedem Bucket werden dann nacheinander herausgenommen Vervollständigen Sie die Sortierung.

Bucket-Sortierung: Platzieren Sie das Element mit dem Wert i in Bucket i und schütten Sie schließlich die Elemente im Bucket nacheinander aus.

Idee für die Bucket-Sortiersequenz:

Legen Sie ein quantitatives Array als leeren Bucket fest.

Durchsuchen Sie die Reihenfolge und legen Sie die Gegenstände nacheinander in die entsprechenden Eimer.

• Sortieren Sie jeden Eimer, der nicht leer ist.

• Legen Sie Gegenstände aus dem Eimer, der nicht leer ist, wieder in die ursprüngliche Reihenfolge.

• import java.util.Arrays;//希尔排序：插入排序的升级public class ShellSort_04 {
  	public static void main(String[] args) {
  		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
  		int count=0;//比较次数
  		for (int gap=a.length / 2; gap > 0; gap = gap / 2) {
  			//将整个数组分为若干个子数组
  			for (int i = gap; i < a.length; i++) {
  				//遍历各组的元素
  				for (int j = i - gap; j>=0; j=j-gap) {
  					//交换元素
  					if (a[j]>a[j+gap]) {
  						int temp=a[j];
  						a[j]=a[j+gap];
  						a[j+gap]=temp;
  						count++;
  					}
  				}
  			}
  		}
  		System.out.println(count);//16
  		System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  	}}

  10. Radix-Sortierung (Raix-Sortierung)

Wir gehen davon aus, dass es ein zu sortierendes Array gibt [53, 3, 542, 748, 14, 214]. Wie kann man es also mit der Radix-Sortierung sortieren?
• Zuerst haben wir zehn eindimensionale Arrays wie dieses, in der Basissortierung auch Buckets genannt. Implementiert mit Bucket-Sortierung.

In der ersten Runde differenzieren Sie nach den einzelnen Ziffern der Elemente: [542, 53, 3, 14, 214,748]

In der zweiten Runde differenzieren Sie nach den zehn Ziffern der Elemente: [3, 14, 214, 542, 748, 53]

Die dritte Runde, gekennzeichnet durch die Hundertstelziffer der Elemente: [3, 14, 53, 214, 542, 748]

import java.util.Arrays;//快速排序：冒泡排序的升华版public class QuickSort_05 {
	public static void main(String[] args) {
		//int a[]={50,1,12,2};
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		quicksort(a,0,a.length-1);
		System.out.println(Arrays.toString(a));
	}
	private static void quicksort(int[] a, int low, int high) {
		int i,j;
		if (low>high) {
			return;
		}
		i=low;
		j=high;
		int temp=a[low];//基准位,low=length时，会报异常，java.lang.ArrayIndexOutOfBoundsException: 4 ，所以必须在if判断后面,就跳出方法。
		while(i<j){
			//先从右边开始往左递减，找到比temp小的值才停止
			while ( temp<=a[j] && i<j) {
				j--;
			}
			//再看左边开始往右递增，找到比temp大的值才停止
			while ( temp>=a[i] && i<j) {
				i++;
			}
			//满足 i<j 就交换,继续循环while(i<j)
			if (i<j) {
				int t=a[i];
				a[i]=a[j];
				a[j]=t;
			}
		}
		//最后将基准位跟  a[i]与a[j]相等的位置，进行交换,此时i=j
		a[low]=a[i];
		a[i]=temp;
		//左递归
		quicksort(a, low, j-1);
		//右递归
		quicksort(a, j+1, high);	
	}}

Radix-Sortierung ist ein Austausch Raum für Zeit Der klassische Algorithmus: Wenn genügend Daten vorhanden sind, reicht der Speicherplatz möglicherweise nicht aus, wenn er mehrere zehn Millionen erreicht, und es kommt zu einem Heap-Speicherüberlauf

Das obige ist der detaillierte Inhalt vonWas sind die Sortieralgorithmen in Java?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!