栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

常用排序算法总结及java实现

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

常用排序算法总结及java实现

文章目录
  • 1 冒泡排序
  • 2 选择排序
  • 3 插入排序
  • 4 希尔排序
  • 5 堆排序
  • 6 归并排序
  • 7 快速排序

1 冒泡排序
  • 冒泡排序(Bubble Sort):一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。
  • 时间复杂度 O ( n 2 ) O(n^2) O(n2)
//冒泡排序
public void bubbleSort(int[] arr){
    int len=arr.length;
    boolean flag;//标识是否发生了交换
    for (int i = 0; i 
        flag=false;
        for (int j = len-1; j >i ; j--) {
            //轻者上浮
            if(arr[j-1]>arr[j]){
                swap(arr,j-1,j);
                flag=true;
            }
        }
        if(!flag) break;//全程无交换
    }
}
2 选择排序
  • 选择排序(Selection Sort)就是通过 n-i 次关键字间的比较,从 n-i+1 个记录中选出关键字最小的记录,并和第 i(0
  • 时间复杂度 O ( n 2 ) O(n^2) O(n2)
//选择排序
public void selectSort(int[] arr){
    int len=arr.length;
    for (int i = 0; i 
        int min=i; //定义当前元素为最小元素
        for (int j = i+1; j 
            if(arr[j]
                //如果有更小的元素,更新min
                min=j;
            }
        }
        if(min!=i) swap(arr,min,i);
    }
}
3 插入排序
  • 插入排序(Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。
  • 时间复杂度 O ( n 2 ) O(n^2) O(n2);同样的时间复杂度,但插入排序比冒泡排序和选择排序的性能要好一些
  • 插入排序的效率在某些时候是很高的,比如,我们的记录本身就是基本有序的,我们只需要少量的插入操作,就可以完成整个记录集的排序工作,此时直接插入很高效。还有就是记录数比较少时,直接插入的优势也比较明显。可这两个条件本身就过于苛刻,现实中记录少或者基本有序都属于特殊情况。
//插入排序
public void insertSort(int[] arr){
    int len=arr.length;
    for (int i = 1; i < len ; i++) {
        int tmp=arr[i];
        int j;
        for (j = i; j>0 && tmp < arr[j-1] ; j--) {
            //当遍历到索引0的位置 或 当前选择的插入元素已经不比前面的元素小,退出循环
            arr[j]=arr[j-1];
        }
        arr[j]=tmp;
    }
}
4 希尔排序
  • 间隔取值排序,先引入增量序列(增量序列相邻元素最好互质),再插入排序或者冒泡排序
  • 时间复杂度 O ( n 5 4 ) O(n^{frac 54}) O(n45​)、 O ( n 7 6 ) O(n^{frac 76}) O(n67​) …(具体幂次由增量序列决定)
//希尔排序
public void shellSort(int[] arr){
    int len=arr.length;
    //最后一个增量必须为1
    for (int gap = len/3+1; gap >0 ; gap=gap/3+1) {
        for (int i=gap;i
            int tmp=arr[i];
            int j;
            for (j = i; j>=gap && tmp < arr[j-gap] ; j-=gap) {
                arr[j]=arr[j-gap];
            }
            arr[j]=tmp;
        }
        if(gap==1) break;
    }
}
5 堆排序
  • 基于优先队列,每次取出最大(或最小)元素,放入另外一个数组,以此实现排序
  • 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。一共执行n次deleteMax操作,每次都要执行percDown,每个percDown花费 O ( l o g n ) O(logn) O(logn)时间,所以总的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
//堆排序
public void heapSort(int[] arr){
    int len=arr.length;
    for (int i=len/2-1;i>=0;i--) // buildHeap
        percDown(arr,i,len);
    for (int i=len-1; i>0; i--) { // deleteMax
        swap(arr,0,i);
        percDown(arr,0,i);
    }
}
// 向下过滤(最大堆)
private void percDown(int[] arr,int hole,int len)  {
    int child;
    int tmp=arr[ hole ];
    // hole * 2+1 < len 可以保证hole绝对有孩子结点
    for( ; hole * 2+1 < len; hole = child ) {
        child = hole * 2+1;
        // child不是最后一个结点 and 右孩子大于左孩子
        if( child != len-1 &&
                arr[child+1]>arr[child])
            child++;
        // 这里已经筛选出了两个孩子中最大的;
        if( arr[ child ]>tmp ) // 父结点小于(最大的)孩子,故父结点与(大)孩子交换位置
            arr[ hole ] = arr[ child ];
        else // 父结点大于两个孩子
            break;
    }
    arr[ hole ] = tmp;
}
6 归并排序
  • 归并排序是经典的分治策略,其基本思想是:将待排序数组一分为二,分别实现归并排序,当数组长度为1时,显然并不需要排序,直接返回即可。
  • 时间复杂度 O ( n l o g n ) O(n logn) O(nlogn)
//归并排序
public void mergeSort(int[] arr){
    int[] tmparr=new int[arr.length];
    mergeSort(arr,tmparr,0,arr.length-1);
}
private void mergeSort(int[] arr,int[] tmparr,int left,int right){
    if(left
        int mid=(left+right)/2;
        mergeSort(arr,tmparr,left,mid);
        mergeSort(arr,tmparr,mid+1,right);
        merge(arr,tmparr,left,mid+1,right);
    }
}
private void merge(int[] arr,int[] tmparr,int left,int mid,int right){
    int i=left,j=mid,tmp=left;
    while (i<=mid-1 && j<=right){
        if (arr[i]<=arr[j]) tmparr[tmp++]=arr[i++];
        else tmparr[tmp++]=arr[j++];
    }
    while (i<=mid-1) tmparr[tmp++]=arr[i++];
    while (j<=right) tmparr[tmp++]=arr[j++];
    for (int k = left; k <=right ; k++) {
        arr[k]=tmparr[k];
    }
}
7 快速排序
  • 先在前中后三个位置选取主元,然后从首尾开始遍历所有元素,比主元小的放在主元左边,比主元大的放在主元右边
  • 时间复杂度 O ( n l o g n ) O(n logn) O(nlogn)
  • 对于很小的数组(N≤20),快速排序不如插入排序。一种好的截止范围( cutoff range)是N=10(一般5-20均可),即N≤10时,使用插入排序。
//快速排序
public void quickSort(int[] arr){
    quickSort(arr, 0, arr.length-1);
}
private void quickSort(int[] arr,int left,int right){
    if(right-left<10){
        insertSort(arr,left,right);
        return;
    }
    //选取主元
    int mid=(left+right)/2;
    if(arr[mid]
        //如果有元素等于pivot,也要停下来进行交换
        while (arr[++i]pivot);
        if(i
    for (int i = left+1; i <= right ; i++) {
        int tmp=arr[i];
        int j;
        for (j = i; j>left && tmp < arr[j-1] ; j--) {
            //当遍历到索引0的位置 或 当前选择的插入元素已经不比前面的元素小,退出循环
            arr[j]=arr[j-1];
        }
        arr[j]=tmp;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/975695.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号