算法

2023-12-10 09:07| 来源: 网络整理| 查看: 265

排序时间复杂度比较复杂度

常见算法如: 冒泡, 选择, 插入, 归并, 快速, 希尔, 堆排序, 属于比较排序

一. 冒泡排序(Bubble Sort)

执行流程

从头开始比较每一对相邻元素, 如果第一个比第二个大, 交换位置, 执行一轮后, 末尾元素就是最大值排除第一轮中末尾最大元素, 重复执行第一步骤, 直到全部有序 for (int end = array.length - 1; end > 0; end--) { for (int begin = 1; begin 0; end--) { boolean sorted = true;// 使用标识 for (int begin = 1; begin 0; end--) { Integer sortedIndex = 1;// 记录位置, 初始值, 是在数组完全有序的时候可以用 for (int begin = 1; begin 0; end--) { Integer maxIndex = 0; for (int begin = 1; begin 1) - 1; i >= 0; i--) { siftDown(i); } while (heapSize > 1) { // 交换堆顶元素和末尾元素 swap(0, --heapSize); // 对0 位置进行siftDown 操作, 恢复堆的性质 siftDown(0); } private void siftDown(int index) { Integer element = array[index]; int half = heapSize >> 1; while (index < half) { // index必须是非叶子节点 // 默认是左边跟父节点比 int childIndex = (index 0) { child = array[childIndex = rightIndex]; } // 大于等于子节点 if (cmpElements(element, child) >= 0) break; array[index] = child; index = childIndex; } array[index] = element; }

复杂度分析: 最好和最坏, 平均复杂度O(nlogn), 空间复杂度O(1), 属于不稳定排序

五. 插入排序(Insertion Sort)

类似于扑克牌的排序

插入排序执行流程在执行过程中, 插入排序会将序列分为2 部分. 头部时已经排好序的, 尾部为待排序从头开始扫描每一个元素, 每当扫描到一个元素, 就将它插入到头部合适位置, 使得头部数据依然保持有序 for (int begin = 0; begin < array.length; begin++) { int cur = begin; while (cur > 0 && cmp(cur, cur - 1) < 0) { swap(cur, cur - 1); cur--; } } 逆序对

数组的逆序对: , 5 个逆序对

插入排序的时间复杂度与逆序对的数量成正比

逆序对越多, 时间复杂度越高

最坏平均为O(n^2)

最好O(n)

空间复杂度O(1)

属于稳定排序

插入排序优化

将其中的交换改为挪动

先将待排序的元素备份头部有序数据中比待插入元素大的, 都向后移动一位将待插入元素放到最终的合适位置 for (int begin = 0; begin < array.length; begin++) { int cur = begin; E v = array[cur]; while (cur > 0 && cmp(v, array[cur - 1]) < 0) { array[cur] = array[cur - 1]; cur--; } array[cur] = v; } 二分搜索

假设在[begin, end) 范围内搜索某个元素v, mid == (begin + end)/2

如果v < m, 在[begin, mid) 范围二分搜索

如果v > m,在[mid + 1, end) 范围二分搜索

如果v == m, 返回mid

二分搜索 if (array == null || array.length == 0) return -1; int begin = 0; int end = array.length; while (begin < end) { int mid = (begin + end) >> 1; if (v < array[mid]) { end = mid; } else if (v > array[mid]) { begin = mid + 1; } else { return mid; } } return -1;

如果有重复的值, 返回的元素位置不确定

优化, 使用二分搜索

假设在[begin, end) 范围搜索某个元素v, mid == (begin + end) / 2

如果v < m, 去[begin, mid) 范围内二分搜索

如果v >= m, 在[mid + 1, end) 范围二分搜索

搜索10 搜索失败 /** * 二分查找到index 位置元素的待插入位置 * 已经排好序的数组区间范围[0, index) * @param index * @return */ private int search(int index) { int begin = 0; int end = index; while (begin < end) { int mid = (begin + end) >> 1; if (cmp(array[index], array[mid]) < 0) { end = mid; } else { begin = mid + 1; } } return begin; } private void insert(int source, int dest) { E v = array[source]; for (int i = source; i > dest; i--) { array[i] = array[i - 1]; } array[dest] = v; } protected void sort() { for (int begin = 1; begin < array.length; begin++) { insert(begin, search(begin)); } }

二分查找, 只是减少了比较的次数, 但插入排序的平均时间复杂度依然是O(n^2).

六. 归并排序(Merge Sort)

执行流程

不断将当前序列平均分隔成2个子序列, 直到不能再分割, 序列中只剩下一个元素不断将2 个子序列合并成一个有序列, 直到最终只剩下一个有序序列分治合并

分隔

/** * 对[begin, end), 范围的数据进行归并排序 */ private void sort(int begin, int end) { if (end - begin < 2) return; int mid = (begin + end) >> 1; sort(begin, mid); sort(mid, end); merge(begin, mid, end); }

合并

将两个序列合并的思路为：左序列和右序列的中元素挨个比较，将较小的放入新序列中，最后新序列中的元素必然升序。

下图中 li，ri 分别代表指向左、右序列的元素索引，ai 为新序列（合并后的序列）的元素索引；【li】代表左序列 li 位置的元素，【ri】代表右序列 ri 位置的元素，【ai】为新序列 ai 位置的元素；

第一轮：【li】 < 【ri】，【li】放入新数组，【ai】=【li】，li++; ai++; 第二轮：【li】 > 【ri】，【ri】放入新数组，【ai】=【ri】，ri++; ai++; 第三轮：【li】 < 【ri】，【li】放入新数组，【ai】=【li】，li++; ai++； .... 第....轮：左序列已经遍历完毕，直接将右序列剩余元素放入新序列，得到新序列（升序）。右边先结束移动

左边先结束循环, 右边数组不动, 因为剩下的元素已经有序

左边先结束移动

右边先结束循环, 左边的元素, 以此从ai 挪动到右侧, 最后数组有序

黄色代表"++" 操作, 当前正在比较的数值, 且为较小值, 蓝色和紫色保持不变黑色不用考虑,

创建一个左边一般长度的备份数组原地合并

将 array的左半部分[begin, mid)，备份到 leftArray 中；然后将 leftArray 视为左子序列，arrary的右半部分[mid, end] 视为右子序列；将左子序列和右子序列合并到 array 中。备份左边数组

merge 过程

li < ri

array[ai] = leftArray[li]；

li++，ai++;

li >= ri

array[ai] = array[ri];

ri++，ai++;

/** * 将 [begin, mid), 和[mid, end), 范围的序列合并成一个有序列 */ private void merge(int begin, int mid, int end) { int li = 0, le = mid - begin; // 左边数组, 基于leftArray int ri = mid, re = end; // 右边数组, array int ai = begin; // array 的索引, 当前交换需要交换位置的地方 // 备份左边数组 for (int i = li; i < le; i++) { leftArray[i] = array[begin + i]; } // 如果左边还没有遍历结束 while (li < le) { if (ri < re && cmp(array[ri], leftArray[li]) < 0) { array[ai++] = array[ri++]; // 右边值较小, 拷贝到左边数组array } else { array[ai++] = leftArray[li++]; // 左边数组大于等于右边, leftArray 拷贝的左边数组, ai++, 保持稳定性 } } // cmp 的位置为轴点 end--; } else { // 右边元素 0) { begin++; } else { // 左边元素 >= 轴点 array[end--] = array[begin]; break; } } } array[begin] = pivot; return begin; } 不断找轴点分隔后插入轴点

值相同时, 可以分隔的均匀

值相同分隔不均匀八. 希尔排序(Shell Sort)

希尔排序把序列看做是一个矩阵, 分成m 列, 逐列进行排序

m 从某个整数逐渐减为1, 当m 为1 时, 整个序列完全有序, 因此希尔排序也叫递减增量排序

矩阵的列数取决于步长序列, 不同步长序列, 执行效率也不同

希尔本人给出的步长序列是n/(2^k), 例如n 为16, 步长序列为{1, 2, 4, 8}

步长序列分成8个序列分成4个序列分成2个序列分成1个序列

从8 列变成1 列, 逆序对逐渐减少, 每一列排序过程中使用插入排序, 也认为希尔排序是对插入排序的改进版

protected void sort() { List stepSequence = shellStepSequence(); for (Integer step : stepSequence) { sort(step); } } /** * 分成step 列进行排序 * @param step */ private void sort(int step) { for (int col = 0; col < step; col++) { // col, col+step, col+2*step, col+3*step for (int begin = col + step; begin < array.length; begin += step) { int cur = begin; while (cur > col && cmp(cur, cur - step) < 0) { swap(cur, cur - step); cur -= step; } } } }

最好情况是步长为1, 序列几乎有序, 时间复杂度为O(n)

空间复杂度为O(1), 属于不稳定排序

最坏情况, 时间复杂度为O(n^2)

目前已知最好的步长序列, 最坏情况时间复杂度为O(n^(4/3))

步长计算公式 private List sedgewickStepSequence() { List stepSequence = new LinkedList(); int k = 0, step = 0; while (true) { if (k % 2 == 0) { int pow = (int) Math.pow(2, k >> 1); step = 1 + 9 * (pow * pow - pow); } else { int pow1 = (int) Math.pow(2, (k - 1) >> 1); int pow2 = (int) Math.pow(2, (k + 1) >> 1); step = 1 + 8 * pow1 * pow2 - 6 * pow2; } if (step >= array.length) break; stepSequence.add(0, step); k++; } return stepSequence; }

【本文地址】

公司简介

联系我们