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

算法之排序/sort

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

算法之排序/sort

排序算法/sort

基本的排序算法

  • 冒泡排序/Bubble Sort
  • 插入排序 / Insertion Sort

常考的排序算法

  • 归并排序/Merge Sort
  • 快速排序/Quick Sort
  • 拓扑排序/Topological Sort

其他排序算法

  • 堆排序/Heap Sort
  • 桶排序/Bucket Sort 

冒泡排序

题目:对一个数组使用冒泡排序进行升序/降序排列
空间复杂度:O(1)
时间复杂度:O(n^2)

public  void bubbleSort(int[] ary) {
    //外层or循环表示轮数
    for (int i=0; iary[j+1]){
                int tmp = ary[j];
                ary[j]=ary[j+1];
                ary[j+1] = tmp;
            }
        }
    }
}
String[] ary = {"tom","amy","jack","rose","张三","李四"};
        //使用冒泡排序对String[]进行升序排列
        for (int i=0;i0){
                    String tmp = ary[j];
                    ary[j]= ary[j+1];
                    ary[j+1]=tmp;
                }
            }
        }
        System.out.println(Arrays.toString(ary));

插入排序

不断地将尚未排好序的数插入到已经排好序的部分。在插入排序中,经过每一轮的排序处理后,数组前端的数都是排好序的。
空间复杂度:O(1)
时间复杂度:O(n^2)

void insertionSort(int[] nums) {
    for (int i =1, j,current; i < nums.length; i++){
        current = nums[i];
        for ( j = i - 1; j >= 0 && nums[j] > current; j--){
            nums[j +1] = nums[j];
        }
        nums[j + 1] = current;
    }
}

归并排序

归并排序的核心思想是分治,把一个复杂问题拆分成若干个子问题来求解。把数组从中间划分成两个子数组;一直递归地把子数组划分成更小的子数组,直到子数组里面只有一个元素;
空间复杂度:O(n)
时间复杂度:O(nlogn)

 

void sort(int[] A, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo +(hi - lo)/ 2;
    sort(A,lo, mid);
    sort(A, mid + 1, hi);
    merge(A,lo, mid, hi);
}
void merge(int[] nums, int lo, int mid, int hi) {
    int[]copy = nums.clone();
    int k = lo, i = lo, j = mid + 1;
    while (k <= hi){
        if (i > mid) {
            nums[k++] = copy[j++];
        }else if(j >hi) {
            nums[k++] = copy[i++];
        }else if (copy[j] 

快速排序/ Quick Sort

快速排序也采用了分治的思想;
把原始的数组筛选成较小和较大的两个子数组,然后递归地排序两个子数组;
在分成较小和较大的两个子数组过程中,如何选定一个基准值尤为关键。

时间复杂度:O(n^2)
空间复杂度:O(Iogn)
 

void sort(int[] nums,int lo,int hi){
    if (lo >= hi) return;
    int p = partition(nums, lo, hi);    
    sort(nums,lo,p - 1);
    sort(nums, p + 1,hi);
}
int partition(int[] nums, int lo,int hi) {
    swap(nums,randRange( lo,hi), hi);
    int i,j;
    for (i = lo, j = lo; j 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/950610.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

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

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