算法 | Java 常见排序算法（纯代码） _排序

莫道桑榆晚，为霞尚满天。这篇文章主要讲述算法 | Java 常见排序算法（纯代码）相关的知识，希望能为你提供帮助。
@[TOC](java 常见排序算法)
汇总

序号	排序算法	平均时间	最好情况	最差情况	稳定度	额外空间	备注	相对时间
1	冒泡算法	O(n^2^)	O(n)	O(n^2^)	稳定	O(1)	n 越小越好	182 ms
2	选择算法	O(n^2^)	O(n^2^)	O(n^2^)	不稳定	O(1)	n 越小越好	53 ms
3	插入算法	O(n^2^)	O(n)	O(n^2^)	稳定	O(1)	大部分排序好时好	16 ms

4	快速算法	O(nlog~2~n)	O(nlog~2~n)	O(n^2^)	不稳定	O(nlog~2~n)	n 大时好	719 ms
5	归并算法	O(nlog~2~n)	O(nlog~2~n)	O(nlog~2~n)	稳定	O(n)	n 大时好	550 ms
6	希尔算法	O(nlog~2~n)	O(n)	O(n^2^)	不稳定	O(1)		197 ms/4 ms
7	堆排序	O(nlog~2~n)	O(nlog~2~n)	O(nlog~2~n)	不稳定	O(1)	n 大时好	3 ms

8	计数排序	O(n+k)	O(n+k)	O(n+k)	稳定	O(n+k)	k 是桶的数量	2 ms
9	桶排序	O(n+k)	O(n)	O(n^2^)	稳定	O(n+k)		11 ms
10	基数排序	O(n*k)	O(n*k)	O(n*k)	稳定	O(n+k)		4 ms

11	优先队列				不稳定	O(n)		9 ms
12	Java API					O(1)		4 ms

1. 冒泡排序

public void bubbleSort(int[] nums) int temp; boolean isSort = false; //优化，发现排序好就退出 for (int i = 0; i < nums.length-1; i++) for (int j = 0; j < nums.length-1-i; j++)//每次排序后能确定较大值 if(nums[j] > nums[j+1]) isSort = true; temp = nums[j]; nums[j] = nums[j+1]; nums[j+1] = temp; if(!isSort) return; else isSort = false;

2. 选择排序

public void selectSort(int[] nums) for (int i = 0; i < nums.length-1; i++) int index = i; int minNum = nums[i]; for (int j = i+1; j < nums.length; j++) if(nums[j] < minNum) minNum = nums[j]; index = j; if(index != i) nums[index] = nums[i]; nums[i] = minNum;

3. 插入排序

public void insertionSort(int[] nums) for (int i = 1; i < nums.length; i++) int j = i; int insertNum = nums[i]; while(j-1 > = 0 & & nums[j-1] > insertNum) nums[j] = nums[j-1]; j--; nums[j] = insertNum;

4. 快速排序

public void quickSortDfs(int[] nums, int left, int right) if(left > right) return; int l = left; int r = right; int baseNum = nums[left]; while(l < r) //必须右边先走 while(nums[r] > = baseNum & & l < r) r--; while(nums[l] < = baseNum & & l < r) l++; int temp = nums[l]; nums[l] = nums[r]; nums[r] = temp; nums[left] = nums[l]; nums[l] = baseNum; quickSortDfs(nums, left, r-1); quickSortDfs(nums, l+1, right);

5. 归并排序

//归 public void mergeSortDfs(int[] nums, int l, int r) if(l > = r) return; int m = (l+r)/2; mergeSortDfs(nums, l, m); mergeSortDfs(nums, m+1, r); merge(nums, l, m, r); //并 private void merge(int[] nums, int left, int mid, int right) int[] temp = new int[right-left+1]; int l = left; int m = mid+1; int i = 0; while(l < = mid & & m < = right) if(nums[l] < nums[m]) temp[i++] = nums[l++]; else temp[i++] = nums[m++]; while(l < = mid) temp[i++] = nums[l++]; while(m < = right) temp[i++] = nums[m++]; System.arraycopy(temp, 0, nums, left, temp.length);

6. 希尔排序6.1 希尔-冒泡排序（慢）

public void shellBubbleSort(int[] nums) for (int step = nums.length/2; step > 0 ; step /= 2) for (int i = step; i < nums.length; i++) for (int j = i-step; j > = 0; j -= step) if(nums[j] > nums[j+step]) int temp = nums[j]; nums[j] = nums[j+step]; nums[j+step] = temp;

6.2 希尔-插入排序（快）

public void shellInsertSort(int[] nums) for (int step = nums.length/2; step > 0; step /= 2) for (int i = step; i < nums.length; i++) int j = i; int insertNum = nums[i]; while(j-step > = 0 & & nums[j-step] > insertNum) nums[j] = nums[j-step]; j-=step; nums[j] = insertNum;

7. 堆排序

public void heapSort2(int[] nums) for(int i = nums.length/2-1; i > = 0; i--) sift(nums, i, nums.length); for (int i = nums.length-1; i > 0; i--) int temp = nums[0]; nums[0] = nums[i]; nums[i] = temp; sift(nums, 0, i); private void sift(int[] nums, int parent, int len) int value = https://www.songbingjia.com/android/nums[parent]; for (int child = 2*parent +1; child < len; child = child*2 +1) if(child+1 < len & & nums[child+1] > nums[child]) child++; if(nums[child] > value) nums[parent] = nums[child]; parent = child; else break; nums[parent] = value;

8. 计数排序

public void countSort(int[] nums) int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int num : nums) max = Math.max(max, num); min = Math.min(min, num); int[] countMap = new int[max-min+1]; for(int num : nums) countMap[num-min]++; int i = 0; int j = 0; while(i < nums.length & & j < countMap.length) if(countMap[j] > 0) nums[i] = j+min; i++; countMap[j]--; else j++;

9. 桶排序

public void bucketSort(int[] nums) int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int num : nums) max = Math.max(max, num); min = Math.min(min, num); int bucketCount = (max-min)/nums.length+1; List< List< Integer> > bucketList = new ArrayList< > (); for (int i = 0; i < bucketCount; i++) bucketList.add(new ArrayList< > ()); for(int num : nums) int index = (num-min)/nums.length; bucketList.get(index).add(num); for(List< Integer> bucket : bucketList) Collections.sort(bucket); int j = 0; for(List< Integer> bucket : bucketList) for(int num : bucket) nums[j] = num; j++;

10. 基数排序

publicvoid radixSort(int[] nums) int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; for (int num : nums) min = Math.min(min, num); max = Math.max(max, num); for (int i = 0; i < nums.length; i++) nums[i] -= min; max -= min; int maxLen = (max+"").length(); int[][] bucket = new int[nums.length][10]; int[] bucketCount = new int[10]; for (int i = 0, n = 1; i < maxLen; i++, n*=10) for (int num : nums) int digitVal = num / n % 10; bucket[bucketCount[digitVal]][digitVal] = num; bucketCount[digitVal]++; int index = 0; for (int j = 0; j < bucketCount.length; j++) if(bucketCount[j] > 0) for (int k = 0; k < bucketCount[j]; k++) nums[index] = bucket[k][j]; index++; bucketCount[j] = 0; for (int i = 0; i < nums.length; i++) nums[i] += min;

11. 使用集合或 API 11.1 优先队列

public void priorityQueueSort(int[] nums) PriorityQueue< Integer> queue = new PriorityQueue< > (); for(int num : nums) queue.offer(num); for (int i = 0; i < nums.length; i++) nums[i] = queue.poll();

11.2 Java API