本帖最后由 小爷邱烙 于 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;
- }
- }
遍历数组依次取出每个元素，当取出第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;
- }
- }
- }
希尔排序是插入排序的一种改进，其底层使用的还是插入排序的方法，只不过把数组按照一定的规则，由大到小，分成不同的区域，再依次使用插入排 序，由于插入排序在处理小数据量的时候效率明显，希尔排序能有效提高速度，了解一下就行
代码实现：
- 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;
- }
- }
- }
- }
- }
|
收藏
淘帖
踩
