排序算法-用Java实现

admin2024-09-05  8

排序算法

排序(Sort)是将一组数据按照一定的规则来进行排列,一般按递增或递减的顺序来进行排列,排序算法是一种最基本的算法。

冒泡排序

思路:交换排序,通过相邻数据的交换来达到排序的目的。

流程

1.对数组中的各数据,依次比较相邻的两个元素的大小

2.如果前面的数据大于后面的数据,就交换这两个数据,经过第一轮的多次比较排序后,便可将最小的数据排好

3.再用同样的方法把剩下的数据逐个进行比较,最后便可按照从小到大的顺序排好数组各数据

// 冒泡排序算法
    public static void bubbleSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = i; j < n - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    // 交换 array[j] 和 array[j+1]
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true;
                }
            }
            // 如果内层循环没有交换元素,说明数组已经有序
            if (!swapped) break;
        }
    }

选择排序

思路:选择排序算法在每一步中选择最小的值来重新排列,从而达到排序的目的。

流程

1.首先从原始数据中选择最小的1个数据,将其和位于第1个位置的数据交换

2.接着从剩下的n-1个数据中选择次小的1个数据,将其和第2个位置的数据交换

3.然后不断重复上述过程,直到最后两个数据完成交换。至此,便完成了对原始数组的从小到大的排序

 // 选择排序算法
    public static void selectionSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            // 假设最小值的位置是 i
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                // 找到比当前最小值更小的元素
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换找到的最小值和当前位置的值
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
    }

插入排序

思路:通过对未排序的数据执行逐个插入至合适的位置而完成排序工作

流程

1.首先对数组的前两个数据进行从小到大的排序

2.接着将第3个数据与排好序的两个数据比较,将第3个数据插入合适的位置

3.然后,将第4个数据插入已经排好序的前3个数据中

4.不断重复上述过程,直到把最后一个数据插入合适的位置。最后便完成了对原始数组从小到大的排序

// 插入排序算法
    public static void insertionSort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; ++i) {
            int key = array[i];
            int j = i - 1;

            // 将当前元素插入到已经排序好的部分的正确位置
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key;
        }
    }

Shell排序算法

Shell排序算法严格来说是基于插入排序的思想,其又成为希尔排序或者缩小增量排序。

流程

  1. 将有n个元素的数组分成n/2个数字序列,第1个数据和第n/2 + 1个数据为一对,…

  2. 一次循环使每一个序列对排好顺序

  3. 然后,再变为n/4个序列,再次排序

  4. 不断重复上述过程,随着序列减少最后变为一个,也就完成了整个排序

    // 希尔排序算法
    public static void shellSort(int[] array) {
        int n = array.length;

        // 初始步长
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 从步长位置开始插入排序
            for (int i = gap; i < n; i++) {
                int temp = array[i];
                int j;
                for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                    array[j] = array[j - gap];
                }
                array[j] = temp;
            }
        }
    }

快速排序

快速排序算法和冒泡排序算法类似,都是基于交换排序思想,快速排序算法对冒泡排序算法进行了改进,从而具有更高的执行效率

流程

1.首先设定一个分界值,通过该分界值将数组分成左右两部分。

2.将大于等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于等于分界值,而右边部分中都大于等于分界值。

3.然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分为左右两部分,同样将左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。

4.重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两部分各数据排序完成后,整个数组的排序也就完成了。

 // 快速排序算法
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            // 获取分区索引
            int pi = partition(array, low, high);

            // 递归排序左侧和右侧子数组
            quickSort(array, low, pi - 1);
            quickSort(array, pi + 1, high);
        }
    }

    // 分区方法
    public static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = (low - 1); // 小于 pivot 元素的索引

        for (int j = low; j < high; j++) {
            // 如果当前元素小于或等于 pivot
            if (array[j] <= pivot) {
                i++;

                // 交换 array[i] 和 array[j]
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        // 交换 array[i + 1] 和 array[high] (或 pivot)
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;

        return i + 1;
    }

堆排序

堆排序(Heap Sort)算法是基于选择排序思想的算法,其利用堆结构和二叉树的一些性质来完成数据的排序

堆结构

​ 堆结构是一种完全二叉树,按照从小到大的顺序排序,要求非叶结点的数据要大于或等于其左、右子结点的数据,对结点的左子结点和右子结点的大小没有要求,只规定父结点和子结点数据之间必须满足的大小关系

流程

一个完整的堆排序需要经过反复的两个步骤:构造堆结构和堆排序输出

1.构造堆结构就是把原始无序数据按照前面堆结构的定义进行调整,首先,需要将原始的无序数据放置到一个完全二叉树的各个结点中。

2.然后由完全二叉树的下层向上层逐层对父子结点的数据进行比较,使父结点的数据大于子结点的数据,这里需要使用“筛”运算进行结点数据的调整,直到所有结点最后满足堆结构的条件为止。筛运算主要针对非叶结点进行调整。

   // 堆排序算法
    public static void heapSort(int[] array) {
        int n = array.length;

        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }

        // 一个个地从堆中取出元素
        for (int i = n - 1; i > 0; i--) {
            // 移动当前根到数组末尾
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            // 调整堆
            heapify(array, i, 0);
        }
    }

    // 调整堆
    public static void heapify(int[] array, int n, int i) {
        int largest = i; // 将当前节点设为最大值
        int left = 2 * i + 1; // 左子节点
        int right = 2 * i + 2; // 右子节点

        // 如果左子节点存在且大于当前节点
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }

        // 如果右子节点存在且大于当前节点
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }

        // 如果最大值不是当前节点
        if (largest != i) {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;

            // 递归调整堆
            heapify(array, n, largest);
        }
    }
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!