Quels sont les algorithmes de tri en Java

1. Tri à bulles

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次
	}}

Optimisation du tri à bulles 1 :

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次
	}}

2.Sélectionner le tri

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]
	}}

3.

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]
	}}

4 . Tri par coquille (Tri par coquille)

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]
	}}

5. Tri par fusion (Tri par fusion)

Tri par fusion (Tri par fusion)

.

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);	
	}}

7. Heap Sort (Heap Sort)

Heap Sort Étape 1 : Construisez le tas initial buildHeap, utilisez le puits (arr, i, length) pour ajuster la valeur du haut du tas ;

Étape 2 : Le Le but de couler l'élément supérieur du tas est de faire flotter le plus grand élément vers le haut du tas, puis d'utiliser Sink(arr, 0,length) pour ajuster ;

Illustration du tri du tas : lien

import java.util.Arrays;//归并排序public class MergeSort_06 {
	public static void main(String[] args) {
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		//int a[]={5,2,4,7,1,3,2,2};
		int temp[]=new int[a.length];
		mergesort(a,0,a.length-1,temp);
		System.out.println(Arrays.toString(a));
	}
	private static void mergesort(int[] a, int left, int right, int[] temp) {
		//分解
		if (left<right) {
			int mid=(left+right)/2;
			//向左递归进行分解
			mergesort(a, left, mid, temp);
			//向右递归进行分解
			mergesort(a, mid+1, right, temp);
			//每分解一次便合并一次
			merge(a,left,right,mid,temp);
		}
	}
	/**
	 *
	 * @param a  待排序的数组
	 * @param left  左边有序序列的初始索引
	 * @param right 右边有序序列的初始索引
	 * @param mid	中间索引
	 * @param temp	做中转的数组
	 */
	private static void merge(int[] a, int left, int right, int mid, int[] temp) {
		int i=left; //初始i，左边有序序列的初始索引
		int j=mid+1;//初始化j，右边有序序列的初始索引（右边有序序列的初始位置即中间位置的后一位置）
		int t=0;//指向temp数组的当前索引，初始为0
		
		//先把左右两边的数据（已经有序）按规则填充到temp数组
		//直到左右两边的有序序列，有一边处理完成为止
		while (i<=mid && j<=right) {
			//如果左边有序序列的当前元素小于或等于右边的有序序列的当前元素，就将左边的元素填充到temp数组中
			if (a[i]<=a[j]) {
				temp[t]=a[i];
				t++;//索引向后移
				i++;//i后移
			}else {
				//反之，将右边有序序列的当前元素填充到temp数组中
				temp[t]=a[j];
				t++;//索引向后移
				j++;//j后移
			}
		}
		//把剩余数据的一边的元素填充到temp中
		while (i<=mid) {
			//此时说明左边序列还有剩余元素
			//全部填充到temp数组
			temp[t]=a[i];
			t++;
			i++;
		}
		while (j<=right) {
			//此时说明左边序列还有剩余元素
			//全部填充到temp数组
			temp[t]=a[j];
			t++;
			j++;
		}
		//将temp数组的元素复制到原数组
		t=0;
		int tempLeft=left;
		while (tempLeft<=right) {
			a[tempLeft]=temp[t];
			t++;
			tempLeft++;
		}
	}
	}

8. Counting Sort (Count Sort)

Lien de référence Les étapes de l'algorithme sont les suivantes :

Trouver le plus grand élément max du tableau à trier

• Compter le nombre d'occurrences de chaque élément de valeur i dans le tableau, et stockez Entrez le i-ème élément du tableau count

• et accumulez tous les comptes (en commençant par le premier élément du count, chaque élément est ajouté à l'élément précédent)

• Remplissez le tableau cible à l'envers : ajoutez chaque élément i placé dans l'élément count [i] du nouveau tableau. Chaque fois qu'un élément est placé, le nombre [i] est soustrait

• public class Heap_Sort_07 {
  	public static void main(String[] args) {
  		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};	
  		sort(a);
  		System.out.println(Arrays.toString(a));
  	}
      public static void sort(int[] arr) {
          int length = arr.length;
          //构建堆
          buildHeap(arr,length);
          for ( int i = length - 1; i > 0; i-- ) {
              //将堆顶元素与末位元素调换
              int temp = arr[0];
              arr[0] = arr[i];
              arr[i] = temp;
              //数组长度-1 隐藏堆尾元素
              length--;
              //将堆顶元素下沉 目的是将最大的元素浮到堆顶来
              sink(arr, 0,length);
          }
      }
      private static void buildHeap(int[] arr, int length) {
          for (int i = length / 2; i >= 0; i--) {
              sink(arr,i, length);
          }
      }
      
      private static void sink(int[] arr, int index, int length) {
          int leftChild = 2 * index + 1;//左子节点下标
          int rightChild = 2 * index + 2;//右子节点下标
          int present = index;//要调整的节点下标
  
          //下沉左边
          if (leftChild < length && arr[leftChild] > arr[present]) {
              present = leftChild;
          }
  
          //下沉右边
          if (rightChild < length && arr[rightChild] > arr[present]) {
              present = rightChild;
          }
  
          //如果下标不相等 证明调换过了
          if (present != index) {
              //交换值
              int temp = arr[index];
              arr[index] = arr[present];
              arr[present] = temp;
  
              //继续下沉
              sink(arr, present, length);
          }
      }}

9.

Tri par compartiment Il peut être considéré comme une version améliorée du tri par comptage. Il divise les données à trier en plusieurs compartiments ordonnés. Les données de chaque compartiment sont triées séparément, puis les données de chaque compartiment sont extraites tour à tour. terminer le tri. Tri du seau : placez l'élément de valeur i dans le seau i, et enfin versez les éléments dans le seau dans l'ordre.

Idée de séquence de tri de seau :

Définissez un tableau quantitatif comme un seau vide.

Recherchez la séquence et placez les éléments dans le seau correspondant un par un.

• Triez chaque seau qui n'est pas vide.

• Remettez les éléments du seau qui n'est pas vide dans la séquence d'origine.

• import java.util.Arrays;public class CountSort_08 {
  	public static void main(String[] args) {
  		int[] array = { 4, 2, 2, 8, 3, 3, 1 };
  		// 找到数组中最大的值 ---> max:8
  		int max = findMaxElement(array);
  		int[] sortedArr = countingSort(array, max + 1);
  		System.out.println("计数排序后的数组： " + Arrays.toString(sortedArr));
  	}
  	private static int findMaxElement(int[] array) {
  		int max = array[0];
  		for (int val : array) {
  			if (val > max)
  				max = val;
  		}
  		return max;
  	}
  	private static int[] countingSort(int[] array, int range) { //range:8+1
  		int[] output = new int[array.length]; 
  		int[] count = new int[range];
  		//初始化： count1数组
  		for (int i = 0; i < array.length; i++) {
  			count[array[i]]++;
  		}
  		//计数： count2数组，累加次数后的，这里用count2区分
  		for (int i = 1; i < range; i++) {
  			count[i] = count[i] + count[i - 1];
  		}
  		//排序：最后数组
  		for (int i = 0; i < array.length; i++) {
  			output[count[array[i]] - 1] = array[i];
  			count[array[i]]--;
  		}
  		return output;
  	}}

  10. Tri par base (Raix Sort)
• Nous supposons qu'il y a un tableau à trier [53, 3, 542, 748, 14, 214], alors comment le trier en utilisant le tri par base ?

  Nous avons d’abord dix tableaux unidimensionnels comme celui-ci, également appelés buckets en tri par base. Implémenté à l'aide du tri par bucket.

Au premier tour, différenciez par les chiffres simples des éléments : [542, 53, 3, 14, 214,748]

Au deuxième tour, différenciez par les dizaines de chiffres des éléments : [3, 14, 214, 542, 748, 53]

Le troisième tour, distingué par le centième chiffre des éléments : [3, 14, 53, 214, 542, 748]

public class BucketSort_09 {
    public static void sort(int[] arr){
        //最大最小值
        int max = arr[0];
        int min = arr[0];
        int length = arr.length;

        for(int i=1; i<length; i++) {
            if(arr[i] > max) {
                max = arr[i];
            } else if(arr[i] < min) {
                min = arr[i];
            }
        }

        //最大值和最小值的差
        int diff = max - min;

        //桶列表
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
        for(int i = 0; i < length; i++){
            bucketList.add(new ArrayList<>());
        }

        //每个桶的存数区间
        float section = (float) diff / (float) (length - 1);

        //数据入桶
        for(int i = 0; i < length; i++){
            //当前数除以区间得出存放桶的位置 减1后得出桶的下标
            int num = (int) (arr[i] / section) - 1;
            if(num < 0){
                num = 0;
            }
            bucketList.get(num).add(arr[i]);
        }

        //桶内排序
        for(int i = 0; i < bucketList.size(); i++){
            //jdk的排序速度当然信得过
            Collections.sort(bucketList.get(i));
        }

        //写入原数组
        int index = 0;
        for(ArrayList<Integer> arrayList : bucketList){
            for(int value : arrayList){
                arr[index] = value;
                index++;
            }
        }
    }}

Le tri Radix consiste à échanger espace pour le temps L'algorithme classique, lorsqu'il y a suffisamment de données, l'espace mémoire peut ne pas être suffisant lorsqu'il atteint des dizaines de millions, et un débordement de mémoire du tas se produit

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!