一、冒泡排序（Bubble Sort）
1.1 基本思想：
冒泡排序算是比較簡單的排序了。
即對 n 個數(shù)進行排序，每次都是由前一個數(shù)和后一個數(shù)比較，一對一對地比，最后可以將最大的數(shù)移到數(shù)組的后面，總共循環(huán) n-1 次，完成對數(shù)組的排序。
1.2 動圖演示
冒泡排序
1.3 代碼實現(xiàn)：
/**
* @anthor shkstart
* @create 2020-03-19-15:33
*/
public class Test1 {
public static void main(String[] args) {
int[] arr = new int[]{
65,98,34,16,0,-5,-6,45,39,-44,-99,35,34
};
//外層控制排序的對比的次數(shù)，比數(shù)組長度少1是因為最后一個數(shù)據(jù)不用比
for (int i = 0; i < arr.length; i++) {
//-i 是因為排序導最后可以得出一個最大值，就不用參與排序了
for (int j = 0; j < arr.length-1-i; 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] + "\t");
}
}
}
二、選擇排序（Selection Sort）
2.1 基本思想：
選擇排序是由一個數(shù)去和全部的數(shù)都比較一次，每次選取相對較小的那個數(shù)的下標來進行下一次比較，并且不斷更新較小的數(shù)的下標，一次循環(huán)結束，再通過一次交換，把較小的數(shù)放在最前面，一共循環(huán) n-1 次。
相對于冒泡排序，比較的次數(shù)不變，但數(shù)據(jù)交換的次數(shù)大大減少了。算是冒泡排序的改良版。
2.2 動圖演示：
選擇排序
2.3 代碼演示：
/**
* 選擇排序
*
* @author czh
* @create 2020-03-19-21:40
*/
public class selectSort {
public static void main(String[] args) {
int[] arr = new int[]{
65,98,34,16,0,-5,-6,45,39,-44,-99,35,34
};
//外層循環(huán)控制循環(huán)次數(shù)，最后一個數(shù)據(jù)自動為最大值，所以arr.length-1
for (int i = 0; i < arr.length - 1; i++) {
//用來保存每次比較的最小值的下標
int MinIndex = i;
//內層控制每次的比較，因為前面的數(shù)據(jù)已經排好
//所以下一次循環(huán)就可以跳過，j=i+1
for (int j = i+1; j < arr.length; j++) {
//對比時，遇到比自己小的，就替換下標
if (arr[MinIndex] > arr[j]){
MinIndex = j;
}
}
//一輪對比下來，發(fā)現(xiàn)下標發(fā)生了改變
//就把下標對應的數(shù)據(jù)進行替換
if (MinIndex != i){
int temp = arr[i];
arr[i] = arr[MinIndex];
arr[MinIndex] = temp;
}
}
System.out.println("排序后的數(shù)據(jù)：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + "\t");
}
}
}
三、插入排序（Insertion Sort）
3.1 基本思想：
首先默認數(shù)組中的第一個數(shù)的位置是正確的。然后取下一個數(shù)，與前面已經排序好的數(shù)據(jù)從后往前依次比較，如果該數(shù)的值比前一個小，就把排序好的數(shù)據(jù)后移一位。重復該操作，直到找到合適的位置后結束循環(huán)，將數(shù)據(jù)放到找到的位置。
3.2 動圖演示：
插入排序
3.3 代碼演示：
/**
*
* 插入排序
*
* @author czh
* @create 2020-03-20-8:42
*/
public class insertSort {
public static void main(String[] args) {
int[] arr = new int[]{
65,98,34,16,0,5,-6,45,39,-44,-99,35,34
};
//控制外層循環(huán)，因為第一個數(shù)據(jù)假定是正確的
//所以i的起始值是1
for (int i = 1; i < arr.length; i++) {
int j=i;//用來記錄要排序的數(shù)的下標，原來的位置
int target = arr[j];//用來記錄要排序的數(shù)的值
//因為是從后向前比較，所以j-1和j做比較
//j>0 讓比較不要跑出范圍
while (j>0 && target<arr[j-1]){
arr[j] = arr[j-1]; //發(fā)現(xiàn)前一個比自己大，就往前移動一位
j--;//讓目標與下一個繼續(xù)比較
}
//更換目標數(shù)的位置
arr[j] = target;
}
System.out.println("排序后的數(shù)據(jù)：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + "\t");
}
}
}
四、希爾排序（Shell Sort）
4.1 基本思想：
先將需要排序的數(shù)組分為多個子序列，這樣每個子序列的元素個數(shù)不多，對每個子序列進行直接插入排序。完成后，再對整個數(shù)組進行一次直接排序。希爾排序是直接插入排序的升級版。
4.2 動圖演示：
希爾排序
4.3 代碼演示：
/**
* @author czh
* @create 2020-03-20-9:40
*/
public class shellSort {
public static void main(String[] args) {
int[] arr = new int[]{
3,65,98,34,-16,0,-5,-6,45,39,-44,-99,35,34
};
//初始增量為數(shù)組長度的一半
int k = arr.length / 2;
//while循環(huán)控制按增量的值來劃分不同的子序列，
//每完成一個增量就減少為原來的一半
while (k>0){
//這其實是升級版的直接插入排序，是對每一個子序列進行直接插入排序
//所以將插入排序的“1”變成“k”
for (int i = k; i < arr.length; i++) {
int j = i;
int target = arr[i];
while (j>=k && target < arr[j-k]){
arr[j] = arr[j-k];
j-=k;
}
arr[j] = target;
}
k/=2;
}
System.out.println("排序后的數(shù)據(jù)：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + "\t");
}
}
}
五、歸并排序（Merge Sort）
5.1 基本思想：
總體概括就是從上到下遞歸拆分，然后從下到上逐步合并。
- 遞歸拆分：先把待排序數(shù)組分為左右兩個子序列，再分別將左右兩個子序列拆分為四個子子序列，以此類推直到最小的子序列元素的個數(shù)為兩個或者一個為止。
- 逐步合并（一定要注意是從下到上層級合并，可以理解為遞歸的層級返回）：將最底層的最左邊的一個子序列排序，然后將從左到右第二個子序列進行排序，再將這兩個排好序的子序列合并并排序，然后將最底層從左到右第三個子序列進行排序..... 合并完成之后記憶完成了對數(shù)組的排序操作。
5.2 動圖演示：
歸并排序
5.3 代碼演示（基本思想理解。代碼實現(xiàn)不會，參考大佬的代碼）：
import java.util.Arrays;
/**
* 歸并排序
* 不太會，參考別人的代碼的
*
* @author czh
* @create 2020-03-20-10:25
*/
public class test {
public static void main(String[] args) {
int[] arr = {
65,98,34,16,0,-5,-6,45,39,-44,-99,35,34};
mergeSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
/**
* 遞歸拆分
* @param arr 待拆分數(shù)組
* @param left 待拆分數(shù)組最小下標
* @param right 待拆分數(shù)組最大下標
*/
public static void mergeSort(int[] arr,int left,int right){
int mid = (left + right) / 2;//中間下標
if (left < right){
mergeSort(arr, left, mid);//遞歸拆分左邊
mergeSort(arr,mid+1,right);//遞歸拆分右邊
sort(arr,left,mid,right);//合并左右
}
}
/**
* 合并兩個有序子序列
* @param arr 待合并數(shù)組
* @param left 待合并數(shù)組最小下標
* @param mid 待合并數(shù)組中間下標
* @param right 待合并數(shù)組最大下標
*/
public static void sort(int[] arr,int left,int mid,int right){
int[] temp = new int[right - left + 1];//臨時數(shù)組，用來保存每次合并之后的結果
int i = left;
int j = mid + 1;
int k = 0;//臨時數(shù)組的初始下標
//循環(huán)能夠初步篩選出待合并的了兩個子序列中的較小數(shù)
while (i<=mid && j<=right){
if (arr[i]<=arr[j]){
temp[k++] = arr[i++];
}else {
temp[k++] = arr[j++];
}
}
//將左邊序列中剩余的數(shù)放入臨時數(shù)組
while (i<=mid){
temp[k++] = arr[i++];
}
//將右邊序列中剩余的數(shù)放入臨時數(shù)組
while (j<=right){
temp[k++] = arr[j++];
}
//將臨時數(shù)組中的元素位置對應到真實數(shù)組中
for (int m = 0; m < temp.length; m++) {
arr[m+left] = temp[m];
}
}
}
六、快速排序（Quick Sort）
6.1 基本思想：
快速排序也采用了分治的策略，這里引入了‘基準數(shù)’的概念。
- 找一個基準數(shù)（一般將待排序的數(shù)組的第一個數(shù)作為基準數(shù)）。
- 對數(shù)組進行分區(qū)，將小于等于基準數(shù)的全部放在左邊，大于基準數(shù)的全部放在右邊。
- 重復1，2步驟，分別對左右兩個子分區(qū)進行分區(qū)，一直到各分區(qū)只有一個數(shù)為止。
6.2 動圖演示：
快速排序
6.3 代碼演示（基本思想理解，代碼實現(xiàn)也是參考別人的代碼）：
import java.util.Arrays;
/**
* @author czh
* @create 2020-03-20-14:27
*/
public class test1 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {65,98,34,16,0,-5,-6,45,39,-44};
quickSort(arr,0,9);
System.out.println(Arrays.toString(arr));
}
/**
* 分區(qū)過程
* @param arr 待分區(qū)數(shù)組
* @param left 待分區(qū)數(shù)組最小下標
* @param right 待分區(qū)數(shù)組最大下標
*/
public static void quickSort(int[] arr,int left,int right) {
if(left<right) {
int temp=qSort(arr,left,right);
quickSort(arr,left,temp-1);
quickSort(arr,temp+1,right);
}
}
/**
* 排序過程
* @param arr 待排序數(shù)組
* @param left 待排序數(shù)組最小下標
* @param right 待排序數(shù)組最大下標
* @return 排好序之后基準數(shù)的位置下標，方便下次的分區(qū)
*/
public static int qSort(int[] arr,int left,int right) {
int temp=arr[left];//定義基準數(shù)，默認為數(shù)組的第一個元素
while(left<right) {//循環(huán)執(zhí)行的條件
//因為默認的基準數(shù)是在最左邊，所以首先從右邊開始比較進入while循環(huán)的判斷條件
//如果當前arr[right]比基準數(shù)大，則直接將右指針左移一位，當然還要保證left<right
while(left<right && arr[right]>temp) {
right--;
}
//跳出循環(huán)說明當前的arr[right]比基準數(shù)要小，那么直接將當前數(shù)移動到基準數(shù)所在的位置，并且左指針向右移一位（left++）
//這時當前數(shù)（arr[right]）所在的位置空出，需要從左邊找一個比基準數(shù)大的數(shù)來填充。
if(left<right) {
arr[left++]=arr[right];
}
//下面的步驟是為了在左邊找到比基準數(shù)大的數(shù)填充到right的位置。
//因為現(xiàn)在需要填充的位置在右邊，所以左邊的指針移動，如果arr[left]小于或者等于基準數(shù)，則直接將左指針右移一位
while(left<right && arr[left]<=temp) {
left++;
}
//跳出上一個循環(huán)說明當前的arr[left]的值大于基準數(shù)，需要將該值填充到右邊空出的位置，然后當前位置空出。
if(left<right) {
arr[right--]=arr[left];
}
}
//當循環(huán)結束說明左指針和右指針已經相遇。并且相遇的位置是一個空出的位置，
//這時候將基準數(shù)填入該位置，并返回該位置的下標，為分區(qū)做準備。
arr[left]=temp;
return left;
}
}
七、堆排序（Heap Sort）
7.1 基本思想：
堆是一種特殊的完全二叉樹，分為大頂堆和小頂堆。
- 大頂堆：每個結點的值都大于它的左右子結點的值，升序排序用大頂堆。
- 小頂堆：每個結點的值都小于它的左右子結點的值，降序排序用小頂堆。
所以，需要將待排序數(shù)組構成大頂堆的格式，這時候該堆的頂節(jié)點就是最大的值，將其與堆最后一個節(jié)點的元素交換。再將剩余的樹重新調整成堆，再次對比一輪后，首節(jié)點與尾節(jié)點交換，重復執(zhí)行直到只剩下最后一個節(jié)點即完成排序。
7.2 動圖演示：
堆排序
7.3 代碼演示（參考大佬的代碼...）：
import java.util.Arrays;
/**
* @author czh
* @create 2020-03-20-14:27
*/
public class test1 {
public static void main(String[] args) {
int[] arr= {72,6,-7,88,0,42,354,83,-73,48,85,7};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
if(arr==null) {
return;
}
int len=arr.length;
//初始化大頂堆（從最后一個非葉節(jié)點開始，從左到右，由下到上）
for(int i=len/2-1;i>=0;i--) {
adjustHeap(arr,i,len);
}
//將頂節(jié)點和最后一個節(jié)點互換位置，再將剩下的堆進行調整
for(int j=len-1;j>0;j--) {
swap(arr,0,j);
adjustHeap(arr,0,j);
}
}
/**
* 整理樹讓其變成堆
* @param arr 待整理的數(shù)組
* @param i 開始的結點
* @param j 數(shù)組的長度
*/
public static void adjustHeap(int[] arr,int i,int j) {
int temp=arr[i];//定義一個變量保存開始的結點
//k就是該結點的左子結點下標
for(int k=2*i+1;k<j;k=2*k+1) {
//比較左右兩個子結點的大小，k始終記錄兩者中較大值的下標
if(k+1<j && arr[k]<arr[k+1]) {
k++;
}
//經子結點中的較大值和當前的結點比較，比較結果的較大值放在當前結點位置
if(arr[k]>temp) {
arr[i]=arr[k];
i=k;
}else{//說明已經是大頂堆
break;
}
}
arr[i]=temp;
}
/**
* 交換數(shù)據(jù)
* @param arr
* @param num1
* @param num2
*/
public static void swap(int[] arr, int num1,int num2) {
int temp=arr[num1];
arr[num1]=arr[num2];
arr[num2]=temp;
}
}
八、計數(shù)排序（Counting Sort）
8.1 基本思想：
計數(shù)排序采用了一種全新的思路，將待排序數(shù)組中的最大值+1作為一個臨時數(shù)組的長度，然后用臨時數(shù)組記錄待排序數(shù)組中每個元素出現(xiàn)的次數(shù)。最后再遍歷臨時數(shù)組，因為是升序，所以從前往后遍歷將臨時數(shù)組中值>0的數(shù)的下標循環(huán)取出，依次放入待排序數(shù)組中，即可完成排序。計數(shù)排序的效率很高，但是實在犧牲內存的前提下，并且有著限制，那就是待排序數(shù)組的值必須 限制在一個確定的范圍。
8.2 動圖演示：
計數(shù)排序
8.3 代碼演示：
import java.util.Arrays;
/**
效率高，但無法對負數(shù)進行排序
* @author czh
* @create 2020-03-20-14:27
*/
public class test1 {
public static void main(String[] args) {
int[] arr= {65,98,34,16,0,45,39,35,34};
countSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void countSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
//保存待排序數(shù)組中的最大值，目的是確定臨時數(shù)組的長度（必須）
int maxNum=arr[0];
//保存待排序數(shù)組中的最小值，目的是確定最終遍歷臨時數(shù)組時下標的初始值（非必需，只是這樣可以加快速度，減少循環(huán)次數(shù)）
int minNum=arr[0];
//for循環(huán)就是為了找到待排序數(shù)組的最大值和最小值
for(int i=1;i<len;i++) {
maxNum=maxNum>arr[i]?maxNum:arr[i];
minNum=minNum<arr[i]?minNum:arr[i];
}
//創(chuàng)建一個臨時數(shù)組
int[] temp=new int[maxNum+1];
//for循環(huán)是為了記錄待排序數(shù)組中每個元素出現(xiàn)的次數(shù)，并將該次數(shù)保存到臨時數(shù)組中
for(int i=0;i<len;i++) {
temp[arr[i]]++;
}
//k=0用來記錄待排序數(shù)組的下標
int k=0;
//遍歷臨時數(shù)組，重新為待排序數(shù)組賦值。
for(int i=minNum;i<temp.length;i++) {
while(temp[i]>0) {
arr[k++]=i;
temp[i]--;
}
}
}
}
九、桶排序（Bucket Sort）
9.1 基本思想：
桶排序其實就是計數(shù)排序的強化版，需要利用一個映射函數(shù)首先定義有限個數(shù)個桶，然后將待排序數(shù)組內的元素按照函數(shù)映射的關系分別放入不同的桶里邊，現(xiàn)在不同的桶里邊的數(shù)據(jù)已經做了區(qū)分，比如A桶里的數(shù)要么全部大于B桶，要么全部小于B桶里的數(shù)。但是A，B桶各自里邊的數(shù)還是亂序的。所以要借助其他排序方式（快速，插入，歸并）分別對每一個元素個數(shù)大于一的桶里邊的數(shù)據(jù)進行排序。最后再將桶里邊的元素按照順序依次放入待排序數(shù)組中即可。
9.2 圖片展示：
9.3 代碼演示（這個也沒懂...CP大佬的代碼）：
public static void main(String[] args) {
int[] arr= {72,6,57,88,60,42,83,73,48,85};
bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bucketSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
//定義桶的個數(shù)，這里k的值要視情況而定，這里我們假設待排序數(shù)組里的數(shù)都是[0,100)之間的。
int k=10;
//用嵌套集合來模擬桶，外層集合表示桶，內層集合表示桶里邊裝的元素。
List<List<Integer>> bucket=new ArrayList<>();
//for循環(huán)初始化外層集合即初始化桶
for(int i=0;i<k;i++){
bucket.add(new ArrayList<>());
}
//循環(huán)是為了將待排序數(shù)組中的元素通過映射函數(shù)分別放入不同的桶里邊
for(int i=0;i<len;i++) {
bucket.get(mapping(arr[i])).add(arr[i]);
}
//這個循環(huán)是為了將所有的元素個數(shù)大于1的桶里邊的數(shù)據(jù)進行排序。
for(int i=0;i<k;i++) {
if(bucket.size()>1) {
//因為這里是用集合來模擬的桶所以用java寫好的對集合排序的方法。
//其實應該自己寫一個方法來排序的。
Collections.sort(bucket.get(i));
}
}
//將排好序的數(shù)重新放入待排序數(shù)組中
int m=0;
for(List<Integer> list:bucket) {
if(list.size()>0) {
for(Integer a:list) {
arr[m++]=a;
}
}
}
}
/**
* 映射函數(shù)
* @param num
* @return
*/
public static int mapping(int num) {
return num/10;
}
十、基數(shù)排序（Radix Sort）
10.1 基本思想：
基數(shù)排序就是將待排序的數(shù)組拆分成多個關鍵字進行排序。基數(shù)排序的實質是多關鍵字排序。多關鍵字排序的思路是將待排數(shù)據(jù)里德排序關鍵字拆分成多個排序關鍵字； 第1個排序關鍵字，第2個排序關鍵字，第3個排序關鍵字......然后，根據(jù)子關鍵字對待排序數(shù)據(jù)進行排序。
10.2 動圖演示：
基數(shù)排序
10.3 代碼演示（理論理解，實操不懂...參考大佬的代碼）：
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {720,6,57,88,60,42,83,73,48,85};
redixSort(arr,10,3);
System.out.println(Arrays.toString(arr));
}
public static void redixSort(int[] arr, int radix, int d) {
// 緩存數(shù)組
int[] tmp = new int[arr.length];
// buckets用于記錄待排序元素的信息
// buckets數(shù)組定義了max-min個桶
int[] buckets = new int[radix];
for (int i = 0, rate = 1; i < d; i++) {
// 重置count數(shù)組，開始統(tǒng)計下一個關鍵字
Arrays.fill(buckets, 0);
// 將data中的元素完全復制到tmp數(shù)組中
System.arraycopy(arr, 0, tmp, 0, arr.length);
// 計算每個待排序數(shù)據(jù)的子關鍵字
for (int j = 0; j < arr.length; j++) {
int subKey = (tmp[j] / rate) % radix;
buckets[subKey]++;
}
for (int j = 1; j < radix; j++) {
buckets[j] = buckets[j] + buckets[j - 1];
}
// 按子關鍵字對指定的數(shù)據(jù)進行排序
for (int m = arr.length - 1; m >= 0; m--) {
int subKey = (tmp[m] / rate) % radix;
arr[--buckets[subKey]] = tmp[m];
}
rate *= radix;
}
}
十一、算法總結：
算法對比圖：
算法對比
圖片名詞解釋：
- n：數(shù)據(jù)規(guī)模
- k：“桶”的個數(shù)
- In-place：占用常數(shù)內存，不占用額外內存
- Out-place：占用額外內存
