java快速排序算法
2018-07-20 來(lái)源：open-open
/**
* 快速排序
*
* 在當(dāng)前無(wú)序區(qū)R[1..H]中任取一個(gè)數(shù)據(jù)元素作為比較的"基準(zhǔn)"(不妨記為X)，用此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左右兩個(gè)較小的無(wú)序區(qū)：
* R[1..I-1]和R[I+1..H]，且左邊的無(wú)序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無(wú)序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，
* 而基準(zhǔn)X則位于最終排序的位置上，即R[1..I-1]≤ X.Key≤R[I+1..H](1≤I≤H)，當(dāng)R[1..I-1]和R[I+1..H]均非空時(shí)，
* 分別對(duì)它們進(jìn)行上述的劃分過(guò)程，直至所有無(wú)序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂? */
public class QuickSort {
/**
* 排序算法的實(shí)現(xiàn)，對(duì)數(shù)組中指定的元素進(jìn)行排序
*
* @param array
* 待排序的數(shù)組
* @param from
* 從哪里開(kāi)始排序
* @param end
* 排到哪里
* @param c
* 比較器
*/
// 定義了一個(gè)這樣的公有方法sort，在這個(gè)方法體里面執(zhí)行私有方法quckSort（這種方式值得借鑒）。
public void sort(Integer[] array, int from, int end) {
quickSort(array, from, end);
}
/**
* 遞歸快速排序?qū)崿F(xiàn)
*
* @param array
* 待排序數(shù)組
* @param low
* 低指針
* @param high
* 高指針
* @param c
* 比較器
*/
private void quickSort(Integer[] array, int low, int high) {
/*
* 如果分區(qū)中的低指針小于高指針時(shí)循環(huán)；如果low=higth說(shuō)明數(shù)組只有一個(gè)元素，無(wú)需再處理； 如果low >
* higth，則說(shuō)明上次樞紐元素的位置pivot就是low或者是higth，此種情況 下分區(qū)不存，也不需處理
*/
if (low < high) {
// 對(duì)分區(qū)進(jìn)行排序整理
// int pivot = partition1(array, low, high);
int pivot = partition2(array, low, high);
// int pivot = partition3(array, low, high);
/*
* 以pivot為邊界，把數(shù)組分成三部分[low, pivot - 1]、[pivot]、[pivot + 1, high]
* 其中[pivot]為樞紐元素，不需處理，再對(duì)[low, pivot - 1]與[pivot + 1, high]
* 各自進(jìn)行分區(qū)排序整理與進(jìn)一步分區(qū)
*/
quickSort(array, low, pivot - 1);
quickSort(array, pivot + 1, high);
}
}
/**
* 實(shí)現(xiàn)一
*
* @param array
* 待排序數(shù)組
* @param low
* 低指針
* @param high
* 高指針
* @param c
* 比較器
* @return int 調(diào)整后中樞位置
*/
private int partition1(Integer[] array, int low, int high) {
Integer pivotElem = array[low];// 以第一個(gè)元素為中樞元素
// 從前向后依次指向比中樞元素小的元素，剛開(kāi)始時(shí)指向中樞，也是小于與大小中樞的元素的分界點(diǎn)
int border = low;
/*
* 在中樞元素后面的元素中查找小于中樞元素的所有元素，并依次從第二個(gè)位置從前往后存放
* 注，這里最好使用i來(lái)移動(dòng)，如果直接移動(dòng)low的話(huà)，最后不知道數(shù)組的邊界了，但后面需要 知道數(shù)組的邊界
*/
for (int i = low + 1; i <= high; i++) {
// 如果找到一個(gè)比中樞元素小的元素
if ((array[i].compareTo(pivotElem)) < 0) {
swap(array, ++border, i);// border前移，表示有小于中樞元素的元素
}
}
/*
* 如果border沒(méi)有移動(dòng)時(shí)說(shuō)明說(shuō)明后面的元素都比中樞元素要大，border與low相等，此時(shí)是
* 同一位置交換，是否交換都沒(méi)關(guān)系；當(dāng)border移到了high時(shí)說(shuō)明所有元素都小于中樞元素，此
* 時(shí)將中樞元素與最后一個(gè)元素交換即可，即low與high進(jìn)行交換，大的中樞元素移到了 序列最 后；如果 low <minIndex<
* high，表 明中樞后面的元素前部分小于中樞元素，而后部分大于
* 中樞元素，此時(shí)中樞元素與前部分?jǐn)?shù)組中最后一個(gè)小于它的元素交換位置，使得中樞元素放置在 正確的位置
*/
swap(array, border, low);
return border;
}
/**
* 實(shí)現(xiàn)二
*
* @param array
* 待排序數(shù)組
* @param low
* 待排序區(qū)低指針
* @param high
* 待排序區(qū)高指針
* @param c
* 比較器
* @return int 調(diào)整后中樞位置
*/
private int partition2(Integer[] array, int low, int high) {
int pivot = low;// 中樞元素位置，我們以第一個(gè)元素為中樞元素
// 退出條件這里只可能是 low = high
while (true) {
if (pivot != high) {// 如果中樞元素在低指針位置時(shí)，我們移動(dòng)高指針
// 如果高指針元素小于中樞元素時(shí)，則與中樞元素交換
if ((array[high].compareTo(array[pivot])) < 0) {
swap(array, high, pivot);
// 交換后中樞元素在高指針位置了
pivot = high;
} else {// 如果未找到小于中樞元素，則高指針前移繼續(xù)找
high--;
}
} else {// 否則中樞元素在高指針位置
// 如果低指針元素大于中樞元素時(shí)，則與中樞元素交換
if ((array[low].compareTo(array[pivot])) > 0) {
swap(array, low, pivot);
// 交換后中樞元素在低指針位置了
pivot = low;
} else {// 如果未找到大于中樞元素，則低指針后移繼續(xù)找
low++;
}
}
if (low == high) {
break;
}
}
// 返回中樞元素所在位置，以便下次分區(qū)
return pivot;
}
/**
* 實(shí)現(xiàn)三
*
* @param array
* 待排序數(shù)組
* @param low
* 待排序區(qū)低指針
* @param high
* 待排序區(qū)高指針
* @param c
* 比較器
* @return int 調(diào)整后中樞位置
*/
private int partition3(Integer[] array, int low, int high) {
int pivot = low;// 中樞元素位置，我們以第一個(gè)元素為中樞元素
low++;
// ----調(diào)整高低指針?biāo)赶虻脑仨樞�，把小于中樞元素的移到前部分，大于中樞元素的移到后面部�? // 退出條件這里只可能是 low = high
while (true) {
// 如果高指針未超出低指針
while (low < high) {
// 如果低指針指向的元素大于或等于中樞元素時(shí)表示找到了，退出，注：等于時(shí)也要后移
if ((array[low].compareTo(array[pivot])) >= 0) {
break;
} else {// 如果低指針指向的元素小于中樞元素時(shí)繼續(xù)找
low++;
}
}
while (high > low) {
// 如果高指針指向的元素小于中樞元素時(shí)表示找到，退出
if ((array[high].compareTo(array[pivot])) < 0) {
break;
} else {// 如果高指針指向的元素大于中樞元素時(shí)繼續(xù)找
high--;
}
}
// 退出上面循環(huán)時(shí) low = high
if (low == high) {
break;
}
swap(array, low, high);
}
// ----高低指針?biāo)赶虻脑嘏判蛲瓿珊�，還得要把中樞元素放到適當(dāng)?shù)奈恢? if ((array[pivot].compareTo(array[low])) > 0) {
// 如果退出循環(huán)時(shí)中樞元素大于了低指針或高指針元素時(shí)，中樞元素需與low元素交換
swap(array, low, pivot);
pivot = low;
} else if ((array[pivot].compareTo(array[low])) <= 0) {
swap(array, low - 1, pivot);
pivot = low - 1;
}
// 返回中樞元素所在位置，以便下次分區(qū)
return pivot;
}
/**
* 交換數(shù)組中的兩個(gè)元素的位置
*
* @param array
* 待交換的數(shù)組
* @param i
* 第一個(gè)元素
* @param j
* 第二個(gè)元素
*/
public void swap(Integer[] array, int i, int j) {
if (i != j) {// 只有不是同一位置時(shí)才需交換
Integer tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
/**
* 測(cè)試
*
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
QuickSort quicksort = new QuickSort();
quicksort.sort(intgArr, 0, intgArr.length - 1);
for (Integer intObj : intgArr) {
System.out.print(intObj + " ");
}
}
}
標(biāo)簽： swap
版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。
最新資訊
熱門(mén)推薦