龙港 网站建设,嘉兴网站建设运营,网站建设找推推蛙,做一个简单的公司网站要多少钱#x1f495;每一天都是值得被热爱的#x1f495; 作者#xff1a;Mylvzi 文章主要内容#xff1a;常见排序算法实现 1.排序的概念 所谓排序#xff0c;就是按照特定顺序重新排列序列的操作 排序的稳定性#xff1a;
当一个序列中存在相同的元素时 排序过… 每一天都是值得被热爱的 作者Mylvzi 文章主要内容常见排序算法实现 1.排序的概念 所谓排序就是按照特定顺序重新排列序列的操作 排序的稳定性
当一个序列中存在相同的元素时 排序过后 他们出现的顺序和原来序列的顺序一致就说明此排序稳定否则就不稳定
内部排序 内部排序是指对数据集合完全加载到内存中进行排序的过程。这种排序方法适用于数据量较小可以在计算机内存中容纳整个数据集的情况。常见的内部排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。内部排序的优点是速度较快因为所有数据都在内存中不需要频繁的读取和写入操作。 外部排序 外部排序是指对大规模数据集合进行排序的方法数据量太大无法一次性加载到内存中。这种排序方法涉及将数据分割成适当大小的块然后在内存中对这些块进行排序最后将排序后的块写回磁盘或其他存储介质并合并这些块以得到最终的排序结果。外部排序常用于需要处理大量数据的场景比如数据库系统中对大型表进行排序或外部存储设备上的数据排序。常见的外部排序算法包括归并排序、多路归并排序等这些算法允许对大规模数据进行高效排序因为它们能够有效地利用磁盘I/O操作。 常见的排序算法 1.插入排序 插入排序是一种非常简单的排序 比如在玩扑克牌时 在发牌阶段 我们每抽取一张牌 都要从后往前去比较大小 把抽取的牌插入到合适的位置 所以插入排序就是将待排序的元素抽取的牌插入到一个已经有序的序列之中 代码实现
/*** 插入排序 在一个已经存在的序列中 插入到合适位置* 时间复杂度* 最好情况O(N)* 最坏情况:O(N^2)* 空间复杂度* O(1)* 稳定性是一个稳定的排序* 所以对于一个有序的序列来说 插入排序就是最快的*/public static void insertSort(int[] arr) {for (int i 1; i arr.length; i) {int tmp arr[i];int j i-1;for (; j 0; j--) {// tmp j向后挪动if(arr[j] tmp) {arr[j1] arr[j];}else {// 要插入的元素已经是最大的了 不需要再去比较了//arr[j1] tmp;break;}}// 跳出循环有两种情况 1.tmp是最小的需要插入到第一个元素 此时j-1 结束条件是j不0了 2.else语句中的breakarr[j1] tmp;}} 2.希尔排序缩小增量排序 是根据插入排序的优点来进行优化的插入排序 我们知道插入排序对于有序化高的序列来说速度是更快的也就是说一个序列有序化越高使用插入排序的时间复杂度就越低速度就越快
所以对于一大堆的数据来说我们可以先进行“预排”使其有序化程度越来越高从而实现效率更高
设置gap 利用插入排序的思想 分组进行优化 组数不断降低 直到最后为1 最后一个进行排序时 序列的有序化程度已经很高 速度很快
希尔排序看似繁琐 实则提高了效率 虽然要进行多次插入排序 但时间优化了很多 主要原因在于以下几个方面 1.分组会使得待排序的数据量减小 每次排序的数据量少 时间快 2.当gap 1时也就是要对整个序列进行排序 虽然数据量很大 但是有序化程度高 时间快 希尔排序的分析过 代码实现
/*** 希尔排序 优化的插入排序* 先进行预排序 跳跃式进行分组 分的组数逐渐减少 直到组数为1* 分组优化* 时间复杂度O(N^1.3)* 空间复杂度O(1)* 稳定性不稳定*/public static void shellSort(int[] arr) {int gap arr.length;while (gap 1) {gap / 2;shell(arr,gap);}}private static void shell(int[] arr,int gap) {for (int i gap; i arr.length; i) {int tmp arr[i];int j i-gap;for (; j 0; j- gap) {// tmp j向后挪动if(arr[j] tmp) {arr[jgap] arr[j];}else {// 要插入的元素已经是最大的了 不需要再去比较了//arr[j1] tmp;break;}}arr[jgap] tmp;}}
3.选择排序 选择排序也是一个比较简单的排序 其核心思想在于每次都要选择一个最小的/最大的元素位于最左边 选择排序无论你的顺序如何 都要遍历整个数组去寻找最小值/最大值 所以对于初始顺序不敏感
代码实现 public static void selectSort(int[] arr) {for (int i 0; i arr.length; i) {int minIndex i;for (int j i1; j arr.length; j) {if(arr[j] arr[minIndex]) {minIndex j;}}swap(arr,i,minIndex);}}private static void swap(int[] arr,int i,int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}
4.堆排 堆排 就是利用堆的特性进行排序的一种方式 思路
1.看条件创建堆 升序--》大根堆 降序--》小根堆
2.交换首元素和末元素 向下调整 代码实现 /*** 堆排 从小到大* 1.创建大根堆* 2.交换 向下调整*/public static void heapSort(int[] arr) {creatBigHeap(arr);int end arr.length-1;while(end 0) {swap(arr,0,end);shiftDown(arr,0,end);end--;}}private static void creatBigHeap(int[] arr) {for (int parent (arr.length-1-1)/2; parent 0; parent--) {shiftDown(arr,parent,arr.length);}}private static void shiftDown(int[] arr, int parent, int end) {int child 2*parent1;while (child end) {// 判断左右孩子谁是最大的if(child1 end arr[child] arr[child1]) {child;}if(arr[child] arr[parent]) {swap(arr,child,parent);parent child;child 2*parent1;}else {break;}}}
5.快速排序 核心思路分而治之 概念任取待排序元素序列中的某元 素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有 元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 快速排序 本质上是一个递归的过程 有序时 会出现单叉树 此时时间复杂度最高 达到0(N^2) 代码实现 /*** 快速排序*时间复杂度O(N*logN); 每次分而治之需要遍历的数字都是N 最好情况是一颗完全二叉树 高度为logN 所以时间复杂度是N*logn** 容易溢出 占用内存大* 三种写法hore法 挖坑法推荐 前后指针法* 递归方法 最好的情况是一种完全二叉树*/public static void quickSort(int[] arr) {quick(arr,0,arr.length-1);}private static void quick(int[] arr,int start,int end) {if(start end) return;if(end - start 1 7) {insertSortRange(arr,start,end);return;}midOfThree(arr,start,end);// 获得按照规则交换后的基准值的下标int pivot parttion(arr,start,end);// 遍历左子树 分而治之quick(arr,start,pivot-1);// 遍历右子树 分而治之quick(arr,pivot1,end);}public static void insertSortRange(int[] arr,int begin,int end) {for (int i 1; i end; i) {int tmp arr[i];int j i-1;for (; j begin; j--) {// tmp j向后挪动if(arr[j] tmp) {arr[j1] arr[j];}else {// 要插入的元素已经是最大的了 不需要再去比较了//arr[j1] tmp;break;}}// 跳出循环有两种情况 1.tmp是最小的需要插入到第一个元素 此时j-1 结束条件是j不0了 2.else语句中的breakarr[j1] tmp;}}private static void midOfThree(int[] arr, int left, int right) {int mid (left right) / 2;if(arr[left] arr[right]) swap(arr,left,right);// 保证左边元素是较小值if(arr[mid] arr[right]) swap(arr,mid,right);// 保证中间元素是较小值if(arr[mid] arr[left]) swap(arr,mid,left);// 此时保证left下标的值是中间大小}private static int parttionHoare(int[] arr,int left,int right) {int i left;// 每次都选取第一个元素为基准值int key arr[left];// 遍历交换// left 从左往右 找比Key大的// right 从右往左 找比key小的while (left right) {/*** 为什么先走右边* 先走right保证他们相遇时 一定是比key值小的数据* 如果先走left 相遇时碰到的一定是比key大的 此时再交换 则key的左边存在比key大的数据了*/// 先从右边找while (left right arr[right] key) { // 等号必须要取 万一两个都是6 会陷入死循环right--;}// 此时right下标的元素比key小while (left right arr[left] key) {left;}swap(arr,left,right);}// 使基准值位于中间即左边都比key小 右边都比key大swap(arr,i,left);return left;}/*** 快排的优化* 1.三数取中法解决特殊情况 --》第一个数字是最小的 或者是最大的 减少了树的高度 开辟的空间更小* 2.小区间内采用插入排序 减少递归的次数但时间有可能会增加 降低了内存的要求*/
parttion的第二种写法挖坑法 // 挖坑法private static int parttion2(int[] arr,int left,int right) {// 每次都选取第一个元素为基准值int key arr[left];// 遍历交换// left 从左往右 找比Key大的// right 从右往左 找比key小的while (left right) {// 先从右边找while (left right arr[right] key) { // 等号必须要取 万一两个都是6 会陷入死循环right--;}// 此时right下标的元素比key小arr[left] arr[right];while (left right arr[left] key) {left;}arr[right] arr[left];}// 使基准值位于中间即左边都比key小 右边都比key大arr[left] key;return left;}parttion的第三种写法前后指针法 private static int parttion(int[] arr,int left,int right) {// 前后指针法int prev left;int cur left1;while (cur right) {// 后面那个条件cur和prev之间必须至少间隔一个元素// 如果没有间隔元素 交换后又把比left大的移到了左边if(arr[cur] arr[left] arr[prev] ! arr[cur]) {swap(arr,cur,prev);}cur;}// 遍历完整个数组了swap(arr,left,prev);return prev;}
注意 1.parttion一共有三种写法推荐以挖坑法为先 前后指针或者Hoare法次之 2.为什么快速排序要先走right因为这样能够保证left和right最后相遇的位置的元素是比key小的元素交换过后仍满足条件 快速排序的非递归写法
// 快排的非递归写法public static void quickSortNor(int[] arr) {StackInteger stack new Stack();int left 0;int right arr.length-1;int pivot parttion(arr,left,right);// 如果等于 证明pivot左边只有一个数据 此时不需要再去排列了 下面的right同理if(pivot-1 left) {stack.push(left);stack.push(pivot-1);}if (pivot 1 right) {stack.push(pivot1);stack.push(right);}while(!stack.isEmpty()) {right stack.pop();left stack.pop();pivot parttion(arr,left,right);if(pivot-1 left) {stack.push(left);stack.push(pivot-1);}if (pivot 1 right) {stack.push(pivot1);stack.push(right);}}} 6.冒泡排序法不做讲解
/*** 冒泡排序* 时间复杂度O(N^2) 最好加了优化O(N)* 空间复杂度O(1)* 稳定性好*/public static void bubbleSort(int[] arr) {for (int i 0; i arr.length; i) {boolean flg false;for (int j 0; j arr.length-1-i; j) {if(arr[j] arr[j1]) {swap(arr,j,j1);flg true;}}if(!flg) {return;}}}
7.归并排序 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使 子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 分解左边 分解右边 合并 代码实现
/*** 归并排序* 时间复杂度O(n*logN)* 空间复杂度O(N);* 稳定** 分解左边 分解右边 归并(合并两个有序数组)** 稳定的排序冒泡 插入 归并*/public static void mergeSort(int[] arr) {mergeSortFunc(arr,0,arr.length-1);}private static void mergeSortFunc(int[] arr, int left, int right) {if(left right) return;int mid (leftright) / 2;mergeSortFunc(arr,left,mid);mergeSortFunc(arr,mid1,right);merge(arr,left,mid,right);}private static void merge(int[] arr, int left, int mid, int right) {// 这里边的思路相当于是 合并两个有序序列int[] tmpArr new int[right-left1];int k 0;// 分别定义两个需要合并的数组的首元素的下标int s1 left;int s2 mid1;// 遍历两个数组while(s1 mid s2 right) {if(arr[s1] arr[s2]) {tmpArr[k] arr[s1];}else {tmpArr[k] arr[s2];}}// 出循环证明有一个数组不为空while(s1 mid) {tmpArr[k] arr[s1];}while (s2 right) {tmpArr[k] arr[s2];}// 将排序好的元素返回给原数组for (int i 0; i tmpArr.length; i) {arr[ileft] tmpArr[i];}}
非递归写法
// 归并排序的非递归写法public static void mergeSortNor(int[] arr) {int gap 1;while(gap arr.length) {for (int i 0; i arr.length; i 2*gap) {int left i;int mid igap-1;int right midgap;if(mid arr.length) {mid arr.length-1;}if(right arr.length) {right arr.length-1;}merge(arr,left,mid,right);}gap * 2;}} 8.计数排序 设置一个计数数组 用于记录待排序数组中相应元素出现的次数 并按照下标排列 最后返回给原数组 /*** 计数排序* 时间复杂度O(N范围* 空间复杂度O(范围)* 适用于数据范围集中 数据量较小的情况* 稳定性好*/public static void countSort(int[] arr) {// 1.得到数组的最大值和最小值数组的下标只能从0开始int minVal arr[0];int maxVal arr[0];for (int i 0; i arr.length; i) {if (arr[i] minVal) {minVal arr[i];}if (arr[i] maxVal) {maxVal arr[i];}}//2.遍历arr 并在计数数组中存放对应的次数int[] count new int[maxVal - minVal 1];for (int i 0; i arr.length; i) {count[arr[i] - minVal];}//3.重新写入到原数组int index 0;for (int i 0; i count.length; i) {while(count[i] 0) {arr[index] i minVal;index;count[i]--;}}}
总结
1. 稳定的排序插入排序 冒泡排序 归并排序
2.希尔排序的时间复杂度很复杂到现在也没有一个具体的结论 3.初始序列顺序对排序的影响 选择排序无论你的顺序如何 都要遍历整个数组去寻找最小值/最大值 所以对于初始顺序不敏感
4.表格汇总
