【数据结构

2024-07-04 03:30| 来源: 网络整理| 查看: 265

文章目录插入排序直接插入排序折半插入排序希尔排序(缩小增量排序) 选择排序简单选择排序堆排序交换排序冒泡排序快速排序Hoare法“挖坑”法归并排序基数排序计数排序

插入排序直接插入排序算法基本思想：（从大到小排序）在一个非递减的有序数组中，要新增一个元素x，有两个方法： 1.从数组的头部开始向后遍历，寻找第一个比x 大的元素y，从y元素开始的所有元素全部向后移动，最后将x元素插入数组。（×） 2.从数组的尾部开始向后向前遍历，寻找第一个比x小的元素k，从k元素开始，后面每个元素都向后移动，最后将元素x插入数组。（√）在这里插入图片描述

在这里插入图片描述那么我们应该选择哪种方式呢？其实仔细思考一下，我们很容易会想到选择第2种方式，原因也很简单：在寻找第一个比x小的元素k时，我们可以边把比 x 大的元素往后移动。

因此，我们对一个数组排序时，可以从第2个元素开始，看作是把元素插入一个已经有序的数组中。具体代码如下：

public static void insertSort1(int[] array) { for(int i = 1; i = 0; j--) { if(array[j] > tmp) { array[j+1] = array[j]; } else { // 此时array[j] < array[i]，且 j + 1下标为 array[i] 在已排序元素中的位置 break; } } array[j+1] = tmp; } }

时间复杂度：O(n²)。最好情况是数组已经有序，只需比较n-1次，时间复杂度为O(n)；最坏情况是数组为待排序顺序的逆序，需要(n-1)(n-1)…1次，时间复杂度为O(n²)。空间复杂度：O(1)。记录每次待排序的元素的额外空间。稳定性：稳定。适用情况：数组基本有序的情况下。

折半插入排序

算法基本思想：（从大到小排序）折半插入排序的本质也是在一个已经有序的数组的插入一个元素，与直接插入排序的唯一区别是：折半插入排序是利用二分查找找到那个合适的插入位置。

二分查找的基本步骤：将要插入元素跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0（即 left>right ，数组中不存在指定元素）。在这里插入图片描述注意事项：（1）若插入元素在数组不存在（如上图所示情况），则插入元素的下标应为 right+1，因此需要将 right+1 下标开始的所有元素全部向后移动。（2）若插入元素与 mid 下标的元素相等，为了操作的统一性，我们可以使 right=mid-1，这样一来，待插入元素的下标也为 right+1 ，接下来同样将 right+1 下标开始的所有元素全部向后移动。

具体代码实现如下：

public static void binaryInsertSort(int[] array) { for (int i = 1; i = 0; parent-- ) { shiftDown(array,parent, array.length); } } // root表示当前调整的数的根结点下标，len表示待调整的整个数组的长度 private static void shiftDown(int[] array, int root, int len) { int parent = root; int child = root * 2 + 1; // 防止出现需要多次调整的情况 while(child = right) return; // 在 partition方法中，完成分区操作，并返回 pivot的下标 int pivot = partition(array, left, right); // 对 pivot 的左右区间进行递归操作 quick(array,pivot + 1, right); quick(array,left, pivot - 1); } private static int partition(int[] array, int left, int right) { int tmp = array[left]; int i = left; // 记录基准值的下标 while(left

【本文地址】

【数据结构

【数据结构

今日新闻

推荐新闻