Codebeispiele zu Blase und Schnellsortierung

Dieser Artikel stellt hauptsächlich Java Blasensortierung und Beispielcode für die schnelle Sortierung vor. Freunde, die ihn benötigen, können sich auf

Blasensortierung

Bubble Sort ist ein einfacher Sortieralgorithmus. Es durchläuft wiederholt die zu sortierende Sequenz, vergleicht jeweils zwei Elemente und vertauscht sie, wenn sie in der falschen Reihenfolge sind. Der Besuch des Arrays wird wiederholt, bis kein Austausch mehr erforderlich ist, was bedeutet, dass das Array sortiert wurde. Der Name dieses Algorithmus rührt von der Tatsache her, dass kleinere Elemente durch den Austausch langsam an die Spitze des Arrays „schweben“.

Der Blasensortierungsalgorithmus wird wie folgt implementiert: [Nach der Sortierung wird das

Array von klein nach groß geordnet]

　　/**
  * 冒泡排序
  * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 
  * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 
  * 针对所有的元素重复以上的步骤，除了最后一个。
  * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 
  * @param numbers 需要排序的整型数组
  */
 public static void bubbleSort(int[] numbers)
 {
  int temp = 0;
  int size = numbers.length;
  for(int i = 0 ; i < size-1; i ++)
  {
  for(int j = 0 ;j < size-1-i ; j++)
  {
   if(numbers[j] > numbers[j+1]) //交换两数位置
   {
   temp = numbers[j];
   numbers[j] = numbers[j+1];
   numbers[j+1] = temp;
   }
  }
  }
 }

Schnellsortierung

Die Grundidee der Schnellsortierung:

Teilen Sie die zu sortierenden Datensätze auf Zwei unabhängige Teile durchlaufen einen Sortierdurchgang. Wenn die Schlüsselwörter eines Teils der Datensätze kleiner sind als die Schlüsselwörter des anderen Teils, werden die beiden Teile weiterhin sortiert, bis die gesamte Reihenfolge in Ordnung ist.

Behandeln Sie die gesamte Sequenz als Array, betrachten Sie die nullte Position als Mittelachse und vergleichen Sie sie mit der letzten. Wenn sie kleiner ist, wird sie ausgetauscht. Wenn sie größer ist, erfolgt keine Verarbeitung Nach dem Austausch wird es mit dem kleineren Ende kombiniert. Wenn es kleiner ist, tauschen Sie es nicht aus. Wenn es jedoch größer ist, tauschen Sie es aus. Auf diese Weise werden

Schleifen in einem Durchgang durchgeführt. Die linke ist kleiner als die Mittelachse und die rechte ist größer als die Mittelachse Die Methode wird verwendet, um die beiden unabhängigen Arrays zu sortieren.

Der Code ist wie folgt implementiert:

1. Finden Sie die Position der Mittelachse (das niedrigste Bit wird als Mittelachse verwendet)

　　/**
  * 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
  * 
  * @param numbers 带查找数组
  * @param low 开始位置
  * @param high 结束位置
  * @return 中轴所在位置
  */
 public static int getMiddle(int[] numbers, int low,int high)
 {
  int temp = numbers[low]; //数组的第一个作为中轴
  while(low < high)
  {
  while(low < high && numbers[high] > temp)
  {
   high--;
  }
  numbers[low] = numbers[high];//比中轴小的记录移到低端
  while(low < high && numbers[low] < temp)
  {
   low++;
  }
  numbers[high] = numbers[low] ; //比中轴大的记录移到高端
  }
  numbers[low] = temp ; //中轴记录到尾
  return low ; // 返回中轴的位置
 }

2.

Rekursive Form des Divide-and-Conquer-Sortieralgorithmus:

 /**
  * 
  * @param numbers 带排序数组
  * @param low 开始位置
  * @param high 结束位置
  */
 public static void quickSort(int[] numbers,int low,int high)
 {
  if(low < high)
  {
  　　int middle = getMiddle(numbers,low,high); //将numbers数组进行一分为二
  　　quickSort(numbers, low, middle-1); //对低字段表进行递归排序
  　　quickSort(numbers, middle+1, high); //对高字段表进行递归排序
  }
 }

3 Aufrufe

 /**
  * 快速排序
  * @param numbers 带排序数组
  */
 public static void quick(int[] numbers)
 {
  if(numbers.length > 0) //查看数组是否为空
  {
  quickSort(numbers, 0, numbers.length-1);
  }
 }

Analyse:

Die schnelle Sortierung gilt im Allgemeinen als die Methode mit der besten durchschnittlichen Leistung unter den Sortiermethoden derselben Größenordnung (O( nlog2n)). Wenn die anfängliche Reihenfolge jedoch nach Schlüssel oder grundsätzlich geordnet ist, degeneriert die schnelle Sortierung zur Blasensortierung. Um es zu verbessern, wird normalerweise die „Drei-in-Eins-Methode“ zur Auswahl des Benchmark-Datensatzes verwendet, dh die drei Datensatzschlüssel, die auf den beiden Endpunkten zentriert sind, und der Mittelpunkt des Sortierintervalls werden als Drehpunktdatensatz angepasst. Quicksort ist eine instabile Sortiermethode.

Methodentest

Drucken

Funktion:

public static void printArr(int[] numbers)
 {
  for(int i = 0 ; i < numbers.length ; i ++ )
  {
  System.out.print(numbers[i] + ",");
  }
  System.out.println("");
 }

Test:

　public static void main(String[] args) 
 {
  int[] numbers = {10,20,15,0,6,7,2,1,-5,55};
  System.out.print("排序前：");
  printArr(numbers);
  bubbleSort(numbers);
  System.out.print("冒泡排序后：");
  printArr(numbers);
  quick(numbers);
  System.out.print("快速排序后：");
  printArr(numbers);
 }

Ergebnis:

Vor dem Sortieren: 10,20,15,0,6,7,2,1, -5,55,

Nach Blasensortierung: -5,0,1,2,6,7,10,15,20,55,

Nach Schnellsortierung: -5, 0 ,1,2,6,7,10,15,20,55,

【Verwandte Empfehlungen】

1.

Besondere Empfehlung: Version „php Programmer Toolbox“ V0.1 herunterladen

2.

Java kostenloses Video-Tutorial

3.

Umfassende Analyse von Java-Annotationen

Das obige ist der detaillierte Inhalt vonCodebeispiele zu Blase und Schnellsortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!