各類排序算法
排序算法一般分類：
冒泡排序
原理
比較兩個相鄰的元素，將值大的元素交換至右端。
思路
依次比較兩個相鄰的數(shù)，將小數(shù)放到前面，大數(shù)放到后面
即在第一趟：首先比較第1個數(shù)和第2個數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個數(shù)和第3個數(shù)，將小數(shù)放前，大數(shù)放后，如此一直繼續(xù)下去，直到比較最后兩個數(shù)，將小數(shù)放前，大數(shù)放后。然后重復第一趟步驟，直到所有排序完成。
第一趟比較完成后，最后一個數(shù)一定是數(shù)組中最大的一個數(shù)，所以第二趟比較的時候最后一個數(shù)不參與比較。
第二趟完成后，倒數(shù)第二個數(shù)也一定是數(shù)組中第二大的數(shù)，所以第三趟比較的時候最后兩個數(shù)不參與比較。
依次類推......
代碼實現(xiàn)
public class BubbleSort {
public static void main(String[] args) {
int[] array = {2,4,1,5,67,2,45,78,3,9};
bubbleSort(array);
}
public static void bubbleSort(int[] array){
for(int i = 0 ; i < array.length-1; i++){
for(int j = 0 ; j < array.length-1; j++){
if(array[j] > array[j+1]){
int temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
}
}
}
System.out.println("排序后的數(shù)組為:" + Arrays.toString(array));
}
}
輸出結果：
排序后的數(shù)組為: [1, 2, 2, 3, 4, 5, 9, 45, 67, 78]
特點分析
冒泡排序的優(yōu)點：每進行一趟排序，就會少比較一次，因為每進行一趟排序都會找出一個較大值。如上例：第一趟比較之后，排在最后的一個數(shù)一定是最大的一個數(shù)，第二趟排序的時候，只需要比較除了最后一個數(shù)以外的其他的數(shù)，同樣也能找出一個最大的數(shù)排在參與第二趟比較的數(shù)后面，第三趟比較的時候，只需要比較除了最后兩個數(shù)以外的其他的數(shù)，以此類推……也就是說，沒進行一趟比較，每一趟少比較一次，一定程度上減少了算法的量。
用時間復雜度來說：
- 如果我們的數(shù)據(jù)正序，只需要走一趟即可完成排序。所需的比較次數(shù)C和記錄移動次數(shù)M均達到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的時間復雜度為
O(n)。 - 如果很不幸我們的數(shù)據(jù)是反序的，則需要進行
n-1趟排序。每趟排序要進行n-i次比較(1≤i≤n-1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數(shù)均達到最大值。
- 冒泡排序的最壞時間復雜度為：O(n^2)
- 冒泡排序的最好時間復雜夫為：O(n)
- 冒泡排序的平均時間復雜度：O(n)
- 冒泡排序是一種穩(wěn)定的排序算法
快速排序
原理
從一個數(shù)組中隨機選出一個數(shù)N，通過一趟排序將數(shù)組分割成三個部分，1、小于N的區(qū)域 2、等于N的區(qū)域 3、大于N的區(qū)域，然后再按照此方法對小于區(qū)的和大于區(qū)分別遞歸進行，從而達到整個數(shù)據(jù)變成有序數(shù)組。
思路
如下圖：
假設最開始的基準數(shù)據(jù)為數(shù)組的第一個元素23，則首先用一個臨時變量去存儲基準數(shù)據(jù)，即tmp=23，然后分別從數(shù)組的兩端掃描數(shù)組，設兩個指示標志：low指向起始位置，high指向末尾。
首先從后半部分開始，如果掃描到的值大于基準數(shù)據(jù)就讓high-1，如果發(fā)現(xiàn)有元素比該基準數(shù)據(jù)的值小，比如上面的18 <= tmp，就讓high位置的值賦值給low位置，結果如下：
然后開始從前往后掃描，如果掃描到的值小于基準數(shù)據(jù)就讓low+1，如果發(fā)現(xiàn)有元素大于基準數(shù)據(jù)的值，比如上圖46 >= tmp，就再將low位置的值賦值給high位置的值，指針移動并且數(shù)據(jù)交換后的結果如下：
然后再開始從前往后遍歷，直到low=high結束循環(huán)，此時low或者high的下標就是基準數(shù)據(jù)23在該數(shù)組中的正確索引位置，如下圖所示：
這樣一遍遍的走下來，可以很清楚的知道，快排的本質就是把比基準數(shù)據(jù)小的都放到基準數(shù)的左邊，比基準數(shù)大的數(shù)都放到基準數(shù)的右邊，這樣就找到了該數(shù)據(jù)在數(shù)組中的正確位置。
然后采用遞歸的方式分別對前半部分和后半部分排序，最終結果就是自然有序的了。
代碼實現(xiàn)
public class QuickSort {
public static void main(String[] args) {
int[] array = {2,4,1,5,67,2,45,78,3,9};
quickSort(array,0,array.length-1);
System.out.println(Arrays.toString(array));
}
public static void quickSort(int[] array,int low,int high){
if(low < high){
//找到基準數(shù)據(jù)位置
int index = getIndex(array,low,high);
//遞歸
quickSort(array,0,index-1);
quickSort(array,index+1,high);
}
}
//獲取基準數(shù)據(jù)位置
public static int getIndex(int[] array,int low,int high){
//一般取第一個數(shù)作為基準數(shù)據(jù)
int tmp = array[low];
while(low < high){
while(low < high && array[high] >= tmp){
high--;
}
//否則high處元素小于基準數(shù)據(jù)，將high處賦值給low處數(shù)據(jù)
array[low] = array[high];
//賦值完后，需要從前面開始掃描數(shù)組
while(low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
//整個循環(huán)結束時high=low,但是該位置處不等于基準元素
array[low] = tmp;
return low;
}
}
輸出結果：
[1, 2, 2, 3, 4, 5, 9, 45, 67, 78]
特點分析
最好情況下快排每次能恰好均分序列，那么時間復雜度就是O(nlogn)，最壞情況下，快排每次劃分都只能將序列分為一個元素和其它元素兩部分，這時候的快排退化成冒泡排序，時間復雜度為O(n^2)。
- 平均時間復雜度是O(nlogn)
- 最壞時間復雜度是O(n^2)
- 對于大的，亂序排列的數(shù)組來說快排一般是已知的最快的已知排序
- 快排是一種不穩(wěn)定排序
插入排序
原理
插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時間復雜度為O(n^2)。是穩(wěn)定的排序方法。
思路
將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中
- 將要排序的是一個亂的數(shù)組
int[] arrays = {3, 2, 1, 3, 3}; - 在未知道數(shù)組元素的情況下，我們只能把數(shù)組的第一個元素作為已經(jīng)排好序的有序數(shù)據(jù)，也就是說，把
{3}看成是已經(jīng)排好序的有序數(shù)據(jù)
第一趟排序：
用數(shù)組的第二個數(shù)與第一個數(shù)(看成是已有序的數(shù)據(jù))比較
- 如果比第一個數(shù)大，那就不管他
- 如果比第一個數(shù)小，將第一個數(shù)往后退一步，將第二個數(shù)插入第一個數(shù)去
第二趟排序：
用數(shù)組的第三個數(shù)與已是有序的數(shù)據(jù){2,3}(剛才在第一趟排的)比較
- 如果比2大，那就不管它
- 如果比2小，那就將2退一個位置，讓第三個數(shù)和1比較
在第二步中：
- 如果第三個數(shù)比1大，那么將第三個數(shù)插入到2的位置上
- 如果第三個數(shù)比1小，那么將1后退一步，將第三個數(shù)插入到1的位置上
...
后面依此類推
代碼實現(xiàn)
public class InsertSort {
public static void main(String[] args) {
int[] array = {2,4,1,5,67,2,45,78,3,9};
insertSort(array);
}
public static void insertSort(int[] arr) {
if (arr.length < 2)
System.out.println(Arrays.toString(arr));
for (int i = 1;i < arr.length;i++) {
for (int j = i;j > 0;j--) {
if (arr[j-1] > arr[j]) {
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
} else {
break;//插入新的元素
}
}
}
System.out.println(Arrays.toString(arr));
}
}
輸出結果：
[1, 2, 2, 3, 4, 5, 9, 45, 67, 78]
特點分析
- 最壞時間復雜度為O(n^2)
- 最好時間復雜度為O(n)
- 平均時間復雜度為O(n^2)
- 插入排序是一種穩(wěn)定的排序算法。
選擇排序
原理
選擇排序是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素排完。 選擇排序是不穩(wěn)定的排序方法。
思路
舉例：數(shù)組 int[] arr={5,2,8,4,9,1}
第一趟排序： 原始數(shù)據(jù)：5 2 8 4 9 1
最小數(shù)據(jù)1，把1放在首位，也就是1和5互換位置，
排序結果：1 2 8 4 9 5
第二趟排序：
第1以外的數(shù)據(jù){2 8 4 9 5}進行比較，2最小，
排序結果：1 2 8 4 9 5
第三趟排序：
除1、2以外的數(shù)據(jù){8 4 9 5}進行比較，4最小，8和4交換
排序結果：1 2 4 8 9 5
第四趟排序 :
除第1、2、4以外的其他數(shù)據(jù){8 9 5}進行比較，5最小，8和5交換
排序結果：1 2 4 5 9 8
第五趟排序：
除第1、2、4、5以外的其他數(shù)據(jù){9 8}進行比較，8最小，8和9交換
排序結果：1 2 4 5 8 9
代碼實現(xiàn)
public class SelectionSort {
public static void main(String[] args) {
int[] array = {2,4,1,5,67,2,45,78,3,9};
selectionSort(array,0,array.length-1);
System.out.println(Arrays.toString(array));
}
public static void selectionSort(int[] array,int start,int end){
for(int i = 0; i < array.length ;i++){
int k = i;
for(int j = k + 1; j < array.length; j++){
if(array[j] < array[k]){
k = j; //記下目前找到的最小值所在的位置
}
}
//在內層循環(huán)結束，也就是找到本輪循環(huán)的最小的數(shù)以后，再進行交換
if(i != k){ //交換a[i]和a[k]
int temp = array[i];
array[i] = array[k];
array[k] = temp;
}
}
}
}
輸出結果：
[1, 2, 2, 3, 4, 5, 9, 45, 67, 78]
特點分析：
- 最壞時間復雜度為O(n^2)
- 平均時間復雜度為O(n^2)
- 選擇排序是一種不穩(wěn)定的排序
歸并排序
原理
歸并排序（merge sort）是利用歸并的思想實現(xiàn)的排序方法，該算法采用經(jīng)典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。
思路
比如我們對[8,4,5,7,1,3,6,2]這個數(shù)組進行歸并排序，我們首先利用分治思想的“分”將數(shù)組拆分。
可以看到這種結構很像一棵完全二叉樹，本文的歸并排序我們采用遞歸去實現(xiàn)（也可采用迭代的方式去實現(xiàn)）。分階段可以理解為就是遞歸拆分子序列的過程，遞歸深度為
log2n。再來看看治階段，我們需要將兩個已經(jīng)有序的子序列合并成一個有序序列，比如上圖中的最后一次合并，要將
[4,5,7,8]和[1,2,3,6]兩個已經(jīng)有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來看下實現(xiàn)步驟。
代碼實現(xiàn)
public class MergeSort {
public static void main(String []args){
int[] array = {2,4,1,5,67,2,45,78,3,9};
sort(array);
System.out.println(Arrays.toString(array));
}
public static void sort(int []arr){
int []temp = new int[arr.length];//在排序前，先建好一個長度等于原數(shù)組長度的臨時數(shù)組，避免遞歸中頻繁開辟空間
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
sort(arr,left,mid,temp);//左邊歸并排序，使得左子序列有序
sort(arr,mid+1,right,temp);//右邊歸并排序，使得右子序列有序
merge(arr,left,mid,right,temp);//將兩個有序子數(shù)組合并操作
}
}
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指針
int j = mid+1;//右序列指針
int t = 0;//臨時數(shù)組指針
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//將左邊剩余元素填充進temp中
temp[t++] = arr[i++];
}
while(j<=right){//將右序列剩余元素填充進temp中
temp[t++] = arr[j++];
}
t = 0;
//將temp中的元素全部拷貝到原數(shù)組中
while(left <= right){
arr[left++] = temp[t++];
}
}
}
輸出結果：
[1, 2, 2, 3, 4, 5, 9, 45, 67, 78]
特點分析
- 歸并排序是一種穩(wěn)定排序
- Java中的
Arrays.sort()采用了一種名為TimSort的排序算法，就是歸并排序的優(yōu)化版本 - 每次合并操作的時間復雜度為O(n)，完全二叉樹的深度為
|log2n|，總的平均時間復雜度為O(nlogn) - 歸并排序的最好、最壞、平均時間復雜度都為O(nlongn)
