boss直聘|算法 | Java 常见排序算法（纯代码）( 三 )

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://mparticle.uc.cn/api/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. 桶排序类似计数排序，不同点在于统计的是某个区间（桶）里的数；