柚子快報(bào)激活碼778899分享：八大排序算法（面試被問(wèn)到）

http://yzkb.51969.com/

1.八大排序算法都是什么？

八大排序算法有：插入排序、冒泡排序、歸并排序、選擇排序、快速排序、希爾排序、堆排序、基數(shù)排序（通常不提）。此外，還可以直接調(diào)用Arrays.sort()進(jìn)行排序。

2.八大排序算法時(shí)間復(fù)雜度和穩(wěn)定性？

這里有一個(gè)口訣記法：

插（插入）帽（冒泡）龜（歸并），他很穩(wěn)（穩(wěn)定）；

插冒歸喜歡選（選擇）插（插入）帽（冒泡），插完他就方了O(n^2)；

快（快速）歸（歸并）隊(duì)（堆），n老O(logn)；

基（基數(shù)）你太穩(wěn)（穩(wěn)定）；

3.算法講解？

? (1) 冒泡排序

過(guò)程：

①?gòu)臄?shù)列的開頭開始，在這趟遍歷中對(duì)沒(méi)有進(jìn)行比較的一對(duì)兩兩比較，直到數(shù)列的結(jié)尾；

②如果第一個(gè)元素比第二個(gè)元素大，則交換它們的位置，這樣較大的元素就逐漸“浮”到數(shù)列的末尾；

③然后，算法再次從數(shù)列的開始執(zhí)行相同的操作，但是排好序的元素（即最大的元素）不再參與比較；這個(gè)過(guò)程一直持續(xù)到整個(gè)數(shù)列都排好序?yàn)橹埂?/p>

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

public class BubbleSort {

11 public static void main(String[] args) {

12 int[] arr={5,4,2,1};

13 bubblesort(arr);

14 System.out.println("Sorted array:"+ Arrays.toString(arr));

15 for(int i=0;i

16 System.out.print(arr[i]+" ");

17 }

18 }

19

20 private static void bubblesort(int[] arr) {

21 int n=arr.length;

22 for(int i=0;i

23 for(int j=0;j

24 if(arr[j]>arr[j+1]){

25 int temp=arr[j];

26 arr[j]=arr[j+1];

27 arr[j+1]=temp;

28 }

29 }

30 }

31 }

34 }

優(yōu)點(diǎn)：

穩(wěn)定性——在排序過(guò)程中，相同元素的相對(duì)順序保持不變。

缺點(diǎn)：

不適合大規(guī)模數(shù)據(jù)——對(duì)于大規(guī)模亂序序列的排序效率較低，時(shí)間復(fù)雜度較高。

（2）插入排序

過(guò)程：

?①將第一個(gè)元素視為已排序序列。

②從第二個(gè)元素開始，將其與已排序序列中的元素逐個(gè)比較，并插入到正確的位置上。這個(gè)過(guò)程不斷重復(fù)，直到整個(gè)數(shù)組變得有序。

③在實(shí)現(xiàn)上，插入排序使用雙層循環(huán)，外層循環(huán)遍歷數(shù)組中的每個(gè)元素，內(nèi)層循環(huán)則在已排序的部分中查找新元素應(yīng)插入的位置。

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

public class InsertSort {

11 public static void main(String[] args) {

12 int[] arr={23,46,87,11,24,1};

13 System.out.println("Original array:"+ Arrays.toString(arr));

14 insertsort(arr);

15 System.out.println("Sorted array:"+Arrays.toString(arr));

16 for(int i=0;i

17 System.out.print(arr[i]+" ");

18 }

19 }

20 public static void insertsort(int[] arr){

21 //遍歷除第一個(gè)數(shù)之外的所有數(shù)字

22 for(int i=1;i

23 //當(dāng)前數(shù)字比前一個(gè)數(shù)字小

24 if(arr[i]

25 //把當(dāng)前數(shù)字保存起來(lái)，當(dāng)前位置騰開

26 int temp=arr[i];

27 //當(dāng)前數(shù)字和他之前所有數(shù)字進(jìn)行比較

28 int j=0;

29 for(j=i-1;j>=0&&arr[j]>temp;j--){//如果前面的數(shù)字大于temp，右移

30 arr[j+1]=arr[j];

31 }

32 arr[j+1]=temp;//如果前面的數(shù)字小于等于temp，將temp放入

33 }

34 }

35 }

36

37 }

優(yōu)點(diǎn)：

穩(wěn)定性——在排序過(guò)程中，相同元素的相對(duì)順序保持不變。

缺點(diǎn)：

不適合大規(guī)模數(shù)據(jù)——對(duì)于大規(guī)模亂序序列的排序效率較低，時(shí)間復(fù)雜度較高。

（3）歸并排序

過(guò)程：

①分解（Divide）：將數(shù)組遞歸地分成兩半，直到數(shù)組被分解為單個(gè)元素。 ②解決（Conquer）：對(duì)每一對(duì)分解后的子數(shù)組進(jìn)行排序，這一過(guò)程通常通過(guò)歸并排序遞歸地完成。 ③合并（Merge）：將已排序的子數(shù)組合并成一個(gè)完整的、有序的數(shù)組。

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

public class MergeSort {

11 public static void main(String[] args) {

12 int[] arr={12,11,13,43,5,9};

13 System.out.println("Original Array:"+ Arrays.toString(arr));

14 mergesort(arr,0,arr.length-1);

15 System.out.println("Sorted Array:"+Arrays.toString(arr));

16 }

17

18 private static void mergesort(int[] arr,int left,int right) {

19 if(left

20 int mid=(left + right) / 2;

21 mergesort(arr,left,mid);

22 mergesort(arr,mid+1,right);

23 Merge(arr,left,mid,right);

24 }

25

26 }

27

28 private static void Merge(int[] arr, int left, int mid, int right) {

29 int i=left;int j=mid+1;int k=0;

30 int[] temp=new int[right-left+1];

31 while(i<=mid&&j<=right){

32 if(arr[i]

33 temp[k++]=arr[i++];

34 }else{

35 temp[k++]=arr[j++];

36 }

37 }

38 while(i<=mid){

39 temp[k++]=arr[i++];

40 }

41 while(j<=right){

42 temp[k++]=arr[j++];

43 }

44 //按照排好的順序給arr賦值

45 for(int t=0;t

46 arr[t+left]=temp[t];

47 }

48 }

49 }

優(yōu)點(diǎn)：

穩(wěn)定性——在排序過(guò)程中，相同元素的相對(duì)順序保持不變。

缺點(diǎn)：

內(nèi)存占用大——在劃分和合并過(guò)程中，需要額外的內(nèi)存來(lái)存儲(chǔ)列表的兩半和最終排序的列表，

（4）選擇排序

過(guò)程：

①?gòu)拇判虻臄?shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置；

②再?gòu)氖Ｓ嗟奈磁判蛟刂欣^續(xù)尋找最?。ɑ蜃畲螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?；

③重復(fù)操作，直到所有元素均排序完畢。

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

public class SelectSort {

11 public static void main(String[] args) {

12 int[] arr={12,45,72,32,10};

13 System.out.println("Original Array:"+ Arrays.toString(arr));

14 insertsort(arr);

15 System.out.println("Sorted Array:"+Arrays.toString(arr));

16 for(int i=0;i

17 System.out.print(arr[i]+" ");

18 }

19 }

20 public static void insertsort(int[] arr){

21 int n=arr.length;

22 for(int k=0;k

23 int min=k;//設(shè)置第一個(gè)下標(biāo)為最小值

24 for(int i=k+1;i

25 if(arr[i]

26 min=i;//更新最小值對(duì)應(yīng)的下標(biāo)

27 }

28 }

29 int temp=arr[k];//交換，將最小值標(biāo)記到最前面，之后k++，尋找第二個(gè)最小值，循環(huán)

30 arr[k]=arr[min];

31 arr[min]=temp;

32 }

33 }

35 }

優(yōu)點(diǎn)：

可讀性高——簡(jiǎn)單易懂、易于實(shí)現(xiàn)，以及它是原地排序算法，不占用額外的內(nèi)存空間。

缺點(diǎn)：

時(shí)間復(fù)雜度較高——無(wú)論數(shù)據(jù)是否有序，都需要進(jìn)行O(n2)次比較，處理大規(guī)模數(shù)據(jù)集時(shí)效率較低。

不穩(wěn)定——這意味著在排序過(guò)程中相等元素的相對(duì)位置可能發(fā)生變化，導(dǎo)致相同元素的相對(duì)順序不同。

（5）快速排序

過(guò)程：

①選擇基準(zhǔn)元素：從待排序序列中選取一個(gè)元素作為基準(zhǔn)（pivot）。 ②分區(qū)操作：通過(guò)比較其他元素與基準(zhǔn)元素的大小，將序列分為兩部分。所有比基準(zhǔn)元素小的元素放在其左邊，所有比基準(zhǔn)元素大的元素放在其右邊。 ③遞歸排序：對(duì)基準(zhǔn)元素左右兩邊的子序列遞歸執(zhí)行上述步驟，直到子序列的長(zhǎng)度為0或1，此時(shí)子序列已經(jīng)有序。

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

public class QuickSort {

11 //快速排序：

12 //首先在序列中隨機(jī)選擇一個(gè)基準(zhǔn)值（privot)

13 //除了基準(zhǔn)值以外的數(shù)分為：“比基準(zhǔn)值小的數(shù)”、“比基準(zhǔn)值大的數(shù)”，再將其排列成以下形式 【比基準(zhǔn)值小的數(shù)】 基準(zhǔn)值 【比基準(zhǔn)值大的數(shù)】

14 //對(duì)【】中的數(shù)據(jù)進(jìn)行遞歸，同樣使用快速排序

15 public static void main(String[] args) {

16 int[] arr={12,45,67,81,1,2};

17 System.out.println("Original array:"+ Arrays.toString(arr));

18 quicksort(arr,0,arr.length-1);

19 System.out.println("Sorted array:"+Arrays.toString(arr));

20 for(int i=0;i

21 System.out.print(arr[i]+" ");

22 }

23 }

24 public static void quicksort(int[] arr,int left,int right){

25 if(left

26 int partitionIndex=partition(arr,left,right);

27 quicksort(arr,left,partitionIndex-1);

28 quicksort(arr,partitionIndex+1,right);

29 }

30 }

31 public static int partition(int[] arr,int left,int right) {

32 int privot=arr[left];

33 while(left

34 while(left=privot){

35 right--;

36 }

37 arr[left]=arr[right];

38 while(left

39 left++;

40 }

41 arr[right]=arr[left];

42 }

43 //在left==right時(shí)候，將privot放進(jìn)去，此時(shí)privot左邊都是比privot小的，privot右邊都是比privot大的

44 arr[left]=privot;

45 return left;

46 }

47 }

優(yōu)點(diǎn)：

高效率——快速排序的平均時(shí)間復(fù)雜度為O(NlogN)，使其在處理大量數(shù)據(jù)時(shí)表現(xiàn)出色。

數(shù)據(jù)移動(dòng)少——在排序過(guò)程中，快速排序需要移動(dòng)的數(shù)據(jù)量相對(duì)較小。

缺點(diǎn)：

不穩(wěn)定——當(dāng)處理大量重復(fù)元素時(shí)，可能會(huì)導(dǎo)致遞歸深度過(guò)大，甚至棧溢出。

（6）堆排序

過(guò)程：

①最大堆調(diào)整（Max Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)； ②創(chuàng)建最大堆（Build Max Heap）：將堆中的所有數(shù)據(jù)重新排序（按照最大堆調(diào)整）； ③堆排序（HeapSort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)（最大堆順序就會(huì)被打亂），并重復(fù)做最大堆調(diào)整的遞歸運(yùn)算。

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

public class HeapSort {

11 //大頂堆：

12 // 孩子節(jié)點(diǎn)下標(biāo)為i時(shí)，父節(jié)點(diǎn)下標(biāo)：（i-1）/2

13 //父親節(jié)點(diǎn)下標(biāo)為k時(shí)，左孩子下標(biāo)(k*2)+1;右孩子下標(biāo)k*2+2

14 public static void main(String[] args) {

15 //測(cè)試用例

16 int[] arr={12,45,72,32,10};

17 System.out.println("Original Array:"+ Arrays.toString(arr));

18 heapsort(arr);

19 System.out.println("Sorted Array:"+Arrays.toString(arr));

20 for(int k:arr){

21 System.out.print(k+" ");

22 }

23 }

24

25 //堆排序函數(shù)

26 private static void heapsort(int[] arr) {

27 int n=arr.length;

28 //建堆

29 buildMaxHeap(arr,n);

30 for(int i=n-1;i>0;i--){

31 //交換

32 swap(arr,0,i);

33 //維護(hù)最大堆的性質(zhì)

34 heapify(arr,0,i);

35 }

36 //

37 }

38

39 private static void heapify(int[] arr, int x, int n) {

40 int father=x;

41 int left=2*x+1;

42 int right=2*x+2;

43 if(leftarr[father]){

44 father=left;

45 }

46 if(rightarr[father]){

47 father=right;

48 }

49 if(father!=x){

50 swap(arr,x,father);

51 heapify(arr,father,n);//向下調(diào)整維護(hù)大堆性質(zhì)

52 }

53

54 }

55

56 private static void swap(int[] arr, int a, int b) {

57 int temp=arr[a];

58 arr[a]=arr[b];

59 arr[b]=temp;

60 }

61

62 private static void buildMaxHeap(int[] arr, int n) {

63 //尋找最后一個(gè)非葉子節(jié)點(diǎn)

64 for(int i=n/2-1;i>=0;i--){

65 heapify(arr,i,n);

66 }

67 }

68 }

優(yōu)點(diǎn)：

速度快——時(shí)間復(fù)雜度為O(nlogn)，這意味著無(wú)論數(shù)據(jù)規(guī)模多大，堆排序都能在多項(xiàng)式時(shí)間內(nèi)完成。排序空間復(fù)雜度O(1)，這意味著它不需要額外的存儲(chǔ)空間來(lái)保存數(shù)據(jù)，這使得堆排序在空間效率方面表現(xiàn)優(yōu)異；

穩(wěn)定——堆排序是一種穩(wěn)定的排序算法，堆排序適用于多種場(chǎng)景，包括在數(shù)據(jù)頻繁變動(dòng)的情況下，因?yàn)樗梢栽诓恢亟ㄕ麄€(gè)堆的情況下更新堆頂元素。

缺點(diǎn)：

堆維護(hù)問(wèn)題——需要頻繁地重建和維護(hù)堆，這可能會(huì)在數(shù)據(jù)頻繁變動(dòng)的情況下導(dǎo)致效率降低，因?yàn)槊看螖?shù)據(jù)更新都可能需要調(diào)整堆的結(jié)構(gòu)，這增加了額外的計(jì)算負(fù)擔(dān)。

（7）希爾排序

希爾排序是一種改進(jìn)后的插入排序算法，也被稱為縮小增量排序。

過(guò)程：

①選擇一個(gè)小于數(shù)組長(zhǎng)度的增量(gap)，最開始gap=n/2，然后將數(shù)組分為多個(gè)子序列，每個(gè)子序列的元素間隔為這個(gè)增量值，對(duì)每個(gè)子序列分別進(jìn)行直接插入排序。 ②逐漸減小增量值（減半），再次進(jìn)行子序列的劃分和排序。

③直到增量減至1，此時(shí)整個(gè)數(shù)組被當(dāng)作一個(gè)序列進(jìn)行插入排序。

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

public class ShellSort {

11 public static void main(String[] args) {

12 int[] arr=new int[]{12,23,11,5,65,88};

13 System.out.println("Original Array:"+ Arrays.toString(arr));

14 shellsort(arr);

15 System.out.println("Sorted Array:"+Arrays.toString(arr));

16 for(int i=0;i

17 System.out.print(arr[i]+" ");

18 }

19 }

20

21 private static void shellsort(int[] arr) {//時(shí)間復(fù)雜度n^1.3

22 int n=arr.length;

23 //初始化間隔為數(shù)組長(zhǎng)度的一半

24 int gap=n/2;

25 while(gap>0){

26 //對(duì)每個(gè)間隔進(jìn)行直接插入排序

27 for(int i=gap;i

28 int temp=arr[i];

29 int j=0;

30 //對(duì)間隔為 gap 的元素進(jìn)行插入排序

31 for(j=i;j>=gap&&temp

32 arr[j]=arr[j-gap];

33 }

34 arr[j]=temp;

35 }

36 // 縮小間隔

37 gap=gap/2;

38 }

39 }

40 }

優(yōu)點(diǎn)：

速度快——由于開始時(shí)增量的取值較大，每個(gè)子序列中的元素較少，所以排序速度快；隨著增量逐漸減小，雖然子序列中的元素個(gè)數(shù)增多，但是由于前面工作的基礎(chǔ)，大多數(shù)元素已經(jīng)基本有序，因此排序速度仍然較快。希爾排序的時(shí)間復(fù)雜度為O(n^1.3)至O(n^2)。

缺點(diǎn)：

不穩(wěn)定——取決于增量序列的選擇，它是一種非穩(wěn)定排序算法，這意味著在排序過(guò)程中，相同的元素可能會(huì)移動(dòng)位置，導(dǎo)致最終順序與原始順序不同。

柚子快報(bào)激活碼778899分享：八大排序算法（面試被問(wèn)到）

http://yzkb.51969.com/

文章來(lái)源