• 十大排序算法汇总

    目录

    1、冒泡排序

    2、选择排序

    3、插入排序

    4、希尔排序

    5、归并排序

    6、快速排序

    7、堆排序

    8、计数排序

    9、桶排序

    10、基数排序

    1、冒泡排序

    思想：每次左右两两比较，把最大或最小元素放到最后，直到整体有序

    时间复杂度：O(n²)

    稳定性：稳定

    1. package com.xch2.DiGui;
    2.  
    3. import java.util.*;
    4.  
    5. public class Main7_1 {
    6.  
    7. 	//冒泡排序
    8. 	//小到大排序
    9. 	public static void f8(int[] arr) {
    10. 		boolean flag=true;
    11. 		int mid;
    12. 		for (int i = arr.length-1; i > 0; i--) {
    13. 			for (int j = 0; j < i; j++) {
    14. 				if(arr[j]>arr[j+1]) {
    15. 					mid=arr[j];
    16. 					arr[j]=arr[j+1];
    17. 					arr[j+1]=mid;
    18. 					flag=false;
    19. 				}
    20. 			}
    21. 			//优化，提前整体有序
    22. 			if(flag) {
    23. 				return;
    24. 			}
    25. 			flag=true;
    26. 		}
    27. 	}
    28.  
    29. 	//大到小排序
    30. 	public static void f9(int[] arr) {
    31. 		boolean flag=true;
    32. 		int mid;
    33. 		for (int i = arr.length-1; i > 0; i--) {
    34. 			for (int j = 0; j < i; j++) {
    35. 				if(arr[j]1]) {
    36. 					mid=arr[j];
    37. 					arr[j]=arr[j+1];
    38. 					arr[j+1]=mid;
    39. 					flag=false;
    40. 				}
    41. 			}
    42. 			//优化，提前整体有序
    43. 			if(flag) {
    44. 				return;
    45. 			}
    46. 			flag=true;
    47. 		}
    48. 	}
    49. 	
    50. 	public static void main(String[] args) {
    51. 		// TODO 自动生成的方法存根
    52. 		int[] arr= {5,2,8,9,2,6,7,10};
    53. //		f8(arr);
    54. 		f9(arr);
    55. 		System.out.println(Arrays.toString(arr));
    56. 		
    57. 	}
    58.  
    59. }

    2、选择排序

    思想：每次从待排数组中取一个最小或最大的元素放到前面，直到整体有序

    时间复杂度：O(n²)

    稳定性：不稳定

    1. package com.xch2.DiGui;
    2.  
    3. import java.util.*;
    4.  
    5. public class Main7_1 {
    6. 	
    7. 	//选择排序(简单选择排序)
    8. 	//小到大排序
    9. 	public static void f6(int[] arr) {
    10. 		int min=arr[0],p=0,mid;
    11. 		for (int i = 0; i < arr.length-1; i++) {
    12. 			for (int j = i+1; j < arr.length; j++) {
    13. 				if(arr[j]
    14. 					p=j;
    15. 					min=arr[j];
    16. 				}
    17. 			}
    18. 			mid=arr[p];
    19. 			arr[p]=arr[i];
    20. 			arr[i]=mid;
    21. 			
    22. 			min=arr[i+1];
    23. 			p=i+1;
    24. 		}
    25. 	}
    26. 	
    27. 	//大到小排序
    28. 	public static void f7(int[] arr) {
    29. 		int max=arr[0],p=0,mid;
    30. 		for (int i = 0; i < arr.length-1; i++) {
    31. 			for (int j = i+1; j < arr.length; j++) {
    32. 				if(arr[j]>max) {
    33. 					p=j;
    34. 					max=arr[j];
    35. 				}
    36. 			}
    37. 			mid=arr[p];
    38. 			arr[p]=arr[i];
    39. 			arr[i]=mid;
    40. 			
    41. 			max=arr[i+1];
    42. 			p=i+1;
    43. 		}
    44. 	}
    45. 	
    46. 	public static void main(String[] args) {
    47. 		// TODO 自动生成的方法存根
    48. 		int[] arr= {5,2,8,9,2,6,7,10};
    49. //		f6(arr);
    50. 		f7(arr);
    51. 		System.out.println(Arrays.toString(arr));
    52. 		
    53. 	}
    54.  
    55. }

    3、插入排序

    思想：每次取一个元素拆入到已排序的数组中有序的位置，直到整体有序

    时间复杂度：O(n²)

    稳定性：稳定

    1. package com.xch2.DiGui;
    2.  
    3. import java.util.*;
    4.  
    5. public class Main1 {
    6.  
    7. 	//插入排序
    8. 	static void f8(int[] arr,int k) {//k代表个数或数组长度
    9. 		if(k==1)//k代表元素个数
    10. 			return;
    11. 		f8(arr,k-1);//先把前k-1个元素排好序
    12. 		int index=k-1;//index代表数组下标
    13. 		while(index>0&&arr[index]1]) {
    14. 			int mid=arr[index];
    15. 			arr[index]=arr[index-1];
    16. 			arr[index-1]=mid;
    17. 			index--;
    18. 		}
    19. 	}
    20. 	
    21. 	//方法二（前往后排序）
    22. 	static void f9(int[] arr,int index) {//index代表开始下标，为0
    23. 		if(index==arr.length)
    24. 			return;
    25. 		int r=index;
    26. 		while(r>0&&arr[r]1]) {
    27. 			int mid=arr[r];
    28. 			arr[r]=arr[r-1];
    29. 			arr[r-1]=mid;
    30. 			r--;
    31. 		}
    32. 		f9(arr,index+1);//把剩余的index+1下标元素排序
    33. 	}
    34. 	
    35. 	//方法三（后往前排序）
    36. 	static void f10(int[] arr,int index) {//index代表结束下标，为arr.length-1
    37. 		if(index==-1)
    38. 			return;
    39. 		int r=index;
    40. 		while(r1&&arr[r]>arr[r+1]) {
    41. 			int mid=arr[r];
    42. 			arr[r]=arr[r+1];
    43. 			arr[r+1]=mid;
    44. 			r++;
    45. 		}
    46. 		f10(arr,index-1);//把剩余的index-1下标元素排序
    47. 	}
    48. 	
    49. 	public static void main(String[] args) {
    50. 		// TODO 自动生成的方法存根
    51. 		int[] arr1=new int[]{2,5,99,5,1,-5,-9};
    52. 		f8(arr1,7);
    53. 		for (int i = 0; i < arr1.length; i++) {
    54. 			System.out.print(arr1[i]+",");
    55. 		}
    56. 		System.out.println();
    57. 		
    58. 		int[] arr2=new int[]{2,5,99,5,1,-5,-9};
    59. 		f9(arr2,0);
    60. 		for (int i = 0; i < arr2.length; i++) {
    61. 			System.out.print(arr2[i]+",");
    62. 		}
    63. 		System.out.println();
    64. 		
    65. 		int[] arr3=new int[]{2,5,99,5,1,-5,-9};
    66. 		f10(arr3,6);
    67. 		for (int i = 0; i < arr3.length; i++) {
    68. 			System.out.print(arr3[i]+",");
    69. 		}
    70. 		System.out.println();
    71. 		
    72. 	}
    73.  
    74. }

    4、希尔排序

    思想：确定一个渐进缩小的增量，进行分组后在组内插入排序，直到整体有序(插入排序的进阶版)

    时间复杂度：O(nlogn)

    稳定性：不稳定

    1. package com.xch2.DiGui;
    2.  
    3. import java.util.*;
    4.  
    5. public class Main2 {
    6.  
    7. 	//希尔排序（缩小增量排序，优化插入排序）
    8. 	static void f2(int arr[]) {
    9. 		for (int incre = arr.length/2; incre > 0; incre=incre/2) {
    10. 			for (int i = incre; i < arr.length; i++) {
    11. 				int target=i;
    12. 				while(target>=incre&&arr[target]
    13. 					int mid=arr[target];
    14. 					arr[target]=arr[target-incre];
    15. 					arr[target-incre]=mid;
    16. 					target-=incre;
    17. 				}
    18. 			}
    19. 		}
    20. 	}
    21. 	
    22. 	public static void main(String[] args) {
    23. 		// TODO 自动生成的方法存根=
    24. 		int arr1[]=new int[] {9,8,7,6,5,4,3,6,2,1,99,0,-4};
    25. 		f2(arr1);
    26. 		for (int i : arr1) {
    27. 			System.out.print(i+",");
    28. 		}
    29. 		System.out.println();
    30. 		
    31. 	}
    32.  
    33. }

    5、归并排序

    思想：分治思想，把待排数组渐进分割，进行有序合并，直到整体有序(偏合并)

    时间复杂度：O(nlogn)

    稳定性：稳定

    1. package com.xch2.DiGui;
    2.  
    3. public class Main5 {
    4.  
    5. 	//归并排序
    6. 	static int[] arr1;
    7. 	static void f1(int[] arr,int l,int r) {
    8. 		arr1=new int[arr.length];//外移到递归函数外，不会多次new节省存储空间
    9. 		f2(arr,l,r);
    10. 	}
    11. 	static void f2(int[]arr,int l,int r) {
    12. 		if(l>=r)//递归出口
    13. 			return;
    14. 		
    15. 		int mid=l+((r-l)>>1),left=l,right=mid+1,ori=l;
    16. 		f2(arr,l,mid);//子递归
    17. 		f2(arr,mid+1,r);
    18. 		
    19. 		for (int i = 0; i < arr1.length; i++) {
    20. 			arr1[i]=arr[i];//更新辅助数组
    21. 		}
    22. 		while(left<=mid&&right<=r) {//递归体
    23. 			if(arr1[left]<=arr1[right]) {
    24. 				arr[ori]=arr1[left];
    25. 				left++;
    26. 			}else {
    27. 				arr[ori]=arr1[right];
    28. 				right++;
    29. 			}
    30. 			ori++;
    31. 		}
    32. 		while(left<=mid) {
    33. 			arr[ori]=arr1[left];
    34. 			left++;
    35. 			ori++;
    36. 		}
    37. 	}
    38. 	
    39. 	public static void main(String[] args) {
    40. 		// TODO 自动生成的方法存根
    41. 		int[] arr=new int[] {11,8,3,4,9,8,22,0,5,8,3};
    42. 		f1(arr,0,10);
    43. 		for (int i : arr) {
    44. 			System.out.print(i+" ");
    45. 		}
    46. 		System.out.println();
    47. 		
    48. 	}
    49.  
    50. }

    6、快速排序

    思想：分治思想，先定主元把数组分为两(三)段[小于(等于)大于]，后调整主元位置，递归渐进分割比较，直到整体有序(偏拆分)

    时间复杂度：O(nlogn)

    稳定性：不稳定

    其中，实现方法分为三种：

    1、双指针-单向扫描快速排序

    2、双指针-双向扫描快速排序

    3、三指针-双向扫描快速排序（相等元素优化）

    定主元的两种方法：

    1、取第一个

    2、三点中值法（推荐，取本段数组头中尾三个元素比较值）

    1. package com.xch2.DiGui;
    2.  
    3. public class Main4 {
    4.  
    5. 	//单向单指针扫描分区快排法
    6. 	static void f1(int[] arr,int l,int r) {
    7. 		if(l>=r)//递归出口
    8. 			return;
    9. 		
    10. 		int left=l+1,right=r,mid=0;
    11. 		while(left<=right) {//递归体
    12. 			if(arr[left]<=arr[l])
    13. 				left++;
    14. 			else {
    15. 				mid=arr[left];
    16. 				arr[left]=arr[right];
    17. 				arr[right]=mid;
    18. 				right--;
    19. 			}
    20. 		}
    21. 		mid=arr[right];
    22. 		arr[right]=arr[l];
    23. 		arr[l]=mid;
    24. 		
    25. 		f1(arr,l,right-1);//子递归
    26. 		f1(arr,right+1,r);
    27. 	}
    28. 	
    29. 	//双向双指针扫描分区快排法
    30. 	static void f2(int[] arr,int l,int r) {
    31. 		if(l>=r)//递归出口
    32. 			return;
    33. 		
    34. 		int left=l+1,right=r,mid=0;
    35. 		while(left<=right) {//递归体
    36. 			while(left<=right&&arr[left]<=arr[l])
    37. 				left++;
    38. 			while(left<=right&&arr[right]>arr[l])
    39. 				right--;
    40. 			if(left
    41. 				mid=arr[right];
    42. 				arr[right]=arr[left];
    43. 				arr[left]=mid;
    44. 			}
    45. 		}
    46. 		mid=arr[right];
    47. 		arr[right]=arr[l];
    48. 		arr[l]=mid;
    49. 		
    50. 		f2(arr,l,right-1);//子递归
    51. 		f2(arr,right+1,r);
    52. 	}
    53. 	
    54. 	//双向和等于三指针扫描分区快排法
    55. 	static void f3(int[] arr,int l,int r) {
    56. 		if(l>=r)//递归出口
    57. 			return;
    58. 		
    59. 		int equ=l,left=l+1,right=r,mid=0;
    60. 		while(left<=right) {//递归体
    61. 			while(left<=right&&arr[left]<=arr[l]) {
    62. 				if(arr[left]==arr[l]&&equ==l)
    63. 					equ=left;
    64. 				if(arr[left]
    65. 					mid=arr[left];
    66. 					arr[left]=arr[equ];
    67. 					arr[equ]=mid;
    68. 					equ++;
    69. 				}
    70. 				left++;
    71. 			}
    72. 			while(left<=right&&arr[right]>arr[l])
    73. 				right--;
    74. 			if(left
    75. 				mid=arr[right];
    76. 				arr[right]=arr[left];
    77. 				arr[left]=mid;
    78. 			}
    79. 		}
    80. 		if(equ!=l) {
    81. 			equ--;
    82. 			mid=arr[equ];
    83. 			arr[equ]=arr[l];
    84. 			arr[l]=mid;
    85. 			
    86. 			f3(arr,l,equ-1);//子递归
    87. 			f3(arr,right+1,r);
    88. 		}else {
    89. 			mid=arr[right];
    90. 			arr[right]=arr[l];
    91. 			arr[l]=mid;
    92. 			
    93. 			f3(arr,l,right-1);//子递归
    94. 			f3(arr,right+1,r);
    95. 		}
    96. 	}
    97. 	
    98. 	//以上方法均为去第一个随机数为比较主元
    99. 	//一般用三点取中值法取比较主元，如f4单指针，其他一样（取中值后和第一个数值换成为主元）
    100. 	
    101. 	//单向单指针扫描分区快排法（三点取中值为主元法）
    102. 	static void f4(int[] arr,int l,int r) {
    103. 		if(l>=r)//递归出口
    104. 			return;
    105. 		
    106. 		int left=l+1,right=r,mid=0;
    107. 		
    108. 		int midsub=l+((r-l)>>1);//三点取中值
    109. 		if(arr[l]>=arr[midsub]&&arr[midsub]>=arr[r]||
    110. 			arr[l]<=arr[midsub]&&arr[midsub]<=arr[r]) {
    111. 			mid=arr[midsub];
    112. 			arr[midsub]=arr[l];//换主元
    113. 			arr[l]=mid;
    114. 		}else if(arr[midsub]>=arr[r]&&arr[r]>=arr[l]||
    115. 				arr[midsub]<=arr[r]&&arr[r]<=arr[l]){
    116. 			mid=arr[r];
    117. 			arr[r]=arr[l];
    118. 			arr[l]=mid;
    119. 		}
    120. 		
    121. 		while(left<=right) {//递归体
    122. 			if(arr[left]<=arr[l])
    123. 				left++;
    124. 			else {
    125. 				mid=arr[left];
    126. 				arr[left]=arr[right];
    127. 				arr[right]=mid;
    128. 				right--;
    129. 			}
    130. 		}
    131. 		mid=arr[right];
    132. 		arr[right]=arr[l];
    133. 		arr[l]=mid;
    134. 		
    135. 		f4(arr,l,right-1);//子递归
    136. 		f4(arr,right+1,r);
    137. 	}
    138. 	
    139. 	public static void main(String[] args) {
    140. 		// TODO 自动生成的方法存根
    141. 		int[] arr=new int[] {0,1,9,5,4,1};
    142. 	//	f1(arr,0,5);
    143. 	//	f2(arr,0,5);
    144. 	//	f3(arr,0,5);
    145. 		f4(arr,0,5);
    146. 		for (int i : arr) {
    147. 			System.out.print(i+" ");
    148. 		}
    149. 		System.out.println();
    150. 		
    151. 	}
    152.  
    153. }

    7、堆排序

    思想：利用二叉树的特性，每次把最大或最小的元素比较到根节点维持一个大或小顶堆，取出根节点放到最后，直到整体有序

    时间复杂度：O(nlogn)

    稳定性：不稳定

    分为两种：

    1、小顶堆-逆向排序

    2、大顶堆-顺向排序

    1. package com.xch2.DiGui;
    2.  
    3. import java.util.*;
    4.  
    5. public class Main7 {
    6. 	
    7. 	//堆排序（小顶堆=逆序，大顶堆=顺序）
    8. 	//建小顶堆
    9. 	static void f1(int[] arr,int index,int leng) {//index初始为数组二分值减一
    10. 		if(index<0)								  //leng 初始为数组长度
    11. 			return;
    12. 		
    13. 		int left=2*index+1,right=2*index+2,mid;
    14. 		if(left==leng-1) {//最后一个父节点为单亲节点
    15. 			if(arr[left]
    16. 				mid=arr[left];
    17. 				arr[left]=arr[index];
    18. 				arr[index]=mid;
    19. 			}
    20. 		}else {
    21. 			if(arr[left]<=arr[right]&&arr[left]
    22. 				mid=arr[left];
    23. 				arr[left]=arr[index];
    24. 				arr[index]=mid;
    25. 			}else if(arr[right]<=arr[left]&&arr[right]
    26. 				mid=arr[right];
    27. 				arr[right]=arr[index];
    28. 				arr[index]=mid;
    29. 			}
    30. 		}
    31. 		
    32. 		f1(arr,index-1,leng);
    33. 	}
    34. 	
    35. 	//小顶堆转逆序数组
    36. 	static void f2(int arr[],int leng) {
    37. 		if(leng==1)
    38. 			return;
    39. 		
    40. 		f1(arr,leng/2-1,leng);
    41. 		int mid=arr[leng-1];
    42. 		arr[leng-1]=arr[0];
    43. 		arr[0]=mid;
    44. 		leng--;
    45. 		
    46. 		f2(arr,leng);
    47. 	}
    48. 	
    49. 	//建大顶堆
    50. 	static void f3(int[] arr,int index,int leng) {//index初始为数组二分值减一
    51. 		if(index<0)								  //leng 初始为数组长度
    52. 			return;
    53. 		
    54. 		int left=2*index+1,right=2*index+2,mid;
    55. 		if(left==leng-1) {//最后一个父节点为单亲节点
    56. 			if(arr[left]>arr[index]) {
    57. 				mid=arr[left];
    58. 				arr[left]=arr[index];
    59. 				arr[index]=mid;
    60. 			}
    61. 		}else {
    62. 			if(arr[left]>=arr[right]&&arr[left]>arr[index]) {
    63. 				mid=arr[left];
    64. 				arr[left]=arr[index];
    65. 				arr[index]=mid;
    66. 			}else if(arr[right]>=arr[left]&&arr[right]>arr[index]) {
    67. 				mid=arr[right];
    68. 				arr[right]=arr[index];
    69. 				arr[index]=mid;
    70. 			}
    71. 		}
    72. 		
    73. 		f3(arr,index-1,leng);
    74. 	}
    75. 	
    76. 	//大顶堆转顺序数组
    77. 	static void f4(int arr[],int leng) {
    78. 		if(leng==1)
    79. 			return;
    80. 		
    81. 		f3(arr,leng/2-1,leng);
    82. 		int mid=arr[leng-1];
    83. 		arr[leng-1]=arr[0];
    84. 		arr[0]=mid;
    85. 		leng--;
    86. 		
    87. 		f4(arr,leng);
    88. 	}
    89. 	
    90. 	public static void main(String[] args) {
    91. 		// TODO 自动生成的方法存根
    92. 		int arr[]= {5,2,8,9,2,6,7,10};
    93. 	//	f1(arr,arr.length/2-1,8);
    94. 		f2(arr,8);
    95. 	//	f3(arr,arr.length/2-1,8);
    96. 	//	f4(arr,8);
    97. 		for (int i : arr) {
    98. 			System.out.print(i+" ");
    99. 		}
    100. 		System.out.println();
    101. 		
    102. 	}
    103. 	
    104. }

    8、计数排序

    思想：利用数组的特性，把元素值记录到新的辅助数组对应下标中，后顺序恢复即可(适用于元素较为集中的排序，如年龄、分数等)

    时间复杂度：O(n)

    稳定性：稳定

    1. package com.xch2.DiGui;
    2.  
    3. import java.util.*;
    4.  
    5. public class Main7 {
    6. 	
    7. 	//计数顺序排序（包含负数）
    8. 	static void f5(int[] arr) {
    9. 		int cur=0,max=0,min=0;
    10. 		for (int i : arr) {
    11. 			if(i>max)
    12. 				max=i;
    13. 			else if(i<-min)
    14. 				min=-i;
    15. 		}
    16. 		int[] helper=new int[max+1];
    17. 		int[] helper1=new int[min+1];
    18. 		for (int i : arr) {
    19. 			if(i>=0)
    20. 				helper[i]++;
    21. 			else
    22. 				helper1[-i]++;
    23. 		}
    24. 		for (int i = helper1.length-1; i > 0; i--) {
    25. 			while(helper1[i]>0) {
    26. 				arr[cur]=-i;
    27. 				helper1[i]--;
    28. 				cur++;
    29. 			}
    30. 		}
    31. 		for (int i = 0; i < helper.length; i++) {
    32. 			while(helper[i]>0) {
    33. 				arr[cur]=i;
    34. 				helper[i]--;
    35. 				cur++;
    36. 			}
    37. 		}
    38. 	}
    39. 	
    40. 	//方法二
    41. 	static void f5_1(int[] arr){
    42. 		int max=0,min=0,cur=0;
    43. 		for (int i : arr) {
    44. 			if(i>max)
    45. 				max=i;
    46. 			else if(i
    47. 				min=i;
    48. 		}
    49. 		for (int i = 0; i < arr.length; i++) {
    50. 			arr[i]-=min;//把所有负数转正数
    51. 		}
    52. 		int[] helper=new int[max-min+1];
    53. 		for (int i : arr) {
    54. 			helper[i]++;
    55. 		}
    56. 		for (int i = 0; i < helper.length; i++) {
    57. 			while(helper[i]!=0) {
    58. 				arr[cur]=i+min;//恢复原数组输出
    59. 				helper[i]--;
    60. 				cur++;
    61. 			}
    62. 		}
    63. 	}
    64. 	
    65. 	public static void main(String[] args) {
    66. 		// TODO 自动生成的方法存根
    67. //		int arr1[]= {-3,2,4,-3,66,4,66,9,0,-90,2};
    68. //	//	f5(arr1);
    69. //		f5_1(arr1);
    70. //		System.out.println(Arrays.toString(arr1));
    71. 		
    72. 	}
    73. 	
    74. }

    9、桶排序

    思想：利用链表的特性，通过公式把数组分为多个数段的子链表(桶，元素进入链表时是有序插入)，再顺序取出即可(计数排序的进阶版：浪费率相比更低、适用数据分布相比更广)

    时间复杂度：O(n)

    稳定性：稳定

    1. package com.xch2.DiGui;
    2.  
    3. import java.util.*;
    4.  
    5. public class Main7 {
    6. 	
    7. 	//桶排序（包含负数）
    8. 	static void f6(int[] arr) {
    9. 		int max=arr[0],min=arr[0],cur=0;
    10. 		for (int i : arr) {
    11. 			if(i>max)
    12. 				max=i;
    13. 			else if(i
    14. 				min=i;
    15. 		}
    16. 		List> bucketlist=new ArrayList<>();
    17. 		for (int i=0;i
    18. 			bucketlist.add(new LinkedList());//初始化桶
    19. 		}
    20. 		for (int i : arr) {
    21. 			int num=(i-min)*arr.length/(max-min+1);//最优公式，元素放置桶
    22. 			bucketlist.get(num).add(i);
    23. 		}
    24. 		for (LinkedList linkedlist:bucketlist) {
    25. 			Collections.sort(linkedlist);//归并排序桶中的集合
    26. 		}
    27. 		for (LinkedList linkedlist:bucketlist) {
    28. 			for (Integer integer : linkedlist) {
    29. 				arr[cur]=integer;//遍历输出
    30. 				cur++;
    31. 			}
    32. 		}
    33. 	}
    34. 	
    35. 	public static void main(String[] args) {
    36. 		// TODO 自动生成的方法存根
    37. //		int arr1[]= {-3,2,4,-3,66,4,66,9,0,-90,2};
    38. //	//	f6(arr1);
    39. //		System.out.println(Arrays.toString(arr1));
    40. 		
    41. 	}
    42. 	
    43. }

    10、基数排序

    思想：利用链表的特性，通过数字的位数(个-十-百…)渐进顺序分配到链表中，再顺序收集即可，直到最高位即整体有序(桶排序的进阶版)

    时间复杂度：O(n)

    稳定性：稳定

    1. package com.xch2.DiGui;
    2.  
    3. import java.util.*;
    4.  
    5. public class Main7 {
    6.  
    7. 	//基数排序（包含负数）
    8. 	static void f7(int[] arr) {
    9. 		List[] bucketarr=new List[10];
    10. 		for (int i = 0; i < bucketarr.length; i++) {
    11. 			bucketarr[i]=new LinkedList();//初始化数组中的集合
    12. 		}
    13. 		int maxd=0,min=arr[0];
    14. 		for (int i:arr) {
    15. 			int len=(i+"").length();
    16. 			if(len>maxd)
    17. 				maxd=len;//找最大位数
    18. 			if(i
    19. 				min=i;//找最小值
    20. 		}
    21. 		if(min<0) {
    22. 			for (int i = 0; i < arr.length; i++) {
    23. 				arr[i]=arr[i]-min;//负数移位转正数
    24. 			}
    25. 		}
    26. 		int der=1,cur=0;
    27. 		for (int i = 1; i <= maxd; i++) {
    28. 			for (int j = 0; j < arr.length; j++) {
    29. 				int x=(arr[j]/der)%10;
    30. 				bucketarr[x].add(arr[j]);//入桶
    31. 			}
    32. 			for (int j = 0; j < bucketarr.length; j++) {
    33. 				for (Integer value : bucketarr[j]) {
    34. 					arr[cur]=value;//出桶
    35. 					cur++;
    36. 				}
    37. 				bucketarr[j].clear();
    38. 			}
    39. 			der*=10;
    40. 			cur=0;
    41. 		}
    42. 		if(min<0) {
    43. 			for (int i = 0; i < arr.length; i++) {
    44. 				arr[i]=arr[i]+min;//负数移位复原
    45. 			}
    46. 		}
    47. 	}
    48. 	
    49. 	public static void main(String[] args) {
    50. 		// TODO 自动生成的方法存根
    51. //		int arr1[]= {-3,2,4,-3,66,4,66,9,0,-90,2};
    52. //	//	f7(arr1);
    53. //		System.out.println(Arrays.toString(arr1));
    54. 		
    55. 	}
    56. 	
    57. }

    十大排序算法的时间复杂度：

    时间复杂度效率对比： 

  • 相关阅读:
    linux下基于boost/process库实现多进程管理，基于c++开发
    温敏传感器概述
    实例分割Yolact边缘端部署 （三） 从onnx到caffemodel
    VM虚拟机安装ikuai软路由系统
    不解压的情况下从各种压缩包中直接读取文本行内容
    23、JAVA进阶——日期操作类
    DETR纯代码分享（五）__init__.py(datasets)
    数据统计和分析怎么做?spss如何做好数据分析?
    2022年（第二届）信息技术服务业应用技能大赛网络与信息安全管理赛项的通知
    二维数组与稀疏数组转换(java)
  • 原文地址：https://blog.csdn.net/weixin_51091560/article/details/126920866