冒泡排序
排序（假設從小到大）的步驟如下：

• 從頭開始，比較相鄰的兩個數，如果第一個數比第二個數大，那么就交換它們位置。
• 從開始到最后一對比較完成，一輪結束后，最后一個元素的位置已經確定。
• 除了最后一個元素以外，前面的所有未排好序的元素重復前面兩個步驟。
• 重復前面 1 ～ 3 步驟，直到所有元素都已經排好序。
  

package com.ty;public class BubbleSort {public static void main(String[] args) {int[] arr= {1,10,5,6,3,8,2,0};bubbleSort(arr);printArr(arr);}public static void bubbleSort(int[] arr){int n=arr.length;for(int i=n-1;i>=0;i--){for(int j=0;j<i;j++){if(arr[j]>arr[j+1]){swap(arr,j,j+1);}}}}public static void swap(int[] arr,int i,int j){int temp;temp=arr[i];arr[i]=arr[j];arr[j]=temp;}public static void printArr(int[] arr){for(int i:arr){System.out.print(i+" ");}} }

選擇排序
排序的步驟如下：

• 從第一個元素開始，遍歷其后面的元素，找出其后面比它更小的且最小的元素，若有，則兩者交換，保證第一個元素最小。
• 對第二個元素一樣，遍歷其后面的元素，找出其后面比它更小的且最小的元素，若存在，則兩者交換，保證第二個元素在未排序的數中（除了第一個元素）最小。
• 依次類推，直到最后一個元素，那么數組就已經排好序了。

package com.ty;/*** @description: 選擇排序*/ public class SelectSort {public static void main(String[] args) {int[] arr={1,10,5,6,3,8,2,0};printArr(arr);System.out.println();selectSort(arr);printArr(arr);}public static void selectSort(int[] arr){int n=arr.length;for(int i=0;i<n;i++){int minValueIndex=i;for(int j=i;j<n;j++){minValueIndex=arr[minValueIndex]<arr[j]?minValueIndex:j;}swap(arr,minValueIndex,i);}}public static void swap(int[] arr,int i,int j){int temp;temp=arr[i];arr[i]=arr[j];arr[j]=temp;}public static void printArr(int[] arr){for(int i:arr){System.out.print(i+" ");}}}

插入排序

選擇排序是每次選擇出最小的放到已經排好的數組后面，而插入排序是依次選擇一個元素，插入到前面已經排好序的數組中間，確保它處于正確的位置，當然，這是需要已經排好的順序數組不斷移動。步驟描述如下：

步驟描述如下：

• 從第一個元素開始，可以認為第一個元素已經排好順序。
• 取出后面一個元素 n，在前面已經排好順序的數組里從尾部往頭部遍歷，假設正在遍歷的元素為 nums[i]，如果 num[i] > n，那么將 nums[i] 移動到后面一個位置，直到找到已經排序的元素小于或者等于新元素的位置，將 n 放到新騰空出來的位置上。如果沒有找到，那么 nums[i] 就是最小的元素，放在第一個位置。
• 重復上面的步驟 2，直到所有元素都插入到正確的位置。

package com.ty;public class InsertSort {public static void main(String[] args) {int[] arr={1,7,5,4,3,2,9};printArr(arr);System.out.println();insetSort(arr);printArr(arr);}public static void insetSort(int[] arr){int n=arr.length;for(int end=1;end<n-1;end++){for(int pre=end-1;pre>=0&&arr[pre]>arr[pre+1];pre--){swap(arr,pre,pre+1);}}}public static void swap(int[] arr,int i,int j){int temp;temp=arr[i];arr[i]=arr[j];arr[j]=temp;}public static void printArr(int[] arr){for(int i:arr){System.out.print(i+" ");}} }

希爾排序

希爾排序（Shell’s Sort）又稱“縮小增量排序”（Diminishing Increment Sort），是插入排序的一種更高效的改進版本，同時該算法是首次沖破 O(n^2n 2 ) 的算法之一

希爾排序基本步驟如下：

• 選擇一個增量 gap，一般開始是數組的一半，將數組元素按照間隔為 gap 分為若干個小組。
• 對每一個小組進行插入排序。
• 將 gap 縮小為一半，重新分組，重復步驟 2（直到 gap 為 1 的時候基本有序，稍微調整一下即可）。

public class ShellSort {public static void shellSort(int[] nums) {int times = 1;for (int gap = nums.length / 2; gap > 0; gap /= 2) {System.out.print("第" + (times++) + "輪希爾排序, gap= " + gap + " ,結果：");for (int i = gap; i < nums.length; i++) {int j = i;int temp = nums[j];while (j - gap >= 0 && temp < nums[j - gap]) {// 移動法nums[j] = nums[j - gap];j -= gap;}nums[j] = temp;}printf(nums);}}public static void printf(int[] nums) {for (int num : nums) {System.out.print(num + " ");}System.out.println("");} }

快速排序
快速排序比較有趣，選擇數組的一個數作為基準數，一趟排序，將數組分割成為兩部分，一部分均小于/等于基準數，另外一部分大于/等于基準數。然后分別對基準數的左右兩部分繼續排序，直到數組有序。這體現了分而治之的思想，其中還應用到挖坑填數的策略。

package com.ty;public class QuickSort {public static void main(String[] args) {int[] arr={101,109,1,10,5,6,3,8,2,0,-1,99};printArr(arr);System.out.println();quickSort(arr,0,arr.length-1);printArr(arr);}public static void quickSort(int[] arr,int left, int right){int pivot =arr[(left+right)/2];int l=left,r=right;// 讓值比pivot 小的放在左邊，比pivot 大的放在右邊while(l<r){while (arr[l]<pivot){l++;}while (arr[r]>pivot){r--;}//此時pivot 左邊的數字都比他小，右邊的數字都比他大if(l>=r){break;}//進行交換swap(arr,l,r);//如果兩個數交換的其中有一個的等于pivotif(arr[l]==pivot){r--;}if(arr[r]==pivot){l++;}}if(l==r){l++;r--;}//對排序好的左邊部分進行遞歸if(left<r){quickSort(arr,left,r);}//對排序好的右邊部分進行遞歸if(l<right){quickSort(arr,l,right);}}public static void swap(int[] arr,int i,int j){int temp;temp=arr[i];arr[i]=arr[j];arr[j]=temp;}public static void printArr(int[] arr){for(int i:arr){System.out.print(i+" ");}}}

身份證排序

安全局搜索到了一批 (n 個) 身份證號碼，希望按出生日期對它們進行從大到小排序，如果有相同日期，則按身份證號碼大小進行排序。身份證號碼為 18 位的數字組成，出生日期為第 7 到第 14 位。

package com.ty.test01;import java.io.*; import java.util.ArrayList; import java.util.List;public class CartId {public static void main(String[] args) {BufferedReader bufferedReader= new BufferedReader(new InputStreamReader(System.in));PrintWriter printWriter=new PrintWriter(new OutputStreamWriter(System.out));List<String> strings=new ArrayList<>();try(bufferedReader;printWriter) {int n = Integer.parseInt( bufferedReader.readLine());for (int i = 0; i < n; i++) {strings.add(bufferedReader.readLine());}strings.sort((str1, str2) -> {String sub1 = str1.substring(6, 14);String sub2 = str2.substring(6, 14);if (!sub1.equals(sub2)) {return sub2.compareTo(sub1);}return str2.compareTo(str1);});for (String str : strings) {printWriter.println(str);}} catch (IOException e) {e.printStackTrace();}} }5 466272307503271156 215856472207097978 234804580401078365 404475727700034980 710351408803093165 404475727700034980 234804580401078365 215856472207097978 710351408803093165 466272307503271156

歸并排序

前面學的快速排序，體現了分治的思想，但是不夠典型，而歸并排序則是非常典型的分治策略。歸并的總體思想是先將數組分割，再分割 … 分割到一個元素，然后再兩兩歸并排序，做到局部有序，不斷地歸并，直到數組又被全部合起來。

package com.ty;public class MergeSort {public static void merge(int[]arr,int left,int mid,int right){int[]temp=new int[right-left+1];int l=left;int r=mid+1;int t=0;// 比較左右兩部分的元素，哪個小，就把那個元素填入temp中while(l<=mid&&r<=right){if(arr[l]<=arr[r]){temp[t]=arr[l];t++;l++;}else {temp[t] = arr[r];t++;r++;}}// 如果左邊還有元素剩下，則全部合并過去while (l<=mid){temp[t]=arr[l];t++;l++;}// 如果右邊有元素剩下，則把右邊元素合并過去while (r<=right){temp[t]=arr[r];t++;r++;}//把最后的排序結果復制到原數組for(int i=0;i<temp.length;i++){arr[left+i]=temp[i];}}public static void sort(int[]arr,int left,int right){if(left==right){return;}int mid=(left+right)/2;sort(arr,left,mid);sort(arr,mid+1,right);merge(arr,left,mid,right);}public static void printArr(int[] arr){for(int i:arr){System.out.print(i+" ");}}public static void main(String[] args) {int[] arr={101,109,1,10,5,6,3,8,2,0,-1,99};printArr(arr);System.out.println();sort(arr,0,arr.length-1);printArr(arr);} }

計數排序

計數排序，不是基于比較，而是基于計數，比較適合元素數值相近且為整數的情況。

• 遍歷數組，找出最大值和最小值。
• 根據最大值和最小值，初始化對應的統計元素數量的數組。
• 遍歷元素，統計元素個數到新的數組。
• 遍歷統計的數組，按照順序輸出排序的數組元素。

首先先遍歷一遍，找出最小的 min 和最大的元素 max，創建一個大小為 max - min + 1 的數組，再遍歷一次，統計數字個數，寫到數組中。

然后再遍歷一次統計數組，將每個元素置為前面一個元素加上自身，為什么這樣做呢？

這是為了讓統計數組存儲的元素值等于相應整數的最終排序位置，這樣我們就可以做到穩定排序，比如下面的 15 對應的是 8，也就是 15 在數組中出現是第 8 個元素，從后面開始遍歷，我們就可以保持穩定性。

public class CountSort {public static void countSort(int[] nums) {int max = nums[0];int min = nums[0];for (int i = 1; i < nums.length; i++) {if (nums[i] > max) {max = nums[i];}if (nums[i] < min) {min = nums[i];}}System.out.println("min:" + min + ",max:" + max);int count = max - min;int[] countNums = new int[count + 1];for (int i = 0; i < nums.length; i++) {countNums[nums[i] - min]++;}System.out.print("countNums: ");printf(countNums);int sum = 0;// 后面的元素等于前面元素加上自身for (int i = 0; i < count + 1; i++) {sum += countNums[i];countNums[i] = sum;}System.out.print("countNums: ");printf(countNums);int[] newNums = new int[nums.length];for (int i = nums.length - 1; i >= 0; i--) {/*** nums[i] - min 表示原數組 nums 里面第i位置對應的數在統計數組里面的位置索引*/newNums[countNums[nums[i] - min] - 1] = nums[i];countNums[nums[i] - min]--;}printf(newNums);}public static void printf(int[] nums) {for (int num : nums) {System.out.print(num + " ");}System.out.println("");} }

桶排序
桶排序，是指用多個桶存儲元素，每個桶有一個存儲范圍，先將元素按照范圍放到各個桶中，每個桶中是一個子數組，然后再對每個子數組進行排序，最后合并子數組，成為最終有序的數組。這其實和計數排序很相似，只不過計數排序每個桶只有一個元素，而且桶存儲的值為該元素出現的次數。

桶排序的具體步驟：

• 遍歷數組，查找數組的最大最小值，設置桶的區間（非必需），初始化一定數量的桶，每個桶對應一定的數值區間。
• 遍歷數組，將每一個數，放到對應的桶中。
• 對每一個非空的桶進行分別排序（桶內部的排序可以選擇 JDK 自帶排序）。
• 將桶中的子數組拼接成為最終的排序數組。

import java.util.ArrayList; import java.util.Collections; import java.util.List;public class BucketSort {public static void bucketSort(int[] nums) {// 遍歷數組獲取最大最小值int max = Integer.MIN_VALUE;int min = Integer.MAX_VALUE;for (int i = 0; i < nums.length; i++) {max = Math.max(max, nums[i]);min = Math.min(min, nums[i]);}// 計算桶的數量int bucketNum = (max - min) / nums.length + 1;System.out.println("最小：" + min + "，最大：" + max + ",桶的數量：" + bucketNum);List<List<Integer>> buckets = new ArrayList<List<Integer>>(bucketNum);for (int i = 0; i < bucketNum; i++) {buckets.add(new ArrayList<Integer>());}// 將每個元素放入桶for (int i = 0; i < nums.length; i++) {int num = (nums[i] - min) / (nums.length);buckets.get(num).add(nums[i]);}// 對每個桶內部進行排序for (int i = 0; i < buckets.size(); i++) {Collections.sort(buckets.get(i));}// 將桶的元素復制到數組中int index = 0;for (int i = 0; i < buckets.size(); i++) {for (int j = 0; j < buckets.get(i).size(); j++) {nums[index++] = buckets.get(i).get(j);}}}public static void printf(int[] nums) {for (int num : nums) {System.out.print(num + " ");}System.out.println("");} }

堆排序
排序的思路為：

• 將無序的數組構建出一個大頂堆，也就是上面的元素比下面的元素大。
• 將堆頂的元素和堆的最末尾的元素交換，將最大元素下沉到數組的最后面（末端）。
• 重新調整前面的順序，繼續交換堆頂的元素和當前末尾的元素，直到所有元素全部下沉。

package com.ty;public class HeapSort {public static void heaptrify(int[] arr,int cur,int length){int leftNode=cur*2+1;int rightNode=cur*2+2;int maxNode=cur;if(leftNode<length&&arr[maxNode]<arr[leftNode]){maxNode=leftNode;}if(rightNode<length&&arr[maxNode]<arr[rightNode]){maxNode=rightNode;}if(maxNode!=cur){swap(arr,maxNode,cur);heaptrify(arr,maxNode,length);}}public static void buildHeap(int[]arr){int lastNode=arr.length-1;int curNode=(lastNode-1)/2;for (int i = curNode; i >=0 ; i--) {heaptrify(arr,i, arr.length);}}public static void heapSort(int[]arr){buildHeap(arr);int k=arr.length-1;while(k>=0){swap(arr,0,k);heaptrify(arr,0,k);k--;}}public static void swap(int[] arr,int i,int j){int temp;temp=arr[i];arr[i]=arr[j];arr[j]=temp;}public static void printArr(int[] arr){for(int i:arr){System.out.print(i+" ");}}public static void main(String[] args) {int[] arr= {1,10,5,6,3,8,2,0,100,45};printArr(arr);heapSort(arr);System.out.println();printArr(arr);} }

基數排序

假設有一串數字，12,12, 10, 45, 32, 56, 677, 93, 22, 22, 30。

先準備一個盒子，里面有0到9的數據。

第一步、根據個位的數字將按照順序排列到盒子里：10, 30, 12, 12, 32, 22, 22, 93, 45, 56, 677

第二步、根據十位的數字將按照順序排列到盒子里：10, 12, 12, 22, 22, 30, 32, 45, 56, 677, 93

第三步、根據百位的的數字按照順序排列到盒子里：10, 12, 12, 22, 22, 30, 32, 45, 56, 93, 677

1、判斷這一串數字中最大數的位數。
2、因為每次排序只有位數不一樣，所以排序的代碼基本相同，用一個循環實現排序。
3、打印排序好的數。

import java.util.Arrays;public class Paix {public static void main(String[] args) {int[] arr = new int[]{12,12, 10, 45, 32, 56, 677, 93, 22, 22, 30}; //定義一個數組int max = 0;for (int k : arr) { //得到這些數里面最大數的長度if ((k + "").length() > max) {max = (k + "").length();}}for (int x = 0; x < max; x++) {int[][] temp = new int[10][arr.length];int[] tempcount = new int[10];int n = (int) Math.pow(10, x);for (int k : arr) {int number = (((k / n) % 10));temp[number][tempcount[number]] = k; //temp[number]默認值為0tempcount[number]++;}int result = 0;for (int i = 0; i < tempcount.length; i++) {for (int j = 0; j < tempcount[i]; j++) {arr[result] = temp[i][j];result++;}}System.out.println(Arrays.toString(arr));}} }

總結

以上是生活随笔為你收集整理的十大经典排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。