java中幾種常見的排序算法總結
本節目標；
：分析常見的比較排序算法基本原理及實現
：分析排序算法的性能分析
：分析Java中常用排序方法
1 排序
排序，就是使一串記錄，按照其中某個或某些關鍵字的大小，遞增或遞減排列的操作。
平時的上下文中，提到排序 通常指排升序。
2 穩定性
兩個相同的數據，如果經過排序後，排序算法能保證其相對位置不發生變化，則稱該算法具備穩定發行。
【插入排序】
【優化版】
分析步驟；
第一步；將第一個元素下標設置為 i ，設 index 與 i 指向同一個元素
第二部 設置循環 利用 j 循環找出除 第一個元素以為最小的元素 將其交到index下
第三步 將index 與 第一個元素交換
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 {
//array[j+1] = tmp; 隻要j回退的時候，遇到瞭 比tmp小的元素就結束這次的比較
break;
}
}
//j回退到瞭 小於0 的地方
array[j+1] = tmp;
}
}
【希爾排序】
(以瞭解為主 面試很少考的）
【分析步驟 】
【選擇排序】
分析步驟；
第一步；將第一個元素下標設置為 i ，設 index 與 i 指向同一個元素
第二部 設置循環 利用 j 循環找出除 第一個元素以為最小的元素 將其交到index下
第三步 將index 與 第一個元素交換
【堆排序】
註釋 ！其基本原理還是排序.隻其用堆來進行無序間排序，不用遍歷進行排序
public static void createHeap(int[] array) {
for (int parent = (array.length - 1 - 1) / 2; parent > 0; parent--) {//設置出父親節點
shiftDown(array, parent, array.length);//
}
}
public static void shiftDown(int[] array, int parent, int len) {
int child = 2 * parent + 1;//設置出子節點
while (child < len) {
if (child + 1 < len && array[child] < array[child + 1]) {
child++;//以防有兩個子節點 找出兩個子節點最大一位
}
if (array[child] > array[parent]) {
swap(array, parent, child);//交換父親節點和子節點
parent = child;//從新設置父親節點
child = 2*parent+1;
}else{
break;
}
}
}
public static void heapSort(int[] array) {//
createHeap( array);
int end = array.length-1;//每次交換完最後一位元素減一位
while(end > 0){
swap(array,0,end);
shiftDown(array,0, array.length-1);//這個循環裡 向下轉型
end--;
}
}
【冒泡排序】
註釋；可能是幾種排序比較簡單的一種
介紹一個冒泡排序的優化方法；
【快速排序】
原理簡介-總覽
1 從待排序區間選擇一個數，作為基準值（pivot）
2 partition：遍歷整個待排序區間， 將比基準小的(可以與基準相同)放在基左側，將比基準大 的(可以與基準相同）放在基準右側。
3 采用分治思想，對左右兩個小區間按照同樣的方法進行處理 直到小區間的長度 == 1； 則其 代表有序，如果長度 ==0， 則代表沒有元素。
public static void quick(int[] array,int left,int right) {
if( left >= right) {//判斷遞歸條件 不滿足退出
return;
}
int pivot = partition( array,left,right);//找出基準值
quick( array, left, pivot-1);//左側進行遞歸
quick( array, pivot+1 ,right);//右側進行遞歸
}
private static int partition(int[] array,int start,int end) {
int tmp = array[start];
while(start< end){//
while(start< end &&array[end] > tmp){//末尾值比tmp大時 將末尾下標減減
end--;
}
array[start] = array[end];//在右側遇到比tmp小的元素 進行交換
while(start< end && array[start] < tmp ){//先從頭部進行比較 比tmp小時交換
start++;
}
array[end] = array[start];
}
array[end] = tmp;
return end;
}
public static void quickSort(int[] array) {
quick(array,0, array.length-1);
}
}
}
【歸並排序】
原理-總覽
歸並排序（MERGE-SORT）是建立在歸並操作上的一種有效的排序算法，該算法采用分治法（Divide and Conquer)的一個非常典型的應用。將以有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。
在此之前先復習一下(鏈表題）【合並兩個有序鏈表】（歸並排序的基礎）
public static int[] mergeArray(int[] array1,int[] array2) {
//註意判斷參數
int [] tmp = new int[array1.length + array2.length];
int i = 0;
int s1 = 0;
int e1 = array1.length-1;
int s2 = 0;
int e2 = array2.length-1;
while( s1<e1 && s2<e2){
if(array1[s1] < array2[s2]){
tmp[i++] = array1[s1++];
}
if(array1[s1] > array2[s2]){
tmp[i++] = array2[s2++];
}
}
while( s1<= e1){
tmp[i++] = array1[s1++];
}
while( s2<= e2){
tmp[i++] = array2[s2++];
}
return tmp;
【正文】
【代碼簡介；】
public static void mergeSort1(int[] array) {
mergeSortInternal(array,0,array.length-1) ;
}
private static void mergeSortInternal(int[] array,int low,int high) {
if(low > high){
return ;
}
int mid = (low +(high-low))/2;//找到數組的中間位置 分為左右兩部分
mergeSortInternal( array, low,mid-1 );// 將左邊部分進行遞歸排序
mergeSortInternal( array, mid+1,high );// 將右邊部分進行遞歸排序
merge(array,low,mid,high);// 將兩部分進行合並
}
private static void merge(int[] array,int low,int mid,int high) {
int [] tmp = new int[array.length];//創建一個新的數組
int s1 = low;
int e1 = mid;
int s2 = mid+1;
int e2 = high;
int i = 0;
while(s1<e1 && s2<e2){//循環的的條件
if(array[s1] < array[s2]){
tmp[i++] = array[s1++];
}else{
tmp[i++] = array[s2++];
}
}
while(s1 < s2){//當到這一步 說明左側比右側長 將左側剩餘部分銜接到數組中
tmp[i++] = array[s1++];
}
while(s2 < e2){
tmp[i++] = array[s2++];//當到這一步 說明左側比右側長 將左側剩餘部分銜接到數組中
}
for(int j = 0; j < i; j++){//將tmp數組中元素放置array數組中
array[i+low] = tmp[j];
}
【排序總結】
到此這篇關於java中幾種常見的排序算法總結的文章就介紹到這瞭,更多相關java排序算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！