• 算法学习:排序


    一、O(n^2)排序算法

    (一)、冒泡排序

    package Sort_Zhu;
    
    /*
        冒泡排序:从第一个数开始,依次与后面的数进行比较,依次找到最大的
        时间复杂度:O(n^2)
        eg:{3,52,15,62,9,32}
        第一次冒泡:3,15,52,9,32,62
        第二次冒泡:3,15,9,32,52,62
        第三次冒泡:3,9,15,32,52,62
        第四次冒泡:没有数据交换,直接退出程序
     */
    public class MpSort {
        public static void main(String[] args) {
            int[] a = new int[]{3,52,15,62,9,32};
            mpsort(a,6);
            for (int i = 0; i < a.length;i++){
                System.out.println(a[i]);
            }
        }
    
        public static void mpsort(int[] a, int n){
            if (n == 1){
                return;
            }
    
            for (int i = 0; i < n; i++){
                boolean flag = false;
                for (int j = 0;j < n -i - 1; j++){
                    if (a[j] > a[j+1]){
                        int tmp = a[j];
                        a[j] = a[j + 1];
                        a[j + 1] = tmp;
                        flag = true;
                    }
                }
                if (!flag){
                    break;
                }
            }
        }
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    (二)、插入排序

    package Sort_Zhu;
    
    /*
        插入排序:从第二个数开始,依次与前面的数进行比较,插入到合适的位置
        时间复杂度:O(n^2)
        eg:{6,52,3,12,35,91}
        第一次插入:6,52,3,12,35,91(52 > 16不需要插入)
        第二次插入:3,6,52,12,35,91
        第三次插入:3,6,12,52,35,91
        第四次插入:3,6,12,35,52,91
        顺序已经正确,后面无需排序
     */
    public class InsertSort {
        public static void main(String[] args) {
            int[] a = new int[]{6,52,3,12,35,91};
            insertsort(a,6);
            for (int i = 0; i < a.length;i++){
                System.out.println(a[i]);
            }
        }
    
        public static void insertsort(int[] a,int n){
            if (n == 1){
                return;
            }
    
            for (int i = 1; i < n; i++){
                int tmp = a[i];
                int j = i - 1;
                for (;j >= 0; j--){
                    if (a[j] > tmp){
                        a[j+1] = a[j];
                    }else{
                        break;
                    }
                }
                a[j+1] = tmp;
            }
        }
    }
    
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    (三)、选择排序

    package Sort_Zhu;
    /*
        选择排序:会从未排序区间中找到最小的值,放入已排序区间的末尾
        时间复杂度:O(n^2)
        eg:{3,52,6,16,4,9};
        第一次选择:3,52,6,16,4,9
        第二次选择:3,4,6,16,52,9
        第三次选择:3,4,6,16,52,9
        第四次选择:3,4,6,9,52,16
        第五次选择:3,4,6,9,16,52
     */
    public class SelectSort {
    
        public static void main(String[] args) {
            int[] a = new int[]{3,52,6,16,4,9};
            selectsort(a,6);
            for (int i = 0; i < a.length; i++){
                System.out.println(a[i]);
            }
        }
    
        public static void selectsort(int[] a,int n){
            if (n == 1){
                return;
            }
    
    
            for (int i = 0; i < n; i++){
                int min = a[i];
                int k = i;
                for (int j = i + 1;j < n; j++){
                    if (a[j] < min){
                        min = a[j];
                        k = j;
                    }
                }
                int tmp = a[i];
                a[i] = min;
                a[k] = tmp;
            }
        }
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    二、O(nlogn)排序算法

    (一)、合并排序

    package Sort_Zhu;
    
    /*
        归并排序:利用递归的思想对两边的数组分别进行排序,然后比较两个有序数组并且合并
        1)、稳定排序,相同值排序后还能保持前后关系
        2)、非原地排序,需要额外申请O(n)的临时数组
        3)、时间复杂度(On*logn)
     */
    public class MergeSort {
        public static void mergesort(int[] a,int left,int right,int[] tmp){
            if (left < right){
                //递归终止条件
                int mid = (left + right) / 2;
                mergesort(a,left,mid,tmp);
                mergesort(a,mid+1,right,tmp);
                sort(a,left,mid,right,tmp);
            }
        }
    
        public static void sort(int[] a,int left,int mid,int right,int[] tmp){
            int i = left;
            int j = mid + 1;
            int index = 0;
    
            while (i <= mid && j <= right){
                if (a[i] > a[j]){
                    tmp[index] = a[j];
                    index++;
                    j++;
                }else{
                    tmp[index] = a[i];
                    index++;
                    i++;
                }
            }
    
            while(i <= mid){
                tmp[index] = a[i];
                index++;
                i++;
            }
    
            while(j <= right){
                tmp[index] = a[j];
                index++;
                j++;
            }
    
            index = 0;
            while (left <= right){
                a[left] =tmp[index];
                left++;
                index++;
            }
        }
    
        public static void main(String[] args) {
            int[] a = new int[]{38,12,5,98,42,7,342,11,52,62,98,13,41,512,53,111};
            int[] tmp = new int[a.length];
            mergesort(a,0,a.length - 1,tmp);
    
            for (int i = 0; i < a.length;i++){
                System.out.println(a[i]);
            }
        }
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67

    (二)、快速排序

    package Sort_Zhu;
    
    public class QuickSort {
        public static void quicksort(int[] a,int p,int q){
            if (p >= q){
                return;
            }
    
            int r = partition(a,p,q);
            quicksort(a,p,r-1);
            quicksort(a,r+1,q);
        }
    
        public static int partition(int[] a,int start,int end){
            int provt = a[end];
            int i = start;
            for (int j = start;j < end;j++){
                if (a[j] < provt){
                    swap(a,i,j);
                    i += 1;
                }
            }
            swap(a,end,i);
            return i;
        }
    
        public static void swap(int[] a,int i,int j){
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    
    
        public static void main(String[] args) {
            int[] a = new int[]{342,62,12,52,6,9,23,85,92,215};
            quicksort(a,0,a.length - 1);
            for (int i = 0; i < a.length;i++){
                System.out.println(a[i]);
            }
        }
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    三、O(n)排序算法

    (一)桶排序(Bucket Sort)

    • 将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序,桶内排完序之后,再把每个桶里的数据按照顺序取出则为有序的数据
    • 桶排序的时间复杂度为O(n),假设有n个数据,m个桶,每个桶内都有n/m = k个数据,每个桶都使用快排,时间复杂度为O(klogk),m个桶就为O(m * k * log k) => O(n * log(n /m)),当m的个数无限趋近于n时,log(n/m)就是个非常小的常量,桶排序的时间复杂度就趋近于O(n)
    • 桶排序要求还是比较苛刻的,首先桶与桶之间要有天然的大小顺序,这样桶内的数据排序完之后,不需要再对桶与桶之间排序;其二,各个桶内的数据分布要均匀,若数据全到一个桶内,时间复杂度又退化为O(nlogn)
    • 桶排序比较适合用在外部排序中,即内存有限,可以把数据分在各个桶内,使桶内的数据能够放在内存中进行排序

    (二)计数排序(Counting Sort)

    • 桶排序的一种特殊情况,针对数据范围比数据个数小的情况,比如给50万高考考生成绩排序,高考成绩总分为750分,可以划分为751个桶,相同成绩的考生放在一个桶内,只需遍历扫描桶,即可完成排序操作

    (三)基数排序(Radix Sort)

  • 相关阅读:
    使用vuex实时更新右上角通知信息的红点数量
    SpringBoot、Vue、Nginx配置 https 并部署发布
    双十二有哪些实用性强的数码好物?值得入手的实用数码好物推荐
    word行距怎么设置?专业排版,让文档更具吸引力!
    golang本地缓存库之bigcache
    pytest框架之mark标记功能详细介绍
    Nodejs -- Express的安装和定义get、post方法
    (ICLR-2019)DARTS:可微分架构搜索
    我们为什么要做一名系统管理员?
    RHCSA --- Linux存储管理
  • 原文地址:https://blog.csdn.net/nzbing/article/details/125526071