模板做网站多少钱,o2o系统,婚庆公司网站设计,网站设计需要什么软件文章目录 交换排序一.冒泡排序二.快速排序1.挖坑法2.Hoare法 交换排序 根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置将键值较大的记录向序列的尾部移动#xff0c;键值较小的记录向序列的前部移动。
一.冒泡排序 /*** 冒泡排序* 时间复杂度 n^2* 空间复杂… 文章目录 交换排序一.冒泡排序二.快速排序1.挖坑法2.Hoare法 交换排序 根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
一.冒泡排序 /*** 冒泡排序* 时间复杂度 n^2* 空间复杂度 1* param array*/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[j1]){swap(array,j,j1);flg true;}}if (flg false){return;}}} 1.遍历 i 代表交换的趟数遍历 j 进行两两交换 2.j array.length-1-i 是对于趟数的优化每走一趟交换就少一次 3.boolean flg false;当两两交换时flg变为true 4.进一步优化如果遍历完没发生交换flg还是false,直接返回排序结束 时间复杂度O ( N2 )空间复杂度O ( 1 )稳定性稳定
二.快速排序 二叉树结构的交换排序方法 任取一个待排序元素作为基准值把序列一分为二左子序都比基准值小右子序都比基准值大左右两边再重复进行 左边找比基准值大的右边找比基准值小的
1.挖坑法 基准值位置挖一个坑后面找一个比基准值小的把坑埋上前面找一个比基准值大的埋后面的坑当lr时把基准值填入剩下的坑中 左右两边重复进行上述步骤直到排完为止左右两边都以同样的方法进行划分运用递归来实现 /*** 快速排序 ---挖坑法** param array*/public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int start, int end) {if (start end) {return;//结束条件// start end说明只剩一个了是有序的返回//start end ,说明此时的基准值在开头或者末尾//在开头start不变endpivot-1,start end end-1 没有左树//在结尾end不变start pivot1,start end,超出索引没有右树}//不断递归quickint pivot partition(array, start, end);// 进行排序划分找到pivot//然后递归划分法左边递归划分的右边quick(array, start, pivot - 1);quick(array, pivot 1, end);}//划分返回基准值private static int partition(int[] array, int left, int right) {int tmp array[left];//挖一个坑取left位置为基准值while (left right) {//在右边找一个比基准值小的把坑填上while (left right array[right] tmp) {//防止越界right--;}array[left] array[right];//找到比tmp小的数填坑,//在左边找一个比tmp大的值填到右边的坑while (left right array[left] tmp) {//防止越界left;}array[right] array[left];}//如果相遇了退出循环array[left] tmp;//填坑return left;} 先划分序列递归左边然后再递归右边 递归结束条件 start end时说明只剩一个了是有序的返回 start end 时 ,说明此时的基准值在开头或者末尾 如果基准值在开头start不变endpivot-1,start end end-1 没有左树 如果基准值在结尾end不变start pivot1,start end,超出索引没有右树 2.Hoare法 不同的方法找出基准值排的序列是不一样的 i记录基准值一开始在left位置的下标r找到比基准值小的停下来l找到比基准值大的停下来互相交换l和r相遇的时候把i 记录基准值的初始下标和相遇位置交换
以左边为基准先找右边再找左边相遇的位置就是以右边为基准的值要比基准小才能交换 /*** Hoare法 划分排序找基准值* param array* param left* param right* return*/private static int partition2(int[] array, int left, int right) {int tmp array[left];int i left;//记录基准值一开始在left位置的下标while (left right) {while (left right array[right] tmp) {right--;}while (left right array[left] tmp) {left;}swap(array,left,right);}swap(array,i,left);return left;}点击移步博客主页欢迎光临~
