常见排序算法

文章目录

• 1 冒泡
• 2 选排
• 3 归并
• 4 快排
• 5 直接插入
• 6 希尔
• 7 计数
• 8 计数基数
• 9 堆排

---

PS：以下演示的排序都是升序

1 冒泡

🚀 代码

• 无优化

  public void bubbleSort(int[] nums) {
  	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]) {
  				swap(nums, j, j + 1);
  			}
  		}
  	}
  }
  

• 简单优化

  public void optimisticBubbleSort(int[] nums) {
  	for (int i = 0;i < nums.length - 1;i++) {
  		// 整个标记
  		boolean isSwap = false;
  		for (int j = 0;j < nums.length - 1 - i;j++) {
  			if (nums[j] > nums[j + 1]) {
  				swap(nums, j, j + 1);
  				// 发生了交换，改为true
  				isSwap = true;
  			}
  		}
  		if (! isSwap) {
  			// 如果当前冒泡没有发生过交换，直接结束循环
  			break;
  		}
  	}
  }	
  

🚀 算法分析

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定

---

2 选排

🚀 代码

public void selectionSort(int[] nums) {
    for (int i = 0;i < nums.length - 1;i++) {
        int minId = i;
        for (int j = i + 1;j < nums.length;j++) {
            // 找出最小值
            if (nums[minId] > nums[j]) {
                minId = j;
            }
        }
        if (minId != i) {
            // 把最小值换到起初位置
            swap(nums, minId, i);
        }
    }
}

🚀 算法分析

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 不稳定

---

3 归并

🚀 代码

public void mergeSort(int[] nums) {
    int len = nums.length;
    if (len > 1) {
        // 先拆分
        int[] lNums = Arrays.copyOfRange(nums, 0, len / 2);
        int[] rNums = Arrays.copyOfRange(nums, len / 2, len);
        
        // 拆分后继续递归排序（继续拆分）
        mergeSort(lNums);
        mergeSort(rNums);
        
        // 拆完再合并
        merge(lNums, rNums, nums);
    }
}

// 合并算法
public void merge(int[] lNums, int[] rNums, int[] nums) {
    // 指向两个待合并的数组的指针
    int l = 0, r = 0;
    // 合并后数组的指针
    int id = 0;
    
    int lLen = lNums.length;
    int rLen = rNums.length;
    
    while (l < lLen && r < rLen) {
        // 元素值较小的数组先移动指针
        if (lNums[l] < rNums[r]) {
            nums[id++] = lNums[l];
            l++;
        } else {
            nums[id++] = rNums[r];
            r++;
        }
    }
    
    // 把还没遍历完的数组剩下元素直接cv
    if (l == lLen) {
        System.arraycopy(rNums, r, nums, id, rLen - r);
    } else {
        System.arraycopy(lNums, l, nums, id, lLen - l);
    }
}

🚀 算法分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)
• 稳定

---

4 快排

🚀 代码

public void quickSort(int[] nums, int left, int right) {
    if (left < right) {
        // 先分区，找出基准点
        int p = partition(nums, left, right);
        
        // 根据基准点拆分，继续排序
        quickSort(nums, left, p - 1);
        quickSort(nums, p + 1, right);
    }
}

// 分区算法
public int partition(int[] nums, int left, int right) {
    // 记住基准点对应值（也可以随机生成）
    int pVal = nums[left];
    int l = left, r = right;
    
    while (l < r) {
        // 右指针先移动，找到第一个比pVal小的值
        while (l < r && nums[r] >= pVal) {
            r--;
        }
        
        // 找到后直接替换此时l对应值
        nums[l] = nums[r];
        
        // 左指针同理，找到第一个比pVal大的值
        while (l < r && nums[l] <= pVal) {
            l++;
        }
        nums[r] = nums[l];
    }
    
    // 遍历结束后，此时l就是基准点
    nums[l] = pVal;
    return l;
}

🚀 算法分析

• 时间复杂度：最好O(nlogn)，最差O(n^2)
• 空间复杂度：O(logn)
• 不稳定

---

5 直接插入

🚀 代码

public void insertSort(int[] nums) {
    for (int i = 1;i < nums.length;i++) {
        // 记住待排序的元素
        int temp = nums[i];
        int j = i;
        
        while (j >= 1 && temp < nums[j - 1]) {
            // 前面的元素往后挪，给temp让出位置
            nums[j] = nums[j - 1];
            j--;
        }
        
        if (j != i) {
            // j移动过，则换回原来元素
            nums[j] = temp;
        }
    }
}

🚀 算法分析

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定

---

6 希尔

🚀 代码

// 直接插入的升级版
public void shellSort(int[] nums) {
    for (int step = nums.length / 2;step > 0;step >>= 1) {
        // 下面就是步长为step的直接插入
        for (int i = step;i < nums.length;i += step) {
            int temp = nums[i];
            int j = i;
            while (j >= step && temp < nums[j - step]) {
                // 往后挪step步
                nums[j] = nums[j - step];
                j -= step;
            }
            
            if (j != i) {
                nums[j] = temp;
            }
        }
    }
}

🚀 算法分析

• 时间复杂度：平均O(nlogn)
• 空间复杂度：O(1)
• 不稳定

---

7 计数

🚀 代码

public void countSort(int[] nums) {
	// 先找出数组中最大值
    int maxVal = nums[0];
    for (int num : nums) {
        maxVal = Math.max(maxVal, num);
    }
    
    // 根据最大值创建出计数数组
    int[] count = new int[maxVal + 1];
    
    // 统计数组元素出现次数
    for (int num : nums) {
        count[num]++;
    }
    
    // 根据计数结果依次将元素放到原数组
    for (int i = 0, id = 0;i < count.length;i++) {
        while (count[i]-- > 0) {
            nums[id++] = i;
        }
    }
}

🚀 算法分析

• 时间复杂度：O(n + k)
• 空间复杂度：O(k)
• 稳定

---

8 计数基数

🚀 代码

• 一维桶实现

  public void radixSort(int[] nums) {
      // 先找出最大值
      int maxVal = nums[0];
      for (int num : nums) {
          maxVal = Math.max(maxVal, num);
      }
      
      // 取最大值的最大位数
      int maxLen = (maxVal + "").length();
  
      // 根据每一位进行排序（从低位到高位）
      int len = 0, n = 1;
      while (len++ < maxLen) {
          // 计数数组，基数是10
          int[] count = new int[10];
          // 整个桶，暂存当前位有序的数组
          int[] bucket = new int[nums.length];
          
          // 初始化count
          for (int num : nums) {
              count[(num / n) % 10]++;
          }
          // 将count修改为在bucket中对应索引
          for (int i = 1;i < 10;i++) {
              count[i] += count[i - 1];
          }
          
          // 根据count往桶里填数据，必须从后往前遍历
          for (int i = bucket.length - 1;i >= 0;i--) {
              int countId = (nums[i] / n) % 10;
              // 索引要减一
              bucket[count[countId] - 1] = nums[i];
              // 填了之后，对应元素数量减一
              count[countId]--;
          }
          
          // 把此时的桶拷到nums
          System.arraycopy(bucket, 0, nums, 0, bucket.length);
          // 位数增加
          n *= 10;
      }
  }
  

• 二维桶实现

  public void radixSort(int[] nums) {
      // 先找出最大值
      int maxVal = nums[0];
      for (int num : nums) {
          maxVal = Math.max(maxVal, num);
      }
      
      // 取最大值的最大位数
      int maxLen = (maxVal + "").length();
      
      // 整个二维桶（行对应基数，列对应基数出现的次数）
      int[][] bucket = new int[10][nums.length];
      // 计数数组，基数是10
      int[] count = new int[10];
  
      // 根据每一位进行排序（从低位到高位）
      int len = 0, n = 1;
      while (len++ < maxLen) {   
          // 计数同时往桶里添加元素
          for (int num : nums) {
              int countId = (num / n) % 10;
              bucket[countId][count[countId]++] = num;
          }
          
          // 将桶中元素依次放到数组中
          for (int i = 0, id = 0;i < bucket.length;i++) {
              // 不用遍历桶每一列，根据计数结果即可
              for (int j = 0;j < count[i];j++) {
                  nums[id++] = bucket[i][j];
              }
              // 遍历完一行，把对应计数清0
              count[i] = 0;
          }
          
          // 位数增加
          n *= 10;
      }
  }
  

🚀 算法分析

• 时间复杂度：O(nk)
• 空间复杂度：O(n + k)
• 稳定

---

9 堆排

🚀 代码

public void heapSort(int[] nums) {
    // 获取节点个数/元素个数（如果索引从1开始，节点个数为数组长度-1）
    int len = nums.length;
    
    // 建大顶堆（如果索引从1开始，pos初始值为len/2，且只需遍历到1）
    for (int pos = len / 2 - 1;pos >= 0;pos--) {
        // 从下往上，从右往左堆化
        bigHeap(nums, pos, len);
    }
    
    // 依次将堆顶元素与最后一个元素交换，去除最后元素再堆化
    while (len > 1) {
        // 如果索引从1开始，堆顶元素索引为1，最后元素索引为len
        swap(nums, 0, --len);
        // 因为只换了堆顶元素，因此直接从堆顶元素开始堆化即可
        bigHeap(nums, 0, len);
    }
}

// 建大顶堆
public void bigHeap(int[] nums, int pos, int len) {
    // 如果索引从1开始，循环条件为pos<=len/2
    while (pos <= len / 2 - 1) {
        // 先找出子节点中的大哥
        int bigBro = pos * 2 + 1;
        if (bigBro < len - 1 && nums[bigBro] < nums[bigBro + 1]) {
            bigBro++;
        }
        
        if (nums[bigBro] <= nums[pos]) {
            // 老爸还是老大，不用换了，直接结束
            return ;
        } 
        
        // 大哥比老爸还大，交换，大哥变老爸
        swap(nums, bigBro, pos);
        // 老爸变儿子
        pos = bigBro;
    }
}

🚀 算法分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)
• 不稳定