网站智能建设系统源码,沧州网站设计公司,企业网站建设的收获,百度搜索 手机目录
交换排序
冒泡排序#xff1a;
快速排序
Hoare法
挖坑法
前后指针法【了解即可】
优化 再次优化#xff08;插入排序#xff09;
迭代法
其他排序
归并排序
计数排序
排序总结 结束了上半章四个较为简单的排序#xff0c;接下来的难度将会大幅度上升
快速排序
Hoare法
挖坑法
前后指针法【了解即可】
优化 再次优化插入排序
迭代法
其他排序
归并排序
计数排序
排序总结 结束了上半章四个较为简单的排序接下来的难度将会大幅度上升那么就开始本章的排序吧
交换排序
基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
冒泡排序
冒泡排序是相对来说是最简单的排序我们从c语言开始就接触过了冒泡排序其主要思想如下
它的基本思想是对所有相邻记录的关键字值进行比效如果是逆顺a[j]a[j1]则将其交换最终达到有序化。
具体的就不多说了直接跳过
代码如下
/*** 冒泡排序*/public static void bubbleSort1(int[] array) {for (int i 0; i array.length; i) {for (int j 0; j array.length; j) {if (array[j] array[j1]) {swap(array,j,j1);}}}}//优化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; j) {if (array[j] array[j1]) {swap(array,j,j1);flg true;}}if ( !flg) {return;}}}
【冒泡排序的特性总结】 冒泡排序是一种非常容易理解的排序时间复杂度O(N^2) 空间复杂度O(1)稳定性稳定而接下来要介绍的就是交换排序的大哥快速排序
快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。
无论是什么版本的快排都是遵循一个原则选 key划分选取一个 key 使 key 左边的值小于等于 key 右边的值大于 key 这是快排的核心思想。
Hoare提出的快排又叫做Hoare法。
Hoare法
其基本思想为 任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 步骤如下
选取最左边的值为 key比较时右边先走因选的是左边所以右边会先走向左走当右边在走的过程中遇到小于等于 key 的值时停下右边走完后换左边走向右走当遇到大于 key 的值时停止此时交换左右两处的值当左遇到右时必定相遇因为一次走一步终止循环执行最后一步交换此时左右与 key 值此时就完成了需求右边值 key 左边值
这时单次排序
为了方便动图演示我就直接抄一个动图 单次循环结束后我们将整个区域分为了【begin,key - 1】 和 【key 1, end】两个区域将其中的两块区域传入函数继续执行递归当所有数据都排序完成后快排就结束了
具体代码如下 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) { // 为什么要大于end如果是有序的情况 就会失效return;}int pivot partition(array,start,end);quick(array,0,pivot - 1);quick(array,pivot1,end);}private static int partition(int[] array,int left,int right) {int tmp array[left];int i left;while (left right) { // 一趟排序while (left right array[right] tmp) {right--;}while (left right array[left] tmp) {left;}swap(array,left,right);}swap(array,left,i);return left;}
挖坑法
基本思想
Hoare法的另一种思想不过挖坑法为了便于理解引入了坑位这个概念简单来说就是先在 key 处挖坑然后右边先走假设 key 在最左边找到小于等于 key 的值就将此值放入到坑中并在这里形成新坑然后是左边走同样的找到值 - 填入坑 - 挖新坑如此重复直到左右相遇此时的相遇点必然是一个未填充的坑当然这个坑就是给 key 值准备的。
动图演示 代码如下
private static int partition2(int[] array,int left,int right) {int temp array[left];while (left right) { // 一趟排序while (left right array[right] temp) {right--;}array[left] array[right];while (left right array[left] temp) {left;}array[right] array[left];}array[left] temp;return left;}private static void swap(int[] array,int i,int j) {int tmp array[i];array[i] array[j];array[j] tmp;}
前后指针法【了解即可】
基本思想
前后指针法不同于之前的两种思想但是其核心依旧是利用 key 找一个基准创建两个指针一个prev 指向 key 下标一个cur指向 key 的下一个位置
判断 cur 处的值是否小于等于 key 值如果是则先 prev 后再交换 prev 与 cur 处的值如此循环直到 cur 移动至数据尾最后一次交换为 key 与 prev 间的交换交换完后就达到快排的目的。
动图演示 代码如下
//前后指针法 【了解即可】private static int partition3(int[] array,int left,int right) {int prev left ;int cur left1;while (cur right) {if(array[cur] array[left] array[prev] ! array[cur]) {swap(array,cur,prev);}cur;}swap(array,prev,left);return prev;}private static void swap(int[] array,int i,int j) {int tmp array[i];array[i] array[j];array[j] tmp;}
【快速排序的特性总结】
快速排序不同于其他排序快排需要区分最好情况和最坏情况如果我们给定一个有序的数组对其进行快排无论是利用以上哪种方法结果都如下 由于有序每一次排序都需要全部遍历一遍如果是无序情况每一次排序过程中都会使一部分数据趋近有序。
最好情况无序
时间复杂度O(n*logn)空间复杂度O(logN)
类似于一颗满二叉树 每次 key 都恰好是中间位置。
最坏情况有序 时间复杂度O(n^2)空间复杂度O(n) 记住一句话快速排序越有序越慢越无序越快。 稳定性不稳定对于最坏情况明显不能满足我们的需求由于jdk默认分配的内存很小对于一个很大的数据使用快排递归太多了很可能照成栈溢出的情况故此我们需要对其进行优化。
假设是一个升序的情况没有左树 我们对其进行优化
优化
方法1 随机选取基准法
思想 3的左边都小于33的右边都大于3 再对左右进行递归。 但是随机选取基准法太随机了也并不理想不是最好的优化方法。
方法2三数取中法
从最左边中间和最右边三个数中选取中间的值作为基准 这样做就可能变成二分查找那么就不会出现最坏情况了。
代码如下 //初次优化优化方法之一:三数取中法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 {//array[left] array[right]if (array[mid] array[right]) {return right;} else if (array[mid] array[left]) {return left;} else {return mid;}}} 再次优化插入排序
对于一颗完全二叉树而言最后两层占了大多数数据 代码如下
//再次优化private static void insertSort2(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[j1] array[j];}else {break;}}array[j1] tmp;}}
迭代法
利用栈的性质来完成快速排序
核心思想
参照之前的代码 迭代法同样对此进行划分【start,pivot - 1 】【pivot 1,end】我们将下标压入栈中对栈中元素进行弹出每次弹出两个分别用right和left来接收排序完后 我们同样需要压入下标入栈但是当左右有一边只有一个元素时不用入栈。
如此反复就可以排序完。
代码如下
//栈利用栈的性质public static void quickSort2(int[] array) {DequeInteger stack new LinkedList();int left 0;int right array.length-1;int pivot partition(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() ) {stack.pop();stack.pop();pivot partition(array,left,right);if(pivot left1) {stack.push(left);stack.push(pivot-1);}if(pivot right-1) {stack.push(pivot1);stack.push(right);}}}
其他排序
归并排序
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。
基本思想
每次将数据均分为两组直不可再分每次再将两组数据进行合并如下图所示 归并排序多用于外排序即对磁盘中的大数据进行排序。
动图演示 思路首先要得到左右皆有序的数组然后合并显然这个需要借助递归实现将大问题化小问题将原数据分为左右两个区间交给递归让他们变得有序最后再执行有序数组合并。依靠递出区间会慢慢变小直到区间内只有两个数执行合并然后逐渐向上回归回归的过程就是不断合并的过程数据最开始的左右区间会逐渐变得有序当回归到第一层时执行最后一次有序数组合并数据整体就变得有序了。
代码如下
public static void mergeSort1(int[] array) {//保证接口的统一性所以需要借组mergeSortFuncmergeSortFunc(array,0,array.length-1);}private static void mergeSortFunc(int[] array,int left,int right) {if(left right) {return;}int mid (leftright) / 2;mergeSortFunc(array,left,mid);//将数据进行拆分mergeSortFunc(array,mid1,right);merge(array,left,right,mid);//将数据合并}private static void merge(int[] array,int start,int end,int mid) {int s1 start;//int e1 mid;int s2 mid1;//int e2 end;int[] tmp new int[end-start1];int k 0;//tmp数组的下标while (s1 mid s2 end) {if(array[s1] array[s2]) {tmp[k] array[s1];}else {tmp[k] array[s2];}}while (s1 mid) {tmp[k] array[s1];}while (s2 end) {tmp[k] array[s2];}for (int i 0; i tmp.length; i) {array[istart] tmp[i];}}public static void mergeSort(int[] array) {int gap 1;while (gap array.length) {// i gap * 2 当前gap组的时候去排序下一组for (int i 0; i array.length; i gap * 2) {int left i;int mid left gap - 1;//有可能会越界if (mid array.length) {mid array.length - 1;}int right mid gap;//有可能会越界if (right array.length) {right array.length - 1;}merge(array, left, right, mid);}//当前为2组有序 下次变成4组有序gap * 2;}}
【归并排序总结】
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定
计数排序 基本思想
1找出待排序的数组中最大和最小的元素2统计数组中每个值为i的元素出现的次数存入数组C的第i项3对所有的计数累加从C中的第一个元素开始每一项和前一项相加4反向填充目标数组将每个元素i放在新数组的第C(i)项每放一个元素就将C(i)减去1
复制一个动图演示 代码如下
public static void countSort(int[] array) {//1. 遍历数组 找到最大值 和 最小值int max array[0];int min array[0];//O(N)for (int i 1; i array.length; i) {if(array[i] min) {min array[i];}if(array[i] max) {max array[i];}}//2. 根据范围 定义计数数组的长度int len max - min 1;int[] count new int[len];//3.遍历数组在计数数组当中 记录每个数字出现的次数 O(N)for (int i 0; i array.length; i) {count[array[i]-min];}//4.遍历计数数组int index 0;// array数组的新的下标 O(范围)for (int i 0; i count.length; i) {while (count[i] 0) {//这里要加最小值 反应真实的数据array[index] imin;index;count[i]--;}}}
参考链接
1.8 计数排序 | 菜鸟教程 (runoob.com)
【计数排序总结】 时间复杂度O(n 范围) 空间复杂度O(范围) 稳定性稳定 计数排序只使用于数据范围集中的情况使用场景较少 排序总结
排序分类 排序方法最好平均最坏空间复杂度稳定性冒泡排序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 * log(n))O(n * log(n))O(n * log(n))O(1)不稳定快速排序O(n * log(n))O(n * log(n))O(n^2)O(log(n)) ~ O(n)不稳定归并排序O(n * log(n))O(n * log(n))O(n * log(n))O(n)稳定
