1开皿、快速排序
快速排序是冒泡排序的改進(jìn)版锡足，也是最好的一種內(nèi)排序忱屑，在很多面試題中都會(huì)出現(xiàn)蹬敲，也是作為程序員必須掌握的一種排序方法。
基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分莺戒，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小伴嗡，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行从铲，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列
1.1 原理
在要排的數(shù)（比如數(shù)組A）中選擇一個(gè)中心值key（比如A[0]）瘪校，通過(guò)一趟排序?qū)?shù)組A分成兩部分，其中以key為中心名段，key右邊都比key大阱扬，key左邊的都key小，然后對(duì)這兩部分分別重復(fù)這個(gè)過(guò)程伸辟，直到整個(gè)有序麻惶。
整個(gè)快排的過(guò)程就簡(jiǎn)化為了一趟排序的過(guò)程，然后遞歸調(diào)用就行了信夫。
假設(shè)要排的數(shù)組為：A[8] ={ 5 2 8 9 2 3 4 9 }窃蹋，選擇 key = 5， 開(kāi)始時(shí) i=0静稻，j=7（升序排序）
1警没，定義i=0，j=A.lenght-1振湾，i為第一個(gè)數(shù)的下標(biāo)杀迹，j為最后一個(gè)數(shù)下標(biāo)
2，從數(shù)組的最后一個(gè)數(shù)Aj從右往左找押搪，找到第一小于key的數(shù)树酪，記為Aj浅碾；
3，從數(shù)組的第一個(gè)數(shù)Ai 從左往右找嗅回，找到第一個(gè)大于key的數(shù)及穗，記為Ai；
4绵载，交換Ai 和Aj
5埂陆，重復(fù)這個(gè)過(guò)程，直到 i=j
6娃豹，調(diào)整key的位置焚虱，把A[i] 和key交換
1.2 時(shí)間復(fù)雜度
快排在最糟糕得情況下時(shí)間復(fù)雜度是O(n2)，平均的復(fù)雜度是O(nlogn)
1.3 代碼
public class QuickSort {
private static int count;
/**
* 測(cè)試
* @param args
*/
public static void main(String[] args) {
int[] num = {3,45,78,64,52,11,64,55,99,11,18};
System.out.println(arrayToString(num,"未排序"));
QuickSort(num,0,num.length-1);
System.out.println(arrayToString(num,"排序"));
System.out.println("數(shù)組個(gè)數(shù)："+num.length);
System.out.println("循環(huán)次數(shù)："+count);
}
/**
* 快速排序
* @param num 排序的數(shù)組
* @param left 數(shù)組的前針
* @param right 數(shù)組后針
*/
private static void QuickSort(int[] num, int left, int right) {
//如果left等于right懂版，即數(shù)組只有一個(gè)元素鹃栽，直接返回
if(left>=right) {
return;
}
//設(shè)置最左邊的元素為基準(zhǔn)值
int key=num[left];
//數(shù)組中比key小的放在左邊，比key大的放在右邊躯畴，key值下標(biāo)為i
int i=left;
int j=right;
while(i<j){
//j向左移民鼓，直到遇到比key小的值
while(num[j]>=key && i<j){
j--;
}
//i向右移，直到遇到比key大的值
while(num[i]<=key && i<j){
i++;
}
//i和j指向的元素交換
if(i<j){
int temp=num[i];
num[i]=num[j];
num[j]=temp;
}
}
num[left]=num[i];
num[i]=key;
count++;
QuickSort(num,left,i-1);
QuickSort(num,i+1,right);
}
/**
* 將一個(gè)int類(lèi)型數(shù)組轉(zhuǎn)化為字符串
* @param arr
* @param flag
* @return
*/
private static String arrayToString(int[] arr,String flag) {
String str = "數(shù)組為("+flag+")：";
for(int a : arr) {
str += a + "\t";
}
return str;
}
}
2蓬抄、歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法丰嘉。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并嚷缭，得到完全有序的序列饮亏；即先使每個(gè)子序列有序，再使子序列段間有序阅爽。若將兩個(gè)有序表合并成一個(gè)有序表路幸，稱(chēng)為2-路歸并。
2.1 特點(diǎn)：
- 時(shí)間復(fù)雜度無(wú)論是在最好情況下還是在最壞情況下均是O(nlogn)
- 輔助空間復(fù)雜度為O(n)
- 穩(wěn)定
- 順序存儲(chǔ)與鏈表存儲(chǔ)均可
2.2 原理
分而治之(divide - conquer);每個(gè)遞歸過(guò)程涉及三個(gè)步驟
分解: 把待排序的 n 個(gè)元素的序列分解成兩個(gè)子序列, 每個(gè)子序列包括 n/2 個(gè)元素.
治理: 對(duì)每個(gè)子序列分別調(diào)用歸并排序MergeSort, 進(jìn)行遞歸操作
合并: 合并兩個(gè)排好序的子序列,生成排序結(jié)果.
2.3 時(shí)間復(fù)雜度
在最壞付翁、最佳简肴、平均情況下歸并排序時(shí)間復(fù)雜度均為o(nlogn)，從合并過(guò)程中可以看出合并排序穩(wěn)定百侧。
2.4 代碼
public class MergeSort {
/**
* 歸并排序遞歸實(shí)現(xiàn)
* @param a
* @param left
* @param right
*/
public void mergeSort(int[] a,int left,int right){
if(left<right){
int middle = (left+right)/2;//分解
mergeSort(a, left, middle);//治理
mergeSort(a,middle+1,right);
merge(a,left,middle,right);//合并
}
}
/**
* 合并
* @param a
* @param left
* @param middle
* @param right
*/
private void merge(int[] a, int left, int middle, int right) {
int [] tmpArray = new int[a.length];
int rightStart = middle+1;
int tmp = left;
int third = left;
//比較兩個(gè)小數(shù)組相應(yīng)下標(biāo)位置的數(shù)組大小着帽，小的先放進(jìn)新數(shù)組
while(left<=middle&&rightStart<=right){
if(a[left]<=a[rightStart]){
tmpArray[third++] = a [left++];
}else{
tmpArray[third++] = a[rightStart++];
}
}
//如果左邊還有數(shù)據(jù)需要拷貝，把左邊數(shù)組剩下的拷貝到新數(shù)組
while(left<=middle){
tmpArray[third++] = a[left++];
}
//如果右邊還有數(shù)據(jù)......
while(rightStart<=right){
tmpArray[third++] = a[rightStart++];
}
while(tmp<=right){
a[tmp] = tmpArray[tmp++];
}
}
public static void main(String[] args){
MergeSort mergeSort = new MergeSort();
int [] a = new int[]{90,3,2,67,44,-9,87,65,11,9,2,8};
mergeSort.mergeSort(a, 0, a.length-1);
for(int n:a){
System.out.print(" "+n);
}
}
}
歸并算法是分治思想的經(jīng)典應(yīng)用移层，其基本思想就是將兩個(gè)有序的表合并成為一個(gè)有序表。如果a數(shù)組是有序的赫粥，b數(shù)組也是有序的观话，則最后合并后，c數(shù)組也是有序的
//實(shí)現(xiàn)將a越平、b兩個(gè)數(shù)組合并到c數(shù)組
public void merge(int a[], int b[], int[] c) {
int aIndex=0, bIndex=0, cIndex=0;
int aEnd=a.length, bEnd=b.length;
c=new int[aEnd+bEnd];
while (aIndex<=aEnd && bIndex<=bEnd) {
if (a[aIndex]<b[bIndex]) {
c[cIndex++]=a[aIndex++];
} else {
c[cIndex++]=b[bIndex++];
}
}
while (aIndex<=aEnd) {
c[cIndex++]=a[aIndex++];
}
while (bIndex<=bEnd) {
c[cIndex++]=b[bIndex++];
}
}
歸并排序就是在這個(gè)合并有序數(shù)組的例子上繼續(xù)擴(kuò)展频蛔，先把待排序數(shù)組多次分解成兩個(gè)子數(shù)組灵迫，分解到最后，每個(gè)子數(shù)組都只有一個(gè)值晦溪，這樣的話每個(gè)子數(shù)組就是有序的瀑粥，然后就可以調(diào)用上面的合并有序數(shù)組的例子了。
