华为云建站怎么样,免费的html大作业网站,做网站找哪个好,网页设计代码大全表单居中文章目录 一、直接插入排序二、希尔排序三、直接选择排序四、堆排序五、冒泡排序六、快速排序6.1递归实现快速排序6.2非递归实现快速排序 七、归并排序7.1递归实现归并排序7.2非递归实现归并排序 八、计数排序 以下排序以从小到大排序为例 一、直接插入排序
时间复杂度#x… 文章目录 一、直接插入排序二、希尔排序三、直接选择排序四、堆排序五、冒泡排序六、快速排序6.1递归实现快速排序6.2非递归实现快速排序 七、归并排序7.1递归实现归并排序7.2非递归实现归并排序 八、计数排序 以下排序以从小到大排序为例 一、直接插入排序
时间复杂度 最好情况完全有序的情况 1 2 3 4 5 O(N) 最坏情况完全逆序的情况 5 4 3 2 1 O(N^2)相当于等差数列求和 空间复杂度O(1) 稳定性稳定 当所给的数据越有序直接插入排序越快 有一组基本有序的数据时用直接插入排序较好
public static void insertSort(int[] array) {for(int i 1; i array.length; i) {int j i - 1;int tmp array[i];for(; j 0; j--) {//跳出循环有两种情况1.j0 2.array[j]tmpif(array[j] tmp) {//如果条件变为array[j]tmp则排序变为不稳定array[j 1] array[j];}else {break;}}array[j 1] tmp;//每次把tmp插入数组后都会重新获取i和j的位置}}二、希尔排序
希尔排序是对直接插入排序的优化跳跃式的分组可能会将更小的元素尽可能往前方 增量为多少gap为多少则被分为多少组 时间复杂度N^1.3 ~ N^1.5 空间复杂度O(1) 稳定性不稳定
public static void shellSort(int[] array) {int gap array.length;//增量为多少gap为多少则被分为多少组while(gap 1) {//里面已经包括了排序gap为1的情况gap / 2;shell(array, gap);}}private static void shell(int[] array, int gap) {for(int i gap; i array.length; i) {//igap也行因为gap最后会变为1int j i - gap;int tmp array[i];for(; j 0; j - gap) {//跳出循环有两种情况1.j0 2.array[j]tmpif(array[j] tmp) {//如果条件变为array[j]tmp则排序变为不稳定array[j gap] array[j];}else {break;}}array[j gap] tmp;//每次把tmp插入数组后都会重新获取i和j的位置}}三、直接选择排序
时间复杂度不管情况是好还是坏下面两种写法都是O(N^2)相当于等差数列求和 空间复杂度O(1) 稳定性不稳定
public static void selectSort1(int[] array){for(int i 0; i array.length; i) {int minIndex i;for(int j i 1; j array.length; j) {if(array[j] array[minIndex]) {minIndex j;//在所有的j下标元素中找比array[minIndex]还要小的元素的下标}}swap(array, i, minIndex);}}private static void swap(int[]array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;}//写法二public static void selectSort2(int[] array){int left 0;int right array.length - 1;while(left right) {//与写法一相比将写法一最外层的for循环改为了while循环int minIndex left;int maxIndex left;//maxIndex一定是left因为下面的j下标是从left1开始从前往后遍历for(int i left 1; i right; i) {if(array[i] array[minIndex]) {minIndex i;//在所有的j下标元素中找比array[minIndex]还要小的元素的下标}if(array[i] array[maxIndex]) {maxIndex i;//在所有的j下标元素中找比array[maxIndex]还要大的元素的下标}}swap(array, left, minIndex);//当最大值原来刚好在最小值的位置(left位置)时则上一步已经将最小值与left交换此时最大值在原来最小值的位置if(maxIndex left) {//所以要做这一步操作maxIndex minIndex;}swap(array, right, maxIndex);left--;right;}}四、堆排序
时间复杂度O(N)创建大根堆 O(NlogN) (堆的每个节点进行向下调整) 即O(NlogN) 空间复杂度O(1) 稳定性不稳定 数据量非常大的时候堆排序一定比希尔排序快因为希尔排序的时间复杂度为N^1.3 ~ N^1.4堆排是对数希尔排是指数
public static void heapSort(int[] array){creatBigHeap(array);int end array.length - 1;while(end 0) {swap(array, 0, end);//因为是大堆堆顶的元素最大将堆顶元素与队尾元素交换使队尾元素变成队内最大元素shiftDown(array, 0, end);//在这里endarray.length-1而在shiftDown中end代表数组的总长度end--; //相当于去掉队尾元素再进行向下调整}}private static void creatBigHeap(int[] array) {for(int parent (array.length - 1 - 1) / 2; parent 0; parent--) {shiftDown(array, parent, array.length);}}private static void shiftDown(int[] array, int parent, int end) {int child 2 * parent 1;while(child end) {//因为end传的是array.length所以条件用而不用if(child 1 end array[child] array[child 1]) {child;}if(array[child] array[parent]) {swap(array, child, parent);parent child;child 2 * parent 1;}else {break;}}}五、冒泡排序
时间复杂度O(N^2) 加了优化之后最好的情况只比较一趟则是O(N) 空间复杂度O(1) 稳定性稳定
public static void bubbleSort(int[] array){for (int i 0; i array.length - 1; i) {boolean flg false;for (int j 0; j array.length - 1 - i; j) {if(array[j] array[j 1]) {swap(array, j, j 1);flg true;}}if(!flg) {return;}}}六、快速排序
快速排序相当于以基准为根创建二叉树 时间复杂度 最好情况O(N*logN) 满二叉树/完全二叉树 最坏情况O(N^2)相当于等差数列求和 单分支的树 空间复杂度 最好情况O(logN) 满二叉树/完全二叉树的高度 最坏情况O(N) 单分支的树创建N个节点 稳定性不稳定 三种求基准的方法Hoare法挖坑法前后指针法
6.1递归实现快速排序
在这里递归实现的快速排序做了两个优化第一个优化是使用三数取中法求原始基准使创建出来的树更像满二叉树降低了树的高度降低了空间复杂度 第二个优化是递归到一定程度时对每个区间使用插入排序因为区间越来越小且区间的内容越来越有序这时这部分区间可以用插入排序以减少递归次数
public static void quickSort(int[] array){quickSortF(array, 0, array.length - 1);//参数right传的是array.length-1}private static void quickSortF(int[] array, int left, int right) {if(left right) return;//这是递归的结束条件有因为leftright时不用再创建节点了这个节点已经有序//递归到后面的较小区间时用插入法if(right - left 1 7) {//随着快速排序的进行整个数据正在趋于有序当区间越来越小且区间的内容越来越有序时insertSort1(array, left, right);//这部分区间可以用插入排序这样做可以减少递归的次数return;}//三数取中法降低了二叉树的高度降低了空间复杂度使空间复杂度变为O(logn)int midIndex midOfTree(array, left, right);swap(array, midIndex, left);//交换完之后保证left下标是三个数中中间大的数字int pivot partition2(array, left, right);//找到一次基准相当于排好了当前基准这个元素在数组中的顺序找到基准后基准左边都是比基准小的基准右边都是比基准大的//先递归左边递归完左边再递归右边quickSortF(array, left, pivot - 1);quickSortF(array, pivot 1, right);}//插入法private static void insertSort1(int[] array, int left, int right) {for(int i left 1; i right; i) {int j i - 1;int tmp array[i];for(; j left; j--) {//跳出循环有两种情况1.j0 2.array[j]tmpif(array[j] tmp) {//如果条件变为array[j]tmp则排序变为不稳定array[j 1] array[j];}else {break;}}array[j 1] tmp;//每次把tmp插入数组后都会重新获取i和j的位置}}//在三数中找到中间大小数的下标private static int midOfTree(int[] array, int left, int right) {int mid (left right) / 2;if(array[left] array[right]) {if(array[mid] array[left]) {return left;}else if(array[mid] array[right]) {return right;}else {return mid;}}else {if(array[mid] array[left]) {return left;}else if(array[mid] array[right]) {return right;}else {return mid;}}}//三种找基准的方法在排序的过程中序列可能会不一样但最终排好序的结果一样建议优先使用挖坑法right参数传的都是array.length-1//Hoare法找基准private static int partition1(int[] array, int left, int right) {int key array[left];int i left;//将基准的下标保存到i中因为后面要用left与right相交位置的元素与基准进行交换这里的交换函数只传下标while(left right) {while (left right array[right] key) {//leftright这个条件很重要因为right不断--此时再判断array[right]key时array[right]有可能会越界right--;//先走right因为一开始基准为left先走rightleft和right相遇的地方才能是比基准小的才能把比基准小的与基准交换放在基准前}while (left right array[left] key) {//array[left]key或上面array[right]key的一定要有否则可能会进入死循环如当left和right的值相同时left;}swap(array, left, right);}swap(array, left, i);return left;}//挖坑法找基准private static int partition2(int[] array, int left, int right) {int key array[left];while(left right) {while (left right array[right] key) {right--;}array[left] array[right];while (left right array[left] key) {left;}array[right] array[left];}array[left] key;return left;}//前后指针法找基准private static int partition3(int[] array, int left, int right) {int prev left;int cur left 1;while(cur right) {if(array[cur] array[left] array[prev] ! array[cur]) {//cur在前面找比基准小的prev保持在cur找到比基准小的之后要跟prev交换的那个位置prev是前置swap(array, prev, cur);//代码走到这说明cur和prev拉开了距离且curleftprevleft}cur;//array[cur]array[left]时cur直接往前走与prev拉开距离}swap(array, prev, left);return prev;}6.2非递归实现快速排序
public static void quickSortNor(int[] array) {StackInteger stack new Stack();int left 0;int right array.length - 1;int piovt partition2(array, left, right);if(piovt - 1 left) {stack.push(left);//往栈上先放left后放right则出栈时先出right后出leftstack.push(piovt - 1);}if(piovt 1 right) {stack.push(piovt 1);stack.push(right);}while(!stack.isEmpty()) {//因为这里出栈时先出right后出left根据出出来的right和left找新的基准所以相当于先递归二叉树右边再递归二叉树左边right stack.pop();left stack.pop();piovt partition2(array, left, right);if(piovt - 1 left) {stack.push(left);stack.push(piovt - 1);}if(piovt 1 right) {stack.push(piovt 1);stack.push(right);}}}七、归并排序
时间复杂度O(N*logN) 归并排序在合并过程中每层都要遍历N次一共logN层 空间复杂度O(N) 归并排序在最后合并的时候要额外申请与原来数组一模一样大小的数组 归并排序的缺点是空间复杂度过大 稳定性稳定 原始分开的区间从0下标开始和原始分开的区间不从0下标开始的合并过程
7.1递归实现归并排序
public static void mergeSort(int[] array) {mergeSort(array, 0, array.length - 1);//参数right传的是array.length-1}private static void mergeSort(int[] array, int left, int right) {if(left right) return;int mid (left right) / 2;//分裂左边mergeSort(array, left, mid);//分裂右边mergeSort(array, mid 1, right);//合并在合并的过程中进行了排序merge(array, left, right, mid);}private static void merge(int[] array, int left, int right, int mid) {int s1 left;int s2 mid 1;int[] tmpArr new int[right - left 1];//申请一个新的数组大小为right-left1int k 0;while(s1 mid s2 right) {//满足这个循环条件说明s1~mid和s2~right这两个区间都同时有数据if(array[s2] array[s1]) {//若条件改为array[s2]array[s1]则排序变为不稳定tmpArr[k] array[s2];}else {tmpArr[k] array[s1];}}while(s1 mid) {tmpArr[k] array[s1];}while(s2 right) {tmpArr[k] array[s2];}for (int i 0; i tmpArr.length; i) {array[i left] tmpArr[i];//将tmpArr数组拷回原来数组时赋给array[ileft]因为原来数组的left有可能不是0}}7.2非递归实现归并排序
在合并之前分的组数不断减少每组元素不断增多一个一个为一组gap为1再到两个两个为一组gap为2如此类推 合并之前mid和right有可能会越界此时要做出调整
public static void mergeSortNor(int[] array) {int gap 1;while(gap array.length) {for (int i 0; i array.length; i 2*gap) {int left i;int mid left gap - 1;int right mid gap;if(mid array.length) {//mid有可能会越界越界时要做出调整mid array.length - 1;}if(right array.length) {//right有可能会越界越界时要做出调整right array.length - 1;}merge(array, left, right, mid);}gap * 2;}}八、计数排序
时间复杂度O(2N数据范围) 即O(MAX(N数据范围)) 空间复杂度O(数据范围) 稳定性稳定但以下代码实现的计数排序是不稳定的 计数排序适合排序某个区间内且集中的数据 public static void countSort(int[] array) {int minVal array[0];int maxVal array[0];//求数组中的最大值和最小值for (int i 0; i array.length; i) {if(array[i] minVal) {minVal array[i];}if(array[i] maxVal) {maxVal array[i];}}int[] count new int[maxVal - minVal 1];//依据最大值和最小值来确定计数数组的大小//遍历原来的数组进行计数for (int i 0; i array.length; i) {count[array[i] - minVal];//计数数组的下标相当于要排序数组的元素内容}//遍历count把当前元素写回arrayint index 0;for (int i 0; i count.length; i) {while(count[i] ! 0) {array[index] i minVal;index;count[i]--;}}}
