- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

java实现八大经典排序（冒泡、选择、插入、归并、快速排序、堆排序、希尔排序、桶排序）

楚楚冻人玥玥仙女发表于 2021/11/19 02:02:31 2021/11/19

2.9k+ 0 0

【摘要】总结: 经典排序算法的平均时间复杂度： O ( ...

总结:

经典排序算法的平均时间复杂度：
${O(N^2)}$ ：冒泡、选择、插入
${O(N*logN)}$ ：归并、快速排序、希尔排序、堆排序
${O(N)}$ ：桶排序
经典排序算法的空间复杂度：
${O(1)}$ ：插入、选择、冒泡、堆排序、希尔排序
${O(logN)}$ ~ ${O(N)}$ ：快速排序
${O(N)}$ ：归并排序
${O(M)}$ ：桶排序（M是桶的大小）
稳定的排序算法：
冒泡、插入、归并、桶排序
不稳定的排序算法：
快速排序、希尔排序、选择排序、堆排序（可记：快些选队 *^_^*）

一、冒泡排序 BubbleSort

class BubbleSort {
    public int[] bubbleSort(int[] A, int n) {
        // write code here
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (A[j] > A[j + 1]) {
                    int t = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = t;
                }
            }
        }
        return A;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new BubbleSort().bubbleSort(new int[]{1, 2, 3, 5, 2, 3}, 6)));
    }
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19

二、选择排序 SelectionSort

class SelectionSort {
    public int[] selectionSort(int[] A, int n) {
        // write code here
        for (int i = 0; i < n - 1; i++) {
            int min = i;
            for (int j = i; j < n; j++) {
                if (A[j] < A[min]) {
                    min = j;
                }
            }
            int t = A[min];
            A[min] = A[i];
            A[i] = t;
        }
        return A;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new SelectionSort().selectionSort(new int[]{1, 2, 3, 5, 2, 3}, 6)));
    }
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21

三、插入排序 InsertionSort

class InsertionSort {
    public int[] insertionSort(int[] A, int n) {
        // write code here
        for (int i = 1; i < n; i++) {
            int j = i - 1;
            int t = A[i];
            while (j >= 0 && A[j] >= t) {
                A[j + 1] = A[j];
                j--;
            }
            A[j + 1] = t;
//            System.out.println(Arrays.toString(A));
        }
        return A;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new InsertionSort().insertionSort(new int[]{1, 2, 3, 5, 2, 3}, 6)));
    }
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20

四、归并排序 MergeSort

class MergeSort {
    public int[] mergeSort(int[] A, int n) {
        // write code here
        merge(A, 0, n - 1);
        return A;
    }

    private void merge(int[] A, int left, int right) {
        if (right - left <= 0) return;
        int mid = (left + right) >> 1;
        merge(A, left, mid);
        merge(A, mid + 1, right);
        int i = left, j = mid + 1;
        int[] B = new int[right - left + 1];
        int cnt = 0;
        while (i <= mid && j <= right) {
            if (A[i] < A[j]) {
                B[cnt++] = A[i++];
            } else {
                B[cnt++] = A[j++];
            }
        }
        while (i <= mid) {
            B[cnt++] = A[i++];
        }
        while (j <= right) {
            B[cnt++] = A[j++];
        }
        for (i = 0; i < B.length; i++) {
            A[left + i] = B[i];
        }
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new MergeSort().mergeSort(new int[]{1, 2, 3, 5, 2, 3}, 6)));
    }
}

  
 
  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

五、快速排序 QuickSort

class QuickSort {
    public int[] quickSort(int[] A, int n) {
        // write code here
        qSort(A, 0, n - 1);
        return A;
    }

    private void qSort(int[] A, int left, int right) {
        if (right - left <= 0) return;
        int pos = partition(A, left, right);
        qSort(A, left, pos - 1);
        qSort(A, pos + 1, right);
    }

    private int partition(int[] A, int left, int right) {
        int i = left;//第一个大于A[right]的数
        for (int j = left; j < right; j++) {
            if (A[j] < A[right]) {
                int t = A[j];
                A[j] = A[i];
                A[i] = t;
                i++;
            }
        }
        int t = A[right];
        A[right] = A[i];
        A[i] = t;
        return i;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new QuickSort().quickSort(new int[]{1, 2, 3, 5, 2, 3}, 6)));
    }
}

  
 
  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

六、堆排序 HeapSort

class HeapSort {
    /*
    堆排序是一种树形选择排序方法，它的特点是：在排序的过程中，将array[0，...，n-1]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（最小）的元素。

    1. 若array[0，...，n-1]表示一颗完全二叉树的顺序存储模式，则双亲节点指针和孩子结点指针之间的内在关系如下：

    　　任意一节点指针 i：父节点：i==0 ? null : (i-1)/2

    　　　　　　　　　　  左孩子：2*i + 1

    　　　　　　　　　　  右孩子：2*i + 2

    2. 堆的定义：n个关键字序列array[0，...，n-1]，当且仅当满足下列要求：(0 <= i <= (n-1)/2)

    　　　　　　① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]； 称为小根堆；

    　　　　　　② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]； 称为大根堆；

    3. 建立大根堆：

    　　n个节点的完全二叉树array[0，...，n-1]，最后一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调整，使该子树称为堆。

    　　对于大根堆，调整方法为：若【根节点的关键字】小于【左右子女中关键字较大者】，则交换。

    　　之后向前依次对各节点（(n-2)/2 - 1）~ 0为根的子树进行调整，看该节点值是否大于其左右子节点的值，若不是，将左右子节点中较大值与之交换，交换后可能会破坏下一级堆，于是继续采用上述方法构建下一级的堆，直到以该节点为根的子树构成堆为止。

    　　反复利用上述调整堆的方法建堆，直到根节点。

    4.堆排序：（大根堆）

    　　①将存放在array[0，...，n-1]中的n个元素建成初始堆；

    　　②将堆顶元素与堆底元素进行交换，则序列的最大值即已放到正确的位置；

    　　③但此时堆被破坏，将堆顶元素向下调整使其继续保持大根堆的性质，再重复第②③步，直到堆中仅剩下一个元素为止。

    堆排序算法的性能分析：

    　　空间复杂度:o(1)；

    　　时间复杂度:建堆：o(n)，每次调整o(log n)，故最好、最坏、平均情况下：o(n*logn);

    　　稳定性：不稳定
     */
    public int[] heapSort(int[] A, int n) {
        // write code here
        buildMaxHeap(A);
        for (int i = A.length - 1; i >= 1; i--) {
            int t = A[0];
            A[0] = A[i];
            A[i] = t;
            adjustDownToUp(A, 0, i);
        }
        return A;
    }

    private void buildMaxHeap(int[] A) {
        for (int i = (A.length - 2) / 2; i >= 0; i--) {
            adjustDownToUp(A, i, A.length);
        }
    }

    private void adjustDownToUp(int[] A, int k, int length) {
        int t = A[k];
        for (int i = 2 * k + 1; i < length; i = 2 * i + 1) {
            if (i < length - 1 && A[i] < A[i + 1]) {
                i++;
            }
            if (t >= A[i]) {
                break;
            }
            A[k] = A[i];
            k = i;
        }
        A[k] = t;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new HeapSort().heapSort(new int[]{1, 2, 3, 5, 2, 3}, 6)));
    }
}

  
 
  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
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83

七、希尔排序 ShellSort

class ShellSort {
    public int[] shellSort(int[] A, int n) {
        // write code here
        for (int i = n / 2; i >= 1; i /= 2) {
            insertSort(A, i);
        }
        return A;
    }

    private void insertSort(int[] A, int step) {
        for (int i = step; i < A.length; i++) {
            int t = A[i];
            int j = i - step;
            while (j >= 0 && A[j] >= t) {
                A[j + step] = A[j];
                j -= step;
            }
            j += step;
            A[j] = t;
        }
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new ShellSort().shellSort(new int[]{1, 2, 3, 5, 2, 3}, 6)));
    }
}

  
 
  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

八、桶排序 BucketSort

(1). 计数排序 CountingSort

class CountingSort {
    public int[] countingSort(int[] A, int n) {
        // write code here
        int max = A[0];
        for (int i = 1; i < n; i++) {
            max = Math.max(max, A[i]);
        }
        int[] c = new int[max + 1];
        Arrays.fill(c, 0);
        for (int i = 0; i < n; i++) {
            c[A[i]]++;
        }
        int cnt = 0;
        for (int i = 0; i <= max; i++) {
            while (c[i] > 0) {
                A[cnt++] = i;
                c[i]--;
            }
        }
        return A;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new CountingSort().countingSort(new int[]{1, 2, 3, 5, 2, 3}, 6)));
    }
}
  
 
  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

(2). 基数排序 RadixSort

class RadixSort {
    public int[] radixSort(int[] A, int n) {
        // write code here
        int max = 0;
        for (int i = 0; i < n; i++){
            max = Math.max(max, Integer.toString(A[i]).length());
        }
        int [][]r = new int[10][A.length+1];
        initArray(r);
        for(int i = 0; i < max; i++){
            sortByBit(r,A, i);
            initArray(r);
        }
        return A;
    }

    private void initArray(int[][] r) {
        for (int i = 0; i < 10; i++){
            r[i][0] = 0;
            for (int j = 1; j < r[i].length; j++){
                r[i][j] = -1;
            }
        }
    }

    private void sortByBit(int [][]r, int []A, int t) {//按照第t位，将数组A进行基数排序放入r中，然后再放回A中
        for(int i = 0; i < A.length; i++){
            int v = getValueAt(A[i], t);
            int cnt = r[v][0];
            r[v][++cnt] = A[i];
            r[v][0] = cnt;
        }
        int k = 0;
        for (int i = 0; i < 10; i++){
            for(int j = 1; j <= r[i][0]; j++){
                A[k++] = r[i][j];
            }
        }
    }

    private int getValueAt(int value, int t) {//得到整数value的第t位（从右数，自0开始）。如356的第1位是5
        for(int i = 0; i < t; i++){
            value /= 10;
        }
        return value % 10;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new RadixSort().radixSort(new int[]{54,35,48,36,27,12,44,44,8,14,26,17,28},13)));
    }
}

  
 
  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

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/86740736

点赞
收藏
关注作者

作者其他文章

抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认取消

开发者空间

了解空间

工作台

开发工具

实战案例

空间活动

空间论坛

开发平台

软件开发生产线 CodeArts

AI平台ModelArts

数据治理中心 DataArts Studio

数字内容生产线 MetaStudio

精选服务

云数据库 GaussDB

云数据库 RDS for MySQL

MapReduce服务 MRS

数据仓库服务 DWS

分布式缓存服务Redis版

分布式消息服务 DMS

华为云实时音视频 SparkRTC

媒体处理 MPC

主机迁移服务 SMS

对象存储迁移服务 OMS

云消息服务 KooMessage

云手机服务 KooPhone

企业搜索服务 KooSearch

云地图服务 KooMap

更多开放能力

开发工具

API生态

CodeArts API

API Explorer

Terraform Explorer

KooCLI

API 中心

SDK 中心

开发服务

Codelabs

DevStar

低代码平台Astro

CodeArts IDE

Huawei Cloud Toolkit

Classroom

开发资源

开源镜像站

开源资源

开发语言

开发实践

入门精选

分发资源

企业应用中心

企业通用专区

教育专区

华为应用专区

政务云专区

硬件云服务商城

医疗健康专区

跳蚤市场

华为云开发者日

直播专区

开发者精品活动

DTSE Tech Talk

加入HCDE

加入HCDG

加入HCSD

加入HCWD

鲁班会

沃土云创计划·企业

沃土云创计划·高校

沃土云创计划·个人

沃土云创计划·开源共创

博客

论坛

专题

开发者榜单

学习路径

在线课程

动手实验

考试认证

培训服务