1. 排序算法
冒泡排序
public static void bubbleSort(int[] arr) {
boolean swapped = true;
// 最后一个没有经过排序的元素的下标
int indexOfLastUnsortedElement = arr.length - 1;
// 上次发生交换的位置
int swappedIndex = -1;
while (swapped) {
swapped = false;
for (int i = 0; i < indexOfLastUnsortedElement; i++) {
if (arr[i] > arr[i + 1]) {
// 如果左边的数大于右边的数，则交换，保证右边的数字最大
swap(arr, i, i + 1);
// 表示发生了交换
swapped = true;
// 更新交换的位置
swappedIndex = i;
}
}
// 最后一个没有经过排序的元素的下标就是最后一次发生交换的位置
indexOfLastUnsortedElement = swappedIndex;
}
}
// 交换元素
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
-
把数组排成最小的数
剑指offer 45
思路：重新定义数大小的规则 如果 2，10 因为210>102 所以10放在2的前面 -
移动零
link
将所有0移动到数组末尾 并保持相对顺序 对数组原地操作
思路：冒泡排序
思路二：设置非0的个数计数 如果当前值为非0 则将该值移至cnt-1的位置
选择排序
优化：二元选择排序 同时找到最大和最小值
插入排序
class Solution {
public int[] sortArray(int[] nums) {
insertSort(nums);
return nums;
}
public static void insertSort(int[] arr) {
// 从第二个数开始，往前插入数字
for (int i = 1; i < arr.length; i++) {
int currentNumber = arr[i];
int j = i - 1;
// 寻找插入位置的过程中，不断地将比 currentNumber 大的数字向后挪
while (j >= 0 && currentNumber < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
// 两种情况会跳出循环：1. 遇到一个小于或等于 currentNumber 的数字，跳出循环，currentNumber 就坐到它后面。
// 2. 已经走到数列头部，仍然没有遇到小于或等于 currentNumber 的数字，也会跳出循环，此时 j 等于 -1，currentNumber 就坐到数列头部。
arr[j + 1] = currentNumber;
}
}
}
优化：插入时用二分查找优化
应用：对链表进行插入排序
link
思路：如果当前节点比前一节点大时，则无需交换，否则从首节点前的结点开始比较。
插入时，要先把next赋值，如果先赋值当前节点则找不到next
希尔排序
对插入排序的优化，插入排序每次只能交换相邻元素。
思想：
每次排序的间隔 K=N/2 K=K/2
实现：
public static void shellSort(int[] arr) {
// 间隔序列，在希尔排序中我们称之为增量序列
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 从 gap 开始，按照顺序将每个元素依次向前插入自己所在的组
for (int i = gap; i < arr.length; i++) {
// currentNumber 站起来，开始找位置
int currentNumber = arr[i];
// 该组前一个数字的索引
int preIndex = i - gap;
while (preIndex >= 0 && currentNumber < arr[preIndex]) {
// 向后挪位置
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
// currentNumber 找到了自己的位置，坐下
arr[preIndex + gap] = currentNumber;
}
}
}
堆排序
针对于只需要部分排序的场景，例如前K个访问最多的元素
非稳定算法：初始化堆和重建堆的时间复杂度：O(nlogn)
完全二叉树性质:
节点i的左孩子节点：l=2*i+1 右孩子节点：r=l+1
对于有 n个元素的完全二叉树(n≥2)，它的最后一个非叶子结点的下标：n/2 - 1
每次调整完堆后要递归到当前结点的下面，被换下来的最大值的下面节点
代码：
public static void heapSort(int[] arr) {
// 构建初始大顶堆
buildMaxHeap(arr);
for (int i = arr.length - 1; i > 0; i--) {
// 将最大值交换到数组最后
swap(arr, 0, i);
// 调整剩余数组，使其满足大顶堆
maxHeapify(arr, 0, i);
}
}
// 构建初始大顶堆
private static void buildMaxHeap(int[] arr) {
// 从最后一个非叶子结点开始调整大顶堆，最后一个非叶子结点的下标就是 arr.length / 2-1
for (int i = arr.length / 2 - 1; i >= 0; i--) {
maxHeapify(arr, i, arr.length);
}
}
// 调整大顶堆，第三个参数表示剩余未排序的数字的数量，也就是剩余堆的大小
private static void maxHeapify(int[] arr, int i, int heapSize) {
// 左子结点下标
int l = 2 * i + 1;
// 右子结点下标
int r = l + 1;
// 记录根结点、左子树结点、右子树结点三者中的最大值下标
int largest = i;
// 与左子树结点比较
if (l < heapSize && arr[l] > arr[largest]) {
largest = l;
}
// 与右子树结点比较
if (r < heapSize && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
// 将最大值交换为根结点
swap(arr, i, largest);
// 再次调整交换数字后的大顶堆
maxHeapify(arr, largest, heapSize);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
归并排序
快速排序
经典快排模板
public void partion(int[] nums,int k,int l,int r){
if(l>=r)return;
int cur=nums[l];
int i=l;
int j=r;
while(i<j){
while(i<j&&nums[j]>=cur){
j--;
}
while(i<j&&nums[i]<=cur){
i++;
}
swap(nums,i,j);
}
swap(nums,i,l);
if(i==k)return;
if(i>k){
partion(nums,k,l,i-1);
}else{
partion(nums,k,i+1,r);
}
}
数组中的第K个最大元素
思路1：减治(快速排序)
实现步骤：随机选择一个数，将大于这个数的都放该数的右边，小于该数的都放左边
思路2：优先队列 小堆顶
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k);
for (int i = 0; i < nums.length; i++) {
priorityQueue.add(nums[i]);
if (priorityQueue.size() > k) {
priorityQueue.poll();
}
}
return priorityQueue.peek();
}
}
思路3：堆排序
class Solution {
public int findKthLargest(int[] nums, int k) {
buildMaxHeap(nums);
// 调整 k-1 次
for (int i = nums.length - 1; i > nums.length - k; i--) {
swap(nums, 0, i);
maxHeapify(nums, 0, i);
}
// 此时，堆顶的元素就是第 k 大的数
return nums[0];
}
// 构建初始大顶堆
public static void buildMaxHeap(int[] arr) {
// 从最后一个非叶子结点开始调整大顶堆，最后一个非叶子结点的下标就是 arr.length / 2-1
for (int i = arr.length / 2 - 1; i >= 0; i--) {
maxHeapify(arr, i, arr.length);
}
}
// 调整大顶堆，第三个参数表示剩余未排序的数字的数量，也就是剩余堆的大小
private static void maxHeapify(int[] arr, int i, int heapSize) {
// 左子结点下标
int l = 2 * i + 1;
// 右子结点下标
int r = l + 1;
// 记录根结点、左子树结点、右子树结点三者中的最大值下标
int largest = i;
// 与左子树结点比较
if (l < heapSize && arr[l] > arr[largest]) {
largest = l;
}
// 与右子树结点比较
if (r < heapSize && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
// 将最大值交换为根结点
swap(arr, i, largest);
// 再次调整交换数字后的大顶堆
maxHeapify(arr, largest, heapSize);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
基数排序
基数排序可以分为以下三个步骤：
- 找出数组中最大的数字的位数 maxDigitLength
- 获取数组中每个数字的基数
- 遍历 maxDigitLength轮数组，每轮按照基数对其进行排序
|