排序（2）–二分排序、快速排序、歸并排序

*二分排序

/*** 二分排序中，關鍵字的比較次數采用折半查找，數量級為O(nlogn)，* 但是元素移動次數為O(n^2)，因此時間復雜度為O(n^2)。* @author yj*/ public class BinarySort {/*** 二分法插入排序是在插入第i個元素時，對前面的0～i-1元素進行折半，* 先跟他們中間的那個元素比，如果小，則對前半再進行折半，否則對后半進行折半，* 直到left>right，然后再把第i個元素前1位與目標位置之間的所有元素后移，* 再把第i個元素放在目標位置上。*/public static void binarySort(int[] source){int left,right,middle;//left>right說明找到了位置int temp;for(int i = 1;i<source.length;i++){left = 0;//初始化左指向首個元素right = i-1;//右指向需要插入元素的左側temp = source[i];//記錄需要排序的元素while(left<=right){middle = (right+left)/2;if(source[middle]>temp){//中間元素大于待插入元素，說明插入位置在middle左側right = middle -1;//將右指向為左半}else {left = middle + 1;}}for(int j = i-1;j>=left;j--){//插入操作，將元素右移source[j+1]=source[j];}source[left] = temp;spy(source);//顯示排序的過程}}/*** 方便觀察每次排序，可以窺探數組排序的情況* @param source*/public static void spy(int[] source){for(int k = 0;k<source.length;k++){System.out.printf(source[k]+" "); }System.out.println();} }

---

快速排序：

/*** 平均時間復雜度為O(nlgn/ig2);最差為O(n^2);空間復雜度O(logn)* 是不穩定排序* 該方法的基本思想是：1．先從數列中取出一個數作為基準數。* 2．分區過程，將比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊。* 3．再對左右區間重復第二步，直到各區間只有一個數。* @author yj*/ public class QuickSort {/*** 快速排序* @param source* @param low* @param high*/public static void quickSort(int[] source,int low,int high){int pivotpos;//記錄基準位置if(low<high){pivotpos = partition(source,low,high);quickSort(source, low, pivotpos - 1);//左半邊quickSort(source, pivotpos + 1, high);//右半邊}}/*** 劃分算法* @param source* @param i* @param j* @return i 基準位置*/private static int partition(int[] source, int i, int j) {int pivot = source[i];//將第一個數據記錄為基準while(i<j){while(i<j&&source[j]>=pivot){j--;}if(i<j)source[i++] = source[j];//相當于source[i] = source[j];i++spy(source);//打印排序情況while(i<j&&source[i]<=pivot){i++;}if(i<j)source[j--] = source[i];spy(source);//打印排序情況}source[i] = pivot;return i;}/*** 方便觀察每次排序，可以窺探數組排序的情況* @param source*/public static void spy(int[] source){for(int k = 0;k<source.length;k++){System.out.printf(source[k]+" "); }System.out.println();} }

---

*歸并排序

/*** 時間復雜度O(nlogn),空間復雜度O(n),是穩定的排序* @author yj*/ public class MergeSort {public static void mergeSort(int[] s,int start,int end){if(start<end){//兩路歸并int middle = (start+end)/2;mergeSort(s,start,middle);mergeSort(s, middle+1, end);//將兩組數據歸并merge(s,start,middle,middle+1,end);}}/*** 兩組數據歸并* @param s* @param start1* @param end1* @param start2* @param end2*/public static void merge(int[] s,int start1,int end1,int start2,int end2){int i,j;//數組1、2的兩個游標i = start1;j = start2;int[] temp = new int[end2-start1+1];//建立一個數組為兩個之和大小，歸并到這個數組int k =0;while(i<=end1&& j<=end2){if(s[i]>s[j]){temp[k] = s[j];k++;j++;}else{temp[k] = s[i];k++;i++;}}//將剩余的元素加入temp中while(i<=end1){temp[k] = s[i];k++;i++;}while(j<=end2){temp[k] = s[j];k++;j++;}//將temp中數據轉移到原數組中for(int element :temp){s[start1] = element;start1++;}spy(s);}/*** 方便觀察每次排序，可以窺探數組排序的情況* @param source*/public static void spy(int[] source){for(int k = 0;k<source.length;k++){System.out.printf(source[k]+" "); }System.out.println();} }

總結

以上是生活随笔為你收集整理的排序（2）二分排序、快速排序、归并排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。