国外网站 服务器,小内存wordpress,好的建筑设计网站推荐,中国室内设计公司排名前十强文章目录 ⚽冒泡排序⚾算法步骤#x1f3a8;算法优化#x1f94e;代码实现#xff1a;#x1f3c0;冒泡排序的特性总结 #x1f9ed;快速排序⚽算法思路#x1f4cc;思路一#xff08;Hoare版#xff09;#x1f4cc;思路二#xff08;挖坑法#xff09;#x1f4c… 文章目录 ⚽冒泡排序⚾算法步骤算法优化代码实现冒泡排序的特性总结 快速排序⚽算法思路思路一Hoare版思路二挖坑法思路三前后指针 代码实现快速排序优化规模较小时的优化三数取中法 快速排序递归实现代码实现 快速排序特性总结 归并排序⚽基本思想算法步骤代码实现递归实现归并排序归并排序特性总结海量数据的排序问题 排序算法复杂度及稳定性分析⭕总结 ⚽冒泡排序
冒泡排序Bubble Sort也是一种简单直观的排序算法。它重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢浮到数列的顶端。
⚾算法步骤
比较相邻的元素。如果第一个比第二个大就交换他们两个。
对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。
针对所有的元素重复以上的步骤除了最后一个。
持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 算法优化
冒泡排序还有一种优化算法就是立一个 flag当在一趟序列遍历中元素没有发生交换则证明该序列已经有序
直接返回就好
代码实现 public int[] bubbleSort(int[] arr) {int[] array Arrays.copyOf(arr,arr.length);for(int i 1;i array.length ; i ) {Boolean a true;for(int j 0; j array.length - i; j) {if(array[j] array[j 1]) {swap(array,j,j1);a false;}}if(a) {return array;}}return array;}private void swap (int[] arr,int m,int n) {int tmp arr[m];arr[m] arr[n];arr[n] tmp;}冒泡排序的特性总结 冒泡排序是一种非常容易理解的排序 时间复杂度O(N^2) 空间复杂度O(1) 稳定性稳定 什么时候最快 当输入的数据已经是正序时都已经是正序了我还要你冒泡排序有何用啊。 什么时候最慢 当输入的数据是反序时写一个 for 循环反序输出数据不就行了干嘛要用你冒泡排序呢我是闲的吗。
快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止
⚽算法思路
思路一Hoare版
步骤为 选取基准值 从数组右-左找到比基准值小于或等于的值的下标 从数组右-左找到比基准值大于或等于的值的下标 交换这两下标的值 继续执行二操作直到操作2与操作3相遇 将基准值放在相遇位置
如下图所示 思路二挖坑法
步骤为 选取基准值后记录下基准值假设该下标为空相当于是个“坑” 从右-左找小于或等于基准值的值就将该数放入坑中然后该下标变为新的坑 从左-右找小于或等于基准值的值就将该数放入坑中然后该下标变为新的坑 回到步骤2继续执行直到操作2与操作3所找数相同 将记录下的基准值放回坑里
图示如下
思路三前后指针
步骤及其动图如下
代码实现 public int[] quickSort(int[] array) {int[] arr Arrays.copyOf(array,array.length);int left 0;int right arr.length - 1;quick(arr,left,right);return arr;}private void quick(int[] array,int begin,int end) {if(begin end) {return;}int centre partition1(array,begin,end);//int centre partition2(array,begin,end);//int centre partition3(array,begin,end);quick(array,centre 1,end);quick(array,begin,centre - 1);}//挖坑法private int partition1(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;}//Hoare版private int partition2(int[] array,int left,int right) {int tmp array[left];int i left;while (left right) {while (left right array[right] tmp) {right--;}while (left right array[left] tmp) {left;}swap(array,left,right);}swap(array,left,i);return left;}//前后指针法private int partition3(int[] array,int left,int right) {int prev left ;int cur left1;while (cur right) {if(array[cur] array[left] array[prev] ! array[cur]) {swap(array,cur,prev);}cur;}swap(array,prev,left);return prev;}private void swap (int[] arr,int m,int n) {int tmp arr[m];arr[m] arr[n];arr[n] tmp;}快速排序优化
规模较小时的优化
每次递归的时候数据都是再慢慢变成有序的
当数据量少且趋于有序的时候我们可以直接使用插入排序进行优化 private void quick(int[] array,int begin,int end) {if(begin end) {return;}if(end - begin 20) {//插入排序//......return;}int centre partition1(array,begin,end);//int centre partition2(array,begin,end);//int centre partition3(array,begin,end);quick(array,centre 1,end);quick(array,begin,centre - 1);}三数取中法
如果在选取基数时我们发现如果基数一边总是没有数代码的执行次数会增加很多
所以我们的解决方法为 选取数组第一个数、中间的数、和最后一个数进行比较
三数中间的数作为每次的基数
寻找中间数代码如下 private int midThree(int[] array,int left,int right) {int mid (left right) / 2;//6 8if (array[left] array[right]) {if (array[mid] array[left]) {return left;} else if (array[mid] array[right]) {return right;} else {return mid;}} else {//array[left] array[right]if (array[mid] array[right]) {return right;} else if (array[mid] array[left]) {return left;} else {return mid;}}}使用如下 private int partition1(int[] array,int left,int right) {int tmp midThree(array,left,right);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;}//Hoare版private int partition2(int[] array,int left,int right) {int tmp midThree(array,left,right);int i left;while (left right) {while (left right array[right] tmp) {right--;}while (left right array[left] tmp) {left;}swap(array,left,right);}swap(array,left,i);return left;}快速排序递归实现
实现思路 建立一个栈 先让一组数据的起点入栈 再让一组数据的终点出栈 然后两次出栈分别作为该数据的起点与终点 然后经过我们上面所写的方法进行排序后 再将两组数据进行入栈 以此循环直到栈为空
代码实现 //快速排序递归实现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;}快速排序特性总结 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 时间复杂度O(N*logN) 空间复杂度O(logN) 稳定性不稳定
归并排序
⚽基本思想
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤
算法步骤 申请空间使其大小为两个已经排序序列之和该空间用来存放合并后的序列 设定两个指针最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置 重复步骤 3 直到某一指针达到序列尾 将另一序列剩下的所有元素直接复制到合并序列尾。 代码实现 public void mergeSort1(int[] array) {mergeSortFunc(array,0,array.length-1);}private void mergeSortFunc(int[] array,int left,int right) {if(left right) {return;}int mid (leftright) / 2;mergeSortFunc(array,left,mid);mergeSortFunc(array,mid1,right);merge(array,left,right,mid);}private void merge(int[] array,int start,int end,int mid) {int s1 start;//int e1 mid;int s2 mid1;//int e2 end;int[] tmp new int[end-start1];int k 0;//tmp数组的下标while (s1 mid s2 end) {if(array[s1] array[s2]) {tmp[k] array[s1];}else {tmp[k] array[s2];}}while (s1 mid) {tmp[k] array[s1];}while (s2 end) {tmp[k] array[s2];}for (int i 0; i tmp.length; i) {array[istart] tmp[i];}}递归实现归并排序
public static void mergeSort(int[] array) {int gap 1;while (gap array.length) {// i gap * 2 当前gap组的时候去排序下一组for (int i 0; i array.length; i gap * 2) {int left i;int mid leftgap-1;//有可能会越界if(mid array.length) {mid array.length-1;}int right midgap;//有可能会越界if(right array.length) {right array.length-1;}merge(array,left,right,mid);}//当前为2组有序 下次变成4组有序gap * 2;}}private void merge(int[] array,int start,int end,int mid) {int s1 start;//int e1 mid;int s2 mid1;//int e2 end;int[] tmp new int[end-start1];int k 0;//tmp数组的下标while (s1 mid s2 end) {if(array[s1] array[s2]) {tmp[k] array[s1];}else {tmp[k] array[s2];}}while (s1 mid) {tmp[k] array[s1];}while (s2 end) {tmp[k] array[s2];}for (int i 0; i tmp.length; i) {array[istart] tmp[i];}}归并排序特性总结 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 时间复杂度O(N*logN) 空间复杂度O(N) 稳定性稳定
海量数据的排序问题
外部排序排序过程需要在磁盘等外部存储进行的排序
前提内存只有 1G需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下所以需要外部排序而归并排序是最常用的外部排序 先把文件切分成 200 份每个 512 M 分别对 512 M 排序因为内存已经可以放的下所以任意排序方式都可以 进行 2路归并同时对 200 份有序文件做归并过程最终结果就有序了
排序算法复杂度及稳定性分析 ⭕总结
关于《【数据结构】 七大排序详解(贰)——冒泡排序、快速排序、归并排序》就讲解到这儿感谢大家的支持欢迎各位留言交流以及批评指正如果文章对您有帮助或者觉得作者写的还不错可以点一下关注点赞收藏支持一下
