網(wǎng)站建設(shè)能用手機制作嗎網(wǎng)站鏈接分析工具
對于排序算法,是我們在數(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é):
希爾排序是對直接插入排序算法的優(yōu)化!
當(dāng)gap>1時,都是預(yù)排序,目的是讓數(shù)組接近有序,當(dāng)gap=1時,數(shù)組已經(jīng)接近有序了,這樣就會很快,這樣整體而言,可以達(dá)到優(yōu)化的效果,我們實現(xiàn)后可以進行性能測試的對比!
希爾排序的時間復(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中,形成一個坑位!
設(shè)置兩個變量i,j,排序開始的時候,i=0,j=N-1!
以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù),賦值給key,即key=A[0]!
從j開始向前搜素,即由后開始向前搜素(j--),找到第一個小于key的值A(chǔ)[j],將A[j]與A[i]的值進行交換!
從i開始向后搜素,即由前開始向后搜素(i++),找到第一個大于key的值A(chǔ)[i],將A[i]與A[j]的值交換!
重復(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é)束了!!拜拜!