Java實現(xiàn)八種排序算法詳細(xì)代碼舉例
分類
這里的排序可以分為兩大類,
- 基于比較的排序
- 非基于比較的排序
其中有七種基于比較的排序:
- 直接插入排序
- 希爾排序
- 選擇排序
- 堆排序
- 冒泡排序
- 快速排序
- 歸并排序
一種非基于比較的排序:計數(shù)排序。
下面會通過Java來實現(xiàn)這八種排序,快速排序 和 歸并排序 會有遞歸和非遞歸的實現(xiàn)。
直接插入排序
思路:
- 以兩個for循環(huán), 來實現(xiàn)兩個數(shù)及兩數(shù)中小數(shù)與前面數(shù)進(jìn)行比較
- 假設(shè)第一個數(shù)為tmp,認(rèn)為第一個數(shù)已經(jīng)是排好序的,然后去和后面一個數(shù)進(jìn)行比較
- 如果 j位置 的數(shù) > j+1位置的數(shù),把 j位置的數(shù) 賦值給 j+1位置;如果否,則向 j位置的前面去做,直到 j >= 0
- 重復(fù)進(jìn)行步驟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;
}
}時間復(fù)雜度:O(N^2)
空間復(fù)雜度:O(1)
穩(wěn)定性:穩(wěn)定
注意:
- 本身是一個穩(wěn)定的排序,那么可以實現(xiàn)為不穩(wěn)定的 。但是 如果一個排序 本身就是不穩(wěn)定,那就不能實現(xiàn)穩(wěn)定的排序。
- 數(shù)據(jù)越有序,直接插入排序越快
希爾排序
步驟:
希爾排序算是對直接排序進(jìn)行優(yōu)化,把其中的數(shù)據(jù)通過分組來不斷簡化 其中的有序性,上面有提到數(shù)據(jù)越有序,直接插入排序越快,不過這個分組并不是常規(guī)理解的那種把幾個臨近的數(shù)字化為一個組,而是,如下圖所示:

通過間隔(gap)來實現(xiàn)分組,以上面 紫色的原圖 為例,這時的gap為5,這代表著隔著5個空格的數(shù)為一組,然后進(jìn)行組內(nèi)排序,不斷縮小間隔,增加每組內(nèi)元素個數(shù),再次進(jìn)一步比較。
動圖如下:

代碼:
通過代碼部分,我們也能看出這里面有直接排序的存在,只不過其中的部分和希爾排序有些出入。
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;
}
}時間復(fù)雜度:O(N^1.2) - O(N^1.3)
空間復(fù)雜度:O(1)
穩(wěn)定性:不穩(wěn)定
選擇排序
第一種思路
步驟:
- 選擇排序,從名字上我們可以理解為從中不斷選擇出最小值,然后把它交換、排到前面
- 之所以說是不斷選出最小值,是因為每次選出最小值都是以 i位置為準(zhǔn),而i位置也會不斷變化,兩個for循環(huán)來實現(xià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;
}因為其中有元素位置的交換,所以我們可以自己寫一個元素位置交換的方法。
時間復(fù)雜度:O(N^2) 和數(shù)據(jù) 是否有序無關(guān)
空間復(fù)雜度:O(1)
穩(wěn)定性:不穩(wěn)定
第二種思路
步驟:
這里主要是通過雙指針的方法來找到 最小值 和 最大值的位置,當(dāng)然,這是相對于每次i位置的數(shù)的大小。整體過程和上面一種思路有些相似的部分,相對來說,掌握兩種方法還是要好一點。
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 下標(biāo)
//此時把最大值換到了minIndex下標(biāo)
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;
}堆排序
步驟:
- 通過向下調(diào)整,創(chuàng)建一棵大根堆的樹
- 通過把根節(jié)點和最后一個分支節(jié)點進(jìn)行交換
- 再進(jìn)行向下調(diào)整,完成排序
這個思路主要是通過大根堆的由大到小的原理,再通過換位來實現(xiàn)排序。
代碼:
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);//向下調(diào)整,創(chuàng)建大根堆
}
}
/**
*
* @param array
* @param parent 每棵子樹調(diào)整的根節(jié)點
* @param length 每棵子樹調(diào)整的結(jié)束節(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;
}時間復(fù)雜度:O(N*logN)
空間復(fù)雜度:O(1)穩(wěn)定性:不穩(wěn)定
冒泡排序
步驟:
通過相鄰的兩個元素相互比較,若 前位置 比 后位置的數(shù)要大,進(jì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個數(shù)據(jù),比較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;
}
時間復(fù)雜度:不優(yōu)化的情況(沒有下方的boolean元素和-i操作) O(n^2)
優(yōu)化以后,最快情況能達(dá)到O(N)
空間復(fù)雜度:O(1)
穩(wěn)定性:穩(wěn)定
快速排序
快速排序有三種方式能來實現(xiàn)
- 挖坑法
- hoare法
- 雙指針法
如果問題問到快速排序,優(yōu)先使用挖坑法,其次hoare法、雙指針法
挖坑法
步驟:
- 先是實現(xiàn) 保證一個數(shù)的左邊都比它小,右邊都比它大,具體步驟如下步驟2,3,4
- 把第一個數(shù)存起來,為tmp,第一個位置當(dāng)作是坑
- 從后面找比tmp小的值,放到坑里面,后面被放入坑的數(shù)的位置再當(dāng)作坑
- 從前面找比tmp大的值,放到坑里面,前面被放入坑的數(shù)的位置當(dāng)作坑
- 再向兩邊進(jìn)行遞歸來處理
動圖如下:

代碼:
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
private static void quick(int[] array, int start, int end){
// = 是為了應(yīng)對沒有右邊的情況,遞歸結(jié)束條件
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小的數(shù)
while(left < right && array[right] >= tmp){
right--;
}
//挖坑法,然后填坑
//先是把第一個位置當(dāng)作空,從后面數(shù),如果有數(shù)比它小,就放到第一位
//然后是從前數(shù),找最大值,找到后放到,剛剛的位置
//最后再把第一個數(shù)放到right和left相交的位置
//方法就是把兩邊的數(shù)分大小放到第一個數(shù)兩邊
array[left] = array[right];
//找到比tmp大的數(shù)
while(left < right && array[left] <= tmp){
left++;
}
array[right] = array[left];
}
array[left] = tmp;
return left;
}hoare法
步驟:
- 先是實現(xiàn) 保證一個數(shù)的左邊都比它小,右邊都比它大,具體步驟如下步驟2,3,4
- 把第一個數(shù)存起來,為tmp
- tmp和后面的數(shù)進(jìn)行比較,然后把小數(shù)放到tmp前面,大數(shù)放到tmp后面
- 遞歸實現(xiàn)對tmp兩邊進(jìn)行排序
代碼如下:
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
private static void quick(int[] array, int start, int end){
// = 是為了應(yīng)對沒有右邊的情況,遞歸結(jié)束條件
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是為了把右邊的小數(shù)移到左邊
while(left < right && array[right] >= tmp){
right--;
}
while(left < right && array[left] <= tmp){
left++;
}
swap(array, left, right);
}
//因為left所找的是把左邊的大數(shù)放到右邊,所以找到最后的數(shù)會比left小,進(jìn)行交換
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 雙指針來實現(xiàn)排序的,通過前后條件判斷來進(jìn)行排序
代碼如下:
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
private static void quick(int[] array, int start, int end){
// = 是為了應(yīng)對沒有右邊的情況,遞歸結(jié)束條件
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;
}關(guān)于快速排序
時間復(fù)雜度:當(dāng)數(shù)據(jù)給定的是1 2 3 4 5 6……有序的情況是 O(n^2)
最好的情況是O(N*logN)均勻分為叉,滿二叉樹
空間復(fù)雜度:最壞情況,遞歸是要開辟內(nèi)存的O(N),最好的情況,滿二叉樹O(logN)
穩(wěn)定性:不穩(wěn)定
優(yōu)化
通過上面三種方法,我們能看到三種方法中都有遞歸方式,每次遞歸都需要開辟內(nèi)存,那么我們可以采取怎樣的方式來減少遞歸的次數(shù)?
通過下面兩種方法可以實現(xiàn)我們的想法:
三數(shù)取中
直接插入法【針對一定范圍】
關(guān)于三數(shù)取中的意思是:找到左、右、中三個數(shù)的中位數(shù)。
部分直接插入,也可以減少遞歸次數(shù),因為數(shù)據(jù)有越有序,直接插入法越快。
代碼部分如下:
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){
// = 是為了應(yīng)對沒有右邊的情況,遞歸結(jié)束條件
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小的數(shù)
while(left < right && array[right] >= tmp){
right--;
}
//挖坑法,然后填坑
//先是把第一個位置當(dāng)作空,從后面數(shù),如果有數(shù)比它小,就放到第一位
//然后是從前數(shù),找最大值,找到后放到,剛剛的位置
//最后再把第一個數(shù)放到right和left相交的位置
//方法就是把兩邊的數(shù)分大小放到第一個數(shù)兩邊
array[left] = array[right];
//找到比tmp大的數(shù)
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;
}
}非遞歸實現(xiàn)
非遞歸實現(xiàn),主要是棧的使用,通過控制出棧和入棧的元素及其順序來實現(xiàn)
代碼如下:
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小的數(shù)
while(left < right && array[right] >= tmp){
right--;
}
//挖坑法,然后填坑
//先是把第一個位置當(dāng)作空,從后面數(shù),如果有數(shù)比它小,就放到第一位
//然后是從前數(shù),找最大值,找到后放到,剛剛的位置
//最后再把第一個數(shù)放到right和left相交的位置
//方法就是把兩邊的數(shù)分大小放到第一個數(shù)兩邊
array[left] = array[right];
//找到比tmp大的數(shù)
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ù)向下分組(有種遞歸的味道了)
- 把每組元素比較完后,再把兩個有序數(shù)組組合起來

代碼如下:
public static void mergeSort(int[] array){
mergeSortTmp(array, 0, array.length-1);
}
//遞歸實現(xiàn)歸并排序
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);
//走到這里,相當(dāng)于全部分解完
//合并,合并有序數(shù)組
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數(shù)組是有序的
for (int i = 0; i < k; i++) {
array[i+left] = tmp[i];
}
}時間復(fù)雜度:O(N*logN)
空間復(fù)雜度:O(N)
穩(wěn)定性:穩(wěn)定
非遞歸實現(xiàn)
非遞歸的實現(xiàn),主要依靠的間隔gap的不斷變大,然后通過每一小部分的排序進(jìn)而來實現(xiàn)整個數(shù)據(jù)組的排序
代碼如下:
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數(shù)組是有序的
for (int i = 0; i < k; i++) {
array[i+left] = tmp[i];
}
}計數(shù)排序
非基于比較的排序
還有桶排序, 基數(shù)排序,感興趣可以了解一下
使用場景:集中在某個范圍內(nèi)的一組數(shù)據(jù)
步驟:
- 根據(jù)數(shù)據(jù)的個數(shù)來創(chuàng)建數(shù)組
- 把對應(yīng)元素出現(xiàn)的個數(shù)給到對應(yīng)的位置,記錄出現(xiàn)的次數(shù)
- 根據(jù)記錄的次數(shù),依次輸出元素

代碼如下 :
public static void countSort(int[] array){
//1.找最大值 和 最小值 來確定 計數(shù)數(shù)組的大小
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.遍歷原來的數(shù)組array, 把每個元素 放到對應(yīng)的計數(shù)數(shù)組中 進(jìn)行比較
for (int i = 0; i < array.length; i++) {
int index = array[i];
count[index-minVal]++;
}
//3.依次 遍歷計數(shù)數(shù)組
int index = 0;
for (int i = 0; i < count.length; i++) {
while(count[i] != 0){
array[index] = i+minVal;
index++;
count[i]--;
}
}
}總結(jié)
到此這篇關(guān)于Java實現(xiàn)八種排序算法的文章就介紹到這了,更多相關(guān)Java八種排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringBoot同時集成Mybatis和Mybatis-plus框架
在實際開發(fā)中,項目里面一般都是Mybatis和Mybatis-Plus公用,但是公用有版本不兼容的問題,本文主要介紹了Spring Boot項目中同時集成Mybatis和Mybatis-plus,具有一檔的參考價值,感興趣的可以了解一下2024-12-12
MybatisPlus關(guān)聯(lián)查詢的完美實現(xiàn)方案
我們在項目開發(fā)的時候,難免會遇到連表查詢的操作,所以下面這篇文章主要給大家介紹了關(guān)于MybatisPlus關(guān)聯(lián)查詢的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2021-12-12
Netty客戶端接入流程NioSocketChannel創(chuàng)建解析
這篇文章主要為大家介紹了Netty客戶端接入流程NioSocketChannel創(chuàng)建源碼解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-03-03
SpringBoot實現(xiàn)緩存預(yù)熱的幾種常用方案
緩存預(yù)熱是指在 Spring Boot 項目啟動時,預(yù)先將數(shù)據(jù)加載到緩存系統(tǒng)(如 Redis)中的一種機(jī)制,本文給大家介紹了SpringBoot實現(xiàn)緩存預(yù)熱的幾種常用方案,并通過代碼示例講解的非常詳細(xì),需要的朋友可以參考下2024-02-02
MyBatis Mapper.xml入?yún)ist使用in函數(shù)問題
文章主要講述了在使用MyBatis的Mapper.xml文件時,如何正確地在in函數(shù)中使用List作為入?yún)?作者強(qiáng)調(diào)了完整拷貝<if>...</if>格式的重要性,并指出稍微的改動就會導(dǎo)致錯誤2025-02-02
java中char類型轉(zhuǎn)換成int類型的2種方法
這篇文章主要給大家介紹了關(guān)于java中char類型轉(zhuǎn)換成int類型的2種方法,因為java是一門強(qiáng)類型語言,所以在數(shù)據(jù)運算中會存在類型轉(zhuǎn)換,需要的朋友可以參考下2023-07-07

