對于排序算法，是我們在數(shù)據(jù)結(jié)構(gòu)階段，必須要牢牢掌握的一門知識體系，但是，對于排序算法，里面涉及到的思路，代碼……各種時間復(fù)雜度等，都需要我們，記在腦袋瓜里面！！盡量一丟丟不要出現(xiàn)差錯！面試所必備的精彩提問！！

言歸正傳：對于排序，我們首先需要知道的是：排序的概念！！

排序的概念！

所謂的排序，，就是使一串記錄，按照其中的某個或者某些關(guān)鍵字的大小，遞增遞減的排序起來的操作！！

穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍然在r[j]之前，這種排序算法是穩(wěn)定的，否則是不穩(wěn)定的！！

就比如：9??5??2??7??3??6??4??5??8??0?這些數(shù)據(jù)而言！

內(nèi)部排序：數(shù)據(jù)元素部分放在內(nèi)存的排序

外部排序：數(shù)據(jù)元素不能同時放在內(nèi)存中，根據(jù)排序過程的要求不同，在內(nèi)存與外存之間移動數(shù)據(jù)的排序（要排序的數(shù)據(jù)，在內(nèi)存中放不下！！）

下面筆者就以七種常見的排序算法為列，來帶大家走進排序！！（直接插入排序，希爾排序，選擇排序，堆排序，冒泡排序，快速排序，歸并排序）

1.插入排序：

插入排序：把待排序的記錄按照其關(guān)鍵碼值的大小，逐個插入到一個已經(jīng)排序好的有序序列中，直到所有的記錄插完為止，從而得到一個新的有序序列（撲克牌）

下面請看筆者的代碼：

    public static void insertSort(int[] arr){//對傳入的數(shù)組進行排序for (int i = 1; i<arr.length; i++){for (int j = i-1; j>=0; j--){if(arr[j]>arr[j+1]){//穩(wěn)定的int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}elsebreak;}}System.out.println(Arrays.toString(arr));}public static void main(String[] args) {int[] array={12,56,32,67,10,19,4};insertSort(array);}

2.希爾排序

希爾排序的思想：先選定一個整數(shù)，把待排序文件中的所有記錄分成多個組，所有距離為一樣的放在同一個組內(nèi)，并對每一組的記錄進行插入排序，取重復(fù)上述分組和排序的工作，當(dāng)達(dá)到=1時，所有記錄在統(tǒng)一組內(nèi)排序好（先分組，5組，3組，最后為1組）

假設(shè)初始的數(shù)據(jù)為：?9??1??2??5??7??4??8??6??3??5??

那么，我們有著一下?的簡單排序過程：

經(jīng)過上述的過程，我們可以看出：組數(shù)越多，每組進行排序的數(shù)據(jù)越少！（兩兩交換（使用插入排序）越有序越快），組數(shù)越少，每組數(shù)據(jù)越多（數(shù)據(jù)在慢慢變得有序）

那么，我們對于希爾排序，有著一下的幾點總結(jié)：

1. 希爾排序是對直接插入排序算法的優(yōu)化！

2. 當(dāng)gap>1時，都是預(yù)排序，目的是讓數(shù)組接近有序，當(dāng)gap=1時，數(shù)組已經(jīng)接近有序了，這樣就會很快，這樣整體而言，可以達(dá)到優(yōu)化的效果，我們實現(xiàn)后可以進行性能測試的對比！

3. 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，因此在好些書中，給出的希爾排序的時間復(fù)雜度不固定！

有了上述的思考，我們接下來就該實現(xiàn)一下代碼了：

    public static  void shellSort(int[] array){int gap=array.length;//分組while (gap>1){shell(array,gap);gap=gap/2;}//整體進行插入排序，此時gap=1shell(array,1);}//插入排序public static void shell(int[] array,int gap){for (int i = 0; i <array.length; i++) {int tmp=array[i];int j=i-gap;for(;j>=0;j=j-gap){if (array[j]>tmp){array[j+gap]=array[j];}else {break;}}array[j+gap]=tmp;}}public static void main(String[] args) {int[] array={12,56,32,67,10,19,4};shellSort(array);System.out.println(Arrays.toString(array));}

3.選擇排序

在了解選擇排序之前，我們需要知道的是：

選擇排序的思想:每一次從待排序的數(shù)據(jù)元素中選出最小（最大）的一個元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完，直接選擇排序！

第一次從R[0]到R[n-1]中選出最小值，與R[0]進行交換，第二次從R[1]到R[n-1]中選出最小值與R[1]交換……，以此類推，從而得到從小到大的有序排序

經(jīng)過上面的簡單分析，我們可以得出下列的有效代碼：

   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;//minIndex保存最小數(shù)據(jù)的下標(biāo)值！}}swap(array, i, minIndex);}}private static void swap(int[] array,int i,int j){int tmp=array[i];array[i]=array[j];array[j]=tmp;}public static void main(String[] args) {int[] array={12,56,32,67,10,4};selectSort(array);System.out.println(Arrays.toString(array));}

4.堆排序

對于堆排序，是指利用堆積樹（堆），這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是一種選擇排序，通過堆來進行選擇數(shù)據(jù)

需要注意的是：排升序建大堆，排降序建小堆！！

那么，根據(jù)筆者之前的堆排序的環(huán)節(jié)：https://blog.csdn.net/weixin_64308540/article/details/129217324?spm=1001.2014.3001.5502我們可以有著一下的簡單代碼：

   public static void heapSort(int[] array){createBigHeap(array);//創(chuàng)建一個大根堆int end=array.length-1;while (end>0){//等于0的時候就不換了swap(array,0,end);//交換shiftDown(array,0,end);//向下調(diào)整end--;}}private static void createBigHeap(int[] array){//建立大根堆從最后一顆子樹開始for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {shiftDown(array,parent,array.length);//array,length是指結(jié)束位置}}//向下調(diào)整private static void shiftDown(int[] array,int parent,int len){int child=2*parent+1;while (child<len){//至少有左孩子if (child+1<len && array[child]<array[child+1]){//有右孩子//此時child是左孩子最大值的下標(biāo)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 j){int tmp=array[i];array[i]=array[j];array[j]=tmp;}public static void main(String[] args) {int[] array={12,56,32,67,10,4};heapSort(array);System.out.println(Arrays.toString(array));}

5.交換排序

對于交換排序，我們在之前就已經(jīng)有過接觸，其實就是最簡單的冒泡排序

交換排序的基本思想：所謂交換就是根據(jù)序列中的兩個記錄鍵值的比較結(jié)果，交換這兩個記錄在序列中的位置！

交換排序的特點：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動

下面筆者就以冒泡排序來進行書寫代碼：

方法1：

public static void bubblesort2(int[] array ) {//趟數(shù)for (int i = 0; i < array.length-1; i++) {//每趟執(zhí)行的次數(shù)boolean flg=false;for(int j=0;j<array.length-1-i;j++) {if(array[j]>array[j+1]) {int tmp=array[j+1];array[j+1]=array[j];array[j]=tmp;}flg=true;}if(flg==false) {return ;}}}public static void main(String[] args) {int[] array={1,29,10,36,5,21,46,3,6};bubblesort2(array);System.out.println(Arrays.toString(array));}

方法2：

    public static void bubbleSort2(int[] array){for (int i = 0; i < array.length; i++) {for (int j = 0; j < array.length-1-i; j++) {if (array[j]>array[j+1])swap(array,j,j+1);}}}private static void swap(int[] array,int i,int j){int tmp=array[i];array[i]=array[j];array[j]=tmp;}public static void main(String[] args) {int[] array={12,56,32,67,10,19,4};bubbleSort2(array);System.out.println(Arrays.toString(array));}

在上述代碼中，方法1是對方法2的簡單優(yōu)化！！

在方法1中，我們通過一個：boolean flg=false;來優(yōu)化了代碼！！原因在于，在進行冒泡排序的時候，可能對于一串?dāng)?shù)據(jù)，排到一半就有序了，那么，在沒有優(yōu)化之前，肯定還得一個一個嘗試去遍歷，但是，在優(yōu)化以后，可以節(jié)約時間！！

6.快速排序

快速排序的思想：任取待排序元素序列中的某元素（一般是第一個元素），作為基準(zhǔn)值，按照該排序碼，將待排序的集合分為兩個子序列，左子序中的所有元素均小于基準(zhǔn)值，右子序中的所有元素均大于基準(zhǔn)值，然后最左右子序列都重復(fù)該過程，直到所有的元素都排序在相應(yīng)的位置為止！！

對于上述的簡單思想，我們有著挖坑法！Hoare法！

下面我們先講解一下挖坑法：

先將第一個數(shù)據(jù)存放在一個臨時變量key中，形成一個坑位！

1. 設(shè)置兩個變量i，j，排序開始的時候，i=0，j=N-1！

2. 以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]！

3. 從j開始向前搜素，即由后開始向前搜素（j--),找到第一個小于key的值A(chǔ)[j],將A[j]與A[i]的值進行交換！

4. 從i開始向后搜素，即由前開始向后搜素（i++），找到第一個大于key的值A(chǔ)[i]，將A[i]與A[j]的值交換！

5. 重復(fù)步驟3，4，直到i==j為止！

對于上述的思路，我們可以用遞歸來實現(xiàn)！！

package zyh.example.demo.algorithm.kuaisupaixu;import java.util.Arrays;/**
* @ClassName KuaiPai13
* @Author zhangyonghui
* @Description
* @Date 2022/3/29 11:26
* @Version 1.0
**/
public class KuaiPai13 {public static void main(String[] args) {int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};quickSort(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}/*** 快速排序--挖坑法* @param arr 數(shù)組* @param startIndex 左邊界索引* @param endIndex 右邊界索引*/public static void quickSort(int[] arr, int startIndex, int endIndex) {// 遞歸結(jié)束條件：startIndex大等于endIndex的時候if (startIndex >= endIndex) {return;}// 得到基準(zhǔn)元素位置int pivotIndex = partition(arr, startIndex, endIndex);// 用分治法遞歸數(shù)列的兩部分quickSort(arr, startIndex, pivotIndex - 1);quickSort(arr, pivotIndex + 1, endIndex);}/*** 具體每一輪的快速排序：* @param arr 數(shù)組* @param startIndex 左邊界索引* @param endIndex 右邊界索引* @return 返回基準(zhǔn)值的位置，此時基準(zhǔn)值左邊的元素都小于基準(zhǔn)值，基準(zhǔn)值右邊的元素都大于基準(zhǔn)值*/private static int partition(int[] arr, int startIndex, int endIndex) {// 取第一個位置的元素作為基準(zhǔn)元素int pivot = arr[startIndex];// 初始化坑的位置，初始等于pivot基準(zhǔn)值的位置int kengIndex = startIndex;//初始化左右游標(biāo)/指針int leftYb = startIndex;int rightYb = endIndex;//大循環(huán)在左右指針重合時結(jié)束while ( leftYb<rightYb ) {//right指針從右向左進行比較// leftYb<rightYb ，左游標(biāo)永遠(yuǎn)小于右游標(biāo)，是遍歷元素并發(fā)生元素變動的前提：while ( leftYb<rightYb) {// 先遍歷右邊，//  如果元素大于基準(zhǔn)值--右游標(biāo)左移：if (arr[rightYb] >= pivot) {rightYb--;}else{ //如果右邊的當(dāng)前元素小于基準(zhǔn)值了，那么將該元素填入坑中，該元素本來的位置成為新的坑；arr[kengIndex] = arr[rightYb];kengIndex = rightYb;leftYb++;break;}}//再遍歷左邊，// leftYb<rightYb ，左游標(biāo)永遠(yuǎn)小于右游標(biāo)，是遍歷元素并發(fā)生元素變動的前提：while (leftYb<rightYb) {//如果元素小于基準(zhǔn)值--左游標(biāo)右移，if (arr[leftYb] <= pivot) {leftYb++;}else{  //如果左邊的當(dāng)前元素大于基準(zhǔn)值了，那么將該元素填入坑中，該元素本來的位置成為新的坑；arr[kengIndex] = arr[leftYb];kengIndex = leftYb;rightYb--;break;}}}//跳出了大循環(huán)，說明此時此刻左右游標(biāo)是重合的，這時將基準(zhǔn)值放在重合位置(最后一個坑)，// 此時，基準(zhǔn)值左邊的元素都小于基準(zhǔn)值，基準(zhǔn)值右邊的元素都大于基準(zhǔn)值，這一輪交換宣告結(jié)束；arr[kengIndex] = pivot;return kengIndex;}}

接下來進入Hoare法！

right找到比基準(zhǔn)小的停下來，left找到比基準(zhǔn)大的停下來，進行比較，循環(huán)往復(fù)，最后當(dāng)right==left的時候，將此時對應(yīng)的值與基準(zhǔn)進行比較！

請看筆者代碼：

public class Main {static int[] a= {5, 3, 1, 9, 8, 2, 4, 7};public static void main(String[] args) {fastsort(0, a.length-1);for (int i = 0; i < a.length; i++) {System.out.print(a[i] + " ");}}private static int Hoare(int l, int r) {int p = a[l];int i = l-1;int j = r+1 ;while (true) {do {j--;} while (a[j] > p);do {i++;} while (a[i] < p);if (i < j) {int temp = a[i];a[i] = a[j];a[j] = temp;} elsereturn j;}}private static void fastsort(int l, int r) {if (l < r) {int s = Hoare(l, r);fastsort(l, s);fastsort(s+1, r);}}
}

7.歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法的一個非常典型的應(yīng)用，將已有序的子序列合并，得到完全有序的序列，即，先使每個子序列有序，再使子序列斷間有序！

主要的思路及其過程，如下圖所示：

那么，接下來請看代碼吧！！（遞歸實現(xiàn)）

    //遞歸實現(xiàn)
public static void mergeSort(int[] array){mergeSortFunc(array,0, array.length);}private static void mergeSortFunc(int[] array,int left,int right){if (left>=right){return;}//分解int mid=(left+right)/2;mergeSortFunc(array,left,mid);mergeSortFunc(array,mid+1,right);merge(array,left,right,mid);//合并}private static void merge(int[] array,int start,int end,int mid){int s1=start;int s2=mid+1;int[] tmp=new int[end-start+1];//申請一個數(shù)組int k=0;//tmp數(shù)組下標(biāo)while (s1<=mid && s2<=end){if (array[s1]<= array[s2]){tmp[k++]=array[s1++];}else {tmp[k++]=array[s2++];}}while (s1<=mid){tmp[k++]=array[s1++];}while (s2<=end){tmp[k++]=array[s2++];}for (int i = 0; i < tmp.length; i++) {array[i+start]=tmp[i];}}

感興趣的老鐵，可以看一下非遞歸實現(xiàn)的：

//非遞歸public static void mergeSort2(int[] array){int gap=1;while (gap<array.length){for (int i = 0; i < array.length; i++) {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,right,mid);}gap=gap*2;}}

七大排序算法大致就到此結(jié)束了！！拜拜！