本篇內(nèi)容主要講解“Java編程怎么實(shí)現(xiàn)快速排序及優(yōu)化”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“Java編程怎么實(shí)現(xiàn)快速排序及優(yōu)化”吧!

成都創(chuàng)新互聯(lián)主要業(yè)務(wù)有網(wǎng)站營(yíng)銷策劃、網(wǎng)站建設(shè)、做網(wǎng)站、微信公眾號(hào)開(kāi)發(fā)、小程序設(shè)計(jì)、成都h5網(wǎng)站建設(shè)、程序開(kāi)發(fā)等業(yè)務(wù)。一次合作終身朋友，是我們奉行的宗旨；我們不僅僅把客戶當(dāng)客戶，還把客戶視為我們的合作伙伴，在開(kāi)展業(yè)務(wù)的過(guò)程中，公司還積累了豐富的行業(yè)經(jīng)驗(yàn)、全網(wǎng)整合營(yíng)銷推廣資源和合作伙伴關(guān)系資源，并逐漸建立起規(guī)范的客戶服務(wù)和保障體系。 

普通快速排序

找一個(gè)基準(zhǔn)值base，然后一趟排序后讓base左邊的數(shù)都小于base，base右邊的數(shù)都大于等于base。再分為兩個(gè)子數(shù)組的排序。如此遞歸下去。

public class QuickSort {
	public static <T extends Comparable<? super T>> void sort(T[] arr) {
		sort(arr, 0, arr.length - 1);
	}
	public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {
		if (left >= right) return;
		int p = partition(arr, left, right);
		sort(arr, left, p - 1);
		sort(arr, p + 1, right);
	}
	private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
		T base = arr[left];
		int j = left;
		for (int i = left + 1; i <= right; i++) {
			if (base.compareTo(arr[i]) > 0) {
				j++;
				swap(arr, j, i);
			}
		}
		swap(arr, left, j);
		return j;
		//返回一躺排序后基準(zhǔn)值的下角標(biāo)
	}
	public static void swap(Object[] arr, int i, int j) {
		if (i != j) {
			Object temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	private static void printArr(Object[] arr) {
		for (Object o : arr) {
			System.out.print(o);
			System.out.print("\t");
		}
		System.out.println();
	}
	public static void main(String args[]) {
		Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
		printArr(arr);
		//3  5  1  7  2  9  8  0  4  6
		sort(arr);
		printArr(arr);
		//0  1  2  3  4  5  6  7  8  9
	}
}

快速排序優(yōu)化：隨機(jī)選取基準(zhǔn)值base

在數(shù)組幾乎有序時(shí)，快排性能不好（因?yàn)槊刻伺判蚝?，左右兩個(gè)子遞歸規(guī)模相差懸殊，大的那部分最后很可能會(huì)達(dá)到O(n^2)）。

解決：基準(zhǔn)值隨機(jī)地選取，而不是每次都取第一個(gè)數(shù)。這樣就不會(huì)受“幾乎有序的數(shù)組”的干擾了。但是對(duì)“幾乎亂序的數(shù)組”的排序性能可能會(huì)稍微下降，至少多了排序前交換的那部分，亂序時(shí)這個(gè)交換沒(méi)有意義...有很多“運(yùn)氣”成分..

public class QuickSort {
	public static <T extends Comparable<? super T>> void sort(T[] arr) {
		sort(arr, 0, arr.length - 1);
	}
	public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {
		if (left >= right) return;
		int p = partition(arr, left, right);
		sort(arr, left, p - 1);
		sort(arr, p + 1, right);
	}
	private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
		//排序前，先讓基準(zhǔn)值和隨機(jī)的一個(gè)數(shù)進(jìn)行交換。這樣，基準(zhǔn)值就有隨機(jī)性。
		//就不至于在數(shù)組相對(duì)有序時(shí)，導(dǎo)致左右兩邊的遞歸規(guī)模不一致，產(chǎn)生最壞時(shí)間復(fù)雜度
		swap(arr,left,(int)(Math.random()*(right - left + 1)+left));
		T base = arr[left];
		int j = left;
		for (int i = left + 1; i <= right; i++) {
			if (base.compareTo(arr[i]) > 0) {
				j++;
				swap(arr, j, i);
			}
		}
		swap(arr, left, j);
		return j;
		//返回一躺排序后，基準(zhǔn)值的下角標(biāo)
	}
	public static void swap(Object[] arr, int i, int j) {
		if (i != j) {
			Object temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	private static void printArr(Object[] arr) {
		for (Object o : arr) {
			System.out.print(o);
			System.out.print("\t");
		}
		System.out.println();
	}
	public static void main(String args[]) {
		Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
		printArr(arr);
		//3  5  1  7  2  9  8  0  4  6
		sort(arr);
		printArr(arr);
		//0  1  2  3  4  5  6  7  8  9
	}
}

快速排序繼續(xù)優(yōu)化：配合著使用插入排序

快排是不斷減小問(wèn)題規(guī)模來(lái)解決子問(wèn)題的，需要不斷遞歸。但是遞歸到規(guī)模足夠小時(shí)，如果繼續(xù)采用這種 不穩(wěn)定+遞歸 的方式執(zhí)行下去，效率不見(jiàn)得會(huì)很好。

所以當(dāng)問(wèn)題規(guī)模較小時(shí)，近乎有序時(shí)，插入排序表現(xiàn)的很好。Java自帶的Arrays.sort()里經(jīng)常能看到這樣的注釋：“Use insertion sort on tiny arrays”，“Insertion sort on smallest arrays”

public class QuickSort {
	public static <T extends Comparable<? super T>> void sort(T[] arr) {
		sort(arr, 0, arr.length - 1, 16);
	}
	/**
   * @param arr  待排序的數(shù)組
   * @param left 左閉
   * @param right 右閉
   * @param k   當(dāng)快排遞歸到子問(wèn)題的規(guī)模 <= k 時(shí)，采用插入排序優(yōu)化
   * @param <T>  泛型，待排序可比較類型
   */
	public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
		// 規(guī)模小時(shí)采用插入排序
		if (right - left <= k) {
			insertionSort(arr, left, right);
			return;
		}
		int p = partition(arr, left, right);
		sort(arr, left, p - 1, k);
		sort(arr, p + 1, right, k);
	}
	public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {
		for (int i = l + 1; i <= r; i++) {
			T cur = arr[i];
			int j = i - 1;
			for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = cur;
		}
	}
	private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
		//排序前，先讓基準(zhǔn)值和隨機(jī)的一個(gè)數(shù)進(jìn)行交換。這樣，基準(zhǔn)值就有隨機(jī)性。
		//就不至于在數(shù)組相對(duì)有序時(shí)，導(dǎo)致左右兩邊的遞歸規(guī)模不一致，產(chǎn)生最壞時(shí)間復(fù)雜度
		swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
		T base = arr[left];
		int j = left;
		for (int i = left + 1; i <= right; i++) {
			if (base.compareTo(arr[i]) > 0) {
				j++;
				swap(arr, j, i);
			}
		}
		swap(arr, left, j);
		return j;
		//返回一躺排序后，基準(zhǔn)值的下角標(biāo)
	}
	public static void swap(Object[] arr, int i, int j) {
		if (i != j) {
			Object temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	private static void printArr(Object[] arr) {
		for (Object o : arr) {
			System.out.print(o);
			System.out.print("\t");
		}
		System.out.println();
	}
	public static void main(String args[]) {
		Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
		printArr(arr);
		//3  5  1  7  2  9  8  0  4  6
		sort(arr);
		printArr(arr);
		//0  1  2  3  4  5  6  7  8  9
	}
}

快速排序繼續(xù)優(yōu)化：兩路快排

在最開(kāi)始的普通快速排序說(shuō)過(guò)，讓基準(zhǔn)值base左邊的都比base小，而base右邊的都大于等于base。等于base的這些會(huì)聚集到右側(cè)(或者稍微改改大小關(guān)系就會(huì)聚集到左側(cè))?？傊蜁?huì)聚集到一邊。這樣在數(shù)組中重復(fù)數(shù)字很多的時(shí)候，就又會(huì)導(dǎo)致兩邊子遞歸規(guī)模差距懸殊的情況。這時(shí)想把等于base的那些數(shù)分派到base兩邊，而不是讓他們聚集到一起。

（注：測(cè)試代碼的時(shí)候，最好把插入排序那部分注視掉，向我下面代碼中那樣...不然數(shù)據(jù)量小于k=16的時(shí)候執(zhí)行的是插入排序.....）

public class QuickSort {
	public static <T extends Comparable<? super T>> void sort(T[] arr) {
		sort(arr, 0, arr.length - 1, 16);
	}
	/**
   * @param arr  待排序的數(shù)組
   * @param left 左閉
   * @param right 右閉
   * @param k   當(dāng)快排遞歸到子問(wèn)題的規(guī)模 <= k 時(shí)，采用插入排序優(yōu)化
   * @param <T>  泛型，待排序可比較類型
   */
	public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
		// 規(guī)模小時(shí)采用插入排序
		//    if (right - left <= k) {
		//      insertionSort(arr, left, right);
		//      return;
		//    }
		if (left >= right) return;
		int p = partition(arr, left, right);
		sort(arr, left, p - 1, k);
		sort(arr, p + 1, right, k);
	}
	public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {
		for (int i = l + 1; i <= r; i++) {
			T cur = arr[i];
			int j = i - 1;
			for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = cur;
		}
	}
	private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
		//排序前，先讓基準(zhǔn)值和隨機(jī)的一個(gè)數(shù)進(jìn)行交換。這樣，基準(zhǔn)值就有隨機(jī)性。
		//就不至于在數(shù)組相對(duì)有序時(shí)，導(dǎo)致左右兩邊的遞歸規(guī)模不一致，產(chǎn)生最壞時(shí)間復(fù)雜度
		swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
		T base = arr[left];
		//基準(zhǔn)值，每次都把這個(gè)基準(zhǔn)值拋出去，看成[left+1.....right]左閉右閉區(qū)間的排序
		int i = left + 1;
		//對(duì)于上一行提到的[left+1.....right]區(qū)間，i表示 [left+1......i)左閉右開(kāi)區(qū)間的值都小于等于base。
		int j = right;
		//對(duì)于上二行提到的[left+1.....right]區(qū)間，j表示 (j......right]左開(kāi)右閉區(qū)間的值都大于等于base。
		while (true) {
			//從左到右掃描，掃描出第一個(gè)比base大的元素，然后i停在那里。
			while (i <= right && arr[i].compareTo(base) < 0) i++;
			//從右到左掃描，掃描出第一個(gè)比base小的元素，然后j停在那里。
			while (j >= left && arr[j].compareTo(base) > 0) j--;
			if (i > j) {
				//雖說(shuō)是i>j，但其實(shí)都是以j=i-1為條件結(jié)束的
				break;
			}
			swap(arr, i++, j--);
		}
		swap(arr, left, j);
		return j;
		//返回一躺排序后，基準(zhǔn)值的下角標(biāo)
	}
	public static void swap(Object[] arr, int i, int j) {
		if (i != j) {
			Object temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	private static void printArr(Object[] arr) {
		for (Object o : arr) {
			System.out.print(o);
			System.out.print("\t");
		}
		System.out.println();
	}
	public static void main(String args[]) {
		Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
		printArr(arr);
		//3  5  1  7  2  9  8  0  4  6
		sort(arr);
		printArr(arr);
		//0  1  2  3  4  5  6  7  8  9
	}
}

快速排序繼續(xù)優(yōu)化：兩路快排 不用swap,用交換

上面的兩路在找到大于base的值和小于base的值時(shí)，用的是swap()方法來(lái)進(jìn)行交換。兩數(shù)交換涉及到第三個(gè)變量temp的操作，多了讀寫操作。接下來(lái)用直接賦值的方法，把小于的放到右邊，大于的放到左邊，當(dāng)i和j相遇時(shí)，那個(gè)位置就是base該放的地方。至此一趟完成。遞歸即可。

public class QuickSort {
	public static <T extends Comparable<? super T>> void sort(T[] arr) {
		sort(arr, 0, arr.length - 1, 16);
	}
	/**
   * @param arr  待排序的數(shù)組
   * @param left 左閉
   * @param right 右閉
   * @param k   當(dāng)快排遞歸到子問(wèn)題的規(guī)模 <= k 時(shí)，采用插入排序優(yōu)化
   * @param <T>  泛型，待排序可比較類型
   */
	public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
		// 規(guī)模小時(shí)采用插入排序
		//    if (right - left <= k) {
		//      insertionSort(arr, left, right);
		//      return;
		//    }
		if (left >= right) return;
		int p = partition(arr, left, right);
		sort(arr, left, p - 1, k);
		sort(arr, p + 1, right, k);
	}
	public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {
		for (int i = l + 1; i <= r; i++) {
			T cur = arr[i];
			int j = i - 1;
			for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = cur;
		}
	}
	private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
		//排序前，先讓基準(zhǔn)值和隨機(jī)的一個(gè)數(shù)進(jìn)行交換。這樣，基準(zhǔn)值就有隨機(jī)性。
		//就不至于在數(shù)組相對(duì)有序時(shí)，導(dǎo)致左右兩邊的遞歸規(guī)模不一致，產(chǎn)生最壞時(shí)間復(fù)雜度
		swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
		T base = arr[left];
		//基準(zhǔn)值，每次都把這個(gè)基準(zhǔn)值拋出去，看成[left+1.....right]左閉右閉區(qū)間的排序
		int i = left;
		//對(duì)于上一行提到的[left+1.....right]區(qū)間，i表示 [left+1......i)左閉右開(kāi)區(qū)間的值都小于等于base。
		int j = right;
		//對(duì)于上二行提到的[left+1.....right]區(qū)間，j表示 (j......right]左開(kāi)右閉區(qū)間的值都大于等于base。
		while (i < j) {
			//從右到左掃描，掃描出第一個(gè)比base小的元素，然后j停在那里。
			while (j > i && arr[j].compareTo(base) > 0) j--;
			arr[i] = arr[j];
			//從左到右掃描，掃描出第一個(gè)比base大的元素，然后i停在那里。
			while (i < j && arr[i].compareTo(base) < 0) i++;
			arr[j] = arr[i];
		}
		arr[j] = base;
		return j;
		//返回一躺排序后，基準(zhǔn)值的下角標(biāo)
	}
	public static void swap(Object[] arr, int i, int j) {
		if (i != j) {
			Object temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	private static void printArr(Object[] arr) {
		for (Object o : arr) {
			System.out.print(o);
			System.out.print("\t");
		}
		System.out.println();
	}
	public static void main(String args[]) {
		Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
		printArr(arr);
		//3  5  1  7  2  9  8  0  4  6
		sort(arr);
		printArr(arr);
		//0  1  2  3  4  5  6  7  8  9
	}
}

快速排序繼續(xù)優(yōu)化：當(dāng)大量數(shù)據(jù)，且重復(fù)數(shù)多時(shí)，用三路快排

把數(shù)組分為三路，第一路都比base小，第二路都等于base，第三路都大于base。

用指針從前到后掃描，如果：

1.cur指向的數(shù)小于base，那么：交換arr[cur]和arr[i]的值，然后i++,cur++。

2.cur指向的數(shù)等于base,那么：cur++

3.cur指向的數(shù)大于base，那么：交換arr[cur]和arr[j]的值，然后j--。

當(dāng)cur>j的時(shí)候說(shuō)明三路都已經(jīng)完成。

public class QuickSort {
	public static <T extends Comparable<? super T>> void sort(T[] arr) {
		sort(arr, 0, arr.length - 1, 16);
	}
	/**
   * @param arr  待排序的數(shù)組
   * @param left 左閉
   * @param right 右閉
   * @param k   當(dāng)快排遞歸到子問(wèn)題的規(guī)模 <= k 時(shí)，采用插入排序優(yōu)化
   * @param <T>  泛型，待排序可比較類型
   */
	public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
		// 規(guī)模小時(shí)采用插入排序
		//    if (right - left <= k) {
		//      insertionSort(arr, left, right);
		//      return;
		//    }
		if (left >= right) return;
		int[] ret = partition(arr, left, right);
		sort(arr, left, ret[0], k);
		sort(arr, ret[1], right, k);
	}
	public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {
		for (int i = l + 1; i <= r; i++) {
			T cur = arr[i];
			int j = i - 1;
			for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = cur;
		}
	}
	/**
   * @param arr  待排序的數(shù)組
   * @param left 待排序數(shù)組的左邊界
   * @param right 待排序數(shù)組的右邊界
   * @param <T>  泛型
   * @return
   */
	private static <T extends Comparable<? super T>> int[] partition(T[] arr, int left, int right) {
		//排序前，先讓基準(zhǔn)值和隨機(jī)的一個(gè)數(shù)進(jìn)行交換。這樣，基準(zhǔn)值就有隨機(jī)性。
		//就不至于在數(shù)組相對(duì)有序時(shí)，導(dǎo)致左右兩邊的遞歸規(guī)模不一致，產(chǎn)生最壞時(shí)間復(fù)雜度
		swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
		T base = arr[left];
		//基準(zhǔn)值，每次都把這個(gè)基準(zhǔn)值拋出去，看成[left+1.....right]左閉右閉區(qū)間的排序
		//三路快排分為下面這三個(gè)路(區(qū)間)
		int i = left;
		// left表示，[lleft...left) 左閉右開(kāi)區(qū)間里的數(shù)都比base小
		int j = right;
		// left表示，(rright...right] 左開(kāi)右閉區(qū)間里的數(shù)都比base大
		int cur = i;
		//用cur來(lái)遍歷數(shù)組。[left...cur)左閉右開(kāi)區(qū)間里的數(shù)都等于base
		while (cur <= j) {
			if (arr[cur].compareTo(base) == 0) {
				cur++;
			} else if (arr[cur].compareTo(base) < 0) {
				swap(arr, cur++, i++);
			} else {
				swap(arr, cur, j--);
			}
		}
		return new int[]{i - 1, j + 1};
		//[i...j]都等于base,子問(wèn)題就只需要解決i左邊和j右邊就行了
	}
	public static void swap(Object[] arr, int i, int j) {
		if (i != j) {
			Object temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	private static void printArr(Object[] arr) {
		for (Object o : arr) {
			System.out.print(o);
			System.out.print("\t");
		}
		System.out.println();
	}
	public static void main(String args[]) {
		Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
		printArr(arr);
		//3  5  1  7  2  9  8  0  4  6
		sort(arr);
		printArr(arr);
		//0  1  2  3  4  5  6  7  8  9
	}
}

到此，相信大家對(duì)“Java編程怎么實(shí)現(xiàn)快速排序及優(yōu)化”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

分享名稱：Java編程怎么實(shí)現(xiàn)快速排序及優(yōu)化
鏈接URL：http://aaarwkj.com/article12/peijdc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供搜索引擎優(yōu)化、Google、營(yíng)銷型網(wǎng)站建設(shè)、小程序開(kāi)發(fā)、品牌網(wǎng)站設(shè)計(jì)、服務(wù)器托管

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)