建设初级中学网站,哪些网站图片做海报好,学校网站建设多少钱,哈尔滨网站建设公司那家好4.交换排序 基本思想#xff1a;所谓交换#xff0c;就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置 交换排序的特点是#xff1a;将键值较大的记录向序列的尾部移动#xff0c;键值较小的记录向序列的前部移动。
4.1 冒泡排序 冒泡排序#xff08…4.交换排序 基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置 交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
4.1 冒泡排序 冒泡排序Bubble Sorting即通过对待排序的序列从前往后依次比较相邻元素的值若发现逆序则交换位置使较大的元素逐渐移动到后部
4.1.1 算法分析 下面的分析以将序列{2, 9, 7, 10, 30}从小到大排序为例 其基本思想就是在每一趟排序最终实现将该趟得到的最大的数移到序列的最后端 核心操作就是通过比较相邻两个元素实现当相邻的两个元素逆序的时候我们就交换它们。 第1趟排序 第1趟排序共比较了4次将最大的数30冒泡到了序列的尾部。 第2趟排序 由于第一趟排序已经将最大是数30给冒泡到了最末端因此在本次排序中不需要再比较最后一个元素故此本趟共比较了3次将子序列前四个元素中最大的数10整个序列中倒数第二大的数冒泡到了子序列的尾端原序列的倒数第二个位置。 第3趟排序 在第三趟排序时同理倒数两个元素位置已经确定即第一、第二大的数已经排好位置只需要再将倒数第三大的数确认即可。故比较2次实现倒数第三大的数9的位置确定。 第4趟排序 在第四趟排序时只有第一、第二个元素的位置还不确定只需要比较一次若逆序则交换即可。到此排序算法完成原序列已经排序成为一个递增的序列 小结 一共进行了数组大小-1次趟排序即外层循环arr.length-1次每趟排序进行了逐趟减小次数的比较即内层循环arr.length-i-1次i从0依次增加。 4.1.2 代码实现 详细代码如下
/*** version 1.0* 冒泡排序*/public static void main(String[] args) {int[] array {2,9,7, 10, 30};//排序前System.out.println(排序前: Arrays.toString(array));//冒泡排序for (int i 0; i array.length - 1; i) {System.out.println(第 (i1) 趟排序开始!);for (int j 0; j array.length - i - 1; j) {//如果前面的数比后面的数大则交换if(array[j] array[j1]){//交换int temp array[j];array[j] array[j1];array[j1] temp;}System.out.println(------第 (j1) 趟排序: Arrays.toString(array));}System.out.println(第 (i1) 趟排序完成: Arrays.toString(array));System.out.println();}//输出排序后的结果System.out.println(排序后: Arrays.toString(array));} 结果展示 排序前:[2, 9, 7, 10, 30] 第1趟排序开始! ------第1趟排序: [2, 9, 7, 10, 30] ------第2趟排序: [2, 7, 9, 10, 30] ------第3趟排序: [2, 7, 9, 10, 30] ------第4趟排序: [2, 7, 9, 10, 30] 第1趟排序完成: [2, 7, 9, 10, 30] 第2趟排序开始! ------第1趟排序: [2, 7, 9, 10, 30] ------第2趟排序: [2, 7, 9, 10, 30] ------第3趟排序: [2, 7, 9, 10, 30] 第2趟排序完成: [2, 7, 9, 10, 30] 第3趟排序开始! ------第1趟排序: [2, 7, 9, 10, 30] ------第2趟排序: [2, 7, 9, 10, 30] 第3趟排序完成: [2, 7, 9, 10, 30] 第4趟排序开始! ------第1趟排序: [2, 7, 9, 10, 30] 第4趟排序完成: [2, 7, 9, 10, 30] 排序后:[2, 7, 9, 10, 30] 进程已结束,退出代码0 4.1.3 算法的不足及优化 我们仔细观察一下我们上述数组在进行冒泡法时每一个外循环后的结果 我们发现其实在第一次外循环结束之后我们的当前数组已经完成了冒泡法整个算法的最终结果但是由于我们的算法规定它依旧要跑array.length-1次外循环故此我们需要完成代码的优化当我们的数组提前完成排序后就要提前结束外循环终止我们的冒泡排序 我们可以发现一个无序的数组在经过冒泡算法的排序之后这些元素的位置在最后都是固定的每一次的内循环相应的元素可以理解为都是往那个自己最终的位置上跑但是当一次内循环之后发现我们当前的元素位置和该次内循环开始之前的元素位置一样没有发生变化这时候我们可以确认我们的元素都已经到达了自己的最终位置可以提前终止冒泡算法不在进行其他的外循环 所以最终的解决方案就是我们设置一个flag标志位来判断当前内循环前后数组的元素有没有发生顺序的变化优化代码如下图所示 public static void main(String[] args) {int[] array {5, 1, 2, 3, 4};//排序前System.out.println(排序前: Arrays.toString(array));boolean flag false; //用于标记是否进行了交换true则说明进行了交换false表示无//冒泡排序for (int i 0; i array.length - 1; i) {System.out.println(第 (i1) 趟排序开始!);for (int j 0; j array.length - i - 1; j) {//如果前面的数比后面的数大则交换if(array[j] array[j1]){//交换flag true; //标记进行了交换int temp array[j];array[j] array[j1];array[j1] temp;}System.out.println(------第 (j1) 趟排序: Arrays.toString(array));}System.out.println(第 (i1) 趟排序完成: Arrays.toString(array));System.out.println();if (!flag){//如果没有进行交换则直接退出说明排序已经完成break;}else {//回退flag false;}}//输出排序后的结果System.out.println(排序后: Arrays.toString(array));}测试结果 如图所示经过优化后我们相比于之前的代码减少了两次内循环提前结束了冒泡算法大大的节省了时间资源
4.1.4 冒泡排序的特性总结 1、冒泡排序是一种非常容易理解的排序 时间复杂度O(N^2) 空间复杂度O(1) 稳定性稳定 2、什么时候最快 当输入的数据已经是正序时我们的内循环和外循环的执行次数比较少 4.2 快速排序 快速排序是对冒泡排序的一种改进。基本思想为通过一趟排序将要排序的数据分割为独立的两个部分其中一部分的所有数据比另外一部分的所有数据要小然后按照此方法对这两部分分别进行快速排序整个过程可以递归进行以此达到整个数据变成有序序列。
4.2.1 算法分析递归 快速排序算法通过多次比较和交换来实现排序其排序流程如下 (1)首先设定一个分界值通过该分界值将数组分成左右两部分。 (2)将大于或等于分界值的数据集中到数组右边小于分界值的数据集中到数组的左边。此时左边部分中各元素都小于分界值而右边部分中各元素都大于或等于分界值。 (3)然后左边和右边的数据可以独立排序。对于左侧的数组数据又可以取一个分界值将该部分数据分成左右两部分同样在左边放置较小值右边放置较大值。右侧的数组数据也可以做类似处理。 (4)重复上述过程可以看出这是一个递归定义。通过递归将左侧部分排好序后再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后整个数组的排序也就完成了。 下面来举例来详细的分析 首先我们会把数组中的一个数当作基准数然后从两边进行检索。 其次按照如下步骤进行 1、先从右边检索比基准数小的 2、再从左边检索比基准数大的 3、一旦检索到就停下并将检索到的两个元素进行交换 4、重复上述步骤直到检索相遇则替换基准数并更新区间递归进行最终序列会变得有序 接下来就以{618029537}为例详细来分析一下步骤具体分析一下第一趟排序以6为基准数的步骤 1、红色块标识基准数left、right初始位置如图所示 2、right不断向左移动寻找比基准数6小的数如图所示找到了3 3、此时left开始移动不断向右移动寻找比基准数大的数找到了8这时left、right都找到了对应的数进行交换 4、right继续向左寻找比基准数6小的数找到后停止移动此时left继续向右寻找比基准数大的数当left与right都找到对应的数后再次将二者的数值进行交换。 5、重复上述步骤一直到left与right相遇二者共同指向了5的位置则将基准数与该位置的数进行交换这样就可以观察到6的左边都是比6小的右边都是比6大的。 6、该过程需要递归进行直到序列有序。即以5为基准数递归6左边的区间再以9为基数递归6右边的区间反复进行直到left right退出。 4.2.2 代码实现 冒泡法代码如下
public static void quickSort(int[] arr, int left, int right) {//边界条件if (left right){return;}//定义基准数和左右指针int l left;int r right;int base arr[left];//循环将比基准数小的放在左边比基准数大的放在右边while (l ! r){//先从右边找比基准数小的停下while (arr[r] base l r){r--;}//从左边找比基准数大的停下while (arr[l] base l r){l;}//此时已经找到对应的l 和 r进行交换int temp arr[l];arr[l] arr[r];arr[r] temp;}//至此基准数两边都按照需要排好了只需要将基准数与lr相遇的位置进行交换arr[left] arr[l];arr[l] base;//打印中间结果System.out.println(Arrays.toString(arr));//先向左找quickSort(arr, left, r-1);//向右递归quickSort(arr, l1, right);} 测试代码
public static void main(String[] args) {int[] arr {6,1,8,0,2,9,5,3,7};quickSort(arr, 0, arr.length-1);System.out.println(排序后: Arrays.toString(arr));
} 测试结果 4.2.3 快速排序非递归实现 思路 建立一个栈 先让一组数据的起点入栈 再让一组数据的终点出栈 然后两次出栈分别作为该数据的起点与终点 然后经过我们上面所写的方法进行排序后 再将两组数据进行入栈 以此循环直到栈为空 代码实现 //快速排序递归实现public int[] quickSortPlus(int[] array) {int[] arr Arrays.copyOf(array,array.length);DequeInteger stack new LinkedList();int left 0;int right array.length-1;int pivot 0;stack.push(left);stack.push(right);while (!stack.isEmpty()) {right stack.pop();left stack.pop();pivot partition(arr,left,right);if(pivot left1) {stack.push(left);stack.push(pivot-1);}if(pivot right-1) {stack.push(pivot1);stack.push(right);}}return arr;}private int partition(int[] array,int left,int right) {int tmp array[left];while (left right) {while (left right array[right] tmp) {right--;}array[left] array[right];while (left right array[left] tmp) {left;}array[right] array[left];}array[left] tmp;return left;}4.2.4 特性总结 1. 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫 快速 排序 2. 时间复杂度 O(N*logN) 3. 空间复杂度O(logN) 4. 稳定性不稳定 5. 归并排序 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并归并排序核心步骤图解 5.1算法分析 合并相邻有序子序列 ...以此类推 ... ... 如果当其中的一个子序列全部转移到temp数组中时另外未空的子序列的元素直接全部按当前顺序移入到temp中即可。 5.2 代码实现 代码部分
static int count 0;public static void main(String[] args) {int[] arr {10, 6, 7, 1, 3, 4, 2,9};int[] temp new int[arr.length];mergeSort(arr, 0, arr.length - 1, temp);System.out.println(归并排序后: arr[] Arrays.toString(arr));}//归并排序public static void mergeSort(int[] arr, int left, int right, int[] temp){if (left right){int mid left - (left - right) / 2;//向左递归分解mergeSort(arr, left, mid, temp);//向右递归分解mergeSort(arr, mid 1, right, temp);//排序 合并merge(arr, left, mid, right, temp);}}/*** 合并的方法* param arr 排序的原始数组* param left 左边有序序列的初始索引* param mid 中间索引* param right 右边索引* param temp 中转数组*/public static void merge(int[] arr, int left, int mid, int right, int[] temp){int i left; //初始化i左边有序序列的初始索引int j mid 1; //初始化j右边有序序列的初始索引int t 0; //指向temp数组的当前索引//先把左右两边有序数据按照规则填充到temp数组直到左右两边有一边处理完毕while (i mid j right){if (arr[i] arr[j]){temp[t] arr[i];t;i;}else {temp[t] arr[j];t;j;}}//把剩余的一方依次填充到temp数组while (i mid){ //左边序列还有剩余的元素temp[t] arr[i];}while (j right){ //右边序列还有剩余的元素temp[t] arr[j];}//将temp数组的元素拷贝到arr//拷贝每次小序列t 0;int tempLeft left;while (tempLeft right){arr[tempLeft] temp[t];}count;System.out.println(第 count 次合并: arr[] Arrays.toString(arr));} 测试结果展示 分析 {10, 6, 7, 1, 3, 4, 2,9}被拆分成了{10, 6}{7, 1}{3, 4}{2, 9} 第一次合并{6, 10}有序 第二次合并{1, 7}有序 第三次合并: {1 6 7 10}有序 第四次合并{3, 4}有序 第五次合并{2, 9}有序 第六次合并: { 2349}有序 第七次合并{1234679,10}有序 5.3 特点总结 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 时间复杂度O(N*logN) 空间复杂度O(N) 稳定性稳定 5.4 海量数据的排序问题 外部排序排序过程需要在磁盘等外部存储进行的排序 前提内存只有 1G需要排序的数据有 100G 因为内存中因为无法把所有数据全部放下所以需要外部排序而归并排序是最常用的外部排序 1. 先把文件切分成 200 份每个 512 M 2. 分别对 512 M 排序因为内存已经可以放的下所以任意排序方式都可以 3. 进行 2路归并同时对 200 份有序文件做归并过程最终结果就有序了
6.排序算法复杂度及稳定性分析 详解总概图如下所示 ps本次的内容就到这里了本文的相关内容吸取了博主【兴趣使然黄小黄 】的相关思想如果大家感兴趣的话可以去了解一下他如果喜欢的话还请一键三连哦
