前言

算法和數(shù)據(jù)結(jié)構(gòu)是一個(gè)程序員的內(nèi)功，所以經(jīng)常在一些筆試中都會要求手寫一些簡單的排序算法，以此考驗(yàn)面試者的編程水平。下面我就簡單介紹八種常見的排序算法，一起學(xué)習(xí)一下。

一、冒泡排序

思路：

• 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；
• 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素就是最大的數(shù)；
• 排除最大的數(shù)，接著下一輪繼續(xù)相同的操作，確定第二大的數(shù)...
• 重復(fù)步驟1-3，直到排序完成。

動畫演示：

實(shí)現(xiàn)代碼：

/*** @author Ye Hongzhi 公眾號：java技術(shù)愛好者* @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();}@Overrideprotected 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萬個(gè)數(shù)的數(shù)組，耗時(shí)：21554毫秒

平均時(shí)間復(fù)雜度：O(n2)

空間復(fù)雜度：O(1)

算法穩(wěn)定性：穩(wěn)定

二、插入排序

思路：

從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序；

取出下一個(gè)元素，在前面已排序的元素序列中，從后向前掃描；

如果該元素（已排序）大于新元素，將該元素移到下一位置；

重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；

將新元素插入到該位置后；

重復(fù)步驟2~5。

動畫演示：

實(shí)現(xiàn)代碼：

/*** @author Ye Hongzhi 公眾號：java技術(shù)愛好者* @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();}@Overrideprotected 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ù)字往后移動nums[preIndex + 1] = nums[preIndex];//需要插入的數(shù)的下標(biāo)往前移動preIndex--;}//插入到這個(gè)數(shù)的后面nums[preIndex + 1] = curr;}} } //10萬個(gè)數(shù)的數(shù)組，耗時(shí)：2051毫秒

平均時(shí)間復(fù)雜度：O(n2)

空間復(fù)雜度：O(1)

算法穩(wěn)定性：穩(wěn)定

三、選擇排序

思路：

第一輪，找到最小的元素，和數(shù)組第一個(gè)數(shù)交換位置。

第二輪，找到第二小的元素，和數(shù)組第二個(gè)數(shù)交換位置...

直到最后一個(gè)元素，排序完成。

動畫演示：

實(shí)現(xiàn)代碼：

/*** @author Ye Hongzhi 公眾號：java技術(shù)愛好者* @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();}@Overrideprotected 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萬個(gè)數(shù)的數(shù)組，耗時(shí)：8492毫秒

算法復(fù)雜度：O(n2)
算法空間復(fù)雜度：O(1)
算法穩(wěn)定性：不穩(wěn)定

四、希爾排序

思路：

把數(shù)組分割成若干(h)個(gè)小組(一般數(shù)組長度length/2)，然后對每一個(gè)小組分別進(jìn)行插入排序。每一輪分割的數(shù)組的個(gè)數(shù)逐步縮小，h/2->h/4->h/8，并且進(jìn)行排序，保證有序。當(dāng)h=1時(shí)，則數(shù)組排序完成。

動畫演示：

實(shí)現(xiàn)代碼：

/*** @author Ye Hongzhi 公眾號：java技術(shù)愛好者* @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();}@Overrideprotected void sort(int[] nums) {if (nums == null || nums.length < 2) {return;}int length = nums.length;int temp;//步長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萬個(gè)數(shù)的數(shù)組，耗時(shí)：261毫秒

算法復(fù)雜度：O(nlog2n)
算法空間復(fù)雜度：O(1)
算法穩(wěn)定性：穩(wěn)定

五、快速排序

快排，面試最喜歡問的排序算法。這是運(yùn)用分治法的一種排序算法。

思路：

從數(shù)組中選一個(gè)數(shù)做為基準(zhǔn)值，一般選第一個(gè)數(shù)，或者最后一個(gè)數(shù)。

采用雙指針(頭尾兩端)遍歷，從左往右找到比基準(zhǔn)值大的第一個(gè)數(shù)，從右往左找到比基準(zhǔn)值小的第一個(gè)數(shù)，交換兩數(shù)位置，直到頭尾指針相等或頭指針大于尾指針，把基準(zhǔn)值與頭指針的數(shù)交換。這樣一輪之后，左邊的數(shù)就比基準(zhǔn)值小，右邊的數(shù)就比基準(zhǔn)值大。

對左邊的數(shù)列，重復(fù)上面1，2步驟。對右邊重復(fù)1，2步驟。

左右兩邊數(shù)列遞歸結(jié)束后，排序完成。

動畫演示：

實(shí)現(xiàn)代碼：

/*** @author Ye Hongzhi 公眾號：java技術(shù)愛好者* @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();}@Overrideprotected 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萬個(gè)數(shù)的數(shù)組，耗時(shí)：50毫秒

算法復(fù)雜度：O(nlogn)
算法空間復(fù)雜度：O(1)
算法穩(wěn)定性：不穩(wěn)定

六、歸并排序

歸并排序是采用分治法的典型應(yīng)用，而且是一種穩(wěn)定的排序方式，不過需要使用到額外的空間。

思路：

把數(shù)組不斷劃分成子序列，劃成長度只有2或者1的子序列。

然后利用臨時(shí)數(shù)組，對子序列進(jìn)行排序，合并，再把臨時(shí)數(shù)組的值復(fù)制回原數(shù)組。

反復(fù)操作1~2步驟，直到排序完成。

歸并排序的優(yōu)點(diǎn)在于最好情況和最壞的情況的時(shí)間復(fù)雜度都是O(nlogn)，所以是比較穩(wěn)定的排序方式。

動畫演示：

實(shí)現(xiàn)代碼：

/*** @author Ye Hongzhi 公眾號：java技術(shù)愛好者* @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();}@Overrideprotected 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萬個(gè)數(shù)的數(shù)組，耗時(shí)：26毫秒

算法復(fù)雜度：O(nlogn)
算法空間復(fù)雜度：O(n)
算法穩(wěn)定性：穩(wěn)定

七、堆排序

大頂堆概念：每個(gè)節(jié)點(diǎn)的值都大于或者等于它的左右子節(jié)點(diǎn)的值，所以頂點(diǎn)的數(shù)就是最大值。

思路：

對原數(shù)組構(gòu)建成大頂堆。

交換頭尾值，尾指針?biāo)饕郎p一，固定最大值。

重新構(gòu)建大頂堆。

重復(fù)步驟2~3，直到最后一個(gè)元素，排序完成。

構(gòu)建大頂堆的思路，可以看代碼注釋。

動畫演示：

實(shí)現(xiàn)代碼：

/*** @author Ye Hongzhi 公眾號：java技術(shù)愛好者* @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();}@Overrideprotected 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);//末尾的索引值往左減1size--;//重新構(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萬個(gè)數(shù)的數(shù)組，耗時(shí)：38毫秒

算法復(fù)雜度：O(nlogn)
算法空間復(fù)雜度：O(1)
算法穩(wěn)定性：不穩(wěn)定

八、桶排序

思路：

找出最大值，最小值。

根據(jù)數(shù)組的長度，創(chuàng)建出若干個(gè)桶。

遍歷數(shù)組的元素，根據(jù)元素的值放入到對應(yīng)的桶中。

對每個(gè)桶的元素進(jìn)行排序(可使用快排，插入排序等)。

按順序合并每個(gè)桶的元素，排序完成。

對于數(shù)組中的元素分布均勻的情況，排序效率較高。相反的，如果分布不均勻，則會導(dǎo)致大部分的數(shù)落入到同一個(gè)桶中，使效率降低。

動畫演示(來源于五分鐘學(xué)算法，侵刪)：

實(shí)現(xiàn)代碼：

/*** @author Ye Hongzhi 公眾號：java技術(shù)愛好者* @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();}@Overrideprotected 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ù)組，長度是arr數(shù)組的長度+1int[] temp = new int[arr.length + 1];//把傳進(jìn)來的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萬個(gè)數(shù)的數(shù)組，耗時(shí)：8750毫秒

算法復(fù)雜度：O(M+N)

算法空間復(fù)雜度：O(M+N)

算法穩(wěn)定性：穩(wěn)定(取決于桶內(nèi)的排序算法，這里使用的是插入排序所以是穩(wěn)定的)。

總結(jié)

動畫演示來源于算法學(xué)習(xí)網(wǎng)站：https://visualgo.net

講完這些排序算法后，可能有人會問學(xué)這些排序算法有什么用呢，難道就為了應(yīng)付筆試面試？平時(shí)開發(fā)也沒用得上這些。

我覺得我們應(yīng)該換個(gè)角度來看，比如高中時(shí)我們學(xué)物理，化學(xué)，數(shù)學(xué)，那么多公式定理，現(xiàn)在也沒怎么用得上，但是高中課本為什么要教這些呢？

我的理解是：第一，普及一些常識性的問題。第二，鍛煉思維，提高解決問題的能力。第三，為了區(qū)分人才。

回到學(xué)排序算法有什么用的問題上，實(shí)際上也一樣。這些最基本的排序算法就是一些常識性的問題，作為開發(fā)者應(yīng)該了解掌握。同時(shí)也鍛煉了編程思維，其中包含有雙指針，分治，遞歸等等的思想。最后在面試中體現(xiàn)出來的就是人才的劃分，懂得這些基本的排序算法當(dāng)然要比不懂的人要更有競爭力。

?

?

原文鏈接
本文為阿里云原創(chuàng)內(nèi)容，未經(jīng)允許不得轉(zhuǎn)載。

總結(jié)

以上是生活随笔為你收集整理的八种经典排序算法总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。