首页 > 编程语言 >常见排序算法

常见排序算法

时间：2023-12-14 22:15:03浏览次数：29  
标签：sort arr int void 常见 算法 数组 排序

排序

常见的简单排序算法

I. 选择排序

选择排序思路：选择出数组中的最小元素，将它与数组的第一个元素交换位置。 再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。 不断进行这样的操作，直到将整个数组排序。

public void sort(int[] arr){
    int N = arr.length;
    int minIndex = -1;
    for(int i=0;i<N;i++){ // arr[i] 是当前元素
        minIndex=i;
        for(int j=i+1;j<N;j++){ //arr[j] 当前元素后面的元素
            if(arr[j]<arr[minIndex]){
                minIndex=j;
            }
        }
        if(minIndex==i){ //TODO:这里有个小优化：如果当前元素是最小的则不用交换了
            continue;
        }
        swap(arr,minIndex,i);
    }
}

private void swap(int[] arr,int i,int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

@Test
public void test(){
    int[] a={3,5,2,4,1,0,-3};
    PrintArr.printArray(a);
    sort(a);
    PrintArr.printArray(a);
}

选择排序需要 ~N2/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

II. 冒泡排序

冒泡排序思路：从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。在一轮循环中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出。

public void sort(int[] arr){
    for(int i=arr.length-1;i>0;i--){
        for(int j=0;j<i;j++){
            if(arr[j]>arr[j+1]){
                swap(arr,j,j+1);
            }
        }
    }
}

private void swap(int[] arr,int i,int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

添加一个状态变量对冒泡排序进行优化：

public void sort(int[] arr){
    boolean isSorted = false;
    for(int i=arr.length-1;i>0 && !isSorted ;i--){
        //!isSorted 条件，当 isSorted=true 时说明是有序的，则不需要再执行了
        isSorted = true; //初始时认为是有序的
        for(int j=0;j<i;j++){
            if(arr[j]>arr[j+1]){
                isSorted = false; //存在逆序，则是无序的
                swap(arr,j,j+1);
            }
        }
    }
}

private void swap(int[] arr,int i,int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

冒泡排序是稳定的排序算法，平均时间复杂度是 O(n^2)。

III、插入排序

插入排序思路：每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。

对于数组 {3, 5, 2, 4, 1}， 它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)， 插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

插入排序的复杂度取决于数组的初始顺序，如果数组已经部分有序了，逆序较少，那么插入排序会很快。

public void sort(int[] arr){
    for(int i=1;i<arr.length;i++){ //默认 arr[0] 已经有序
        //a[0,,,i] 已经有序，加入一个元素后，进行一次冒泡(从后向前的)，就必然是有序的了。
        for(int j=i;j>0 && arr[j-1]>arr[j];j--){
            swap(arr,j-1,j);
        }
    }
}

private void swap(int[] arr,int i,int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

IV、希尔排序

对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。

希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。

希尔排序思路：希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

public void sort(int[] arr){
    int N = arr.length;

    int h=1;
    while(h<N/3){
        h = 3*h+1;
    }

    while(h>=1){
        for(int i=1;i<N;i++){
            for(int j=i;j>=h && arr[j-h]>arr[j];j-=h){
                swap(arr,j-h,j);
            }
        }
        h /=3;
    }
    //注意 h 的值最终会减为 1
}

private void swap(int[] arr,int i,int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

常见的高级排序算法

I、归并排序

归并排序的思想：将数组分成两部分，分别进行排序，然后归并起来。

public void sort(int[] arr){
    sort(arr,0,arr.length-1);
}

private void sort(int[] arr,int l,int r){
    if(l>=r){
        return;
    }
    int mid = (r-l)/2+l;
    //对 [l,mid] 进行排序
    sort(arr,l,mid);
    //对 [mid+1,r] 进行排序
    sort(arr,mid+1,r);
    //合并这两个有序数组
    merge(arr,l,mid,r);
}

//合并两个有序数组
//[l,mid]
//[mid+1,r]
private void merge(int[] arr,int l,int mid,int r){
    int[] nums = new int[r-l+1];
    int index=0;
    int i=l;
    int j=mid+1;
    while(i<=mid && j<=r){
        if(arr[i]<arr[j]){
            nums[index++] = arr[i++];
        }else{
            nums[index++] = arr[j++];
        }
    }
    while(i<=mid){
        nums[index++]=arr[i++];
    }
    while(j<=r){
        nums[index++]=arr[j++];
    }

    index=0;
    for(int k=l;k<=r;k++){
        arr[k] = nums[index++];
    }
}

II、快速排序

快速排序思路：快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。

public void sort(int[] arr){
    sort(arr,0,arr.length-1);
}

private void sort(int[] arr,int l,int r){
    if(l>=r){
        return;
    }
    int p = partition(arr,l,r);
    sort(arr,l,p-1);
    sort(arr,p+1,r);
}

private int partition(int[] arr,int l,int r){
    int pivot = arr[l];
    while(l<r){
        while(l<r && arr[r]>=pivot){
            r--;
        }
        arr[l] = arr[r];
        while(l<r && arr[l]<=pivot){
            l++;
        }
        arr[r] = arr[l];
    }
    arr[l]=pivot;
    return l;
}

堆

使用数组存储二叉堆，下标从0开始：

堆排序

堆排序思路：把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。

public void sort(int[] arr){
    int N = arr.length;
    //构建大根堆
    for(int i=parent(N-1);i>=0;i--){ //从中间位置开始下沉
        sink(arr,i,N);
    }

    //大根堆的根节点就是最大值
    while(N>0){
        swap(arr,0,N-1);
        //每次交换堆的最后一个元素和堆的一个元素，每次获取的最大值
        N--; // 相当于删除堆的第一个元素
        sink(arr,0,N); //每次再从 0 位置开始下沉，维护长度为 (N-1) 的大根堆
    }
}

// 从 i 位置开始下沉
// N 是堆中元素，可以动态变化
private void sink(int[] num,int i,int N){
    while (leftChild(i)<N){
        int j = leftChild(i);
        if(j+1<N && num[j]<num[j+1]){
            j = rightChild(i);
        }
        if(num[i]>=num[j]){
            break;
        }
        swap(num,i,j); // i 位置和 j 位置元素交换
        i=j; // i 元素已经下沉，需要继续下沉
    }
}

private int parent(int i){
    if(i==0){
        throw new IllegalArgumentException("index=0 时，不存在父节点");
    }
    return (i-1)/2;
}

private int leftChild(int i){
    return 2*i+1;
}

private int rightChild(int i){
    return 2*i+2;
}

private void swap(int[] arr,int i,int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

https://www.mianshi.online，https://www.i9code.cn

标签：sort,arr,int,void,常见,算法,数组,排序
From： https://www.cnblogs.com/i9code/p/17902130.html

相关文章

  • 代码随想录算法训练营第二天| LeetCode977.有序数组的平方、209.长度最小的子数组、59
    LeetCode977.有序数组的平方●今日学习的文章链接和视频链接代码随想录(programmercarl.com) 题目链接977.有序数组的平方-力扣（LeetCode） ●自己看到题目的第一想法昨天正好做了这道题目，总体来说就是用双指针法，要么从绝对值最小的数开始排序，要么从绝对值最大的数开......
  • 算法Day2双指针法排序，滑动窗口，螺旋矩阵
    Day2双指针法排序，滑动窗口，螺旋矩阵ByHQWQF2023/12/14笔记977.有序数组的平方https://leetcode.cn/problems/squares-of-a-sorted-array/返回一个非递减顺序排序的整数数组每个元素的平方后组成的新数组，新数组也按非递减顺序排序。解法：双指针法由于给定数组本身是有序的，......
  • 算法战斗第三天C++1
    A.Bit++TheclassicprogramminglanguageofBitlandisBit++.Thislanguageissopeculiarandcomplicated.Thelanguageisthatpeculiarasithasexactlyonevariable,calledx.Also,therearetwooperations:Operation++increasesthevalueofv......
  • 机器学习中的算法——支持向量机（SVM)
    1.SVM的核心要素支持向量机是一种二分类模型，他基本模型是定义在特征空间上的间隔最大的线性分类器。通俗的说很类似于上次讲的那个回归的分类，其实从平面上看也是找一条直线来分割，分割的两边就是分类的结果，只不过这次的分类是找到一条线使得它能够对两旁的点距离最远。也就是......
  • 【合并排序链表】分治/优先队列
    合并两个排序链表模拟维护一个合并链表，每次添加两个排序链表中较小val的节点即可模拟代码publicListNodemergeTwo(ListNodea,ListNodeb){if(a==null)returnb;if(b==null)returna;ListNodeans=newListNode(0);Lis......
  • 代码随想录算法训练营第二天|977.有序数组的平方、209.长度最小的子数组、59.螺旋矩阵
    LeetCode977有序数组的平方题目链接：977.有序数组的平方思路：双指针，由两侧向中间逼近 LeetCode 209.长度最小的子数组题目链接：209.长度最小的子数组思路：滑动窗口，关键点滑动窗口起始点和终止点位置关系的确定 LeetCode 59.螺旋矩阵题目链接：59.螺旋矩阵关键点：循环处理......
  • 文心一言 VS 讯飞星火 VS chatgpt （156）-- 算法导论12.3 3题
    三、用go语言，对于给定的n个数的集合，可以通过先构造包含这些数据的一棵二叉搜索树(反复使用TREE-INSERT逐个插入这些数)，然后按中序遍历输出这些数的方法，来对它们排序。这个排序算法的最坏情况运行时间和最好情况运行时间各是多少?文心一言：在Go语言中，使用二叉搜索树（BST）进行排序......
  • 【机器学习】算法作用与依赖库合集
    算法与库1.决策树：-库： fromsklearn.treeimportDecisionTreeClassifier（分类树） fromsklearn.treeimportDecisionTreeRegressor（回归树）-计算场景：分类和回归问题2.逻辑回归：-库： fromsklearn.linear_modelimportLogisticRegression-......
  • 软件测试|测试专家（前阿里P8）聊测试职业发展常见瓶颈
    本文整理自资深测试技术专家（前阿里P8）刘**老师在「测试大咖在线沙龙」上的分享精华部分，完整演讲内容（4个经典案例+8个关键问题+100个互动答疑），请扫描文末二维码。我在测试行业工作有十多年了，由于工作经历中曾面试过很多测试工程师（粗略统计在1000人以上），见过各种各样的应聘者，也一......
  • 冒泡排序
    比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个，即需要进行length-1次。第一次是对n个数进行n-1次比较，进行到最后第n个的一......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99