Java實現八種排序算法詳細代碼舉例
更新時間：2024年10月26日 10:11:37 作者：小川_wenxun
排序問題一直是程序員工作與面試的重點,今天特意整理研究下與大家共勉!這篇文章主要介紹了Java實現八種排序算法的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下
分類
這里的排序可以分為兩大類，
- 基于比較的排序
- 非基于比較的排序
其中有七種基于比較的排序：
- 直接插入排序
- 希爾排序
- 選擇排序
- 堆排序
- 冒泡排序
- 快速排序
- 歸并排序
一種非基于比較的排序：計數排序。
下面會通過Java來實現這八種排序，快速排序 和 歸并排序 會有遞歸和非遞歸的實現。
直接插入排序
思路：
- 以兩個for循環(huán)， 來實現兩個數及兩數中小數與前面數進行比較
- 假設第一個數為tmp，認為第一個數已經是排好序的，然后去和后面一個數進行比較
- 如果 j位置 的數 > j+1位置的數，把 j位置的數 賦值給 j+1位置；如果否，則向 j位置的前面去做，直到 j >= 0
- 重復進行步驟3，直到不符合循環(huán)條件
動圖如下：
代碼 ：
public static void insertSort(int[] array){
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int j = i-1;
for (; j >= 0; j--) {
if(array[j] > tmp){
array[j+1] = array[j];
}else{
array[j+1] = tmp;
break;
}
}
array[j+1] = tmp;
}
}時間復雜度：O(N^2)
空間復雜度：O(1)
穩(wěn)定性：穩(wěn)定
注意：
- 本身是一個穩(wěn)定的排序，那么可以實現為不穩(wěn)定的 。但是 如果一個排序 本身就是不穩(wěn)定，那就不能實現穩(wěn)定的排序。
- 數據越有序，直接插入排序越快
希爾排序
步驟：
希爾排序算是對直接排序進行優(yōu)化，把其中的數據通過分組來不斷簡化 其中的有序性，上面有提到數據越有序，直接插入排序越快，不過這個分組并不是常規(guī)理解的那種把幾個臨近的數字化為一個組，而是，如下圖所示：
通過間隔（gap）來實現分組，以上面 紫色的原圖 為例，這時的gap為5，這代表著隔著5個空格的數為一組，然后進行組內排序，不斷縮小間隔，增加每組內元素個數，再次進一步比較。
動圖如下：
代碼：
通過代碼部分，我們也能看出這里面有直接排序的存在，只不過其中的部分和希爾排序有些出入。
public static void shellInsert(int[] array){
int gap = array.length;
while(gap > 1){
gap /= 2;
shell(array, gap);
}
}
private static void shell(int[] array, int gap) {
for (int i = gap; i < array.length; i++) {
int tmp = array[i];
int j = i-gap;
for (; j >= 0; j-= gap) {
if(array[j] > tmp){
array[j+gap] = array[j];
}else{
array[j+gap] = tmp;
break;
}
}
array[j+gap] = tmp;
}
}時間復雜度：O(N^1.2) - O(N^1.3)
空間復雜度：O(1)
穩(wěn)定性：不穩(wěn)定
選擇排序
第一種思路
步驟：
- 選擇排序，從名字上我們可以理解為從中不斷選擇出最小值，然后把它交換、排到前面
- 之所以說是不斷選出最小值，是因為每次選出最小值都是以 i位置為準，而i位置也會不斷變化，兩個for循環(huán)來實現
動圖如下：
代碼：
public static void selectSort(int[] array){
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i+1; j < array.length; j++) {
if(array[j] < array[minIndex]){
minIndex = j;
}
}
swap(array,i,minIndex);
}
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}因為其中有元素位置的交換，所以我們可以自己寫一個元素位置交換的方法。
時間復雜度：O(N^2) 和數據 是否有序無關
空間復雜度：O(1)
穩(wěn)定性：不穩(wěn)定
第二種思路
步驟：
這里主要是通過雙指針的方法來找到 最小值 和 最大值的位置，當然，這是相對于每次i位置的數的大小。整體過程和上面一種思路有些相似的部分，相對來說，掌握兩種方法還是要好一點。
public static void selectSort1(int[] array){
int left = 0;
int right = array.length-1;
while(left < right){
int minIndex = left;
int maxIndex = left;
for (int i = left+1; i <= right; i++) {
if(array[i] < array[minIndex]){
minIndex = i;
}
if(array[i] > array[maxIndex]){
maxIndex = i;
}
}
swap(array, left, minIndex);
//確保最大值的位置，最大值正好是 left 下標
//此時把最大值換到了minIndex下標
if(maxIndex == 0){
maxIndex = minIndex;
}
swap(array, right, maxIndex);
left++;
right--;
}
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}堆排序
步驟：
- 通過向下調整，創(chuàng)建一棵大根堆的樹
- 通過把根節(jié)點和最后一個分支節(jié)點進行交換
- 再進行向下調整，完成排序
這個思路主要是通過大根堆的由大到小的原理，再通過換位來實現排序。
代碼：
public static void heapSort(int[] array){
createHeap(array);
int end = array.length-1;
while(end > 0){
swap(array, 0 ,end);
siftDown(array, 0,end);
end--;
}
}
//創(chuàng)建大根堆
public static void createHeap(int[] array){
//length-1為最后一棵子樹，-1 / 2 是為了找到最后一棵子樹的根節(jié)點
for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
siftDown(array,parent,array.length);//向下調整，創(chuàng)建大根堆
}
}
/**
*
* @param array
* @param parent 每棵子樹調整的根節(jié)點
* @param length 每棵子樹調整的結束節(jié)點，跳到最后
*/
public static void siftDown(int[] array, int parent, int length) {
int child = 2*parent+1;
while(child < length){
if(child + 1 < length && array[child] < array[child +1]){
child++;
}
if(array[child] > array[parent]){
swap(array, child, parent);
parent = child;
child = 2*parent+1;
}else{
break;
}
}
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}時間復雜度：O(N*logN)
空間復雜度：O(1)穩(wěn)定性：不穩(wěn)定
冒泡排序
步驟：
通過相鄰的兩個元素相互比較，若 前位置 比 后位置的數要大，進行交換
動圖如下：
下面代碼部分是優(yōu)化后的部分，未優(yōu)化則不包含(flg元素 和 -i操作 )
代碼：
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length-1; i++) {
boolean flg = false;
for (int j = 0; j < array.length-1-i; j++) {
if(array[j] > array[j+1]){
swap(array, j, j+1);
flg = true;
}
}
//優(yōu)化后的情況
//n個數據，比較n-1次，有可能其中i次就有序了
if(!flg){
break;
}
}
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}
時間復雜度：不優(yōu)化的情況（沒有下方的boolean元素和-i操作） O(n^2)
優(yōu)化以后，最快情況能達到O(N)
空間復雜度：O(1)
穩(wěn)定性：穩(wěn)定
快速排序
快速排序有三種方式能來實現
- 挖坑法
- hoare法
- 雙指針法
如果問題問到快速排序，優(yōu)先使用挖坑法，其次hoare法、雙指針法
挖坑法
步驟：
- 先是實現 保證一個數的左邊都比它小，右邊都比它大，具體步驟如下步驟2，3，4
- 把第一個數存起來，為tmp，第一個位置當作是坑
- 從后面找比tmp小的值，放到坑里面，后面被放入坑的數的位置再當作坑
- 從前面找比tmp大的值，放到坑里面，前面被放入坑的數的位置當作坑
- 再向兩邊進行遞歸來處理
動圖如下：
代碼：
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
private static void quick(int[] array, int start, int end){
// = 是為了應對沒有右邊的情況，遞歸結束條件
if(start >= end){
return;
}
//整個方法走完之后，為第一次交換位置
int pivot = partition1(array, start, end);
quick(array, start, pivot-1);
quick(array, pivot+1, end);
}
private static int partition1(int[] array, int left, int right) {
int tmp = array[left];
while(left < right){
//循環(huán)找，不循環(huán)時則代表找到，找到比tmp小的數
while(left < right && array[right] >= tmp){
right--;
}
//挖坑法，然后填坑
//先是把第一個位置當作空，從后面數，如果有數比它小，就放到第一位
//然后是從前數，找最大值，找到后放到，剛剛的位置
//最后再把第一個數放到right和left相交的位置
//方法就是把兩邊的數分大小放到第一個數兩邊
array[left] = array[right];
//找到比tmp大的數
while(left < right && array[left] <= tmp){
left++;
}
array[right] = array[left];
}
array[left] = tmp;
return left;
}hoare法
步驟：
- 先是實現 保證一個數的左邊都比它小，右邊都比它大，具體步驟如下步驟2，3，4
- 把第一個數存起來，為tmp
- tmp和后面的數進行比較，然后把小數放到tmp前面，大數放到tmp后面
- 遞歸實現對tmp兩邊進行排序
代碼如下：
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
private static void quick(int[] array, int start, int end){
// = 是為了應對沒有右邊的情況，遞歸結束條件
if(start >= end){
return;
}
//整個方法走完之后，為第一次交換位置
int pivot = partition(array, start, end);
quick(array, start, pivot-1);
quick(array, pivot+1, end);
}
private static int partition(int[] array, int left, int right) {
int tmp = array[left];
int tmpleft = left;
while(left < right){
//循環(huán)找，不循環(huán)時則代表找到
//right是為了把右邊的小數移到左邊
while(left < right && array[right] >= tmp){
right--;
}
while(left < right && array[left] <= tmp){
left++;
}
swap(array, left, right);
}
//因為left所找的是把左邊的大數放到右邊，所以找到最后的數會比left小，進行交換
swap(array,left,tmpleft);
return left;
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}雙指針法
步驟：
這個主要是靠 cur + left 雙指針來實現排序的，通過前后條件判斷來進行排序
代碼如下：
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
private static void quick(int[] array, int start, int end){
// = 是為了應對沒有右邊的情況，遞歸結束條件
if(start >= end){
return;
}
//整個方法走完之后，為第一次交換位置
int pivot = partition3(array, start, end);
quick(array, start, pivot-1);
quick(array, pivot+1, end);
}
public static int partition3(int[] array, int left, int right){
int prev = left;
int cur = left+1;
while(cur <= right){
if(array[left] > array[cur] && array[cur] != array[prev]){
swap(array, cur, prev);
}
cur++;
}
swap(array,prev,left);
return prev;
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}關于快速排序
時間復雜度：當數據給定的是1 2 3 4 5 6……有序的情況是 O(n^2)
最好的情況是O(N*logN)均勻分為叉，滿二叉樹
空間復雜度：最壞情況，遞歸是要開辟內存的O(N),最好的情況，滿二叉樹O(logN)
穩(wěn)定性：不穩(wěn)定
優(yōu)化
通過上面三種方法，我們能看到三種方法中都有遞歸方式，每次遞歸都需要開辟內存，那么我們可以采取怎樣的方式來減少遞歸的次數？
通過下面兩種方法可以實現我們的想法：
三數取中
直接插入法【針對一定范圍】
關于三數取中的意思是：找到左、右、中三個數的中位數。
部分直接插入，也可以減少遞歸次數，因為數據有越有序，直接插入法越快。
代碼部分如下：
public class Sort {
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
private static void quick(int[] array, int start, int end){
// = 是為了應對沒有右邊的情況，遞歸結束條件
if(start >= end){
return;
}
if(end - start + 1 <= 7){
insertSortRange(array, start, end);
return;
}
int minIndex = getMiddleNum(array, start, end);
swap(array, start, minIndex);
//整個方法走完之后，為第一次交換位置
int pivot = partition1(array, start, end);
quick(array, start, pivot-1);
quick(array, pivot+1, end);
}
public static void insertSortRange(int[] array, int start, int end){
for (int i = start+1; i <= end; i++) {
int tmp = array[i];
int j = i-1;
for (; j >= start; j--) {
if(array[j] > tmp){
array[j+1] = array[j];
}else{
array[j+1] = tmp;
break;
}
}
array[j+1] = tmp;
}
}
private static int getMiddleNum(int[] array, int left, int right){
int mid = (left+right)/2;
if(array[left] < array[right]){
if(array[mid] < array[left]){
return left;
}else if(array[mid] > array[right]){
return right;
}else{
return mid;
}
}else{
if(array[mid] > array[left]){
return left;
}else if(array[mid] < array[right]){
return right;
}else{
return mid;
}
}
}
private static int partition1(int[] array, int left, int right) {
int tmp = array[left];
while(left < right){
//循環(huán)找，不循環(huán)時則代表找到，找到比tmp小的數
while(left < right && array[right] >= tmp){
right--;
}
//挖坑法，然后填坑
//先是把第一個位置當作空，從后面數，如果有數比它小，就放到第一位
//然后是從前數，找最大值，找到后放到，剛剛的位置
//最后再把第一個數放到right和left相交的位置
//方法就是把兩邊的數分大小放到第一個數兩邊
array[left] = array[right];
//找到比tmp大的數
while(left < right && array[left] <= tmp){
left++;
}
array[right] = array[left];
}
array[left] = tmp;
return left;
}
private static void swap(int[] array, int left, int right){
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
}
}非遞歸實現
非遞歸實現，主要是棧的使用，通過控制出棧和入棧的元素及其順序來實現
代碼如下：
public static void quickSort(int[] array){
quickNor(array,0,array.length-1);
}
private static void quickNor(int[] array, int start, int end){
Deque<Integer> stack = new ArrayDeque<>();
int pivot = partition1(array, start, end);
//pivot左邊有兩個元素
if(pivot > start+1){
stack.push(start);
stack.push(pivot-1);
}
if(pivot < end-1){
stack.push(pivot+1);
stack.push(end);
}
while(!stack.isEmpty()){
end = stack.pop();
start = stack.pop();
pivot = partition1(array, start, end);
if(pivot > start+1){
stack.push(start);
stack.push(pivot-1);
}
if(pivot < end-1){
stack.push(pivot+1);
stack.push(end);
}
}
}
private static int partition1(int[] array, int left, int right) {
int tmp = array[left];
while(left < right){
//循環(huán)找，不循環(huán)時則代表找到，找到比tmp小的數
while(left < right && array[right] >= tmp){
right--;
}
//挖坑法，然后填坑
//先是把第一個位置當作空，從后面數，如果有數比它小，就放到第一位
//然后是從前數，找最大值，找到后放到，剛剛的位置
//最后再把第一個數放到right和left相交的位置
//方法就是把兩邊的數分大小放到第一個數兩邊
array[left] = array[right];
//找到比tmp大的數
while(left < right && array[left] <= tmp){
left++;
}
array[right] = array[left];
}
array[left] = tmp;
return left;
}
private static void swap(int[] array, int left, int right){
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
}歸并排序
步驟：
- 先把要排序的元素分為兩個組，接著繼續(xù)向下分組(有種遞歸的味道了)
- 把每組元素比較完后，再把兩個有序數組組合起來
代碼如下：
public static void mergeSort(int[] array){
mergeSortTmp(array, 0, array.length-1);
}
//遞歸實現歸并排序
private static void mergeSortTmp(int[] array, int left, int right) {
if(left >= right){
return;
}
//找中間值
int mid = (left + right)/2;
mergeSortTmp(array, left, mid-1);
mergeSortTmp(array, mid+1, right);
//走到這里，相當于全部分解完
//合并，合并有序數組
merge(array, left, mid, right);
}
private static void merge(int[] array, int left, int mid, int right) {
int[] tmp = new int[right-left+1];
int k = 0;
int s1 = left;
int e1 = mid;
int s2 = mid+1;
int e2 = right;
while(s1 <= e1 && s2 <= e2){
if(array[s1] <= array[s2]){
tmp[k++] = array[s1++];
}else {
tmp[k++] = array[s2++];
}
}
while(s1 <= e1){
tmp[k++] = array[s1++];
}
while(s2 <= e2){
tmp[k++] = array[s2++];
}
//可以保證tmp數組是有序的
for (int i = 0; i < k; i++) {
array[i+left] = tmp[i];
}
}時間復雜度：O(N*logN)
空間復雜度：O(N)
穩(wěn)定性：穩(wěn)定
非遞歸實現
非遞歸的實現，主要依靠的間隔gap的不斷變大，然后通過每一小部分的排序進而來實現整個數據組的排序
代碼如下：
public static void mergeSortNor(int[] array){
int gap =1;
while(gap < array.length){
for (int i = 0; i < array.length; i = i + gap*2) {
int left = i;
int mid = (left + gap -1);
if(mid >= array.length){
mid = array.length-1;
}
int right = mid + gap;
if(right >= array.length){
right = array.length-1;
}
merge(array, left, mid, right);
}
gap *= 2;
}
}
private static void merge(int[] array, int left, int mid, int right) {
int[] tmp = new int[right-left+1];
int k = 0;
int s1 = left;
int e1 = mid;
int s2 = mid+1;
int e2 = right;
while(s1 <= e1 && s2 <= e2){
if(array[s1] <= array[s2]){
tmp[k++] = array[s1++];
}else {
tmp[k++] = array[s2++];
}
}
while(s1 <= e1){
tmp[k++] = array[s1++];
}
while(s2 <= e2){
tmp[k++] = array[s2++];
}
//可以保證tmp數組是有序的
for (int i = 0; i < k; i++) {
array[i+left] = tmp[i];
}
}計數排序
非基于比較的排序
還有桶排序， 基數排序，感興趣可以了解一下
使用場景：集中在某個范圍內的一組數據
步驟：
- 根據數據的個數來創(chuàng)建數組
- 把對應元素出現的個數給到對應的位置，記錄出現的次數
- 根據記錄的次數，依次輸出元素
代碼如下 ：
public static void countSort(int[] array){
//1.找最大值 和 最小值 來確定 計數數組的大小
int maxVal = array[0];
int minVal = array[0];
for (int i = 1; i < array.length; i++) {
if(array[i] > maxVal){
maxVal = array[i];
}
if(array[i] < minVal){
minVal = array[i];
}
}
int len = maxVal - minVal + 1;
int[] count = new int[len];
//2.遍歷原來的數組array， 把每個元素 放到對應的計數數組中 進行比較
for (int i = 0; i < array.length; i++) {
int index = array[i];
count[index-minVal]++;
}
//3.依次 遍歷計數數組
int index = 0;
for (int i = 0; i < count.length; i++) {
while(count[i] != 0){
array[index] = i+minVal;
index++;
count[i]--;
}
}
}總結
到此這篇關于Java實現八種排序算法的文章就介紹到這了,更多相關Java八種排序算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
SpringBoot同時集成Mybatis和Mybatis-plus框架
在實際開發(fā)中,項目里面一般都是Mybatis和Mybatis-Plus公用,但是公用有版本不兼容的問題,本文主要介紹了Spring Boot項目中同時集成Mybatis和Mybatis-plus,具有一檔的參考價值,感興趣的可以了解一下2024-12-12
這篇文章主要給大家介紹了關于java中引用類型之強軟弱虛的相關資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用java具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2020-06-06
這篇文章介紹了處理jar包依賴沖突的幾種方法,包括：優(yōu)先原則、路徑近者優(yōu)先、排除原則、版本鎖定原則、查看間接依賴、排包和處理jar包依賴沖突的總結2025-01-01
java中通用的線程池實例代碼，需要的朋友可以參考一下2013-03-03
我們在項目開發(fā)的時候,難免會遇到連表查詢的操作,所以下面這篇文章主要給大家介紹了關于MybatisPlus關聯查詢的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2021-12-12
Netty客戶端接入流程NioSocketChannel創(chuàng)建解析
這篇文章主要為大家介紹了Netty客戶端接入流程NioSocketChannel創(chuàng)建源碼解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-03-03
這篇文章主要介紹了關于弗洛伊德算法求最短路徑詳解,弗洛伊德算法VS迪杰斯特拉算法:迪杰斯特拉算法通過選定的被訪問頂點，求出從出發(fā)訪問頂點到其他項點的最短路徑:弗洛伊德算法中每-個頂點都是出發(fā)訪問點,需要的朋友可以參考下2023-07-07
緩存預熱是指在 Spring Boot 項目啟動時,預先將數據加載到緩存系統(tǒng)（如 Redis）中的一種機制,本文給大家介紹了SpringBoot實現緩存預熱的幾種常用方案,并通過代碼示例講解的非常詳細,需要的朋友可以參考下2024-02-02
MyBatis Mapper.xml入參List使用in函數問題
文章主要講述了在使用MyBatis的Mapper.xml文件時,如何正確地在in函數中使用List作為入參,作者強調了完整拷貝<if>...</if>格式的重要性,并指出稍微的改動就會導致錯誤2025-02-02
這篇文章主要給大家介紹了關于java中char類型轉換成int類型的2種方法,因為java是一門強類型語言,所以在數據運算中會存在類型轉換,需要的朋友可以參考下2023-07-07