网上花店网站建设,上海公司排名100强,wordpress 版权加密,wordpress 移动导航菜单一#xff1a;排序的概念及引入
1.1 排序的概念
1.1 排序的概念 排序#xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的操作。 稳定性#xff1a;假定在待排序的记录序列中#xff0c;存在…一排序的概念及引入
1.1 排序的概念
1.1 排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 1.2常见的排序算法
常见的排序算法有七种分别是直接插入排序希尔排序选择排序堆排序冒泡排序快速排序归并排序 下面我们对这些排序进行一 一讲解。
二插入排序
2.1 直接插入排序
直接插入排序是一种简单的插入排序法其基本思想是
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。实际中我们玩扑克牌时就用了插入排序的思想。 插入排序是一种简单直观的排序算法。它的原理是将待排序的元素逐个插入到已排序序列的适当位置从而形成一个有序序列。
该算法的工作原理如下
从第二个元素开始将其与前面已排序的元素逐个比较找到合适的位置插入。将当前元素与前面已排序的元素进行比较如果当前元素小于前面的元素则将前面的元素后移一位直到找到合适的位置。插入当前元素到合适的位置后继续比较并插入下一个元素。重复上述步骤直到所有元素都被插入到合适的位置。
动图如下 下面是一个使用Java实现插入排序的示例代码
public class InsertionSort {public static void insertionSort(int[] arr) {int n arr.length;for (int i 1; i n; i) {int key arr[i]; // 当前要插入的元素int j i - 1; // 已经排好序的元素的最后一个索引// 将比 key 大的元素向后移动while (j 0 arr[j] key) {arr[j 1] arr[j]; // 向后移动元素j--; // 向前遍历已经排好序的元素}// 插入 key 到合适的位置arr[j 1] key; // 将 key 插入到正确的位置}}public static void main(String[] args) {int[] arr {5, 2, 8, 9, 1, 3};insertionSort(arr); // 使用插入排序算法对数组进行排序System.out.println(排序后的数组);for (int num : arr) {System.out.print(num ); // 输出排序后的数组}}
}
直接插入排序的特性总结
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定
2.2 希尔排序( 缩小增量排序 )
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成多个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。
下面是希尔排序的工作原理
选择一个增量序列增量序列由一系列整数构成通常是递减的最后一个增量必须为1。根据选定的增量序列将待排序的数组分割成若干个子数组每个子数组包含相同间隔的元素。对每个子数组进行插入排序即将每个子数组的元素依次与该子数组中的其他元素进行比较和交换使得子数组中的元素逐渐有序。重复以上步骤缩小增量直至增量为1。最后进行一次完整的插入排序以保证数组的最终有序性。
示图如下
希尔排序的特性总结
希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很 快。这样整体而言可以达到优化的效果。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的希尔排 序的时间复杂度都不固定
动图如下
因为咋们的gap是按照Knuth提出的方式取值的而且Knuth进行了大量的试验统计我们暂时就按照On1.25到O1.6 * n1.25 来算。
下面是一个使用Java实现的希尔排序示例代码
public class ShellSort {public static void shellSort(int[] arr) {int n arr.length;// 初始化增量为数组长度的一半int gap n / 2;while (gap 0) {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;}// 缩小增量gap / 2;}}public static void main(String[] args) {int[] arr {9, 5, 2, 7, 1, 3, 6, 8, 4};System.out.println(原始数组);for (int num : arr) {System.out.print(num );}System.out.println();shellSort(arr);System.out.println(排序后的数组);for (int num : arr) {System.out.print(num );}}
}希尔排序稳定性不稳定
三选择排序
3.1直接选择排序
当我们需要对一个数组进行排序时选择排序是一种简单而直观的算法。它的工作原理是选择数组中最小的元素将它与数组的第一个元素交换位置。然后选择剩余元素中最小的元素将它与数组的第二个元素交换位置。以此类推直到整个数组排序完成
动图如下
public class SelectionSort {public static void main(String[] args) {// 创建一个整数数组int[] arr {64, 25, 12, 22, 11};// 调用选择排序方法selectionSort(arr);// 输出排序后的数组System.out.println(排序后的数组);for(int i0; i arr.length; i){System.out.print(arr[i] );}}public static void selectionSort(int[] arr) {// 获取数组长度int n arr.length;// 遍历整个数组for (int i 0; i n-1; i) {// 假设当前索引为 i 的元素是最小值int minIndex i;// 在剩余的元素中寻找最小值的索引for (int j i1; j n; j) {// 如果找到比当前最小值还小的值则更新最小值的索引if (arr[j] arr[minIndex]) {minIndex j;}}// 将最小值与当前位置交换int temp arr[minIndex];arr[minIndex] arr[i];arr[i] temp;}}
}
【直接选择排序的特性总结】
直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定
3.2堆排序
堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 堆排序具体的讲解可以查看这篇文章
【堆排序的特性总结】
堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定
四交换排序
4.1冒泡排序
冒泡排序是一种简单但效率较低的排序算法。它的基本思想是通过不断比较相邻的两个元素并交换位置从而将较大或较小的元素逐渐“冒泡”到数组的顶部或底部。这个过程会不断重复直到数组中的所有元素都按照顺序排列。
下面是一个详细注释的 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 - 1 - i; j) {// 如果当前元素比下一个元素大就交换它们的位置if (arr[j] arr[j 1]) {int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}}}public static void main(String[] args) {int[] arr {64, 34, 25, 12, 22, 11, 90};System.out.println(原始数组);for (int num : arr) {System.out.print(num );}// 调用冒泡排序bubbleSort(arr);System.out.println(\n排序后的数组);for (int num : arr) {System.out.print(num );}}
}动图如下 【冒泡排序的特性总结】
冒泡排序是一种非常容易理解的排序时间复杂度O(N^2)空间复杂度O(1)稳定性稳定
4.2快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
4.2.1Hoare版
实现思路 1: 首先从数组的左端和右端分别设置一个指针即i和j以及选择一个基准值pivot。
2:通过循环从数组的右端开始向左查找找到第一个小于基准值的元素的下标将该下标赋给j。然后从数组的左端开始向右查找找到第一个大于基准值的元素的下标将该下标赋给i。
3: 在找到两个元素的下标后交换它们的位置将小于基准值的元素移动到基准值的左边大于基准值的元素移动到基准值的右边。然后继续循环直到左指针i大于等于右指针j。
最后将基准值放在正确的位置上将其与左指针i所指向的元素进行交换。这样基准值左边的元素都小于基准值右边的元素都大于基准值。
需要注意的是若选择最左边的数据作为key则需要right先走若选择最右边的数据作为key则需要left先走
动图如下
private static int partition(int[] array, int left, int right) {// 设置左右指针和基准值int i left;int j right;int pivot array[left];// 在左指针小于右指针的条件下进行循环while (i j) {// 从右往左找到第一个小于基准值的元素的下标while (i j array[j] pivot) {j--;}// 从左往右找到第一个大于基准值的元素的下标while (i j array[i] pivot) {i;}// 交换找到的两个元素的位置swap(array, i, j);}// 将基准值放在正确的位置上swap(array, i, left);// 返回基准值的下标return i;
}
4.2.2挖坑法
实现思路 1: 首先在函数内部定义两个指针i和j分别指向分区的左侧和右侧。初始时将left作为基准元素的索引即基准元素为array[left]。 2: 然后通过循环不断将大于基准元素的元素移动到右侧将小于基准元素的元素移动到左侧。具体的操作是先从右侧开始找到小于或等于基准元素的元素然后将该元素移动到左侧指针i的位置。 3: 接着从左侧开始找到大于或等于基准元素的元素然后将该元素移动到右侧指针j的位置。如此反复进行直到指针i和j相遇。 4: 最后将基准元素放置到它最终的位置上也就是指针i的位置。这样基准元素左侧的元素都小于或等于它右侧的元素都大于或等于它。 5: 最后返回基准元素的索引i用于后续的分区。
注意若在最左边挖坑则需要R先走若在最右边挖坑则需要L先走
动图如下
private static int partition(int[] array, int left, int right) {// 设置指针i和j分别指向分区的左侧和右侧int i left;int j right;// 设置基准元素为分区的第一个元素int pivot array[left];// 开始循环直到指针i和j相遇while (i j) {// 从右侧开始寻找小于或等于基准元素的元素while (i j array[j] pivot) {j--;}// 找到后将该元素移动到左侧指针i的位置array[i] array[j];// 从左侧开始寻找大于或等于基准元素的元素while (i j array[i] pivot) {i;}// 找到后将该元素移动到右侧指针j的位置array[j] array[i];}// 将基准元素放置到它最终的位置上array[i] pivot;// 返回基准元素的索引用于后续的分区return i;
}
4.2.3前后指针
实现思路
我们首先定义了两个变量 cur 和 prev它们都指向数组的起始位置cur beginprev begin - 1。我们选择数组的最后一个元素作为基准元素将其索引保存在变量 keyi 中。然后我们开始遍历数组从头到尾比较每个元素与基准元素的大小。如果当前元素小于基准元素并且 prev 不等于 cur则将当前元素与 prev 指向的元素交换位置。随后我们将 cur 向后移动一位。当遍历完整个数组后我们将基准元素与 prev 指向的元素交换位置以确保基准元素的位置在整个数组中是正确的。这样数组被分成了两部分左边是小于基准元素的部分右边是大于基准元素的部分。基准元素的位置为 keyi。接下来我们对左半部分begin 到 keyi - 1和右半部分keyi 1 到 end分别进行递归调用。重复以上步骤直到子数组的长度为 1 或 0即递归终止条件。
//快速排序法 前后指针版本
void QuickSort2(int* arr, int begin, int end)
{if (begin end)return;int cur begin, prev begin - 1;int keyi end;while (cur ! keyi){if (arr[cur] arr[keyi] prev ! cur){swap(arr[cur], arr[prev]);}cur;}swap(arr[prev],arr[keyi]);keyi prev;//[begin,keyi -1]keyi[keyi1,end]QuickSort2(arr, begin, keyi - 1);QuickSort2(arr, keyi 1, end);}
快速排序优化
三数取中法选key 三个数中取中间的数为基准递归到小的子区间时可以考虑使用插入排序
快速排序总结
快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序时间复杂度O(N*logN)空间复杂度O(logN)特殊情况如果数据本身有序或者逆序那么时间复杂度为 O N2稳定性不稳定
时间复杂度示图
五归并排序
5.1 基本思想
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 动图 归并排序总结
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定
5.2 代码实现
public class MergeSort {// 归并排序入口函数public int[] mergeSort(int[] array) {// 特殊情况处理当数组为空或只有一个元素时无需排序直接返回if (array null || array.length 1) {return array;}// 调用归并排序算法进行排序mergeSort(array, 0, array.length - 1);return array;}// 归并排序递归函数private void mergeSort(int[] array, int start, int end) {// 当前排序范围只有一个元素无需继续拆分if (start end) {return;}// 找到当前排序范围的中间位置int mid start (end - start) / 2;// 递归拆分左半部分mergeSort(array, start, mid);// 递归拆分右半部分mergeSort(array, mid 1, end);// 合并左右两部分排序结果merge(array, start, mid, end);}// 归并两个有序数组private void merge(int[] array, int start, int mid, int end) {// 创建一个临时数组保存合并的结果int[] temp new int[end - start 1];int i start; // 左半部分起始位置int j mid 1; // 右半部分起始位置int k 0; // 临时数组的索引// 遍历左右两部分数组依次取出较小的元素放入临时数组中while (i mid j end) {if (array[i] array[j]) {temp[k] array[i];} else {temp[k] array[j];}}// 处理剩余的元素while (i mid) {temp[k] array[i];}while (j end) {temp[k] array[j];}// 将临时数组中的元素拷贝回原数组中for (i 0; i temp.length; i) {array[start i] temp[i];}}
}下面对这段代码进行详细的讲解
首先我们定义了一个公共类MergeSort用于实现归并排序算法。mergeSort方法是入口函数接收一个整型数组作为参数并返回一个排序后的整型数组。在这个方法中首先判断特殊情况即当数组为空或只有一个元素时无需排序直接返回原数组否则调用归并排序算法进行排序。归并排序的核心是递归拆分和合并两个有序数组。mergeSort方法是一个递归函数接收一个整型数组array和两个整型变量start和end作为参数表示当前排序范围的起始位置和结束位置。首先判断当前范围是否只有一个元素如果是则无需继续拆分否则找到当前范围的中间位置mid分别递归拆分左半部分和右半部分然后将拆分后的结果合并起来。merge方法用于合并两个有序数组。它接收一个整型数组array和三个整型变量start、mid和end作为参数表示需要合并的两个有序数组在原数组中的位置。首先创建一个临时数组temp用于保存合并的结果长度为end-start1。然后设置三个指针i、j和k分别表示左半部分数组的起始位置、右半部分数组的起始位置和临时数组的索引。接下来遍历左右两部分数组依次取出较小的元素放入临时数组中直到其中一个部分的元素取完。最后如果左半部分数组还有剩余的元素将其全部复制到临时数组中如果右半部分数组还有剩余的元素也将其全部复制到临时数组中。最后将临时数组中的元素拷贝回原数组中完成合并过程。
5.3海量数据的排序问题
外部排序排序过程需要在磁盘等外部存储进行的排序 前提内存只有 1G需要排序的数据有 100G因为内存中因为无法把所有数据全部放下所以需要外部排序而归并排序是最常用的外部排序
先把文件切分成 200 份每个 512 M分别对 512 M 排序因为内存已经可以放的下所以任意排序方式都可以进行 2路归并同时对 200 份有序文件做归并过程最终结果就有序了
六排序总结
6.1排序算法复杂度及稳定性分析 6.2各个排序的比较
排序方法最好平均最坏空间复杂度稳定性冒泡排序O(n)O(n2)O(n2 )O(1)稳定插入排序O(n)O(n2)O(n2)O(1)稳定选择排序O(n^2)O(n2)O(n2)O(1)不稳定希尔排序O(n)O(n1.3)O(n2)O(1)不稳定堆排序O(n*log n)O(n*log n)O(n*log n)O(1)不稳定快速排序O(n*log n)O(n*log n)O(n2)O(log n)~O(n)不稳定归并排序O(n*log n)O(n*log n)O(n*log n)O(n)稳定
