排序算法總結(分析+圖+Java實作)

目錄

• 表格
• 【選擇排序】 O(n^2^) 不穩
• • 📃思想描述
• 【冒泡排序】 O(n^2^) 穩
• • 📃思想描述
  • 優化寫法
• 【插入排序】 O(n^2^) 穩
• • 📃思想描述
  • 【二分插入排序】
• 【希爾排序】 O(n^1.3^) 不穩
• • 📃思想描述
• 【歸并排序】 O(n*logn) 穩
• • 📃思想描述
  • Java裡的對象排序
  • 【TimSort】
• 【快速排序】O(nlogn) 不穩
• • 📃思想描述

寫篇部落格自己回憶一下，如果也能幫助到其他人那更好了。

标題中的時間複雜度均指是是平均時間複雜度。

表格

排序算法	平均時間複雜度	最壞	最好	空間	穩不穩
選擇排序	n2	n2	n2	1	不穩
冒泡排序	n2	n2	n	1	穩
插入排序	n2	n2	n	1	穩
二分插入排序	n2	n2	n	1	穩
希爾排序	n1.3	n2	n	1	不穩
歸并排序	nlogn	nlogn	nlogn	n	穩
TimSort	nlogn	nlogn	n	n	穩
快速排序	nlogn	n2	nlogn	logn	不穩
堆排序	nlogn	nlogn	nlogn	1	不穩
桶排序	n+k	n2	n	n+k	穩
計數排序	n+k	n+k	n+k	n+k	穩
基數排序	n*k	n*k	n*k	n+k	穩

💗🧡💛💚💙💜💗🧡💛💚💙💜💗🧡💛💚💙💜

【選擇排序】 O(n2) 不穩

📃思想描述

• 每輪找最小的，記錄下标往前放
• 最小的記錄下标，一輪結束交換位置

最簡單但是最沒用的排序算法。

思路就是每趟都找剩下的當中最小的那一個。

就是每次都選擇最小的那個往前放。

簡單排序的時間複雜度為O(n2)，這種排序算法不穩定。

## 0->length-1
### i+1->length
#### 比較更新minPos
           

public class SelectionSort {

	public static void main(String[] args) {
		
		int[] arr = {5,3,6,8,1,7,9,4,2};
		int minPos;//記錄目前輪次最小值的下标
		
		for(int i=0;i<arr.length-1;i++) {
			minPos = i;
			for(int j=i+1;j<arr.length;j++) {
				minPos = arr[j] < arr[minPos] ? j : minPos;
			}
			int temp = arr[i];
			arr[i] = arr[minPos];
			arr[minPos] = temp;
		}
		
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}
		
	}
}

           

【冒泡排序】 O(n2) 穩

其實我感覺冒泡和選擇有點像

不過冒泡是每輪找最大的那個。

但是選擇是每輪找最小的那個，并且不用邊找邊交換位置，而是記錄下标，一輪結束了再交換。

📃思想描述

• 每輪都找最大的往後放
• 邊找邊換位置，讓大的冒泡到最後

## 0->length-1
### 0->length-i-1
#### 比較交換位置
           

public static void main(String[] args) {
		
		int[] arr = {5,3,6,8,1,7,9,4,2};
		
		for(int i=0;i<arr.length-1;i++) {
			for(int j=0;j<arr.length-i-1;j++) {
				if(arr[j]>arr[j+1]) {
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
		
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}
	}
           

時間複雜度為O(n2)，

冒泡排序是穩定的排序方法。

優化寫法

冒泡排序最好的情況是O(n)，改進的寫法如下：

public void bubbleSort(int arr[]) {
    boolean didSwap;
    for(int i = 0, len = arr.length; i < len - 1; i++) {
        didSwap = false;
        for(int j = 0; j < len - i - 1; j++) {
            if(arr[j + 1] < arr[j]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                didSwap = true;
            }
        }
        if(didSwap == false) //如果是false，說明剩下的全部是有序的
            return;
    }    
}
           

【插入排序】 O(n2) 穩

對于基本有序的數組最好用

📃思想描述

• 往已經有序的部分中插入下一個數
• 通過交換位置每輪保證目前部分有序

## 1->length
### i->0
#### 比較交換位置
           

public static void main(String[] args) {
		
		int[] arr = {5,3,6,8,1,7,9,4,2};
		
		for(int i=1;i<arr.length;i++) {
			for(int j=i;j>0;j--) {
				if(arr[j]<arr[j-1]) {
					int temp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = temp;
				}
			}
		}
		
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}

	}
           

插排最好情況的和冒泡是一緻的，改進算法也可以按照冒泡的那個寫。

【二分插入排序】

插入排序還可以改進為二分插入排序，在有序部分中找到正确位置這一步驟可以使用二分查找來完成，找到位置再将後面的元素後移。這樣主要是節省比較的時間，雖然依然要移動相同數量的元素，但是數組平移比元素一個一個交換還是要快一點點。

public static void main(String[] args) {
		
		int[] arr = {7,4,3,6,5,2,1,8,12,11,9,10};
		
		for(int i=1;i<arr.length;i++) {
			int des = binarySert(0,i-1,arr,arr[i]);
			int temp = arr[i]; //記錄待插入的數
			for(int j=i;j>des;j--) { //這裡必須逆序,temp記錄的是後一個
				arr[j]=arr[j-1];
			}
			arr[des]=temp;
		}
		
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}
		
	}
	
	public static int binarySert(int start,int end, int[] arr, int a) {
		int mid = start+(end-start)/2;
		//這裡end是有可能會小于start的,循環終止條件不能寫start!=end
		while(start<=end) { 
			if(arr[mid]>a) {
				end=mid-1;
			}else {
				start=mid+1;
			}
			mid = start+(end-start)/2;
		}
		return start;
	}
           

【希爾排序】 O(n1.3) 不穩

插排的改進，為什麼效率比插排好，因為比如像1，通過三步就可以到最前面，而普通排序需要比對很多次。

一次排下來，小的數基本上都放到前面去了，大的很多都在後面了。

📃思想描述

• 每輪按照指定間隔插入排序
• 不斷縮小間隔直到1，完成全部排序

## gap->0 (gap-1)/3
### gap->length
#### i->gap-1 (-=gap)
##### 比較交換位置
           

public static void main(String[] args) {
		
		int[] arr = {7,4,27,6,5,2,1,8,12,9,10,11,34,15,23,20,3};
		int gap = 1;
		while(gap<=arr.length/3) {
			gap = gap*3+1;  //這樣劃分是因為某數學家研究出來這樣最優
		}
		
		for(;gap>0;gap = (gap-1)/3) {
			for(int i=gap;i<arr.length;i++) {
				for(int j=i;j>gap-1;j-=gap) {
					if(arr[j]<arr[j-gap]) {
						int temp = arr[j];
						arr[j] = arr[j-gap];
						arr[j-gap] = temp;
					}
				}
			}
		}
		
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}

	}
           

【歸并排序】 O(n*logn) 穩

📃思想描述

• 将數組排序不斷劃分為更小的子問題
• 解決子問題再将子問題合并

首先讓最小子問題有序，在下面的代碼裡，遞歸的終止是隻有一個元素。

然後從兩個元素合并開始。

問題就是先不斷二分，再合并。

合并的問題是怎樣将兩個有序數組合并。

## Sort()
### start==end return
### mid = (end-start)/2 + start+1
### sort (start,mid-1) ；sort (mid,end)
### merge (start,mid,end)

## merge()
### 三個指針，兩個有序數組，比較放入temp
#### arr[i]<arr[j] i++;k++;  else j++;k++;
### 剩餘放入temp
### arr[start:end] = temp[start:end]
           

public static void main(String[] args) {
		
		int[] arr = {7,4,3,19,6,5,2,13,1,8,12,9,10,11,23};
		int[] temp = new int[arr.length];
		
		sort(arr,0,arr.length-1,temp);
		
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}

	}
	
	static void sort(int[] arr,int start,int end,int[] temp) {
		if(start==end) return;
		//分成兩半
		int mid = (end-start)/2 + start+1; //防止中間兩int相加越界
		sort(arr,start,mid-1,temp);
		sort(arr,mid,end,temp);
		merge(arr,start,mid,end,temp);
	}
	
	static void merge(int[] arr,int start,int mid,int end,int[] temp) {
		int i=start;
		int j=mid;
		int k=start;
		
		while(i<mid && j<=end) {
			if(arr[i]<arr[j]) {
				temp[k]=arr[i];
				i++;
				k++;
			}else {
				temp[k]=arr[j];
				j++;
				k++;
			}
		}
		while(i<mid) temp[k++] = arr[i++];
		while(j<=end) temp[k++] = arr[j++];
		
		for(int a=start;a<=end;a++) {
			arr[a]=temp[a];//這裡注意一定要還給arr
		}
		
	}
           

Java裡的對象排序

對象排序一般要求穩定，是以歸并排序是一個比較好的選擇。

TimSort也是歸并排序，不過不是兩個兩分，而是一下分很多組，然後再将很多組兩兩歸并。

【TimSort】

TimSort是一個自适應的、混合的、穩定的排序算法，融合了歸并算法和二分插入排序算法的精髓。

在Java中是選擇當元素資料少于32時，二分插入排序，如果大于32進行歸并排序。

TimSort中有一個run的概念，run是單調增或者單調減的一段，并且run必須要保證至少有多少個元素:minrun。

在執行排序算法之前，會計算出這個minrun的值（是以說這個算法是自适應的，會根據資料的特點來進行自我調整），minrun會從32到64（包括）選擇一個數字，使得數組的長度除以minrun等于或者略小于2的幂次方。比如長度是65，那麼minrun的值就是33；如果長度是165，minrun就是42（注意這裡的Java的minrun的取值會在16到32之間）。

不斷去找run，遇到遞減的run需要反轉，反轉後壓棧。

最終合并棧中相鄰的兩個run。

【快速排序】O(nlogn) 不穩

就是讓某元素左邊的元素都小于它，右邊的元素都大于它。

快排有很多解法，速度最快的是雙指針,如下圖。

可以了解為指針指在空的位置上就不動，然後遇到大小需要調換的時候，原本空位置的指針将不空，會讓另一個指針不動。

📃思想描述

• 使用雙指針找到temp值的目标位置
• 目标位置左右繼續雙指針遞歸找位置

## quickSort()
### left>=right return
### pos = Partition
### quickSort(left:pos-1)
### quickSort(pos+1:right)

## Partition()
### temp = arr[left]
### left<right
#### arr[right]>temp  right--;
#### arr[left] = arr[right]
#### arr[left]<temp left++;
#### arr[right] = arr[left]
### arr[left] = temp;
### return temp
           

public static void main(String[] args) {
		
		int[] arr = {7,4,3,19,6,5,2,13,1,8,12,9,10,11,23};
		
		quickSort(arr,0,arr.length-1);
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}

	}
	
	public static void quickSort(int[] arr,int left,int right) {
		if(left>=right) return;
		int pos = Partition(arr,left,right);
		quickSort(arr,left,pos-1); //對左子區間遞歸進行快速排序
		quickSort(arr,pos+1,right); //對右子區間遞歸進行快速排序
	}
	
	public static int Partition(int[] arr,int left,int right) {
		int temp = arr[left];
		while(left<right) {
			while(left<right&&arr[right]>temp)
				right--;
			arr[left] = arr[right];
			while(left<right&&arr[left]<=temp)
				left++;
			arr[right] = arr[left];
		}
		arr[left] = temp;
		return left;
	}
           

避免最壞的情況(就是數組已經排好了)，可以選擇随機取一個數，而不是每次都從最左邊取數，或者先判斷是不是順序增長或者順序降低的，如果是就不用快排了。

Java裡Arrays類的這個sort(int[] a)方法是使用雙軸快排實作的。