专栏首页浪淘沙七种常用排序算法的java实现

七种常用排序算法的java实现

一、交换方法(被调用来交换值)

    /**
     * 交换方法
     * @param a
     * @param j
     * @param i
     */
    private static void swap(int[] a, int j, int i) {
        // TODO Auto-generated method stub
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
    }

二、交换算法 1.选择排序

/**
     * 选择排序  每次都选择最小的
     * 时间复杂度O(N^2)
     * 空间复杂度O(1)
     */
    public static void selectionSort(int[] a) {
        if(a==null||a.length<2)
            return;
        for(int i = 0;i < a.length-1;i++) {
            int min = i;
            for(int j = i+1;j < a.length;j++) {
                min = a[j]<a[min]?j:min;   //选择最小的
            }
            swap(a,i,min);  //交换值
        }

    }

2.冒泡算法

/**
     * 冒泡排序   每次选择最大的,放到最后
     * 时间复杂度O(N^2)
     * 空间复杂度O(1)
     */
    public static int[] bubleSort(int[] a) {
        if(a==null||a.length<2) {
            return a;
        }else {
            for(int i = a.length-1;i > 0; i--) {
                for(int j = 0;j<i;j++) {
                    if(a[j]>a[j+1]) {
                        swap(a,j,j+1);//交换值
                    }
                }
            }
            return a;
        }
    }

3.插入排序

/**
     * 插入排序  每次都往已经排好的队列插入数据
     * 时间复杂度O(N^2)
     * 空间复杂度O(1)
     */
    public static int[] insertionSort(int[] a) {
        if(a==null||a.length<2)
            return a;
        for(int i = 1;i < a.length;i++) {
            for(int j = i-1;j >= 0 && a[j] > a [j+1];j--) {
                swap(a, j, j+1);
            }
        }
        return a;
    }

4.希尔排序

/**
*最坏时间复杂度:O(n2)
*稳定想:不稳定
*/
public static void shellSort(int[] a){
        int len = a.length;
        int gap = len/2;
        while(gap>0){
            for(int j = gap;j<len;j++){
                int i = j;
                while(i>=gap&&a[i-gap]>a[i]){
                    int tmp = a[i];
                    a[i] = a[i-gap];
                    a[i-gap] = tmp;
                    i = i-gap;
                }
            }
            gap = gap/2;
        }


    }

5.归并排序

    /**
     * 归并排序  运用递归   
     * 时间复杂度:O(nlogn)
     * 空间复杂度O(n)
     * @param a
     * @param begin
     * @param end
     */
    public static void mergeSort(int[] a,int begin,int end) {
        if (begin < end) {
        int mid = begin+((end-begin)>>1);
            mergeSort(a,begin,mid);
            mergeSort(a,mid+1,end);
            merge(a,begin,mid,end);
        }
    }
    /**
     * 归并运算合起来
     * @param a
     * @param begin
     * @param mid
     * @param end
     */
    private static void merge(int[] a, int begin, int mid, int end) {
        // TODO Auto-generated method stub
        int[] help = new int[end-begin+1];
        int i = 0;
        int p1 = begin;
        int p2 = mid+1;
        while(p1<=mid && p2<=end) {
            help[i++] = a[p1]<a[p2]?a[p1++]:a[p2++];
        }
        while(p1<=mid) {
            help[i++] = a[p1++];
        }
        while(p2<=end) {
            help[i++] = a[p2++];
        }
        for(i = 0;i<help.length;i++)
            a[begin+i] = help[i];

    }

6.快速排序

/**
     *找一个基准,left和right,将基准赋值给left和right重合的位置
     *左边都比它小,右边都大于它
     *继续递归排序
     * 时间复杂度 nlogn
     * 空间复杂度 nlogn
     */
public static void quickSort2(int a[], int low, int hight) {
        int i, j, index;
        if (low > hight) {
            return;
        }
        i = low;
        j = hight;
        index = a[i]; // 用子表的第一个记录做基准
        while(i<j) {
            while(i<j && a[j]>=index) {
                j--;
            }
            if(i<j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
            while(i<j && a[i]<index) {
                i++;
            }
            if(i<j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }

        quickSort2(a, low, i-1);
        quickSort2(a, i+1, hight);


    }

7.堆排序

/**
 * 堆排序
 * 1)将数组变成大根堆
 * 2)把最后一个和堆顶位置交换 堆长度减1
 * 3)从0到最后做 heapify
 * 解决贪心问题,优先性排序
 *时间复杂度O(N*logN)  额外空间 O(1)
 * @author hasee
 *
 */
public static void heapSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        for(int i = 0;i < arr.length;i++) {
            heapInsert(arr, i);//先调成大根堆
        }
        //开始排序,每次都将最大值调到最后
        int heapSize = arr.length;
        swap(arr,0,--heapSize);
        while(heapSize > 0) {
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }

    }
    /**子节点上升
     * 将每个子节点与父类进行比较,并交换
     * @param arr
     * @param index
     */
    public static void heapInsert(int[]arr,int index) {
        while(arr[index]>arr[(index-1)/2]) {
            swap(arr,index,(index-1)/2);
            index=(index-1)/2;
        }
    }

    /**
     * 父节点下沉过程
     * @param arr
     * @param index
     * @param heapSize
     */
    public static void heapify(int[] arr,int index,int heapSize) {
        int left = index*2+1;
        while(left<heapSize) {
            int largest = (left+1<heapSize && arr[left+1]>arr[left]) ?(left+1):left;
            largest = arr[largest] > arr[index] ? largest : index;
            if(largest == index)
                break;
            swap(arr,index,largest);
            index = largest;
            left = index*2+1;
        }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 关于数组的算法

    3.给定一个数组和一个数num,把小于num的书放在数组左边,大于num的书放在数组右边

    曼路
  • 桶排序的算法

    思路:设数组的长度为len,创建三个长度为len+1的(桶)数组。将数组的元素根据大小放在不同的桶中,其中,必定有差值大于一个桶的差存在,故同一个桶中不可能出现...

    曼路
  • 实训day04--二维数组,面向对象

    2018.06.07 1.方法的签名 cn.edu360.function.Demo1.add(int ,int)

    曼路
  • LeetCode 215. Kth Largest Element in an Array分析

    显然最简单的思想就是排序,然后取出倒数第k个元素就可以了,我们可以直接调用内部的排序函数。

    desperate633
  • 蓝桥杯--算法入门级题目及答案解析

    写在最前面: 本文中会出现大量的请查阅.请自学什么的,不是我不讲,本文是面向算法初学者和蓝桥杯的文章,如果真的想看进阶算法的也不会来看这些题目,所以不要介意,...

    风骨散人Chiam
  • 【2019秋PAT乙级真题】7-3 缘分数 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 算法原理系列:木桶排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 高仿京东金融的数值滚动尺

    以前博客讲的大部分都是静态的自定义View的编写,其实无非就是“画画”画出一个好看的效果,而这篇博客写的是写一个动态的自定义控价,这里不仅需要"画",还要各种事...

    HelloJack
  • BZOJ4698: Sdoi2008 Sandy的卡片(二分 hash)

    attack
  • LeetCode刷题记录:733. 图像渲染

    解题思路: 广度优先遍历(BFS)。首先记录下起点初始的颜色,染色(即将值修改为newColor)后将起点的坐标压入队列。之后进入大循环,大循环内取出队列头部...

    英雄爱吃土豆片

扫码关注云+社区

领取腾讯云代金券