溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細(xì)講解有關(guān)java中常見(jiàn)的排序算法有哪些，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。
思路：
動(dòng)畫(huà)演示：
實(shí)現(xiàn)代碼：
/**
* @author Ye Hongzhi 公眾號(hào)：java技術(shù)愛(ài)好者
* @name BubbleSort
* @date 2020-09-05 21:38
**/
public class BubbleSort extends BaseSort {
public static void main(String[] args) {
BubbleSort sort = new BubbleSort();
sort.printNums();
}
@Override
protected void sort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
for (int i = 0; i < nums.length - 1; i++) {
for (int j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}
}
//10萬(wàn)個(gè)數(shù)的數(shù)組，耗時(shí)：21554毫秒
平均時(shí)間復(fù)雜度：O(n2)
空間復(fù)雜度：O(1)
算法穩(wěn)定性：穩(wěn)定
思路：
從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序；
取出下一個(gè)元素，在前面已排序的元素序列中，從后向前掃描；
如果該元素（已排序）大于新元素，將該元素移到下一位置；
重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
將新元素插入到該位置后；
重復(fù)步驟2~5。
動(dòng)畫(huà)演示：
實(shí)現(xiàn)代碼：
/**
* @author Ye Hongzhi 公眾號(hào)：java技術(shù)愛(ài)好者
* @name InsertSort
* @date 2020-09-05 22:34
**/
public class InsertSort extends BaseSort {
public static void main(String[] args) {
BaseSort sort = new InsertSort();
sort.printNums();
}
@Override
protected void sort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
for (int i = 0; i < nums.length - 1; i++) {
//當(dāng)前值
int curr = nums[i + 1];
//上一個(gè)數(shù)的指針
int preIndex = i;
//在數(shù)組中找到一個(gè)比當(dāng)前遍歷的數(shù)小的第一個(gè)數(shù)
while (preIndex >= 0 && curr < nums[preIndex]) {
//把比當(dāng)前遍歷的數(shù)大的數(shù)字往后移動(dòng)
nums[preIndex + 1] = nums[preIndex];
//需要插入的數(shù)的下標(biāo)往前移動(dòng)
preIndex--;
}
//插入到這個(gè)數(shù)的后面
nums[preIndex + 1] = curr;
}
}
}
//10萬(wàn)個(gè)數(shù)的數(shù)組，耗時(shí)：2051毫秒
平均時(shí)間復(fù)雜度：O(n2)
空間復(fù)雜度：O(1)
算法穩(wěn)定性：穩(wěn)定
思路：
第一輪，找到最小的元素，和數(shù)組第一個(gè)數(shù)交換位置。
第二輪，找到第二小的元素，和數(shù)組第二個(gè)數(shù)交換位置...
直到最后一個(gè)元素，排序完成。
動(dòng)畫(huà)演示：
實(shí)現(xiàn)代碼：
/**
* @author Ye Hongzhi 公眾號(hào)：java技術(shù)愛(ài)好者
* @name SelectSort
* @date 2020-09-06 22:27
**/
public class SelectSort extends BaseSort {
public static void main(String[] args) {
SelectSort sort = new SelectSort();
sort.printNums();
}
@Override
protected void sort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int minIndex = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = nums[i];
nums[minIndex] = temp;
nums[i] = nums[minIndex];
}
}
}
}
//10萬(wàn)個(gè)數(shù)的數(shù)組，耗時(shí)：8492毫秒
平均時(shí)間復(fù)雜度：O(n2)
算法空間復(fù)雜度：O(1)
算法穩(wěn)定性：不穩(wěn)定
思路：
把數(shù)組分割成若干(h)個(gè)小組(一般數(shù)組長(zhǎng)度length/2)，然后對(duì)每一個(gè)小組分別進(jìn)行插入排序。每一輪分割的數(shù)組的個(gè)數(shù)逐步縮小，h/2->h/4->h/8，并且進(jìn)行排序，保證有序。當(dāng)h=1時(shí)，則數(shù)組排序完成。
動(dòng)畫(huà)演示：
實(shí)現(xiàn)代碼：
/**
* @author Ye Hongzhi 公眾號(hào)：java技術(shù)愛(ài)好者
* @name SelectSort
* @date 2020-09-06 22:27
**/
public class ShellSort extends BaseSort {
public static void main(String[] args) {
ShellSort sort = new ShellSort();
sort.printNums();
}
@Override
protected void sort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
int length = nums.length;
int temp;
//步長(zhǎng)
int gap = length / 2;
while (gap > 0) {
for (int i = gap; i < length; i++) {
temp = nums[i];
int preIndex = i - gap;
while (preIndex >= 0 && nums[preIndex] > temp) {
nums[preIndex + gap] = nums[preIndex];
preIndex -= gap;
}
nums[preIndex + gap] = temp;
}
gap /= 2;
}
}
}
//10萬(wàn)個(gè)數(shù)的數(shù)組，耗時(shí)：261毫秒
平均時(shí)間復(fù)雜度：O(nlog2n)
算法空間復(fù)雜度：O(1)
算法穩(wěn)定性：穩(wěn)定
快排，面試最喜歡問(wèn)的排序算法。這是運(yùn)用分治法的一種排序算法。
思路：
動(dòng)畫(huà)演示：
實(shí)現(xiàn)代碼：
/**
* @author Ye Hongzhi 公眾號(hào)：java技術(shù)愛(ài)好者
* @name SelectSort
* @date 2020-09-06 22:27
**/
public class QuickSort extends BaseSort {
public static void main(String[] args) {
QuickSort sort = new QuickSort();
sort.printNums();
}
@Override
protected void sort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
quickSort(nums, 0, nums.length - 1);
}
private void quickSort(int[] nums, int star, int end) {
if (star > end) {
return;
}
int i = star;
int j = end;
int key = nums[star];
while (i < j) {
while (i < j && nums[j] > key) {
j--;
}
while (i < j && nums[i] <= key) {
i++;
}
if (i < j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
nums[star] = nums[i];
nums[i] = key;
quickSort(nums, star, i - 1);
quickSort(nums, i + 1, end);
}
}
//10萬(wàn)個(gè)數(shù)的數(shù)組，耗時(shí)：50毫秒
平均時(shí)間復(fù)雜度：O(nlogn)
算法空間復(fù)雜度：O(1)
算法穩(wěn)定性：不穩(wěn)定
歸并排序是采用分治法的典型應(yīng)用，而且是一種穩(wěn)定的排序方式，不過(guò)需要使用到額外的空間。
思路：
歸并排序的優(yōu)點(diǎn)在于最好情況和最壞的情況的時(shí)間復(fù)雜度都是O(nlogn)，所以是比較穩(wěn)定的排序方式。
動(dòng)畫(huà)演示：
實(shí)現(xiàn)代碼：
/**
* @author Ye Hongzhi 公眾號(hào)：java技術(shù)愛(ài)好者
* @name MergeSort
* @date 2020-09-08 23:30
**/
public class MergeSort extends BaseSort {
public static void main(String[] args) {
MergeSort sort = new MergeSort();
sort.printNums();
}
@Override
protected void sort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
//歸并排序
mergeSort(0, nums.length - 1, nums, new int[nums.length]);
}
private void mergeSort(int star, int end, int[] nums, int[] temp) {
//遞歸終止條件
if (star >= end) {
return;
}
int mid = star + (end - star) / 2;
//左邊進(jìn)行歸并排序
mergeSort(star, mid, nums, temp);
//右邊進(jìn)行歸并排序
mergeSort(mid + 1, end, nums, temp);
//合并左右
merge(star, end, mid, nums, temp);
}
private void merge(int star, int end, int mid, int[] nums, int[] temp) {
int index = 0;
int i = star;
int j = mid + 1;
while (i <= mid && j <= end) {
if (nums[i] > nums[j]) {
temp[index++] = nums[j++];
} else {
temp[index++] = nums[i++];
}
}
while (i <= mid) {
temp[index++] = nums[i++];
}
while (j <= end) {
temp[index++] = nums[j++];
}
//把臨時(shí)數(shù)組中已排序的數(shù)復(fù)制到nums數(shù)組中
if (index >= 0) System.arraycopy(temp, 0, nums, star, index);
}
}
//10萬(wàn)個(gè)數(shù)的數(shù)組，耗時(shí)：26毫秒
平均時(shí)間復(fù)雜度：O(nlogn)
算法空間復(fù)雜度：O(n)
算法穩(wěn)定性：穩(wěn)定
大頂堆概念：每個(gè)節(jié)點(diǎn)的值都大于或者等于它的左右子節(jié)點(diǎn)的值，所以頂點(diǎn)的數(shù)就是最大值。
思路：
構(gòu)建大頂堆的思路，可以看代碼注釋。
動(dòng)畫(huà)演示：
實(shí)現(xiàn)代碼：
/**
* @author Ye Hongzhi 公眾號(hào)：java技術(shù)愛(ài)好者
* @name HeapSort
* @date 2020-09-08 23:34
**/
public class HeapSort extends BaseSort {
public static void main(String[] args) {
HeapSort sort = new HeapSort();
sort.printNums();
}
@Override
protected void sort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
heapSort(nums);
}
private void heapSort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
//構(gòu)建大根堆
createTopHeap(nums);
int size = nums.length;
while (size > 1) {
//大根堆的交換頭尾值，固定最大值在末尾
swap(nums, 0, size - 1);
//末尾的索引值往左減1
size--;
//重新構(gòu)建大根堆
updateHeap(nums, size);
}
}
private void createTopHeap(int[] nums) {
for (int i = 0; i < nums.length; i++) {
//當(dāng)前插入的索引
int currIndex = i;
//父節(jié)點(diǎn)的索引
int parentIndex = (currIndex - 1) / 2;
//如果當(dāng)前遍歷的值比父節(jié)點(diǎn)大的話，就交換值。然后繼續(xù)往上層比較
while (nums[currIndex] > nums[parentIndex]) {
//交換當(dāng)前遍歷的值與父節(jié)點(diǎn)的值
swap(nums, currIndex, parentIndex);
//把父節(jié)點(diǎn)的索引指向當(dāng)前遍歷的索引
currIndex = parentIndex;
//往上計(jì)算父節(jié)點(diǎn)索引
parentIndex = (currIndex - 1) / 2;
}
}
}
private void updateHeap(int[] nums, int size) {
int index = 0;
//左節(jié)點(diǎn)索引
int left = 2 * index + 1;
//右節(jié)點(diǎn)索引
int right = 2 * index + 2;
while (left < size) {
//最大值的索引
int largestIndex;
//如果右節(jié)點(diǎn)大于左節(jié)點(diǎn)，則最大值索引指向右子節(jié)點(diǎn)索引
if (right < size && nums[left] < nums[right]) {
largestIndex = right;
} else {
largestIndex = left;
}
//如果父節(jié)點(diǎn)大于最大值，則把父節(jié)點(diǎn)索引指向最大值索引
if (nums[index] > nums[largestIndex]) {
largestIndex = index;
}
//如果父節(jié)點(diǎn)索引指向最大值索引，證明已經(jīng)是大根堆，退出循環(huán)
if (largestIndex == index) {
break;
}
//如果不是大根堆，則交換父節(jié)點(diǎn)的值
swap(nums, largestIndex, index);
//把最大值的索引變成父節(jié)點(diǎn)索引
index = largestIndex;
//重新計(jì)算左節(jié)點(diǎn)索引
left = 2 * index + 1;
//重新計(jì)算右節(jié)點(diǎn)索引
right = 2 * index + 2;
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
//10萬(wàn)個(gè)數(shù)的數(shù)組，耗時(shí)：38毫秒
平均時(shí)間復(fù)雜度：O(nlogn)
算法空間復(fù)雜度：O(1)
算法穩(wěn)定性：不穩(wěn)定
思路：
對(duì)于數(shù)組中的元素分布均勻的情況，排序效率較高。相反的，如果分布不均勻，則會(huì)導(dǎo)致大部分的數(shù)落入到同一個(gè)桶中，使效率降低。
動(dòng)畫(huà)演示(來(lái)源于五分鐘學(xué)算法，侵刪)：
實(shí)現(xiàn)代碼：
/**
* @author Ye Hongzhi 公眾號(hào)：java技術(shù)愛(ài)好者
* @name BucketSort
* @date 2020-09-08 23:37
**/
public class BucketSort extends BaseSort {
public static void main(String[] args) {
BucketSort sort = new BucketSort();
sort.printNums();
}
@Override
protected void sort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
bucketSort(nums);
}
public void bucketSort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
//找出最大值，最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}
int length = nums.length;
//桶的數(shù)量
int bucketCount = (max - min) / length + 1;
int[][] bucketArrays = new int[bucketCount][];
//遍歷數(shù)組，放入桶內(nèi)
for (int i = 0; i < length; i++) {
//找到桶的下標(biāo)
int index = (nums[i] - min) / length;
//添加到指定下標(biāo)的桶里，并且使用插入排序排序
bucketArrays[index] = insertSortArrays(bucketArrays[index], nums[i]);
}
int k = 0;
//合并全部桶的
for (int[] bucketArray : bucketArrays) {
if (bucketArray == null || bucketArray.length == 0) {
continue;
}
for (int i : bucketArray) {
//把值放回到nums數(shù)組中
nums[k++] = i;
}
}
}
//每個(gè)桶使用插入排序進(jìn)行排序
private int[] insertSortArrays(int[] arr, int num) {
if (arr == null || arr.length == 0) {
return new int[]{num};
}
//創(chuàng)建一個(gè)temp數(shù)組，長(zhǎng)度是arr數(shù)組的長(zhǎng)度+1
int[] temp = new int[arr.length + 1];
//把傳進(jìn)來(lái)的arr數(shù)組，復(fù)制到temp數(shù)組
for (int i = 0; i < arr.length; i++) {
temp[i] = arr[i];
}
//找到一個(gè)位置，插入，形成新的有序的數(shù)組
int i;
for (i = temp.length - 2; i >= 0 && temp[i] > num; i--) {
temp[i + 1] = temp[i];
}
//插入需要添加的值
temp[i + 1] = num;
//返回
return temp;
}
}
//10萬(wàn)個(gè)數(shù)的數(shù)組，耗時(shí)：8750毫秒
平均時(shí)間復(fù)雜度：O(M+N)
算法空間復(fù)雜度：O(M+N)
算法穩(wěn)定性：穩(wěn)定(取決于桶內(nèi)的排序算法，這里使用的是插入排序所以是穩(wěn)定的)。
動(dòng)畫(huà)演示來(lái)源于算法學(xué)習(xí)網(wǎng)站：https://visualgo.net
講完這些排序算法后，可能有人會(huì)問(wèn)學(xué)這些排序算法有什么用呢，難道就為了應(yīng)付筆試面試？平時(shí)開(kāi)發(fā)也沒(méi)用得上這些。
我覺(jué)得我們應(yīng)該換個(gè)角度來(lái)看，比如高中時(shí)我們學(xué)物理，化學(xué)，數(shù)學(xué)，那么多公式定理，現(xiàn)在也沒(méi)怎么用得上，但是高中課本為什么要教這些呢？
我的理解是：第一，普及一些常識(shí)性的問(wèn)題。第二，鍛煉思維，提高解決問(wèn)題的能力。第三，為了區(qū)分人才。
回到學(xué)排序算法有什么用的問(wèn)題上，實(shí)際上也一樣。這些最基本的排序算法就是一些常識(shí)性的問(wèn)題，作為開(kāi)發(fā)者應(yīng)該了解掌握。同時(shí)也鍛煉了編程思維，其中包含有雙指針，分治，遞歸等等的思想。最后在面試中體現(xiàn)出來(lái)的就是人才的劃分，懂得這些基本的排序算法當(dāng)然要比不懂的人要更有競(jìng)爭(zhēng)力。
關(guān)于“java中常見(jiàn)的排序算法有哪些”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼