這篇文章，我們接著來講剩下的排序算法：冒泡排序，快速排序（遞歸和非遞歸）、歸并排序（遞歸和非遞歸）
3.3 交換排序
中心思想：
交換就是指根據(jù)序列中的兩個(gè)元素的比較結(jié)果來對換這兩個(gè)元素在序列中的位置，特點(diǎn)就是：將值較大的元素向序列尾部移動，將值較小的元素向序列前部移動
3.3.1 冒泡排序
public static void bubbleSort(int[] arr) {
for(int i = 0; i <arr.length; i++) {
boolean flag = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if(arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
flag = true;
}
}
//優(yōu)化，可加可不加
if(!flag) {
break;
}
}
}
特點(diǎn)
- 時(shí)間復(fù)雜度：不加優(yōu)化O(N2)，對數(shù)據(jù)不敏感；加了優(yōu)化最好情況會達(dá)到O(N)，對數(shù)據(jù)敏感
- 空間復(fù)雜度：O(1)
- 穩(wěn)定
3.3.2 快速排序
快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：
任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。
遞歸
本篇文章是以左邊元素作為基準(zhǔn)值。
根據(jù)基本思想，我們可以列出快排的主框架
// 假設(shè)按照升序?qū)rray數(shù)組中[start, end]區(qū)間中的元素進(jìn)行排序
public static void quickSort(int[] arr) {
quick(arr, 0, arr.length - 1);
}
private static void quick(int[] arr, int start, int end) {
if(start >= end) {
return;
}
// 按照基準(zhǔn)值對array數(shù)組的 [start, end]區(qū)間中的元素進(jìn)行劃分
int pivot = partition(arr, start, end);
// 劃分成功后以pivot為邊界形成了左右兩部分 [start, div - 1] 和 [div + 1, end]
// 遞歸排[start, div - 1]
quick(arr, start, pivot - 1);
// 遞歸排[div+1, end]
quick(arr, pivot + 1, end);
}
與二叉樹前序遍歷規(guī)則非常像，我們在寫遞歸框架時(shí)可想想二叉樹前序遍歷規(guī)則即可快速寫出來，后續(xù)只需分析如何按照基準(zhǔn)值來對區(qū)間中數(shù)據(jù)進(jìn)行劃分的方式即可。
將區(qū)間按照基準(zhǔn)值劃分為左右兩半部分的常見方式有：
-
Hoare版
以 升序、基準(zhǔn)值在左邊為例
- 先從右邊開始遍歷，遍歷到比基準(zhǔn)值小的數(shù)，停下
- 再遍歷左邊的數(shù)，遇到比基準(zhǔn)值大的數(shù)，停下
- 交換這兩個(gè)數(shù)
- 循環(huán)以上三步，直到left和right相遇停下，此時(shí)，left和right相遇的位置就是基準(zhǔn)值排好序的位置
- 然后將基準(zhǔn)值與left(或者right)下標(biāo)的值進(jìn)行交換，完成這個(gè)數(shù)的排序。
- 然后返回基準(zhǔn)值排好序的位置
//基準(zhǔn)值是左邊的元素
private static int partition(int[] arr, int left, int right) {
int index = left;//記錄基準(zhǔn)值的位置
int n = arr[left];
while(left < right) {
//最先從右邊開始比較
//找出小于基準(zhǔn)值的數(shù)
//n <= arr[right] 必須取等于
while(left < right && n <= arr[right]) {
right--;
}
//找出大于基準(zhǔn)值的數(shù)
while(left < right && n >= arr[left]) {
left++;
}
swap(arr, left, right);
}
//循環(huán)完畢之后，left和right的左邊是小于
swap(arr, index, left);//把基準(zhǔn)值放在自己的位置上
return left;
}
//基準(zhǔn)值是右邊的元素
private static int partition2(int[] arr, int left, int right) {
int index = right;
int n = arr[right];
while(left < right) {
while(left < right && n >= arr[left]) {
left++;
}
while(left < right && n <= arr[right]) {
right--;
}
swap(arr, left, right);
}
swap(arr, index, left);
return left;
}
注意：
如果基準(zhǔn)值是左邊的元素，那么一定要最先從右邊開始比較，從右邊開始移動，否則排序會出錯；
反之，最先從左邊開始比較，從左邊開始移動
-
挖坑法
以 升序、基準(zhǔn)值在左邊為例
- 可以把基準(zhǔn)值的位置想象成一個(gè)坑
- 先遍歷右邊的元素，遇到比基準(zhǔn)值小的元素，就把他放入left坑里，自己的地方形成個(gè)坑
- 在遍歷左邊的元素，遇到比基準(zhǔn)值大的元素，就把他放入right坑里，自己的地方形成個(gè)坑
- 直到left和right相遇，然后把基準(zhǔn)值放入left(right)坑里
- 完成基準(zhǔn)值的排序，返回基準(zhǔn)值排好序的位置
private static int partition3(int[] arr, int left, int right) {
int n = arr[left];
while(left < right) {
while(left < right && n <= arr[right]) {
right--;
}
arr[left] = arr[right];//將右邊小于n的數(shù)放在左邊
while(left < right && n >= arr[left]) {
left++;
}
arr[right] = arr[left];//將左邊大于n的數(shù)放在右邊
}
arr[right] = n;//基準(zhǔn)值
return left;//返回基準(zhǔn)值下標(biāo)
}
- 前后指針
寫法一：
- 初始時(shí)，
prev指針指向序列開頭，cur指針指向prev指針后一個(gè)位置. - 當(dāng)cur值小于基準(zhǔn)值key并且++prev的值不等于cur值的時(shí)候，交換cur和prev
- 當(dāng)cur的值大于等于key時(shí)，cur++，prev不動
- 當(dāng)cur小于基準(zhǔn)值key并且++prev的值等于cur值的時(shí)候，cur++
- 當(dāng)cur大于right后結(jié)束循環(huán)，交換key和prev值
注意prev什么時(shí)候動，什么時(shí)候不動。
//寫法一
private static int partition(int[] array, int left, int right) {
int key = array[left];
int prev = left;
int cur = left+1;
while (cur <= right) {
if(array[cur] < key && array[++prev] != array[cur]) {
swap(array,cur,prev);
}
cur++;
}
swap(array,prev,left);
return prev;
}
//寫法二
private static int partition(int[] array, int left, int right) {
int d = left + 1;
int pivot = array[left];
for (int i = left + 1; i <= right; i++) {
if (array[i] < pivot) {
swap(array, i, d);
d++;
}
}
swap(array, d - 1, left);
return d - 1;
}
這三種方法的常用順序是：
挖坑 > Hoare > 前后指針
當(dāng)我們用正序的10_0000數(shù)據(jù)測試時(shí)，發(fā)生了棧溢出錯誤，因?yàn)檎蚝湍嫘蚨紩纬蓡畏种У臉洌f歸調(diào)用太多了。而亂序不會。
那我們該如何優(yōu)化呢？
優(yōu)化
有兩個(gè)方法：
-
三數(shù)取中法。
找到最左邊，中間，最右邊這三個(gè)數(shù)的中間值，將他和最左邊或者最右邊的數(shù)進(jìn)行交換，盡可能將數(shù)據(jù)打亂，不讓他形成單分支的樹。
舉個(gè)例子：
private static int threeNum(int[] arr, int left, int right) { int mid = (left + right) / 2; if(arr[left] < arr[right]) { if(arr[mid] < arr[left]) { return left; } else if (arr[mid] > arr[right]) { return right; } else { return mid; } } else { if (arr[mid] < arr[right]) { return right; } else if (arr[mid] > arr[left]) { return left; } else { return mid; } } }當(dāng)我們用100_0000的數(shù)據(jù)進(jìn)行測試的時(shí)候，正序和亂序不會發(fā)生棧溢出錯誤了，但是逆序依舊會。因?yàn)槟嫘蜻f歸的次數(shù)比順序遞歸的次數(shù)多了一倍。
-
遞歸到小的子區(qū)間時(shí)，可以考慮使用插入排序。根據(jù)二叉樹的特點(diǎn)可知，二叉樹的節(jié)點(diǎn)大多集中在后面幾層，像下面這棵樹
它4/5的結(jié)點(diǎn)都在最后兩層，隨著二叉樹的層數(shù)變多，遞歸調(diào)用的次數(shù)就會越來越多，就可能會形成棧溢出，但是數(shù)據(jù)也會變得越來越有序，所以我們可以試著把后面數(shù)據(jù)排序變成插入排序，這樣不僅可以節(jié)省空間，也能減少時(shí)間。
private static void insertSort2(int[] array, int left, int right) {
for (int i = left; i <= right; i++) {
int n = array[i];
int j = i - 1;
for (; j >= left; j--) {
if(array[j] > n) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = n;
}
}
加上這兩種優(yōu)化后，代碼為：
public static void quickSort(int[] arr) {
quick(arr, 0, arr.length - 1);
}
private static void insertSort2(int[] array, int left, int right) {
for (int i = left; i <= right; i++) {
int n = array[i];
int j = i - 1;
for (; j >= left; j--) {
if(array[j] > n) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = n;
}
}
private static void quick(int[] arr, int start, int end) {
if(start >= end) {
return;
}
if(end - start + 1 <= 20) {
//直接插入排序
insertSort2(arr, start, end);
return;
}
//三數(shù)取中法
int midIndex = threeNum(arr, start, end);
swap(arr, start, midIndex);
int pivot = partition3(arr, start, end);//挖坑法
quick(arr, start, pivot - 1);
quick(arr, pivot + 1, end);
}
private static int partition3(int[] arr, int left, int right) {
int n = arr[left];
while(left < right) {
while(left < right && n <= arr[right]) {
right--;
}
arr[left] = arr[right];
while(left < right && n >= arr[left]) {
left++;
}
arr[right] = arr[left];
}
arr[right] = n;
return left;
}
private static int threeNum(int[] arr, int left, int right) {
int mid = (left + right) / 2;
if(arr[left] < arr[right]) {
if(arr[mid] < arr[left]) {
return left;
} else if (arr[mid] > arr[right]) {
return right;
} else {
return mid;
}
} else {
if (arr[mid] < arr[right]) {
return right;
} else if (arr[mid] > arr[left]) {
return left;
} else {
return mid;
}
}
}
測試100_0000的數(shù)據(jù)，逆序還是會棧溢出，直到數(shù)據(jù)到5_0000才沒有溢出，為什么逆序遞歸的次數(shù)會比順序多一倍，我現(xiàn)在也沒有搞清楚，讀者可以說出你自己的想法，歡迎在評論區(qū)留言！
特點(diǎn)
-
時(shí)間復(fù)雜度：好的情況下（完全二叉樹）
O(N*logN)：一共有l(wèi)og(N)層，每層都會遍歷n個(gè)數(shù)據(jù)；
最壞情況下（順序或者逆序，單分支）：
O(N^2)一般統(tǒng)一是
O(N*logN) -
空間復(fù)雜度：好的情況下
O(logN)；最壞情況下O(N) -
穩(wěn)定性：不穩(wěn)定
非遞歸
當(dāng)數(shù)據(jù)量非常大的時(shí)候，遞歸快排一定會發(fā)生棧溢出，那么我們可以用非遞歸的方法來實(shí)現(xiàn)快排，從而減少函數(shù)開辟所占用的內(nèi)存。
那么非遞歸該如何實(shí)現(xiàn)呢？他的中心思想又是什么呢？
先說用棧來實(shí)現(xiàn)：
把數(shù)隊(duì)的start和end下標(biāo)放入棧中，當(dāng)棧不為空的時(shí)候，也就是說數(shù)據(jù)還沒有都排完序，去找基準(zhǔn)，將基準(zhǔn)的數(shù)據(jù)放入他自己的位置后，放入 以基準(zhǔn)為分界線的 左右兩邊數(shù)隊(duì)的start和end坐標(biāo)。
這里要注意的是，當(dāng)基準(zhǔn)的前面或者是后面只有一個(gè)數(shù)據(jù)的時(shí)候，就不用放了，因?yàn)檫@個(gè)數(shù)已經(jīng)有序了。
然后再彈出一組數(shù)隊(duì)的坐標(biāo)，開始新一輪的找基準(zhǔn)，以此類推，直到棧為空，說明這組數(shù)已經(jīng)有序。
圖示：
public static void quickSort2(int[] arr) {
Stack<Integer> stack = new Stack<>();
int start = 0;
int end = arr.length - 1;
int pivot = partition3(arr, start, end);
//pivot的左邊和右邊的元素個(gè)數(shù)大于一個(gè)再放入棧中，否則沒有意義。
if (pivot > start + 1) {
stack.push(start);
stack.push(pivot - 1);
}
if (pivot < end - 1) {
stack.push(pivot + 1);
stack.push(end);
}
while (!stack.empty()) {
//賦值新的
end = stack.pop();
start = stack.pop();
pivot = partition3(arr,start,end);
if (pivot > start + 1) {
stack.push(start);
stack.push(pivot - 1);
}
if (pivot < end - 1) {
stack.push(pivot + 1);
stack.push(end);
}
}
}
100_0000數(shù)字測試：
很明顯，在100_0000數(shù)據(jù)下，用非遞歸的方法不會造成棧溢出，但是耗費(fèi)的時(shí)間還是相當(dāng)多的。
優(yōu)化
于是我們對非遞歸代碼進(jìn)行了優(yōu)化
public static void quickSort2(int[] arr) {
Stack<Integer> stack = new Stack<>();
int start = 0;
int end = arr.length - 1;
if(end - start + 1 <= 20) {
//直接插入排序
insertSort2(arr, start, end);
return;
}
//三數(shù)取中法
int midIndex = threeNum(arr, start, end);
swap(arr, start, midIndex);
int pivot = partition3(arr, start, end);
if (pivot > start + 1) {
stack.push(start);
stack.push(pivot - 1);
}
if (pivot < end - 1) {
stack.push(pivot + 1);
stack.push(end);
}
while (!stack.empty()) {
end = stack.pop();
start = stack.pop();
if(end - start + 1 <= 20) {
//直接插入排序
insertSort2(arr, start, end);
//這里不能向上面一樣return，因?yàn)槿绻苯觬eturn了的話，會導(dǎo)致其他區(qū)間的數(shù)值還沒有被排序，程序就直接結(jié)束了，這樣只會使一小區(qū)間被排序
} else {
//三數(shù)取中法
midIndex = threeNum(arr, start, end);
swap(arr, start, midIndex);
pivot = partition3(arr,start,end);
if (pivot > start + 1) {
stack.push(start);
stack.push(pivot - 1);
}
if (pivot < end - 1) {
stack.push(pivot + 1);
stack.push(end);
}
}
}
}
測試100_0000的數(shù)據(jù)：
很明顯！快了很多！占用的空間也變少了！
3.4 歸并排序
歸并排序的基本思想：
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。 歸并排序核心步驟：
3.4.1 遞歸
歸并排序核心步驟：
-
分解
每組分成[l,m]和[m+1,r]兩部分，然后再遞歸這兩部分。
當(dāng)l>=r的時(shí)候，"遞"停止，"歸"開始，合并開始。
private static void mergeFunc(int[] arr, int left, int right) { //遞歸的結(jié)束條件 if(left >= right) { return; } int mid = (left + right) / 2; //分組遞歸 mergeFunc(arr, left, mid); mergeFunc(arr, mid + 1, right); //合并 merge(arr, left, mid, right); } -
合并
當(dāng)遞歸到只有一個(gè)數(shù)的時(shí)候，“遞”就結(jié)束了，開始“歸”，合并是在數(shù)的左右兩邊的數(shù)都遍歷完了之后才開始的。
以下面的圖片為例，大家不要和我上面的大圖搞混了，我上面的大圖里的l，r，m是遞的時(shí)候傳的參數(shù)，而不是當(dāng)前方法內(nèi)的left和right和mid的值。
以這個(gè)為例，先申請一個(gè)大小為l - r + 1的新數(shù)組，然后定義s1，e1，s2，e2.
int s1 = left; int e1 = mid; int s2 = mid + 1; int e2 = right; int[] tmpArr = new int[right - left + 1];
怎樣往新數(shù)組里面按順序地放數(shù)字呢？
我們可以比較arr[s1]和arr[s2]的值，把小的值放入數(shù)組，如上圖，arr[s1] < arr[s2],所以我們將arr[s1]放入數(shù)組，s1++，循環(huán)以上步驟，當(dāng)s1 > e1或者s2 > e2時(shí)中斷循環(huán)。
int k = 0;
while(s1 <= e1 && s2 <= e2) {
if(arr[s1] <= arr[s2]) {
tmpArr[k++] = arr[s1++];
} else {
tmpArr[k++] = arr[s2++];
}
}
循環(huán)終止后，可能仍然有沒有放入新數(shù)組的數(shù)，這時(shí)我們就要判斷，哪一組沒有放完，繼續(xù)放。
while(s1 <= e1) {
tmpArr[k++] = arr[s1++];
}
while (s2 <= e2) {
tmpArr[k++] = arr[s2++];
}
最后再將新數(shù)組的值賦給舊數(shù)組。
注意：
這里堅(jiān)決不能這樣寫：arr[i] = tmpArr[i]
因?yàn)槟阋獙?yīng)原數(shù)組的坐標(biāo)進(jìn)行賦值：
以上圖為例，tmpArr[0]賦給arr[4]，我們可以這樣寫arr[i + left] = tmpArr[i]，這樣就可以復(fù)制給對應(yīng)坐標(biāo)了
for (int i = 0; i < k; i++) {
arr[i + left] = tmpArr[i];
}
這里是完整代碼
private static void merge(int[] arr, int left, int mid, int right) {
int s1 = left;
int e1 = mid;
int s2 = mid + 1;
int e2 = right;
int[] tmpArr = new int[right - left + 1];
int k = 0;
while(s1 <= e1 && s2 <= e2) {
if(arr[s1] <= arr[s2]) {
tmpArr[k++] = arr[s1++];
} else {
tmpArr[k++] = arr[s2++];
}
}
while(s1 <= e1) {
tmpArr[k++] = arr[s1++];
}
while (s2 <= e2) {
tmpArr[k++] = arr[s2++];
}
for (int i = 0; i < k; i++) {
arr[i + left] = tmpArr[i];
}
}
private static void mergeFunc(int[] arr, int left, int right) {
if(left >= right) {
return;
}
int mid = (left + right) / 2;
mergeFunc(arr, left, mid);
mergeFunc(arr, mid + 1, right);
merge(arr, left, mid, right);
}
public static void mergeSort(int[] arr) {
mergeFunc(arr, 0, arr.length - 1);
}
3.4.2 非遞歸
非遞歸的思路其實(shí)和遞歸的合并步驟思路一樣，我們先假設(shè)的是數(shù)組已經(jīng)遞歸完了，已經(jīng)分成一個(gè)一個(gè)的數(shù)了，開始合并。
1個(gè)合并成2個(gè)，2個(gè)合并成4個(gè)，設(shè)當(dāng)前合并的數(shù)字有g(shù)ap個(gè)，定義left，right，mid，然后調(diào)用合并方法合并。
注意i的變化，i+=gap*2可以遍歷其他組的數(shù)據(jù)并合并。
private static void merge(int[] arr, int left, int mid, int right) {
int s1 = left;
int e1 = mid;
int s2 = mid + 1;
int e2 = right;
int[] tmpArr = new int[right - left + 1];
int k = 0;
while(s1 <= e1 && s2 <= e2) {
if(arr[s1] <= arr[s2]) {
tmpArr[k++] = arr[s1++];
} else {
tmpArr[k++] = arr[s2++];
}
}
while(s1 <= e1) {
tmpArr[k++] = arr[s1++];
}
while (s2 <= e2) {
tmpArr[k++] = arr[s2++];
}
for (int i = 0; i < k; i++) {
arr[i + left] = tmpArr[i];
}
}
public static void mergeSort1(int[] arr) {
int gap = 1;
while(gap < arr.length) {
for (int i = 0; i < arr.length; i+= gap * 2) {
int left = i;//i不會越界
int mid = left + gap - 1;
int right = mid + gap;
//注意：mid 和 right可能會發(fā)生越界，要判斷并修正
if (mid >= arr.length) {
mid = arr.length - 1;
}
if(right >= arr.length) {
right = arr.length - 1;
}
merge(arr, left, mid, right);
}
gap *= 2;
}
}
特點(diǎn)
-
歸并的缺點(diǎn)在于需要O(N)的空間復(fù)雜度。
-
時(shí)間復(fù)雜度：
O(N*logN)，對數(shù)據(jù)不敏感。遞歸
logN層，每一層都要對n個(gè)數(shù)排序，遍歷n個(gè)數(shù)，相乘為O(N*logN) -
空間復(fù)雜度：
O(N)，開辟了額外的數(shù)組 -
穩(wěn)定性：穩(wěn)定
3.4.3 海量數(shù)據(jù)的排序問題
外部排序：排序過程需要在磁盤等外部存儲進(jìn)行的排序
前提：內(nèi)存只有 1G，需要排序的數(shù)據(jù)有 100G
因?yàn)閮?nèi)存中因?yàn)闊o法把所有數(shù)據(jù)全部放下，所以需要外部排序，而歸并排序是最常用的外部排序
- 先把文件切分成 200 份，每個(gè) 512 M，把每個(gè)小文件當(dāng)中的數(shù)據(jù)讀取到內(nèi)存中進(jìn)行排序。
- 分別對 512 M 排序，因?yàn)閮?nèi)存已經(jīng)可以放的下，所以任意排序方式都可以，排序完之后再寫入文件，此時(shí)這 512 M的每個(gè)文件就已經(jīng)有序了。
- 進(jìn)行2路歸并，同時(shí)對 200 份有序文件做歸并過程，最終結(jié)果就有序了。
4. 排序算法復(fù)雜度及穩(wěn)定性分析
文章來源：http://www.zghlxwxcb.cn/news/detail-448753.html
| 排序方法 | 最好 | 平均 | 最壞 | 空間復(fù)雜度 | 穩(wěn)定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n)(加優(yōu)化) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 |
| 選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 |
| 希爾排序 | O(n) | O(n^1.3) | O(n^1.5) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(1) | 不穩(wěn)定 |
| 快速排序 | O(n * log(n)) | O(n * log(n)) | O(n^2) | O(log(n)) ~ O(n) | 不穩(wěn)定 |
| 歸并排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(n) | 穩(wěn)定 |
對于這些復(fù)雜度和穩(wěn)定性，背是最容易忘的，我們要根據(jù)算法的原理來理解，并且自己要能推出來，這樣是記的最牢的方法了??
這篇文章就先到這里啦~如果有什么問題可以在評論區(qū)留言或者是私信我呦??
下篇預(yù)告：十大排序算法（下）：計(jì)數(shù)排序，基數(shù)排序，桶排序文章來源地址http://www.zghlxwxcb.cn/news/detail-448753.html
到了這里，關(guān)于十大排序算法（中）：冒泡排序，快速排序（遞歸和非遞歸）、歸并排序（遞歸和非遞歸）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
