东莞沙田网站建设桂林哪里可以做网站

当前位置： 首页 > news >正文

东莞沙田网站建设,桂林哪里可以做网站,it网站开发培训中心,国外建筑设计网站目录 1.理解排序
1.1 排序的概念
1.2 排序的运用场景 1.3 常见的排序算法
2.插入排序算法 2.1 直接插入排序 2.2 希尔排序 3.选择排序算法 3.1 直接选择排序 3.2 堆排序
4.交换排序算法 4.1 冒泡排序 4.2 快速排序
4.2.1 hoare 法
4.2.2 挖坑法 4.2.3 前… 目录 1.理解排序  1.1 排序的概念  1.2 排序的运用场景 1.3 常见的排序算法  2.插入排序算法 2.1 直接插入排序 2.2 希尔排序 3.选择排序算法 3.1 直接选择排序 3.2 堆排序  4.交换排序算法 4.1 冒泡排序 4.2 快速排序  4.2.1 hoare 法  4.2.2 挖坑法 4.2.3 前后指针法  4.2.4 三数取中法  5.归并排序算法  6. 排序算法复杂度及稳定性分析 1.理解排序  1.1 排序的概念  排序的概念排序无非就是将一组数据按照其中某个或者某些关键字的大小进行从大到小或者从小到大的顺序排列 升序也称递增也就是从小到大排序  降序也称递减也就是从大到小排序  排序按照稳定性可以分为稳定性排序和不稳定性排序  稳定性排序假设我们现在有一组数据数据中有两个相同的元素。排序完后这两个相同元素的顺序依旧保持原来的顺序在前面的那个元素排序完后依旧在另一个的前面这就是稳定性排序不稳定性排序假设我们现在有一组数据数据中有两个相同的元素。排序完后这两个相同元素的顺序可能会发生变化在前面的那个元素排序完后可能在另一个元素的后面这就是不稳定性排序排序按照排序所在的地方可以分为内部排序和外部排序 内部排序数据元素全部放在内存中的排序 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序 1.2 排序的运用场景 例1我们应该每个人都会用QQ和微信这种通信软件当我们未设置置顶的时候它会默认按照别人所发消息的时间进行排序  例2我们通常都会用淘宝进行购物当我们点击销量时它会按照销量进行排序  1.3 常见的排序算法  我们常见的排序算法有七个分别为直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序 这七个常见的排序又可以分为四类分别为 插入排序、选择排序、交换排序、归并排序 2.插入排序算法 2.1 直接插入排序 直接插入排序大家应该都玩过扑克牌玩扑克牌的时候大家都会一张一张的拿牌每拿到一张牌我们都会将其插入到合适的位置这就是直接插入排序 假设我们现在有一个数组为 {5,2,4,6,1,3} 现在需要采用直接插入排序算法进行排序 直接插入排序思路通过循环遍历数组让 end 存放数组第一个元素的下标tmp 存放的是 end 后面一个元素的值。然后内循环判断 end 是否大于等于 0如果大于等于 0 则进入内循环若为升序排序则判断 tmp 中存放的值是否小于 end 下标对应的值如果时则将 end 下标对应的值放在 end1 下标位置上往后移然后让 end–若 end0 就跳出循环 如果 tmp 中存放的值不小于 end 下标对应的值。跳出内循环后让 end1 下标对应数组元素等于 tmp。然后使 end 指向第二个元素的下标同样的方法依次比较。 //直接插入排序 public void insertSortDirectly(int[] arr) {for (int i 0; i arr.length - 1; i) {int end i;int tmp arr[end 1];while (end 0) {if (tmp arr[end]) {arr[end 1] arr[end];end–;} else {break;}}arr[end 1] tmp;} } 直接插入排序的特性总结 当元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定2.2 希尔排序 希尔排序法又称缩小增量法其实相当于直接插入排序的进阶版它比直接插入排序多了预排序 希尔排序分为两步预排序让数据接近有序直接插入排序让数据有序 希尔排序思想先选定一个整数存放在 gap 变量中把待排序数据按照 gap 大小分成组所有距离为 gap 的分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达 gap1 时所有数据在统一组内排好序。  假设我们现在有一个数组为 {5,2,4,6,1,3} 现在需要采用希尔排序算法进行排序 //希尔排序 public void shellSort(int[] arr) {int gap arr.length;//预排序while (gap 1) {gap gap / 2;for (int i 0; i arr.length - gap; i) {int end i;int tmp end gap;while (end 0) {if (tmp arr[end]) {arr[end gap] arr[end];end end - gap;} else {break;}}arr[end gap] tmp;}} } gap值应该如何设定 gap值通常设为数据长度的一半然后依次除 2。当 gap 不为 1 时都为预排序当 gap 为 1 时就是直接插入排序  希尔排序的特性总结 希尔排序是对直接插入排序的优化当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时就是直接插入排序。它与直接插入排序的区别就是多了一个预排序这样使时间效率更好希尔排序的时间复杂度不好计算需要进行推导推导出来平均时间复杂度 O(N^1.3— N^2稳定性不稳定3.选择排序算法 选择排序每一次从待排序的数据元素中选出最小或最大的一个元素存放在未排序序列的起始位置直到全部待排序的数据元素排完即可   3.1 直接选择排序 直接选择排序 每一次从待排序的数据元素中选出最小或最大的一个元素与未排序序列的起始位置交换直到全部待排序的数据元素排完即可 //直接选择排序 public void directSelectSort(int[] arr) {for (int i 0; i arr.length; i) {int min i;for (int j i 1; j arr.length; j) {if (arr[j] arr[min]) {min j;}}int tmp arr[i];arr[i] arr[min];arr[min] tmp;} } 除了上面的每次使一个元素归位以外还可以每次使两个元素归位每次遍历找到最小的和未排序的第一个元素交换找到最大的和未排序的最后一个元素交换 public void directSelectSort(int[] arr) {for (int i 0; i arr.length; i) {int min i;int max i;for (int j i 1; j arr.length; j) {if (arr[j] arr[min]) {min j;}if (arr[j] arr[max]) {max j;}}int tmp arr[i];arr[i] arr[min];arr[min] tmp;if (max i) {max min;}} } 但是需要注意一个问题就是当待排序的数据元素中第一个是最大值时应该怎么办 当待排序的数据元素中第一个是最大值时在将待排序中最小的值与待排序第一个值交换后还需要将 max 等于 min 直接选择排序的特性总结 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定3.2 堆排序  在上一篇文章中我们已经学习了堆大家也了解了什么是堆也模拟实现了堆那接下来我们就来看看如何采用堆来进行排序 如果想要进行堆排序首先需要构造一个堆如果是升序就构大堆降序就构小堆 然后构造好堆后让堆顶元素与最后一个有效元素交换位置那么最后一个有效元素也就排好序了将有效元素减一在向下调整创建堆。然后依次这样交换向下调整知道所有位置的元素都排好序  假设我们现在有一组数据需要将其排升序  //堆排序 public void heapSort(int[] arr) {buildHeap(arr);//建堆int size arr.length - 1;int first 0;while (first size) {int tmp arr[first];arr[first] arr[size];arr[size] tmp;size–;shiftDown(arr,first ,size1);} } //建堆 public void buildHeap(int[] arr) {if (arr null) {return;}int lastNoLeafNode (arr.length - 1 - 1) / 2;while (lastNoLeafNode 0) {shiftDown(arr,lastNoLeafNode,arr.length);lastNoLeafNode–;} }//向下调整,建大顶堆 public void shiftDown(int[] arr, int parent, int size) {int child parent * 2 1;while (child size) {if (child 1 size arr[child 1] arr[child]) {child 1;}if (arr[parent] arr[child] ) {break;} else {int tmp arr[parent];arr[parent] arr[child];arr[child] tmp;parent child;child parent * 2 1;}} } 堆排序的特性总结 堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定4.交换排序算法 交换排序基本思想所谓交换排序也就是将数据序列中的两个数据值进行比较满足条件则进行交换主要思想就是要进行交换 升序排序就把数据值大的向后移动数据值小的向前移动  降序排序就把数据值小的向后移动数据值大的向前移动  4.1 冒泡排序 冒泡排序的思想每比较一趟就会使一个值进行归位所以一共要比较 n-1 趟才能使全部数据归位 假设现在有这样一组数据序列 {2,5,4,6,3,1}要通过冒泡排序算法来进行排序   //冒泡排序 public void bubbleSort(int[] arr) {for (int i 0; i arr.length - 1; i) {for (int j 1; j arr.length - i; j) {if (arr[j - 1] arr[j]) {int tmp arr[j - 1];arr[j - 1] arr[j];arr[j] tmp;}}} } 如果我们数据序列本来就是有序的难道我们还需要比较 n-1 趟嘛 答不需要我们直接用一个变量来记录是否交换了数据如果比较完一趟后并没有发生交换直接跳出即可 冒泡排序的特性总结 冒泡排序是一种非常容易理解的排序时间复杂度O(N^2)空间复杂度O(1)稳定性稳定 4.2 快速排序  快速排序基本思想任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止 public void quickSort(int[] arr,int left,int right) {if (left right) {return;}//调用快速排序int mid hoareSort(arr,left,right);quickSort(arr,left,mid-1);quickSort(arr,mid 1,right);} 上述是采用递归的方法来调用快速排序算法首先将一个大排序通过递归分成一些小排序来进行排序 那接下来我们就学习三种快速排序算法分别是hoare法、挖坑法、左右指针法  4.2.1 hoare 法  基准值key通常指向第一个位置然后从右边找比基准值小的值左边找比基准值大的值找到之后进行交换当 left 和 right 指向同一个地方说明基准值的最终位置找到 public int hoareSort(int[] arr,int left,int right) {int key left;while (left right) {while (left right arr[right] arr[key]) {right–;}while (left right arr[left] arr[key]) {left;}swap(arr,left,right);}swap(arr,key,left);return left; }public void swap(int[] arr,int left,int right) {int tmp arr[left];arr[left] arr[right];arr[right] tmp; } 4.2.2 挖坑法 首先将第一个值当作基准值放入 key 中那么第一个位置就形成了一个坑从右边找比基准值小的放入左边的坑中那么右边的这个位置也就形成了一个坑再从左边找比基准值大的放入右边的坑中最后 left 和 right 同时指向的地方就是基准值最终的位置  public int digPitSort(int[] arr,int left,int right) {int key arr[left];while (left right) {while (left right arr[right] key) {right–;}arr[left] arr[right];while (left right arr[left] key) {left;}arr[right] arr[left];}arr[left] key;return left; } 4.2.3 前后指针法  首先将第一个值当作基准值将其下标放入 key 中然后让 after 存放第一个元素的下标front 存放第二个元素的下标front right 就进入循环然后判断 front 下标里面的元素是否小于基准值如果小于再判断 after 是否不等于基准值如果满足就进行交换然后再 front 。直到 front 不小于 right 不进入循环然后将基准值与 after 的位置交换基准值归位。 //前后指针法 public int frontBack(int[] arr,int left,int right) {int key left;int after left;int front left 1;while (front right) {if (arr[front] arr[key] arr[after] ! arr[key]) {swap(arr,after,front);}front;}swap(arr,key,after);return after; }public void swap(int[] arr,int after,int front) {int tmp arr[after];arr[after] arr[front];arr[front] tmp; } 4.2.4 三数取中法  当序列为有序的时候快速排序的时间复杂度为 O(N^2)  为了避免这种情况也就可以采用三数取中法  三数取中法思路对比第一个下标的数和中间下标的数与最后下标的数返回中间数不是最大也不是最小 //三数取中法 public int getMidIndex(int[] arr,int left,int right) {int mid (left right) 1;if (arr[left] arr[mid]){if (arr[mid] arr[right]) {return mid;} else if (arr[left] arr[right]) {return left;} else {return right;}} else {if (arr[mid] arr[right]) {return mid;} else if (arr[left] arr[right]) {return left;} else {return right;}} } 快速排序的特性总结 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序时间复杂度O(N*logN)空间复杂度O(logN)稳定性不稳定 5.归并排序算法  归并排序基本思想 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 //归并排序 public void mergeSort(int[] arr,int left,int right) {//分解if (left right) {return;}int mid (left right) / 2;mergeSort(arr,left,mid);mergeSort(arr,mid1,right);//合并merge(arr,left,mid,right); } public void merge(int[] arr,int left,int mid,int right) {int s1 left;int s2 mid 1;int[] ret new int[(right - left) 1];int i 0;while (s1 mid s2 right) {if (arr[s1] arr[s2]) {ret[i] arr[s1];} else {ret[i] arr[s2];}}while (s1 mid) {ret[i] arr[s1];}while (s2 right) {ret[i] arr[s2];}for (int j 0; j ret.length; j) {arr[jleft] ret[j];} } 归并排序的特性总结 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定6. 排序算法复杂度及稳定性分析 排序方法最好情况平均情况最坏情况空间复杂度稳定性冒泡排序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)稳定