Java中一些常见排序算法

ffeiko

冒泡排序（Bubble Sort）：

[Java] 纯文本查看 复制代码

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    // 交换arr[j]和arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}

选择排序（Selection Sort）：

[Java] 纯文本查看 复制代码

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换arr[i]和arr[minIndex]
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

插入排序（Insertion Sort）：
public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr;
            int j = i - 1;

            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
}

[Java] 纯文本查看 复制代码

public class ShellSort {
    public static void shellSort(int[] arr) {
        int n = arr.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }
}

[Java] 纯文本查看 复制代码

public class MergeSort {
    public static void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;
            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }

    private static void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int[] L = new int[n1];
        int[] R = new int[n2];

        System.arraycopy(arr, l, L, 0, n1);
        System.arraycopy(arr, m + 1, R, 0, n2);

        int i = 0, j = 0, k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }

        while (i < n1) {
            arr[k++] = L[i++];
        }

        while (j < n2) {
            arr[k++] = R[j++];
        }
    }
}

[Java] 纯文本查看 复制代码

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
}

[Java] 纯文本查看 复制代码

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

pallove

来个跳表算法，根本不用排序，插入/删除就决定了元素的位置，redis内核有用这个算法

[Java] 纯文本查看 复制代码

import java.util.Random;

class Node {
    int value;
    Node[] nextNodes = new Node[16]; // 假设最大层级为16

    Node(int value) {
        this.value = value;
    }
}

public class SkipList {
    private final Random random = new Random();
    private Node head;
    private int levelCount = 1; // 当前跳表层级数

    public SkipList() {
        head = new Node(Integer.MIN_VALUE);
        for (int i = 0; i < nextNodes.length; i++) {
            head.nextNodes[i] = null;
        }
    }

    // 插入节点
    public void insert(int value) {
        Node newNode = new Node(value);
        Node current = head;
        int newLevel = randomLevel(); // 随机生成新节点的层级

        if (newLevel > levelCount) {
            levelCount = newLevel;
        }

        // 从最高层开始插入
        for (int i = levelCount - 1; i >= 0; i--) {
            while (current.nextNodes[i] != null && current.nextNodes[i].value < value) {
                current = current.nextNodes[i];
            }
            newNode.nextNodes[i] = current.nextNodes[i];
            current.nextNodes[i] = newNode;
        }
    }

    // 查找节点
    public boolean contains(int value) {
        Node current = head;
        for (int i = levelCount - 1; i >= 0; i--) {
            while (current.nextNodes[i] != null && current.nextNodes[i].value < value) {
                current = current.nextNodes[i];
            }
            if (current.nextNodes[i] != null && current.nextNodes[i].value == value) {
                return true;
            }
        }
        return false;
    }

    // 删除节点
    public void delete(int value) {
        Node[] update = new Node[levelCount]; // 更新路径数组
        Node current = head;
        for (int i = levelCount - 1; i >= 0; i--) {
            while (current.nextNodes[i] != null && current.nextNodes[i].value < value) {
                current = current.nextNodes[i];
            }
            update[i] = current;
        }
        if (current.nextNodes[0] != null && current.nextNodes[0].value == value) {
            current = current.nextNodes[0];
            for (int i = levelCount - 1; i >= 0; i--) {
                if (update[i].nextNodes[i] == current) {
                    update[i].nextNodes[i] = current.nextNodes[i];
                }
            }
            // 如果层级计数过高，则向下调整
            while (levelCount > 1 && head.nextNodes[levelCount - 1] == null) {
                levelCount--;
            }
        }
    }

    // 随机生成节点的层级
    private int randomLevel() {
        int lvl = 1;
        while (random.nextDouble() < 0.5 && lvl < nextNodes.length) {
            lvl++;
        }
        return lvl;
    }
}

jeansluo

学习了，学习了！

yangzhm

学到了，总结提炼成子程序，真是科研狗的干活利器啊！

ffeiko

zyc1996 发表于 2024-3-14 19:44
您好，我想问一下，我是做大数据的，主要是数仓开发，对后端java不太懂，如果想学的话，怎么开始比较好呢

先从java基础学习 可以参考如下方向
基础知识学习： 从Java的基础知识开始学起，掌握Java的语法、面向对象编程等基本概念。

学习Java后端开发框架： 了解常用的Java后端开发框架，比如Spring Framework，Spring Boot等。这些框架能够帮助你快速搭建Java后端应用程序。

实践项目： 通过实践项目来巩固所学知识。你可以选择一些小型的项目来开始，逐渐增加复杂度，比如简单的Web应用或者RESTful API。