七种常用排序算法的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 条评论
登录 后参与评论

相关文章

来自专栏平凡文摘

Comparable 与 Comparator 浅析

15240
来自专栏程序员互动联盟

【编程基础】Java Comparator接口的使用

在实际编程中我们经常会用到集合或者数组,有的时候你需要对这个集合中的元素就行排序,那这个时候就用到了Comparator接口,先看一下接口的原型: public...

35790
来自专栏封碎

自定义对象需要重写hashcode

      Java中的很多对象都override了equals方法,都知道,这是为了能比较两个对象是否相等而定义,如果不需要比较,则不需要定义equals方法...

17610
来自专栏一枝花算不算浪漫

[读书笔记]C#学习笔记四: C#2.0泛型 可控类型 匿名方法和迭代器

444110
来自专栏C++

python笔记:#005#算数运算符

19520
来自专栏青玉伏案

窥探Swift之别样的枚举类型

  想必写过程序的童鞋对枚举类型并不陌生吧,使用枚举类型的好处是多多的,在这儿就不做过多的赘述了。Fundation框架和UIKit中的枚举更是数不胜数,枚举可...

21270
来自专栏黑泽君的专栏

java基础学习_基础语法(上)03_day04总结

============================================================================= ==...

12010
来自专栏Java成长之路

六、jvm之如何判断对象已死?

在堆里面几乎存放中Java程序运行所动态生成的所有对象,垃圾回收器在对堆进行回收前,第一件事情就是要确定这些对象之中还有哪些存活,哪些已经死去(即不可能再被任何...

8120
来自专栏分布式系统和大数据处理

C#类型基础

本文之初的目的是讲述设计模式中的 Prototype(原型)模式,但是如果想较清楚地弄明白这个模式,需要了解对象克隆(Object Clone),Clone其实...

10530
来自专栏一个爱瞎折腾的程序猿

LINQ

select:提取要查询的数据                 where:筛选满足条件的元素   

11110

扫码关注云+社区

领取腾讯云代金券