浙江省城乡建设监方网站,自己搭建视频播放网站,wordpress修改社交标签,wordpress add option文章目录 排序一、 排序的概念1.排序#xff1a;2.稳定性#xff1a;3.内部排序#xff1a;4.外部排序#xff1a; 二、插入排序1.直接插入排序2.希尔排序 三、选择排序1.直接选择排序方法一方法二直接插入排序和直接排序的区别 2.堆排序 四、交换排序1.冒泡排序2.快速排序… 文章目录 排序一、 排序的概念1.排序2.稳定性3.内部排序4.外部排序 二、插入排序1.直接插入排序2.希尔排序 三、选择排序1.直接选择排序方法一方法二直接插入排序和直接排序的区别 2.堆排序 四、交换排序1.冒泡排序2.快速排序1.挖坑法2.Hoare法3.前后指针法4.快速排序的优化方法一随机选取基准值方法二三数取中法选基准值方法三递归到最小区间时、用插入排序 5.快速排序非递归实现 排序 一、 排序的概念
1.排序
一组数据按递增/递减排序
2.稳定性 待排序的序列中存在多个相同的关键字拍完序后相对次序保持不变就是稳定的
3.内部排序
数据元素全部放在内存中的排序
4.外部排序
数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序
二、插入排序
1.直接插入排序 和整理扑克牌类似将乱序的牌按值的大小插入整理好的顺序当中
从头开始比最后一个小的话依次向前挪直到大于之前牌时进行插入 1.如果只有一个值则这个值有序所以插入排序 i 从下标1开始把后面的无序值插入到前面的有序当中 2.j i-1,是i的前一个数先用tmp将 i位置的值要插入的值先存起来比较tmp和j位置的值 3.如果tmp的值比 j位置的值小说明要向前插入到有序的值中把 j位置的值后移移动到 j1的位置覆盖掉 i 的值 4.j 下标向前移动一位再次和 tmp 比较 5.如果tmp的值比 j 位置的值大说明找到了要插入的位置就在当前j位置之后把tmp存的值放到 j1的位置 6.如果tmp中存的值比有序的值都小j位置的值依次向后移动一位j不停减1直到排到第一位的数移动到第二位j的下标从0移动到-1循环结束最后将tmp中存的值存放到 j1的位置也就是0下标 public void insertSort(int[] array) {for (int i 1; i array.length; i) {int tmp array[i];//tmp存储i的值int j i - 1;for (; j 0; j--) {if (tmp array[j]) {array[j 1] array[j];} else {// array[j1] tmp;break;}}array[j 1] tmp;}}
插入就是为了维护前面的有序 元素越接近有序直接插入排序算法的时间效率越高 时间复杂度O( N 2 ) 空间复杂度O ( 1 ) 稳定性稳定 如果一个排序是稳定的可以改变实现为不稳定的 如果是不稳定的排序则没有办法改变
2.希尔排序 希尔排序shellSort 叫缩小增量排序是对直接插入排序的优化先分组对每组插入排序让整体逐渐有序
利用了插入排序元素越有序越快的特点 先确定一个整数把待排序数分成多个组每个组中的数距离相同对每一组进行排序然后再次分组排序减少分组数组数多每组数据就少找到分组数1时基本有序了只需要再排一次插入排序即可 一开始组数多每组数据少可以保证效率 随着组数的减少每组数据变多数据越来越有序同样保证了效率 到达1分组之前前面的排序都是预排序 public static void shellSort2(int[] array) {int gap array.length;while (gap 1) { //gap1时缩小增量gap / 2;//直接在循环内进行最后一次排序shell(array, gap);}}/**** 希尔排序* 时间复杂度O(N^1.3---N^1.5)* param array*/public static void shellSort1(int[] array) {int gap array.length;while (gap 1) { //gap1时缩小增量shell(array, gap);gap / 2;//gap1时不进入循环再循环为再次排序}shell(array, gap);//组数为1时进行插入排序}public static void shell(int[] arr, int gap) {//本质上还是插入排序但是i和j的位置相差为组间距for (int i gap ; i arr.length; i) {int tmp arr[i];int j i-gap;for (; j 0; j - gap) {if (tmparr[j]){arr[jgap] arr[j];}else {break;}}arr[jgap] tmp;}}
时间复杂度O( N^1.3 ^) ---- O( N^1.5 ^)空间复杂的O(1)稳定性不稳定
三、选择排序 在待排序序列中找到最小值大的下标和排好序的末尾交换放到待排序列的开头直到全部待排序元素排完
1.直接选择排序 方法一
/*** 选择排序** param array*/public static void selectSort(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;//只要比minIndex小放进去}}//循环走完后minIndex存的就是当前未排序的最小值//将当前i的值和找到的最小值进行交换swap(array,i,minIndex);}}public static void swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;}1.遍历数组长度i从0开始 2.每次循环都由minIndex i 来记录最小值的下标 3.j 从i1开始遍历只要比记录的最小值小就让minIndex记录。找到未排序中的最小值进行交换 4.如果遍历完后未排序中没有比minIndex存的值小i的值就是最小值i; 效率低, 如果较为有序的序列在交换时会破坏有序性时间复杂度O ( N2 )空间复杂的O ( 1 )稳定性不稳定
方法二 上面的方法只是先选出最小的值然后和i的位置交换 进行优化在遍历时选出最大值和最小值和收尾进行交换 /*** 选择排序---选最大值和最小值** param array*/public static void selectSort2(int[] array) {int left 0;int right array.length - 1;while (left right) {int minIndex left;int maxIndex left;//选出最大值和最小值for (int i left 1; i right; i) {if (array[i] array[maxIndex]) {maxIndex i;}if (array[i] array[minIndex]) {minIndex i;}}//用最大值和最小值交换首位swap(array, left, minIndex);//把left和最小值交换//如果left恰好就是最大值就有可能把最大值换到minIndex的位置if(left maxIndex){maxIndex minIndex;//最大值位置不是left了而是换到了minIndex}swap(array, right, maxIndex);left;right--;}}1.在遍历的过程中选出最大值的下标和最小值的下标 2.将left和最小值进行交换 3.如果left恰好为最大值left和最小值交换完成后最大值就在原来最小值的位置上 4.maxIndex minIndex,修正最大值的位置 4.将right和最大值进行交换 直接插入排序和直接排序的区别
和插入排序不同的是插入排序会持续对已排序的数进行比较把合适的数放在合适的位置直接选择排序就是不断找到最小的值依次放在排好序的末尾不干预排好的序列
2.堆排序 时间复杂度: O( N * log N)空间复杂的O (1) 升序建大堆 降序建小堆
将一组数据从小到大排序 —— 建立大根堆 为什么不用小根堆小根堆只能保证根比左右小不能保证左右孩子的大小顺序并且要求对数组本身进行排序 大根堆保证堆顶元素是最大值最大值跟最后一个元素交换将最大的放在最后usedSize–向下调整调整0下标的树维护大根堆最大值继续交换到最后一个有效元素的位置从后往前从大到小依次排列保证在原来数组本身进行排序 /*** 堆排序* 时间复杂度: N*logN* 空间复杂的o(1)** param array*/public static void heapSort(int[] array) {createBigHeap(array);//创建大根堆int end array.length-1;while (end0){swap(array,0,end);//堆顶元素和末尾互换shiftDown(array,0,end);//维护大根堆end--;}}/*** 创建大根堆** param array*/public static void createBigHeap(int[] array) {//最后一个结点的下标 array.length - 1//它的父亲结点的下标就为array.length - 1 - 1) / 2for (int parent (array.length - 1 - 1) / 2; parent 0; parent--) {shiftDown(array, parent, array.length);}}/*** 向下调整** param array* param parent* param len*///向下调整每棵树从父结点向下走public static void shiftDown(int[] array, int parent, int len) {int child parent * 2 1;while (child len) {//child len:最起码要有一个左孩子if (child 1 len array[child] array[child 1]) {child;}//child 1len:保证一定有右孩子的情况下和右孩子比较//拿到子节点的最大值if (array[child] array[parent]) {swap(array, child, parent);parent child;//交换完成后让parent结点等于等于当前child结点child 2 * parent 1;//重新求子节点的位置再次进入循环交换} else {break;//比父结点小结束循环}}} 时间复杂度: O( N * log 2N)空间复杂的O (1)稳定性不稳定 四、交换排序
根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
1.冒泡排序 /*** 冒泡排序* 时间复杂度 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 )稳定性稳定 2.快速排序 时间复杂度 最好情况O (N*log2N) 树的高度为log2N每一层都是N 最坏情况:O (N2)有序、逆序的情况下,没有左树只有右树单分支树树的高度是N,每一层都是N 空间复杂的 最好情况O (log2N)满二叉树均匀分割待排序的序列效率最高树高为 log2N 最坏情况ON:单分支树,树高为N 稳定性不稳定 二叉树结构的交换排序方法 任取一个待排序元素作为基准值把序列一分为二左子序都比基准值小右子序都比基准值大左右两边再重复进行 左边找比基准值大的右边找比基准值小的
1.挖坑法 基准值位置挖一个坑后面找一个比基准值小的把坑埋上前面找一个比基准值大的埋后面的坑当lr时把基准值填入剩下的坑中 左右两边重复进行上述步骤直到排完为止左右两边都以同样的方法进行划分运用递归来实现 /*** 快速排序* 时间复杂度:N*log~2~N* 空间复杂度* * 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;}3.前后指针法 prev记录了比key小的最后一个位置cur去找比key值小的找到后放到prev的下一个位置最后找到基准值并且基准值的左边都比它小右边都比他大 /*** 前后指针法划分排序找基准值** param array* param left* param right* return*/private static int partition3(int[] array, int left, int right) {int prev left; //prev从left位置开始left为当前的基准值int cur left 1;//cur在prev的后一个while (cur right) {//遍历完当前数组段if (array[cur] array[left] array[prev] ! array[cur]) {//只要cur指向的值小于left位置的基准值//并且prev后不等于cur的值swap(array, cur, prev);//将cur和prev位置的值交换//cur;}//如果cur的值大于基准值,或者prev下一位的值等于cur,cur后移cur;}//cur越界循环结束最后交换基准值和prev位置的值//prev记录的就是比基准值小的最后一个数swap(array, prev, left);return prev;//prev为基准值}
4.快速排序的优化 时间复杂度 最好情况O (N*log2N) 树的高度为log2N每一层都是N 最坏情况:O (N2)有序、逆序的情况下,没有左树只有右树单分支树树的高度是N,每一层都是N 空间复杂的 最好情况O (log2N)满二叉树均匀分割待排序的序列效率最高树高为 log2N 最坏情况ON:单分支树,树高为N 稳定性不稳定 快速排序有可能发生栈溢出异常需要进行优化 所以要能均匀分割待排序的序列
递归的次数多了会导致栈溢出所以优化的方向就是减少递归的次数
在最坏情况下比如顺序基准值都取自左边本身没有左树
方法一随机选取基准值
看人品有概率
方法二三数取中法选基准值
三数第一个数、中间的数、最后一个数 在这三个数中选出中等值 有可能会变成二分查找 避免了出现最坏情况从中值来比较排序左右树都有 public static void quickSort(int[] array) {quick2(array, 0, array.length - 1);}private static void quick2(int[] array, int start, int end) {if (start end) {return;//结束条件}//三数取中法int index midThree(array, start, end);//选出的数和开头交换swap(array,index,start);int pivot partition(array, start, end);// 进行排序划分找到pivot//然后递归划分法左边递归划分的右边quick2(array, start, pivot - 1);quick2(array, pivot 1, end);}/*** 三数取中* param array* param left* param right* return*/private static int midThree(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[right]) {return right;} else if (array[mid] array[left]) {return left;} else {return mid;}}}方法三递归到最小区间时、用插入排序
进一步优化减少递归的次数 把快排的递归想象成二叉树最后两层包含了大部分数我们要减少这部分的递归 前几次的找基准值排序导致后面几层趋于有序用直接插入法来排序进一步提高效率有点像希尔排序
如果树的高度为h,最后一层就有 2 h-1 个结点 后两层占了绝大部分
设置条件end-start1 就是当前待排序列的长度如果小于等于某个较小的值直接采用插入排序来排剩下的 private static void quick2(int[] array, int start, int end) {if (start end) {return;//结束条件}//优化----减少递归的次数if(end-start120){//如果当前数列的长度小于15的时候// 用插入排序,然后退出insertSortQ(array,start,end);return;}//三数取中法int index midThree(array, start, end);swap(array,index,start);int pivot partition(array, start, end);// 进行排序划分找到pivot//然后递归划分法左边递归划分的右边quick2(array, start, pivot - 1);quick2(array, pivot 1, end);}/*** 插入排序---来排剩下的待排部分给定需要的区间*/private static void insertSortQ(int[] array,int left,int right) {for (int i left1; i right; i) {int tmp array[i];int j i - 1;for (; j left; j--) {if (array[j] tmp) {array[j 1] array[j];} else {break;}}array[j 1] tmp;}}
5.快速排序非递归实现
1.通过使用栈来实现2.每次找到基准值后把两段序列的开头和末尾压栈3.从栈顶取出两个元素作为新序列的首尾再次找基准值4.找到基准值后如果右边有一个元素不进栈有两个元素的才能进栈5.pivot end-1:证明右边有两个元素pivots1证明左边有两个元素6.栈为空的时候排完元素 /*** 非递归实现快速排序** param array*/public static void quickSortNonRecursive(int[] array) {DequeInteger stack new LinkedList();//利用栈来实现int left 0;int right array.length - 1;//先找到基准值int pivot partition(array, left, right);//左边有两个元素时根据基准值进栈if (pivot left 1) {stack.push(left);stack.push(pivot - 1);}//有边有两个元素时根据基准值进栈if (pivot right - 1) {stack.push(pivot 1);stack.push(right);}//栈不为空的时候取两个栈顶元素做为区间//再次进栈出栈while (!stack.isEmpty()) {right stack.pop();left stack.pop();pivot partition(array, left, right);//左边有两个元素时根据基准值进栈if (pivot left 1) {stack.push(left);stack.push(pivot - 1);}//有边有两个元素时根据基准值进栈if (pivot right - 1) {stack.push(pivot 1);stack.push(right);}}}点击移步博客主页欢迎光临~
