本帖最后由 小爷邱烙 于 2014-11-6 00:07 编辑
最近看完数组排序,查些资料对排序进行了一点总结
1、排序的分类
排序
|------内部排序(只使用内存排序)
|------插入排序
|------直接插入排序
|------希尔排序
|------选择排序
|------简单选择排序
|------堆排序
|------交换排序
|------冒泡排序
|------快速排序
|------归并排序
|------基数排序
|------外部排序(使用内存和外存结合,大数据量,内存存储不下的情况,太高端,不研究)
2、常见的java排序算法主要就是四种:快速排序,简单选择排序,冒泡排序,插入排序
毕老师的视频里已经详细讲解了简单选择排序和冒泡排序,这里主要说一下快速排序,插入排序,顺便提一下毕老师提到的希尔排序
3、提到排序,一定会说效率,这里简单说一下常见排序的效率比较
*正常情况:数组中数据随机,数据大小分布平均(可以理解为数组中的每一个元素都是通过随机数产生的)
*最好情况:数组元素按照由小到大的顺序排列(顺序)
*最坏情况:数组中的元素按照从大到小的顺序排列(逆序)
冒泡排序三种情况下都是所有排序中效率最低的(所以只适合当成一种算法来研究)
最好情况下:选择排序跟冒泡一样慢,其他排序效率都很快(选择排序三种情况下也很慢,也不适合使用)
正常情况下和最坏情况下:选择和插入排序较慢,快速和希尔排序较快
4、快速排序
快速排序是最常用的排序,Arrays.sort();方法底层用的就是快速排序。
其思想是取数组中的任意一个元素(一般是第一个元素)作为基准,遍历数组,将小于基准的元素放在基准元素左边,大于基准的元素放在基准元素 的右边,此时基准元素已经处于正确的位置。将基准左边的元素看作一个新的数组,将基准右边的元素看作一个新的数组,通过递归,重复上边的操
作,直到每个元素都处于正确的位置。
代码实现
- public class FastSort {
- public static void fastSort(int[] arr,int min,int max){
- if(min<max){
- int mid = getMiddle(arr, min, max);
- fastSort(arr, min, mid-1);
- fastSort(arr, mid+1, max);
- }
- }
- public static int getMiddle(int[] arr,int min,int max){
- int temp = arr[min];
- while(min<max){
- while(min<max&&arr[max]>=temp){
- max--;
- }
- arr[min] = arr[max];
- while(min<max&&arr[min]<=temp){
- min++;
- }
- arr[max] = arr[min];
- }
- arr[min] = temp;
- return min;
- }
- }
复制代码 5、插入排序
遍历数组依次取出每个元素,当取出第N个元素时,假设前面N-1个元素已经排好顺序,将第N个元素按照从小到大的规则,插入到前面的序列中
插入排序比较好理解,代码实现:
- public static void insertSort(int[] arr){
- for(int i=0;i<arr.length;i++){
- for(int j=i;j>0;j--){
- if(arr[j]<arr[j-1]){
- int temp = arr[j];
- arr[j] = arr[j-1];
- arr[j-1] = temp;
- }else
- break;
- }
- }
- }
复制代码 6、希尔排序
希尔排序是插入排序的一种改进,其底层使用的还是插入排序的方法,只不过把数组按照一定的规则,由大到小,分成不同的区域,再依次使用插入排 序,由于插入排序在处理小数据量的时候效率明显,希尔排序能有效提高速度,了解一下就行
代码实现:
- public static void shellSort(int[] arr){
- for(int i=arr.length/2;i>0;i/=2){
- for(int j=i;j<arr.length;j++){
- for(int k=j;k>=i;k-=i){
- if(arr[k-i]>arr[k]){
- int temp = arr[k];
- arr[k] = arr[k-i];
- arr[k-i] = temp;
- }
- }
- }
- }
- }
复制代码
|