企业网站主页设计模板,免费影视网站入口大全,网络服务主要包括哪些服务,wordpress登陆注册文章目录排序概念稳定性#xff08;重要#xff09;应用 - 举例1.、各大商城的价格从低到高等2、中国大学排名常见的排序算法#xff08;8 种#xff09;- 总览直接插入排序模拟实现 - 插入排序稳定性分析结论希尔排序思考原理科学家的分组思维模拟实现 - 希尔排序总结选择…
文章目录排序概念稳定性重要应用 - 举例1.、各大商城的价格从低到高等2、中国大学排名常见的排序算法8 种- 总览直接插入排序模拟实现 - 插入排序稳定性分析结论希尔排序思考原理科学家的分组思维模拟实现 - 希尔排序总结选择排序直接选择排序 - 原理优化代码如下附图双向选择排序 了解代码如下堆排序代码冒泡排序代码如下 - 未优化代码优化思维代码如下 - 优化未优化 和 优化代码 运行速度比较快速排序 - 重点原理总结程序框架完善 partition 部分代码细节部分总程序 - 未优化快速排序 的 时间 与 空间复杂度分析堆排序 与 快排 的区别细节拓展if语句中 比较大小的代码中 等号是不能省略的目前版本的 快排代码 不支持 大量数据进行排序 - 会导致栈溢出。基准值的选择 - 优化前的知识补充快速排序几数取中法 优化优化总结拓展 快速排序 - 非递归实现非递归实现快速排序的思维代码如下归并排序 - 重点知识铺垫 二路合并二路合并的代码如下归并排序 - 原理难点1 - 如何将一个数组拆分成一个个单独数组【每个数组里只包含一个元素】。难点2 - 合并归并排序的程序框架合并程序的完善附图归并排序 - 总程序归并排序 - 时间与空间复杂度分析、稳定性归并排序 - 非递归实现代码如下海量数据的排序问题小总结排序总结不常见的排序 - 不基于比较的排序了解基数排序代码如下捅排序计数排序代码如下附图 - 是目前的计数排序稳定排序
概念 排序就是使一串记录按照其中的某个 或 某些关键字的大小递增 或 递减 的 排列起来的操作。 平时的上下文中如果提到排序通常指的是 排升序非降序。 通常意义上的排序都是指的原地排序in place sort 原地排序就是指在排序过程中不申请多余的存储空间只利用原来存储待排数据的存储空间进行比较和交换的数据排序。 稳定性重要 两个相等的数据如果经过排序后排序算法能保证其相对位置不发生变化则我们称该算法是具备稳定性的排序算法。 应用 - 举例
1.、各大商城的价格从低到高等 2、中国大学排名 常见的排序算法8 种- 总览 直接插入排序 插入排序非常简单仅次于冒泡排序。 根据这个思维第一个数据是有序的也就是说在我们遍历的时候是从下标1 开始的。 具体的操作见下图 模拟实现 - 插入排序
import java.util.Arrays;public class DirectInsertionSort {/** 时间复杂度 O(N^2)* 最好情况 O(N) 数组有序的情况* 空间复杂度O(1) 只有 一个 tmp 变量是常驻的* 稳定性稳定* */public static void insertionSort(int[] array){for(int i 1;i array.length;i){int tmp array[i];int j i - 1;for( ; j 0;j-- ){// 前移if(tmp array[j]){array[j 1] array[j];}else{break;}}// 插入【无论是找到了合适插入的位置还是不存在比 tmp更小的值j自减到 -1.执行的代码都是一样的】array[j1] tmp;}}public static void main(String[] args) {int[] array {23,45,56,68,8,9};insertionSort(array);System.out.println(Arrays.toString(array));}}稳定性分析 结论 一个稳定的排序可以实现为 不稳定的排序。 但是一个本身就不稳定的排序是 无法变成 稳定的排序。 直接插入排序 是 有序的。 它的时间复杂度是 O(N^2)最好情况:O(N【数组有序】 也就是说对于直接插入排序数据越有序越快 由此不难联想到直接插入排序 有时候 会用于 优化 排序。 【假设假设我们有一百万个数据需要排序在排序的过程中区间越来越小数据越来越有序。直接插入排序的时间复杂度为 O(N),N 越来越小那么使用 直接插入排序是不是越来越快也就是说直接插入排序 有时候会 用于 排序优化】 直接插入排序经常使用在 数据量不多且整体数据趋于有序的。 import java.util.Random;public class DirectInsertionSort {/** 时间复杂度 O(N^2)* 空间复杂度O(1) 只有 一个 tmp 变量是常驻的* 稳定性稳定* */public static void insertionSort(int[] array){for(int i 1;i array.length;i){int tmp array[i];int j i - 1;for( ; j 0;j-- ){if(tmp array[j]){array[j 1] array[j];}else{break;}}array[j1] tmp;}}// 有序public static void test1(int capacity){int[] array new int[capacity];for (int i 0; i capacity; i) {array[i] i;}// 记录开始排序开始时间long start System.currentTimeMillis();insertionSort(array);// 记录开始排序结束时间long end System.currentTimeMillis();// 输出 整个排序过程的时间System.out.println(end - start);}// 无序public static void test2(int capacity){int[] array new int[capacity];Random random new Random();for (int i 0; i capacity; i) {array[i] random.nextInt(capacity);}// 记录开始排序开始时间long start System.currentTimeMillis();insertionSort(array);// 记录开始排序结束时间long end System.currentTimeMillis();// 输出 整个排序过程的时间System.out.println(end - start);}public static void main(String[] args) {test1(10000);test2(10000);}
}希尔排序
思考 假设现有 1 00 00 个 数据如果对着组数据进行排序使用插入排序。 时间复杂度为 O(N^2)【最坏情况逆序的情况】 故 1 00 00 * 1 00 00 1 亿量化 它不是 1 万个数据嘛。那么我们可以不可以这么去想将这 一万个数据拆分成 100 组【每组100个数据】对其中一组进行直接插入排序的时间复杂度为 100*100 1 00 00量化这样的分组还有99个也就是将这一百组使用直接插入排序的时间复杂度为 1 00 00 * 1 00 1 百万量化。 有没有发现分组过后时间复杂度效率 提高很多由1亿 变成了 1百万。 也就是说如果采用分组的思想我们会发现 时间复杂度会有一个很大的改变。 而这种分组的思想 就是 希尔排序。 原理 希尔排序又称缩小增量法。希尔排序法的基本思想是先选定一个整数 n把待排序文件中所有数据分成 n 组所有距离为 数据量 / n 的 分在同一组。并且对每一组内的数据进行排序。然后重复上述 分组 和 排序工作。当分组的组数为 1 是所有数据 在进行 一个排序。 1、希尔排序 是对直接插入排序的优化。 2、当 group 1 时都是预排序目的是让数组更接近于有序。当 group 1时数组已经接近有序了这样就会更快。对于整体而言可以达到优化的效果。 那么问题来了我们怎去确定分多少组而且越分越少。 【取自清华大学出版的一本书《数据结构》】 科学家的分组思维 现在这组数据我们相当于只排序了一组数据就走人了。数组整体还不是有序的。那么我们该怎么解决这个问题往下看 模拟实现 - 希尔排序
import java.util.Arrays;public class ShellSort {/** 时间复杂度和增量有关系所以无法得出准确的时间复杂度* 但只需要记住在一定的范围里希尔排序的时间复杂度为 O(N^1.3 ~ N^1.5)* 空间复杂度为 O(1)* 稳定性不稳定* 判断稳定性的技巧如果在比较的过程中 发生了 跳跃式交换。那么就是不稳定的排序。* */public static void shell(int[] array,int group){for (int i group; i array.length; i 1) {int tmp array[i];int j i-group;for (; j 0; j-group) {if(tmp array[j]){array[jgroup] array[j];}else{break;}}array[jgroup] tmp;}}public static void shellSort(int[] array){int group array.length;// 预排序while(group 1){// 第一次分组委 数组的长度即 头尾判断。// 其后每次分组个数缩小一倍。shell(array,group);group / 2;}// 最后调整shell(array,1);}public static void main(String[] args) {int[] array {12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};shellSort(array);System.out.println(Arrays.toString(array));}
}总结 其实 希尔排序就是一个直接插入排序。 选择排序
直接选择排序 - 原理 优化 定义 一个 变量 用来记录 此时的 i 后面最小值的下标。等 j 遍历完了最小值的下标也就拿到了。此时再进行交换。 这样就不必让上面那样遇到比 i下标元素 小的就交换。 代码如下
import java.util.Arrays;public class SelectSort {/** 稳定性 不稳定 见附图* 时间复杂度O(N^2) 》》 外层循环 n -1内层循环 n -1* 空间复杂度O(1)* */public static void selectSort(int[] array){for (int i 0; i array.length-1; i) {int index i;for (int j i 1; j array.length; j) {if(array[index] array[j]){index j;}}int tmp array[i];array[i] array[index];array[index] tmp;}}public static void main(String[] args) {int[] array {12,6,10,3,5};selectSort(array);System.out.println(Arrays.toString(array));}
}附图 双向选择排序 了解 每一次从无序区间选出最小 最大的元素存放在无序区间的最前和最后直到全部待排序的数据元素排完 。 代码如下
import java.util.Arrays;public class SelectSortOP {public static void selectSortOP(int[] array){int low 0;int high array.length - 1;// [low,high] 表示整个无序区间while(low high){int min low;int max low;for (int i low1; i high; i) {if(array[i] array[min]){min i;}if(array[i] array[max]){max i;}}swap(array,min,low);if(max low){max min;}swap(array,max,high);low;high--;}}public static void swap(int[] array,int x,int y){int tmp array[x];array[x] array[y];array[y] tmp;}public static void main(String[] args) {int[] array {9, 5, 2, 7, 3, 6, 8 };selectSortOP(array);System.out.println(Arrays.toString(array));}
}堆排序 基本原理也是选择排序只是不在使用遍历的方式查找无序区间的最大的数而是通过堆来选择无序区间的最大的数。 注意 排升序要建大堆排降序要建小堆. 这个我就不讲因为我在堆/优先级中讲的很清楚 有兴趣的可以点击 链接关键字 跳转到该文章该内容在 文章目录最后面。 这里我们就直接上代码。 代码
import java.util.Arrays;public class HeapSort {public static void main(String[] args) {int[] array {12,8,5,4,10,15};creationHeap(array);// 建堆的时间复杂度O(N)System.out.println(Arrays.toString(array));heapSort(array);// 堆排序的时间复杂度O(N * log2 N)// 空间复杂度O(1)System.out.println(Arrays.toString(array));}// 创建一个大根堆public static void creationHeap(int[] array){for (int parent (array.length-1-1)/2; parent 0; parent--) {shiftDown(array,parent,array.length);}}public static void heapSort(int[] array){/** 时间复杂度O(N * log2 N)* 空间复杂度O(1)* 稳定性不稳定* */int end array.length - 1;while(end0){int tmp array[end];array[end] array[0];array[0] tmp;shiftDown(array,0,end);end--;}}// 向下调整public static void shiftDown(int[] array,int parent,int len){int child parent * 2 1;// 做孩纸while(child len){// 获取左右子树最大值的下标if(child1 len (array[child] array[child1])){child;}if(array[child] array[parent]){int tmp array[child];array[child] array[parent];array[parent] tmp;parent child;child parent * 2 1;}else{break;}}}
}冒泡排序 代码如下 - 未优化
import java.util.Arrays;/** 时间复杂度O(N^2) 【无论是最好情况还是最坏情况时间复杂度都不变】* 空间复杂度O(1)* 稳定性稳定【未发生跳跃式交换】* */
public class BubbleSort {public static void bubbleSort(int[] array){// 比较的趟数 数组的长度 - 1 【 0 ~ 3 一共 4趟】for (int i 0; i array.length-1; i) {// 比较完一趟后可以比较的元素个数减一。【因为靠后的数据已经有序】// 内循环中之所以要减一个 1是因为防止 下面的if语句 发生 数组越界异常for(int j 0;j array.length-1-i;j){if(array[j] array[j1]){int tmp array[j];array[j] array[j1];array[j1] tmp;}}}}public static void main(String[] args) {int[] array {12,6,10,3,5};bubbleSort(array);System.out.println(Arrays.toString(array));}
}代码优化思维 代码如下 - 优化
import java.util.Arrays;public class BubbleSort {/** 时间复杂度O(N^2)* 最好情况【数组有序】可以达到 O(N)* 空间复杂度O(1)* 稳定性稳定【未发生跳跃式交换】* */public static void bubbleSort(int[] array){for (int i 0; i array.length-1; i) {boolean flag true;for(int j 0;j array.length-1-i;j){if(array[j] array[j1]){int tmp array[j];array[j] array[j1];array[j1] tmp;flag false;// 表示这一趟比较数组是无序的}}// flag trueif(flag){break;}}}public static void main(String[] args) {// 前半段无序后半段有序int[] array {2,3,1,4,5};bubbleSort(array);System.out.println(Arrays.toString(array));}
}未优化 和 优化代码 运行速度比较
public class BubbleSort {// 优化public static void bubbleSort2(int[] array){for (int i 0; i array.length-1; i) {boolean flag true;for(int j 0;j array.length-1-i;j){if(array[j] array[j1]){int tmp array[j];array[j] array[j1];array[j1] tmp;flag false;}}// flag trueif(flag){break;}}}// 未优化public static void bubbleSort1(int[] array){for (int i 0; i array.length-1; i) {for(int j 0;j array.length-1-i;j){if(array[j] array[j1]){int tmp array[j];array[j] array[j1];array[j1] tmp;}}}}public static void main(String[] args) {int[] array new int[10000];for (int i 0; i array.length; i) {array[i] i;}long start System.currentTimeMillis();bubbleSort2(array);// 优化long end System.currentTimeMillis();System.out.println(end - start);// 输出排序所需时间start System.currentTimeMillis();bubbleSort1(array);// 未优化end System.currentTimeMillis();System.out.println(end - start);//输出排序所需时间}
}快速排序 - 重点
原理 1、从待排序区间选择一个数作为基准值pivot 2、Partition分割遍历整个待排序区间将比基准值小的可以包含相等的放到基准值的左边将比基准值大的可以包含相等的放到基准值的右边。 3、采用分治思想对左右两个小区间按照同样的方式处理直到小区间的长度 1.代表已经有序或者小区间的长度 0代表没有数据。 总结 快速排序其实说白了 和二叉树]很像先根再左后右。利用递归去实现 程序框架
public class QuickSort {public static void quickSort(int[] array){quick(array,0, array.length);}public static void quick(int[] array,int start,int end){if(start end){return;}int pivot partiton(array,start,end);quick(array,start,pivot-1);// 递归左边quick(array,pivot1,end);// 递归右边}// 分割 - 找基准private static int partiton(int[] array,int start,int end){}
}完善 partition 部分 // 分割 - 找基准private static int partiton(int[] array,int start,int end){int tmp array[start];while(start end){while(start end array[end] tmp){end--;}// 此时 end 下标 元素的值 是 小于 tmp的。array[start] array[end];while(startend array[start] tmp){start;}//此时 start 下标元素的值 是 大于 tmp的。array[end] array[start];}// start 和 end 相遇了将 tmp 赋予 它们相遇下标指向的空间array[start] tmp;return start;}代码细节部分 总程序 - 未优化
import java.util.Arrays;public class QuickSort {/** 时间复杂度O(N^2) 【数据有序或者逆序的情况】* 最好情况【每次可以均匀的分割待排序序列】O(N * log2 N)* 空间复杂度O(N)[单分支的一棵树]* 最好log2 N* 稳定性不稳定* */public static void quickSort(int[] array){quick(array,0, array.length-1);}public static void quick(int[] array,int start,int end){if(start end){return;}int pivot partiton(array,start,end);quick(array,start,pivot-1);// 递归左边quick(array,pivot1,end);// 递归右边}// 分割 - 找基准private static int partiton(int[] array,int start,int end){int tmp array[start];while(start end){while(start end array[end] tmp){end--;}// 此时 end 下标 元素的值 是 小于 tmp的。array[start] array[end];while(startend array[start] tmp){start;}array[end] array[start];}array[start] tmp;return start;}public static void main(String[] args) {int[] array {6,1,2,7,9,3,4,5,10,8};quickSort(array);System.out.println(Arrays.toString(array));}
}快速排序 的 时间 与 空间复杂度分析 堆排序 与 快排 的区别 细心的朋友会发现 堆排序 和 快排 的 时间复杂度在最好情况下 都是N* log2 N。 那么两者又有什么区别 堆排序无论最好还是最坏情况时间复杂度都是N* log2 N。空间复杂度 O(1) 那么又为什么快排 比 堆排序 要快 其实再细一点说 在两个排序的时间复杂度都为 N* log2 N时其实连着前面还有 一个 k【K * N* log2 N 】只不过快排前面的K要小一点。所以快排要快一点。 在对空间复杂度没有要求的情况 快排 对空间复杂度有要求的情况或者说对数据的序列也要要求 堆排 细节拓展
if语句中 比较大小的代码中 等号是不能省略的 当 下面框选的代码 没有等号时会造成死循环。 我就改了一下末尾元素的值。 那么问题来了为什么没有等号就死循环了 所以在 写快排的时候比较大小的代码记住一定要加上等号 目前版本的 快排代码 不支持 大量数据进行排序 - 会导致栈溢出。 这是因为 我们递归的太深了1百万数据4百万字节。 1TB等于1024GB;1GB等于1024MB;1MB等于1024KB;1KB等于1024Byte(字节);1Byte等于8bit(位); 有的朋友会说这才多大啊栈怎么会被挤爆 这是因为在递归的时候开辟的栈帧【函数的信息参数等等等…都有】所以每次开辟的栈帧不止 4byte。故栈被挤爆了。 所以我们要优化快排的 代码。【优化数据有序的情况】 基准值的选择 - 优化前的知识补充 1、选择边上左或者右 【重点上面使用的就是这种方法】 2、随机选择针对 有序数据【了解】 3、几数取中常见的就是三数取中array[left]array[mid] array[right]中 大小为 中间值的为基准值【优化的关键】 快速排序几数取中法 优化
import java.util.Arrays;public class QuickSort {/** 时间复杂度O(N^2) 【数据有序或者逆序的情况】* 最好情况【每次可以均匀的分割待排序序列】O(N * log2 N)* 空间复杂度O(N)[单分支情况]* 最好log2 N* 稳定性不稳定* */public static void quickSort(int[] array){quick(array,0, array.length-1);}public static void quick(int[] array,int start,int end){if(start end){return;}// 在找基准之前先确定 start 和 end 的 中间值。[三数取中法]int midValIndex findMidValIndex(array,start,end);//将它 与 start 交换。这样后面的程序就不用改动了。swap(array,start,midValIndex);int pivot partiton(array,start,end);quick(array,start,pivot-1);// 递归左边quick(array,pivot1,end);// 递归右边}// 确定基准值下标private static int findMidValIndex(int[] array,int start,int end){// 确定 start 和 end 的中间下标int mid start ((end - start)1);// start end/ 2// 确定 mid、start、end 三个下标谁指向的元素是三个元素中的中间值if(array[end] array[start]){if(array[start] array[mid]){return start;}else if(array[mid] array[end]){return end;}else{return mid;}}else{// array[start] array[end]if(array[end] array[mid]){return end;}else if(array[mid] array[start]){return start;}else {return mid;}}}// 交换两个下标元素private static void swap(int[] array,int x,int y){int tmp array[x];array[x] array[y];array[y] tmp;}// 分割 - 找基准private static int partiton(int[] array,int start,int end){int tmp array[start];while(start end){while(start end array[end] tmp){end--;}// 此时 end 下标 元素的值 是 小于 tmp的。array[start] array[end];while(startend array[start] tmp){start;}array[end] array[start];}array[start] tmp;return start;}// 有序public static void test1(int capacity){int[] array new int[capacity];for (int i 0; i capacity; i) {array[i] i;}long start System.currentTimeMillis();quickSort(array);long end System.currentTimeMillis();System.out.println(end - start);}public static void main(String[] args) {test1(100_0000);int[] array {6,1,2,7,9,3,4,5,10,6};quickSort(array);System.out.println(Arrays.toString(array));}
} 优化总结 1、选择基准值很重要通常使用几数取中法 2、partition 过程中把和基准值相等的数也选择出来 3、待排序区间小于一个阈(yù)值【临界值】 随着不断的划分基准数组逐渐趋于有序而区间随着递归也在减小。所以利用 直接插入排序的特性【越有序越快】来进一步优化 快排。 拓展 快速排序 - 非递归实现
非递归实现快速排序的思维 代码如下
import java.util.Arrays;
import java.util.Stack;public class QuickSortNonRecursion {public static void quickSort(int[] array){StackInteger stack new Stack();int left 0;int right array.length-1;int pivot partiton(array,left,right);if(pivot left1){stack.push(left);stack.push(pivot-1);}if(pivot right -1){stack.push(pivot1);stack.push(right);}while(!stack.isEmpty()){right stack.pop();left stack.pop();pivot partiton(array,left,right);if(pivotleft1){stack.push(left);stack.push(pivot-1);}if (pivotright-1){stack.push(pivot1);stack.push(right);}}}public static int partiton(int[] array,int start,int end){int tmp array[start];while(startend){while(startend array[end] tmp){end--;}array[start] array[end];while (startend array[start] tmp){start;}array[end] array[start];}array[start] tmp;return start;}public static void main(String[] args) {int[] array {12,5,8,1,10,15};quickSort(array);System.out.println(Arrays.toString(array));}
} 归并排序 - 重点
知识铺垫 二路合并 将两个有序表合并成一个有序表称为二路归并。【简单说就是 将两个有序数组合并为一个有序数组称为二路合并】 二路合并的代码如下
import java.util.Arrays;public class MergeSort {/*
* array1 已有序
* array2 已有序
* */public static int[] mergeArrays(int[] array1,int[] array2){if(array1 null || array2 null){return array1 null ? array2: array1;}int[] arr new int[array1.length array2.length];int i 0;// arr 的 遍历变量int s1 0;//array1 的 遍历变量int s2 0;//array2 的 遍历变量while(s1 array1.length s2 array2.length){if(array1[s1] array2[s2]){arr[i] array2[s2];
// s2;
// i;}else{arr[i] array1[s1];
// s1;
// i;}}// 循环结束有一个数组的元素已经全部存入// 接下来就是将另一个数组的元素放入 arr 中while (s1 array1.length){arr[i] array1[s1];
// i;
// s1;}while (s2 array2.length){arr[i] array2[s2];
// i;
// s2;}return arr;}public static void main(String[] args) {int[] array1 {1,6,7,10};int[] array2 {2,3,4,9};int[] mergeArray mergeArrays(array1,array2);System.out.println(Arrays.toString(mergeArray));}
} 归并排序 - 原理 归并排序MERGE - SORT是建立在归并操作上的一种有效的排序算法该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 难点1 - 如何将一个数组拆分成一个个单独数组【每个数组里只包含一个元素】。 难点2 - 合并 归并排序的程序框架
public class MergeSort {// 归并排序的调用“接口”public static int[] mergeSort(int[] array){if(array null){return array;}mergeSortFunc(array,0,array.length-1);return array;}// 归并排序实现private static void mergeSortFunc(int[] array,int low,int high){if(low high){return;}// 递归分解
// int mid (high low) 1int mid low ((high - low) 1);mergeSortFunc(array,low,mid);// 左边mergeSortFunc(array,mid1,high);// 右边// 合并merge(array,low,mid,high);}private static void merge(int[] array,int low,int mid,int high){}
} 合并程序的完善 其实这个并不难跟我前面做的知识铺垫的思路是一样的。 需要注意的是 1、我们的参数中 只有一个数组 2、数组 arr 只是一个临时数组用来存储 合并之后的结果。 3、在将 arr 数组 存储的结果转移到 原本数组的时候注意赋值的位置 private static void merge(int[] array,int low,int mid,int high){// 获取 区间之内的元素个数加一 是因为 零下标元素也算一个元素。int[] arr new int[high - low 1];// 左边 区间 【你可以理解为 有序数组 array1的起始与结束下标位置】int start1 low;int end1 mid;// 右边 区间【你可以理解为 有序数组 array2的起始与结束下标位置】int start2 mid1;int end2 high;int i 0;while (start1 end1 start2 end2){if(array[start1] array[start2]){arr[i] array[start2];}else{arr[i] array[start1];}}while(start1 end1){arr[i] array[start1];}while(start2 end2){arr[i] array[start2];}// 将 arr 存储的 合并数据转换到原本数组上。// 注意 array 数组中括号的下标的位置。for (int j 0; j arr.length; j) {array[low] arr[j];}} 附图 归并排序 - 总程序
import java.util.Arrays;public class MergeSort {/** 时间复杂度N * log2 N* 空间复杂丢O(N)* 稳定性稳定* */public static int[] mergeSort(int[] array){if(array null){return array;}mergeSortFunc(array,0,array.length-1);return array;}private static void mergeSortFunc(int[] array,int low,int high){if(low high){return;}
// int mid (high low) 1int mid low ((high - low) 1);mergeSortFunc(array,low,mid);// 左边mergeSortFunc(array,mid1,high);// 右边merge(array,low,mid,high);}private static void merge(int[] array,int low,int mid,int high){int[] arr new int[high - low 1];int start1 low;int end1 mid;int start2 mid1;int end2 high;int i 0;while (start1 end1 start2 end2){if(array[start1] array[start2]){arr[i] array[start2];}else{arr[i] array[start1];}}while(start1 end1){arr[i] array[start1];}while(start2 end2){arr[i] array[start2];}for (int j 0; j arr.length; j) {array[low] arr[j];}}public static void main(String[] args) {int[] array {1,6,7,10,2,3,4,9};mergeSort(array);System.out.println(Arrays.toString(array));}
} 归并排序 - 时间与空间复杂度分析、稳定性 归并排序 - 非递归实现 代码如下
import java.util.Arrays;public class MergeSortNonRecursion {public static void mergeSort(int[] array){//归并排序非递归实现int groupNum 1;// 每组的数据个数while(groupNum array.length){// 无论数组含有几个元素 数组每次都需要从下标 0位置开始遍历。for(int i 0;iarray.length;i groupNum * 2){int low i;int mid low groupNum -1;// 防止越界【每组的元素个数超过了数组的长度】if(mid array.length){mid array.length-1;}int high mid groupNum;// 防止越界【超过了数组的长度】if(high array.length){high array.length-1;}merge(array,low,mid,high);}groupNum * 2;//每组的元素个数扩大到原先的两倍。}}public static void merge(int[] array,int low,int mid,int high){// high 与 mid 相遇说明 此时数组分组只有一组也就说没有另一组的数组与其合并// 即数组已经有序了程序不用再往下走。if(high mid){return;}int[] arr new int[high -low 1];int start1 low;int end1 mid;int start2 mid1;int end2 high;int i 0;while(start1 end1 start2 end2){if(array[start1]array[start2]){arr[i] array[start2];}else{arr[i] array[start1];}}while (start1 end1){arr[i] array[start1];}while(start2 end2){arr[i] array[start2];}for (int j 0; j arr.length; j) {array[low] arr[j];}}public static void main(String[] args) {int[] array {12,5,8,7,3,4,1,10};mergeSort(array);System.out.println(Arrays.toString(array));}
} 海量数据的排序问题 外部排序排序过程需要在磁盘等外部存储进行的排序 【内部排序排序过程需要在 内存上进行排序】 前提内存只有 1G需要排序的数据有 100G 因为内存中无法把所有数据全部放下所以需要外部排序而归并排序是最常用的外部排序。 1、先把文件切分成 200 份每个512M 2、分别对 512M 的数据量 进行排序因为 内存已经被分割了512M 1G 内存放得下。所以任何排序方式都可以 3、进行 200 路归并同时对 200 份有序文件做归并过程最终结果就有序了 小总结 目前我们讲了八种排序直接插入排序、希尔排序、直接选择排序双向选择排序、冒泡排序堆排序、快速排序归并排序。 其中稳定的排序插入排序冒泡排序归并排序一共三种。 ? 另外堆排序、归并排序、快速排序的时间复杂度都是 N * log2 N。 如果你想速度快就用快排。 如果你想稳定就用归并。 如果你想空间复杂度低就用堆排。 排序总结 排序方法最好时间复杂度平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(N)O(N^2)O(N^2)O(1)稳定插入排序O(N)O(N^2)O(N^2)O(1)稳定选择排序O(N^2)O(N^2)O(N^2)O(1)不稳定希尔排序O(N)O(N^1.3)O(N^2)O(1)不稳定堆排序O(N * log2 N)O(N * log2 N)O(N * log2 N)O(1)不稳定快速排序O(N * log2 N)O(N * log2 N)O(N ^ 2)O(N)不稳定归并排序O(N * log2 N)O(N * log2 N)O(N * log2 N)O(N)稳定不常见的排序 - 不基于比较的排序了解
基数排序 它的思路假设待排序的数据类型是 整形/十进制数每个数据 分别按照 个百千万的大小放入拿出对应编号空间其最终的结果就是有序的。 放入拿出的次数 取决于 这组数据中 最大值的位数。 代码如下
import java.util.Arrays;public class RadixSort {
// 基数排序功能 实际功能实现方法private static void radixSortFunc(int[] array,int maxDigit){int mode 10 ; // 十进制int divide 1;// 将 数值上的每个数“分割”方便获取数据的一个位上的值// 每个数据从个位到最大值的最高位按照其位上的大小 放出 拿出for (int i 0; i maxDigit; i,mode * 10,divide *10) {// 考虑 负数的 情况0~9 对应负数10 ~ 19 对应正数// 行 对应的是编号 列 对应的存储的数据int[][] counter new int[mode*2][0];for (int j 0; j array.length; j) {int number ((array[j] % mode)/divide) mode; /*获取 数据对应 空间的编号 */counter[number] arrayAppend(counter[number],array[j]);}int pos 0;for (int[] number:counter) {for (int val:number) {array[pos] val;}}}}// 添加 元素private static int[] arrayAppend(int[] arr,int value){arr Arrays.copyOf(arr,arr.length1);arr[arr.length-1] value;return arr;}// 基数排序 功能调用方法“窗口”public static void radixSort(int[] array){int maxNumLength getNumLength(array);radixSortFunc(array,maxNumLength);}// 获取最大值的位数 - 功能“窗口”private static int getNumLength(int[] array){int maxVal getMaxValue(array);return getMaxDigit(maxVal);}//获取最大值private static int getMaxValue(int[] array){int maxValue array[0];for (int value: array) {if(value maxValue){maxValue value;}}return maxValue;}// 获取最大值的位数 - 执行private static int getMaxDigit(int num){if(num 0){return 0;}int len 0;while(num 0){len;num / 10;}return len;}// 程序入口public static void main(String[] args) {int[] array {124,366,170,52,200,78,468};radixSort(array);System.out.println(Arrays.toString(array));}
} 捅排序 计数排序 在使用 计数排序时需注意以下几点 1、确定基数排序的大小 2、这个计数排序 适用的范围【假设数据中最小值 10000最大 12000那么我们的计数数组容量只需要20010 下标也算入 就够了。不需要创建 12000容量避免空间浪费】 计数数组 计数也简单用元素值减去 10000最小值 就行了 3、必须找到数据中的最大值 和 最小值锁定计数数组的长度max - min 1 4、 拿出数据的时候记得将减去的 最小值 加上再进行对原始数组的覆写。 代码如下
import java.util.Arrays;
/*
* 时间复杂度O(N)
* 空间复杂度: O(M) : M 表示 当前数据的范围
* 【空间 换 时间】
* 稳定性 当前代码是不稳定本质是稳定的。
* 在借助一个 数组来存储 每个元素排序后最后出现的位置
* 拿出来的时候就能确定位置。致使该排序 稳定。 - 见附图
* */
public class CountingSort {public static void countingSort(int[] array){int maxVal array[0];int minVal array[0];for (int i 0; i array.length; i) {if (array[i] maxVal){maxVal array[i];}if(array[i] minVal){minVal array[i];}}// 当循环结束获得了 数据的最大值 和 最小值// 可以确定计数数组的容量int[] count new int[maxVal -minVal 1];for (int i 0; i array.length; i) {// 提高空间利用率count[ array[i] - minVal ];}// 此时计数数组 已经把array数组当中每个元素的出现次数统计好了// 接下来只需要遍历计数数组把 数据 覆写 到 array当中。int indexArray 0; // 用于遍历 array数组标记 覆写的位置。for (int i 0; i count.length; i) {while(count[i]0){// 这里一定要加上减去minVal因为 下标 i 不一定 在 array 数组中出现过。array[indexArray] i minVal;// 拿出来的时候记得将减去的值加上// indexArray;count[i]--;}}}public static void main(String[] args) {int[] array {5,0,2,3,4,5,2};countingSort(array);System.out.println(Arrays.toString(array));}
}附图 - 是目前的计数排序稳定
