Je näher die Daten an der Reihenfolge liegen, desto weniger Zeit dauert es, die Sortierung direkt einzufügen.
Zeitkomplexität: O(N^2)
Raumkomplexität O(1), es ist ein stabiler Algorithmus
Direkte Einfügungssortierung:
public static void insertSort(int[] array){ for (int i = 1; i < array.length; i++) { int tmp=array[i]; int j=i-1; for(;j>=0;--j){ if(array[j]>tmp){ array[j+1]=array[j]; }else{ break; } } array[j+1]=tmp; } }
public static void shellSort(int[] array){ int size=array.length; //这里定义gap的初始值为数组长度的一半 int gap=size/2; while(gap>0){ //间隔为gap的直接插入排序 for (int i = gap; i < size; i++) { int tmp=array[i]; int j=i-gap; for(;j>=0;j-=gap){ if(array[j]>tmp){ array[j+gap]=array[j]; }else{ break; } } array[j+gap]=tmp; } gap/=2; } }
//交换 private static void swap(int[] array,int i,int j){ int tmp=array[i]; array[i]=array[j]; array[j]=tmp; } //选择排序 public static void chooseSort(int[] array){ for (int i = 0; i < array.length; i++) { int minIndex=i;//记录最小值的下标 for (int j = i+1; j < array.length; j++) { if (array[j]<array[minIndex]) { minIndex=j; } } swap(array,i,minIndex); } }
2. Heap-Sortierung
Zwei Ideen der Heap-Sortierung (am Beispiel der aufsteigenden Reihenfolge):
Erstellen Sie einen kleinen Root-Heap, nehmen Sie die oberen Elemente des Heaps heraus und fügen Sie sie der Reihe nach in das Array ein, bis der Heap leer ist.//向下调整 public static void shiftDown(int[] array,int parent,int len){ int child=parent*2+1; while(child<len){ if(child+1<len){ if(array[child+1]>array[child]){ child++; } } if(array[child]>array[parent]){ swap(array,child,parent); parent=child; child=parent*2+1; }else{ break; } } } //创建大根堆 private static void createHeap(int[] array){ for (int parent = (array.length-1-1)/2; parent >=0; parent--) { shiftDown(array,parent,array.length); } } //堆排序 public static void heapSort(int[] array){ //创建大根堆 createHeap(array); //排序 for (int i = array.length-1; i >0; i--) { swap(array,0,i); shiftDown(array,0,i); } }
3. Austauschsortierung
1
Zweistufige Schleifen, die erste Schleifenebene stellt die Anzahl der zu sortierenden Male dar, und die zweistufige Schleife stellt die Anzahl der Vergleiche in jedem Durchgang dar. Bei jedem Vergleich wurde die Blasensortierung optimiert kann einen Zähler definieren, um die Anzahl der Datenaustausche aufzuzeichnen. Wenn kein Austausch stattfindet, bedeutet dies, dass die Daten in Ordnung sind. Zeitliche Komplexität: O(N^2)Die räumliche Komplexität ist O(1), was eine stabile Sortierung ist. Blasensortierung:public static void bubbleSort(int[] array){ for(int i=0;i<array.length-1;++i){ int count=0; for (int j = 0; j < array.length-1-i; j++) { if(array[j]>array[j+1]){ swap(array,j,j+1); count++; } } if(count==0){ break; } } }
2. Jede zu sortierende Auswahl ist sicher Gemäß diesem Sortiercode wird die zu sortierende Menge in zwei Teilsequenzen unterteilt. Alle Elemente in der linken Teilsequenz sind kleiner als der Benchmark-Wert größer als der Benchmark-Wert. Dann wird die ganz linke Teilsequenz wiederholt. Die Sequenz wiederholt diesen Vorgang, bis alle Elemente an ihren entsprechenden Positionen angeordnet sind.
Zeitkomplexität: Bestes O(n*logn): Die zu sortierende Sequenz kann jedes Mal so gleichmäßig wie möglich aufgeteilt werden
Schlechtestes O(N^2): Die zu sortierende Sequenz selbst ist geordnetRaumkomplexität: Bestenfalls O(logn), schlimmstenfalls O(N). Instabile Sortierung(1) GrabmethodeWenn die Daten in Ordnung sind, entspricht die schnelle Sortierung einem Binärbaum ohne linke oder rechte Teilbäume. Zu diesem Zeitpunkt erreicht die Raumkomplexität O(N). Das Sortieren großer Datenmengen kann zu einem Stapelüberlauf führen.public static void quickSort(int[] array,int left,int right){ if(left>=right){ return; } int l=left; int r=right; int tmp=array[l]; while(l<r){ while(array[r]>=tmp&&l<r){ //等号不能省略,如果省略,当序列中存在相同的值时,程序会死循环 r--; } array[l]=array[r]; while(array[l]<=tmp&&l<r){ l++; } array[r]=array[l]; } array[l]=tmp; quickSort(array,0,l-1); quickSort(array,l+1,right); }
//key值的优化,只在快速排序中使用,则可以为private private int threeMid(int[] array,int left,int right){ int mid=(left+right)/2; if(array[left]>array[right]){ if(array[mid]>array[left]){ return left; } return array[mid]<array[right]?right:mid; }else{ if(array[mid]<array[left]){ return left; } return array[mid]>array[right]?right:mid; } }
随着我们递归的进行,区间会变的越来越小,我们可以在区间小到一个值的时候,对其进行插入排序,这样代码的效率会提高很多。
(3)快速排序的非递归实现
//找到一次划分的下标 public static int patition(int[] array,int left,int right){ int tmp=array[left]; while(left<right){ while(left<right&&array[right]>=tmp){ right--; } array[left]=array[right]; while(left<right&&array[left]<=tmp){ left++; } array[right]=array[left]; } array[left]=tmp; return left; } //快速排序的非递归 public static void quickSort2(int[] array){ Stack<Integer> stack=new Stack<>(); int left=0; int right=array.length-1; stack.push(left); stack.push(right); while(!stack.isEmpty()){ int r=stack.pop(); int l=stack.pop(); int p=patition(array,l,r); if(p-1>l){ stack.push(l); stack.push(p-1); } if(p+1<r){ stack.push(p+1); stack.push(r); } } }
归并排序(MERGE-SORT):该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。实现序列的完全有序,需要将已经有序的子序列合并,即先让每个子序列有序,然后再将相邻的子序列段有序。若将两个有序表合并成一个有序表,称为二路归并。
时间复杂度:O(n*logN)(无论有序还是无序)
空间复杂度:O(N)。是稳定的排序。
//归并排序:递归 public static void mergeSort(int[] array,int left,int right){ if(left>=right){ return; } int mid=(left+right)/2; //递归分割 mergeSort(array,left,mid); mergeSort(array,mid+1,right); //合并 merge(array,left,right,mid); } //非递归 public static void mergeSort1(int[] array){ int gap=1; while(gap<array.length){ for (int i = 0; i < array.length; i+=2*gap) { int left=i; int mid=left+gap-1; if(mid>=array.length){ mid=array.length-1; } int right=left+2*gap-1; if(right>=array.length){ right=array.length-1; } merge(array,left,right,mid); } gap=gap*2; } } //合并:合并两个有序数组 public static void merge(int[] array,int left,int right,int mid){ int[] tmp=new int[right-left+1]; int k=0; int s1=left; int e1=mid; int s2=mid+1; int e2=right; while(s1<=e1&&s2<=e2){ if(array[s1]<=array[s2]){ tmp[k++]=array[s1++]; }else{ tmp[k++]=array[s2++]; } } while(s1<=e1){ tmp[k++]=array[s1++]; } while(s2<=e2){ tmp[k++]=array[s2++]; } for (int i = left; i <= right; i++) { array[i]=tmp[i-left]; } }
排序方法 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
直接插入排序 | O(n) | O(n^2) | O(1) | 稳定 |
希尔排序 | O(n) | O(n^2) | O(1) | 不稳定 |
直接排序 | O(n^2) | O(n^2) | O(1) | 不稳定 |
堆排序 | O(nlog(2)n) | O(nlog(2)n) | O(1) | 不稳定 |
冒泡排序 | O(n) | O(n^2) | O(1) | 稳定 |
快速排序 | O(nlog(2)n) | O(n^2) | O(nlog(2)n) | 不稳定 |
归并排序 | O(nlog(2)n) | O(nlog(2)n) | O(n) | 稳定 |
Das obige ist der detaillierte Inhalt vonSo verwenden Sie die sieben Sortiermethoden von Java-Datenstrukturen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!