数据结构与算法——排序篇

2019-11-08 01:12:19

字体：大中小

来源：转载

供稿：网友

　　学习java编程也快一年的时间了，都没有好好的写过博客！看着很多大神都在推荐使用博客记录下自己的学习笔记，便打算慢慢开始养成这种习惯。　　最近一直在整理数据结构与算法，以备几个月之后的秋招，想了半天打算就从排序开启我的博客之旅吧！

1. 快速排序

　　快排是目前使用比较多，速度比较快的排序算法。Collections.sort(arr)函数的底层使用了快排。　　在快速排序中核心思想为：寻找基准，根据基准将数组分为大于基准和小于基准两组。一般普遍采用最左边数据或者最右边的数据，但是采用这种的情况下时间复杂度在最差情况下会降到o(n^2)，对基准进行改进。将数组的最左边、中间、最右边进行排序，并将中间值作为基准。如此可以减少越界的判断并且基本可以防止出现最差情况。　　其中快速排序：平均复杂度o(nlogn) 最好o(nlogn) 最差o(n^2) 空间复杂度o(1) 稳定性为不稳定。其中本文采用的是递归版的快排，在这种情况下实际的空间使用是比较大的！

public static void quickSort(int[] arr, int left, int right){ if(arr == null || arr.length <=0) return; if(left>right) return; //获取基准 int pivot = getPivot(arr,left,right); quickSort(arr, left, pivot-1); quickSort(arr, pivot+1, right); } //最右边为基准PRivate static int getPivot(int[] arr, int left, int right) { int leftPtr = left-1; int rightPtr = right; int pivot = right; while(true){ while(arr[++leftPtr] < arr[pivot]); while(rightPtr > 0 && arr[--rightPtr] > arr[pivot]); if(rightPtr <= leftPtr) break; else{ swap(arr,rightPtr,leftPtr); } } swap(arr,leftPtr,right); return leftPtr; }

２.归并排序 　　归并排序也运用了最重要的一种编程思想－－分治思想。归并最大的缺点是使用较多的额外空间，如果数据量过大的情况下，内存消耗较大。优点是最差情况下时间复杂度也为o(nlogn)。　　归并排序：平均复杂度o(nlogn) 最好o(nlogn) 最差o(nlog) 空间复杂度o(n) 稳定性为稳定归并排序的动画图解

public static void mergeSort(int[] arr,int left,int right){ if(arr == null || arr.length <=0) return; if(right <= left) return; int middle = (left+right)/2; mergeSort(arr,left,middle); mergeSort(arr,middle+1,right); merge(arr,left,middle,right); } private static void merge(int[] arr, int left, int middle, int right) { int[] temp = new int[right-left+1]; int i=left; int j=middle+1; int k=0; while(i<=middle && j<=right){ if(arr[i] < arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++]; } while(i<=middle){ temp[k++] = arr[i++]; } while(j<=right){ temp[k++] = arr[j++]; } for(int p =0;p<temp.length;p++){ arr[left++] = temp[p]; } }

3.计数排序 　　计数排序是一种很有意思的排序方式，因为在一定条件下，它可以实现线性时间复杂度。我在认识计数排序之前，是先熟悉bithash算法的，其实我觉得这两者是很相像的，无非就是使保存一个数变成了保存在第i个数组中，即有一个额外空间C，使第i个元素的值等于待排列数组中数值等于i的元素的个数。　　其中额外空间Ｃ有一个要求，空间大小要比待排列数组中最大值大。计数排序：平均复杂度o(n+k) 最好o(n+k) 最差o(n+k) 空间复杂度o(k) 稳定性为稳定

public static void countingSort(int[] arr){ if(arr == null || arr.length <=0) return; int max = maxNum(arr); int[] count = new int[max+1]; for(int i=0;i<arr.length;i++){ count[arr[i]]++; } int k=0; for(int i=0;i<count.length;i++){ while(count[i] >0){ arr[k++] = i; count[i]--; } } } public static int maxNum(int[] arr) { int max = Integer.MIN_VALUE; for(int ele : arr) { if(ele > max) max = ele; } return max; }

　　本文主要就介绍这三种常见的排序算法，算是我学习排序这段时间内觉得比较有意思的三种思想，特别是对于分治的思想要牢记，有时候感觉事情非常复杂的时候，采用分治思想就会觉得豁然开朗。

上一篇：activiti工作流的web流程设计器整合视频教程 SSM和独立部署

下一篇：[转] matlab 怎样做直线检测？