一、冒泡排序(重點)

思路

前后兩兩數據進行比較，小的數據往前走，大的數據往后走，每一輪結束之后，最大的數據到達正確位置

代碼

public static void main(String[] args) {int[] arr={1,5,3,6,22,0,2,5};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr){for(int j =0;j<arr.length;j++){for(int i =0;i<arr.length-j-1;i++){if(arr[i]>arr[i+1]){int temp = arr[i];arr[i] = arr[i+1];arr[i+1] = temp;}}}}

二、快排(面試重點)

思路

1.定義待排序數組當中的第一個作為基準數
2.游標 j 從后往前查找比基準數小的，查找到第一個比基準數小的數停下
3.定義游標i 從前往后查找第一個比基準數大的值停下
4.i 和 j 進行交換
5.重復2，3，4，直到i 和 j 相遇
6.基準數和相遇位置進行交換，基準數到達正確位置
7.以基準數為起始點，分成左右兩部分，重復上述所有 直到數據都被拆分開為止

代碼

public static void quicksort(int[] arr,int left,int right){if(left>=right){return ;}int base = arr[left];int i =left;int j = right;while(i !=j ){//j從后往前走，找比基數小的值while(arr[j] >=base && i<j){j--;}//i從前往后走，找比基數小的值while (arr[i] <= base && i<j){i++;}int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}//當i==j時arr[left] = arr[i];arr[i] = base;quicksort(arr,left,i-1);quicksort(arr,i+1,right);}

三、堆排序(面試重點)

思路

1.利用完全二叉樹構建大頂堆
2.堆頂元素和堆底元素進行互換，除堆底元素之外剩余元素繼續構建大頂堆
3.重復2

arr[i]的 左孩子arr[2i+1]
arr[i]的 右孩子arr[2i+2]
arr[i]的 父親arr[(i-1)/2]

arr[i]>arr[2i+1] && arr[i]>arr[2i+2]
完全二叉樹：數據從上到下 從左到右
大頂堆：父節點的值大于或等于其左右孩子的值

構建大頂堆
一、從后往前檢測節點是否符合大頂堆的要求，如果符合向前檢查，不符合對當前節點進行調整
1.parent指向當前節點
2.定義parent的左孩子 child(有孩子一定有左孩子)
3.判斷parent的右孩子 如果有右孩子，左右孩子進行比較 child指向左右孩子的最大值
4.父子節點進行比較，如果 父節點值大，符合大頂堆，繼續向前檢查
5.如果子節點的值大，父子節點進行交換，parent指向child，child指向其左右孩子的最大值，繼續將父子節點進行比較
6.直到父節點值大或者child為空

二、維護堆頂
parent指向 堆頂，child指向其左右孩子的最大值
父子節點進行比較，如果父節點值大，大頂堆構建完成
如果父節點值小，父子節點交換

代碼

 public static void main(String[] args) {int[] arr={1,5,3,6,22,0,2,5};for(int i = arr.length-1;i>=0;i--){adjust(arr,i, arr.length);}for (int i =arr.length-1;i>=0;i--){int temp =arr[i];arr[i] = arr[0];arr[0] = temp;adjust(arr,0,i);}System.out.println(Arrays.toString(arr));}/*** 堆排*/public static void adjust(int[] arr,int parent,int length){int child = 2*parent+1;while(child<length){int rchild = child + 1;if(rchild<length && arr[rchild]>arr[child]){child++;}if(arr[parent] < arr[child]){int temp = arr[parent];arr[parent] = arr[child];arr[child] = temp;parent = child;child = 2*child +1;}else {break;}}}

四、選擇排序

思路

默認待排序數組當中的第一個數為最小值
找待排序數組當中真正的最小值
找到真正的最小值和待排序數組第一個數據進行交換 真正的最小值到達正確位置

代碼

    /*** 選擇排序*/public static void chooseSort(int[] arr){for(int j = 0;j<arr.length;j++){int min = arr[j];int minIndex = j;for(int i =j+1;i<arr.length;i++){if(min>arr[i]){min = arr[i];minIndex = i;}}//min的真正最小值arr[minIndex] = arr[j];arr[j] = min;}}

接下來的排序算法請看
【八大排序】java版(下) （插入、希爾、基數、歸并）