1、排序算法

排序也稱排序算法(Sort Algorithm)，排序是将一組資料，依指定的順序進行排列的過程。

2、排序的分類

2.1按使用記憶體情況分

内部排序:

指将需要處理的所有資料都加載到内部存儲器中進行排序。
外部排序法：

資料量過大，無法全部加載到記憶體中，需要借助外部存儲進行

排序。

算法（Java實作）-圖解十大經典排序算法(一）——交換排序（冒泡排序、快速排序）1、排序算法2、排序的分類3、算法的複雜度4、冒泡排序5、快速排序算法

2.2按是否為比較類分

比較類排序：通過比較來決定元素間的相對次序，由于其時間複雜度不能突破O(nlogn)，是以也稱為非線性時間比較類排序。
非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運作，是以也稱為線性時間非比較類排序。

算法（Java實作）-圖解十大經典排序算法(一）——交換排序（冒泡排序、快速排序）1、排序算法2、排序的分類3、算法的複雜度4、冒泡排序5、快速排序算法

3、算法的複雜度

穩定：如果a原本在b前面，而a=b，排序之後a仍然在b的前面。
不穩定：如果a原本在b的前面，而a=b，排序之後 a 可能會出現在 b 的後面。
時間複雜度：對排序資料的總的操作次數。反映當n變化時，操作次數呈現什麼規律。
空間複雜度：是指算法在計算機内執行時所需存儲空間的度量，它也是資料規模n的函數。

（時間複雜度和空間複雜度）

算法（Java實作）-圖解十大經典排序算法(一）——交換排序（冒泡排序、快速排序）1、排序算法2、排序的分類3、算法的複雜度4、冒泡排序5、快速排序算法

4、冒泡排序

4.1冒泡排序基本介紹

冒泡排序（Bubble Sorting）的基本思想：通過對待排序序列從前向後（從下标較小的元素開始）,依次比較相鄰元素的值，若發現逆序則交換，使值較大的元素逐漸從前部移向後部，就象水底下的氣泡一樣逐漸向上冒。

算法描述：

比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數；
針對所有的元素重複以上的步驟，除了最後一個；
重複上面的步驟，直到排序完成。

冒泡排序的優化：

因為排序的過程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進行過交換，就說明序列有序，是以要在排序過程中設定一個标志flag判斷元素是否進行過交換。進而減少不必要的比較。(這裡說的優化，可以在冒泡排序寫好後，再進行)

4.2冒泡排序算法的實作

圖解排序過程：

算法（Java實作）-圖解十大經典排序算法(一）——交換排序（冒泡排序、快速排序）1、排序算法2、排序的分類3、算法的複雜度4、冒泡排序5、快速排序算法

代碼實作：

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class BubbleSort {
	public static void main(String[] args) {
		int arr1[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};	
		System.out.println("排序前");
		System.out.println(Arrays.toString(arr1));
		bubbleSort(arr1);	
		System.out.println("排序後");
		System.out.println(Arrays.toString(arr1));
			
		//測試一下冒泡排序的速度O(n^2), 給80000個資料，測試
		//建立要給80000個的随機的數組
		int[] arr2 = new int[80000];
		for(int i =0; i < 80000;i++) {
			arr2[i] = (int)(Math.random() * 8000000); //生成一個[0, 8000000) 數
		}	
		Date data1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(data1);
		System.out.println("排序前的時間是=" + date1Str);	
		bubbleSort(arr2);	
		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序後的時間是=" + date2Str);			
	}
	//冒泡排序算法
	public static void bubbleSort(int[] arr) {
		// 冒泡排序 的時間複雜度 O(n^2), 自己寫出
		int temp = 0; // 臨時變量
		boolean flag = false; // 辨別變量，表示是否進行過交換
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = 0; j < arr.length - 1 - i; j++) {
				// 如果前面的數比後面的數大，則交換
				if (arr[j] > arr[j + 1]) {
					flag = true;
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
			if (!flag) { // 在一趟排序中，一次交換都沒有發生過
				break;
			} else {
				flag = false; // 重置flag!!!, 進行下次判斷
			}
		}
	}
}

排序前
[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序後
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
排序前的時間是=2020-09-14 12:16:50
排序後的時間是=2020-09-14 12:16:58

5、快速排序算法

5.1快速排序算法的基本介紹

快速排序（Quicksort）是對冒泡排序的一種改進。

基本思想是：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列

算法描述：

（快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists））

從數列中挑出一個元素，稱為 “基準”（pivot）；
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
遞歸（recursive）地把小于基準值元素的子數列和大于基準值元素的子數列排序。

比如：

5.2快速排序算法的實作

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class QuickSort {
	public static void main(String[] args) {
		int arr1[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		System.out.println("排序前");
		System.out.println(Arrays.toString(arr1));
		quickSort(arr1,0,arr1.length-1);	
		System.out.println("排序後");
		System.out.println(Arrays.toString(arr1));
		
		//測試快排的執行速度
		// 建立要給80000個的随機的數組
		int[] arr2 = new int[8000000];
		for (int i = 0; i < 8000000; i++) {
			arr2[i] = (int) (Math.random() * 8000000); // 生成一個[0, 8000000) 數
		}		
		System.out.println("排序前");
		Date data1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(data1);
		System.out.println("排序前的時間是=" + date1Str);	
		quickSort(arr2, 0, arr2.length-1);		
		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序前的時間是=" + date2Str);
	}
	
	//快速排序算法
	public static void quickSort(int[] arr,int left, int right) {
		int l = left; //左下标
		int r = right; //右下标
		//pivot 中軸值
		int pivot = arr[(left + right) / 2];
		int temp = 0; //臨時變量，作為交換時使用
		//while循環的目的是讓比pivot 值小放到左邊
		//比pivot 值大放到右邊
		while( l < r) { 
			//在pivot的左邊一直找,找到大于等于pivot值,才退出
			while( arr[l] < pivot) {
				l += 1;
			}
			//在pivot的右邊一直找,找到小于等于pivot值,才退出
			while(arr[r] > pivot) {
				r -= 1;
			}
			//如果l >= r說明pivot 的左右兩的值，已經按照左邊全部是
			//小于等于pivot值，右邊全部是大于等于pivot值
			if( l >= r) {
				break;
			}		
			//交換
			temp = arr[l];
			arr[l] = arr[r];
			arr[r] = temp;		
			//如果交換完後，發現這個arr[l] == pivot值 相等 r--， 前移
			if(arr[l] == pivot) {
				r -= 1;
			}
			//如果交換完後，發現這個arr[r] == pivot值 相等 l++， 後移
			if(arr[r] == pivot) {
				l += 1;
			}
		}		
		// 如果 l == r, 必須l++, r--, 否則為出現棧溢出
		if (l == r) {
			l += 1;
			r -= 1;
		}
		//向左遞歸
		if(left < r) {
			quickSort(arr, left, r);
		}
		//向右遞歸
		if(right > l) {
			quickSort(arr, l, right);
		}	
	}
}

排序前
[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序後
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
排序前
排序前的時間是=2020-09-14 12:36:40
排序前的時間是=2020-09-14 12:36:41

排序算法相關博文：

算法（Java實作）-圖解十大經典排序算法(一）——交換排序（冒泡排序、快速排序）

算法（Java實作）-圖解十大經典排序算法(二）——插入排序（直接插入排序、希爾排序）

算法（Java實作）-圖解十大經典排序算法(三）——選擇排序（簡單選擇排序、堆排序）

算法（Java實作）-圖解十大經典排序算法(四）——歸并排序

算法（Java實作）-圖解十大經典排序算法(五）——計數排序、桶排序、基數排序

歡迎持續關注：部落格首頁

我的個人部落格站：jQueryZK Blog

算法（Java實作）-圖解十大經典排序算法(一）——交換排序（冒泡排序、快速排序）1、排序算法2、排序的分類3、算法的複雜度4、冒泡排序5、快速排序算法

1、排序算法

2、排序的分類

2.1按使用記憶體情況分

2.2按是否為比較類分

3、算法的複雜度

4、冒泡排序

4.1冒泡排序基本介紹

4.2冒泡排序算法的實作

5、快速排序算法

5.1快速排序算法的基本介紹

5.2快速排序算法的實作

繼續閱讀

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希