天天看點
傳回

（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）

目錄

快速排序 （Quick Sort）

快速排序執行流程

軸點構造

構造軸點-複雜度分析

快速排序 -- 與軸點行相等的元素

快速排序最終實作源碼

希爾排序（Shell Sort）

希爾排序執行個體

步長序列計算代碼

步長序列優化

希爾排序最終代碼實作

快速排序 （Quick Sort）

快速排序執行流程

  • ① 從序列中選擇一個軸點元素（pivot）
    • 假設每次選擇 0 位置的元素為軸點元素
  • ② 利用 pivot 将序列分割成 2 個子序列
    • 将小于 pivot 的元素放在pivot前面（左側）
    • 将大于 pivot 的元素放在pivot後面（右側）
    • 等于pivot的元素放哪邊都可以
  • ③ 對子序列進行 ① ② 操作
    • 直到不能再分割（子序列中隻剩下1個元素）
（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）
  • 快速排序的本質就是：
    • 逐漸将每一個元素都轉換成軸點元素。

軸點構造

  • 最終目标是構造出以軸點元素為中心的序列：
    • 左半邊是小于軸點元素的序列
    • 右半邊是大于軸點元素的序列
（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）
  • 首先将 begin位置的元素進行備份，作為軸點元素。
  • begin 為序列首位置。
    • 從右往左掃描，尋找比軸點元素小的元素；
      • 找到以後，放到 begin 位置，begin++，然後反向尋找；
    • 從左往右掃描，尋找比軸點元素大的元素；
      • 找到以後，放到 end 位置，end--，然後反向尋找;
    • 當 begin == end，說明左右都掃描完了，此時将一開始備份的軸點元素放到中間。 
/**
 * 構造出 [begin, end) 範圍的軸點元素
 * @return 軸點元素的最終位置
 */
private int pivotIndex(int begin, int end){	
	// 備份begin位置的元素
	T pivot = array[begin];
	// end指向最後一個元素
	end--;
	while(begin < end){
		while(begin < end){	// 從右往左掃描
			if(cmp(pivot, array[end]) < 0){ // 右邊元素 > 軸點元素
				end--;
			}else{ // 右邊元素 <= 軸點元素
				array[begin++] = array[end];	
				break;
			}
		}
		while(begin < end){ // 從左往右掃描
			if(cmp(pivot, array[begin]) > 0){ // 左邊元素 < 軸點元素
				begin++;
			}else{ // 左邊元素 >= 軸點元素
				array[end--] = array[begin];
				break;
			}
		}
	}
	// 将軸點元素放入最終的位置
	array[begin] = pivot;
	// 傳回軸點元素的位置
	return begin; // begin==end
}
  • 測試
（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）

構造軸點-複雜度分析

  • 在軸點左右元素數量比較均勻的情況下，同時也是最好情況：
    • T(n) = 2 ∗ T(n/2) + O(n) = O(nlogn)
  • 如果軸點左右元素數量極度不均勻，最壞情況：
    • T(n) = T(n − 1) + O(n) = O(n2)
（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）
  • 為了降低最壞情況的出現機率，一般采取的做法是随機選擇軸點元素 
private int pivotIndex(int begin, int end) {
	// 随機選擇一個元素跟begin位置進行交換
	swap(begin, begin + (int)(Math.random() * (end - begin)));
	
	// 備份begin位置的元素
	T pivot = array[begin];
	// end指向最後一個元素

...

快速排序 -- 與軸點行相等的元素

（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）
  • 如果序列中的所有元素都與軸點元素相等，利用上面的算法實作，軸點元素可以将序列分割成 2 個均勻的子序列。
  • 思考：把上面的代碼中，cmp 位置的判斷分别改為 ≤、≥ 會起到什麼效果？
（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）
（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）
  • 軸點元素分割出來的子序列極度不均勻
  • 導緻出現最壞時間複雜度 O(n^2)

快速排序最終實作源碼 

/**
 * 快速排序
 */
public class QuickSort<T extends Comparable<T>> extends Sort<T> {

	@Override
	protected void sort() {
		sort(0, array.length);
	}
	/**
	 * 對 [begin, end) 範圍的元素進行快速排序
	 */
	private void sort(int begin, int end){
		if(end - begin < 2) return;
		
		// 确定軸點位置 O(n)
		int mid = pivotIndex(begin, end);
		// 對子序列進行快速排序
		sort(begin, mid);
		sort(mid + 1, end);
	}
	/**
	 * 構造出 [begin, end) 範圍的軸點元素
	 * @return 軸點元素的最終位置
	 */
	private int pivotIndex(int begin, int end){
		// 随機選擇軸點元素
		swap(begin, begin + (int)Math.random()*(end - begin));
		// 備份begin位置的元素
		T pivot = array[begin];
		// end指向最後一個元素
		end--;
		while(begin < end){
			while(begin < end){	// 從右往左掃描
				if(cmp(pivot, array[end]) < 0){ // 右邊元素 > 軸點元素
					end--;
				}else{ // 右邊元素 <= 軸點元素
					array[begin++] = array[end];	
					break;
				}
			}
			while(begin < end){ // 從左往右掃描
				if(cmp(pivot, array[begin]) > 0){ // 左邊元素 < 軸點元素
					begin++;
				}else{ // 左邊元素 >= 軸點元素
					array[end--] = array[begin];
					break;
				}
			}
		}
		// 将軸點元素放入最終的位置
		array[begin] = pivot;
		// 傳回軸點元素的位置
		return begin; // begin==end
	}
	
}
【總結】
  • 快速排序的複雜度與穩定性：
    • 最好、平均時間複雜度：O(nlogn)
    • 最壞時間複雜度：O(n^2)
    • 由于遞歸調用的緣故，空間複雜度：O(logn)
    • 屬于不穩定排序

希爾排序（Shell Sort）

  • 希爾排序把序列看作是一個矩陣，分成 𝑚 列，逐列進行排序
    • 𝑚 從某個整數逐漸減為1
    • 當 𝑚 為1時，整個序列将完全有序
  • 是以，希爾排序也被稱為遞減增量排序（Diminishing Increment Sort）
  • 矩陣的列數取決于步長序列（step sequence）：
    • 比如,如果步長序列為{1,5,19,41,109…},就代表依次分成109列、41列、19列、5列、1列
    • ​​不同的步長序列，執行效率也不同

希爾排序執行個體

  • 分成8列排序
（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）
  •  分成4列排序
（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）
  •  分成2列排序
（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）
  •  分成1列排序
（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）
  • 不難看出來，從8列變為1列的過程中，逆序對的數量在逐漸減少
  • 是以希爾排序底層一般使用插入排序對每一列進行排序，也很多資料認為希爾排序是插入排序的改進版
（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）
  • 假設元素在第 col 列、第 row 行，步長（總列數）是 step
    • 那麼這個元素在數組中的索引是 row * step + col
      • 比如 9 在排序前是第 0 行、第 2 列，那麼它排序前的索引是 0 * 5 + 2 = 2
      • 比如 4 在排序前是第 1 行、第 2 列，那麼它排序前的索引是 1 * 5 + 2 = 7
  • 代碼實作 
@Override
protected void sort() {
	List<Integer> stepSequence = shellStepSequence();
	for (Integer step : stepSequence) {
		sort(step);
	}
}

/**
 * 分成step列進行排序
 */
private void sort(int step) {
	// col : 第幾列，column的簡稱
	for (int col = 0; col < step; col++) { // 對第col列進行排序
		// col、col+step、col+2*step、col+3*step
		for (int begin = col + step; begin < array.length; begin += step) {
			int cur = begin;
			while (cur > col && cmp(cur, cur - step) < 0) {
				swap(cur, cur - step);
				cur -= step;
			}
		}
	}
}

private List<Integer> shellStepSequence() {
	List<Integer> stepSequence = new ArrayList<>();
	int step = array.length;
	while ((step >>= 1) > 0) {
		stepSequence.add(step);
	}
	return stepSequence;
}
  • 測試：
（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）

步長序列計算代碼

  • 使用希爾本人給出的步長序列：
    （戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）
    （戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）
    ，比如 𝑛 為16時，步長序列是 { 1, 2, 4, 8 } 
/**
 * 希爾本人提出的步長序列
 */
public List<Integer> shellStpSequence(){
	List<Integer> stepSequence = new ArrayList<>();
	int step = array.length; // 16
	while((step >>= 1) > 0){ // 8 4 2 1
		stepSequence.add(step);
	}
	return stepSequence;
}

步長序列優化

  • 隻是提高了最壞和平均時間複雜度，但是沒有突破最好時間複雜度O(n)。
（戀上資料結構筆記）：快速排序 （Quick Sort）、希爾排序（Shell Sort）快速排序 （Quick Sort）希爾排序（Shell Sort）
  • 代碼實作 
/**
 * 目前效率最高的步長序列
 */
private List<Integer> sedgewickStepSequence() {
	List<Integer> stepSequence = new LinkedList<>();
	int k = 0, step = 0;
	while (true) {
		if (k % 2 == 0) {
			int pow = (int) Math.pow(2, k >> 1);
			step = 1 + 9 * (pow * pow - pow);
		} else {
			int pow1 = (int) Math.pow(2, (k - 1) >> 1);
			int pow2 = (int) Math.pow(2, (k + 1) >> 1);
			step = 1 + 8 * pow1 * pow2 - 6 * pow2;
		}
		if (step >= array.length) break;
		stepSequence.add(0, step);
		k++;
	}
	return stepSequence;
}

希爾排序最終代碼實作 

public class ShellSort<T extends Comparable<T>> extends Sort<T> {

	@Override
	protected void sort() {
		List<Integer> stepSequence = sedgewickStepSequence();
		for (Integer step : stepSequence) {
			sort(step);
		}
	}
	
	/**
	 * 分成step列進行排序
	 */
	private void sort(int step) {
		// col : 第幾列，column的簡稱
		for (int col = 0; col < step; col++) { // 對第col列進行排序
			// col、col+step、col+2*step、col+3*step
			for (int begin = col + step; begin < array.length; begin += step) {
				int cur = begin;
				while (cur > col && cmp(cur, cur - step) < 0) {
					swap(cur, cur - step);
					cur -= step;
				}
			}
		}
	}
	
	private List<Integer> shellStepSequence() {
		List<Integer> stepSequence = new ArrayList<>();
		int step = array.length;
		while ((step >>= 1) > 0) {
			stepSequence.add(step);
		}
		return stepSequence;
	}
	
	private List<Integer> sedgewickStepSequence() {
		List<Integer> stepSequence = new LinkedList<>();
		int k = 0, step = 0;
		while (true) {
			if (k % 2 == 0) {
				int pow = (int) Math.pow(2, k >> 1);
				step = 1 + 9 * (pow * pow - pow);
			} else {
				int pow1 = (int) Math.pow(2, (k - 1) >> 1);
				int pow2 = (int) Math.pow(2, (k + 1) >> 1);
				step = 1 + 8 * pow1 * pow2 - 6 * pow2;
			}
			if (step >= array.length) break;
			stepSequence.add(0, step);
			k++;
		}
		return stepSequence;
	}
}
資料結構與算法學習筆記
上一篇: matlab 矩陣除法 0,Matlab中的矩陣除法有問題？？？
下一篇: SpringBoot的入門搭建（三）

繼續閱讀