2019-07-25 10:49 已编辑西北工业大学 Java

关注

排序

1冒泡排序

1.1原理

依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。
第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较；
第二趟比较完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较；
依次类推，每一趟比较次数-1；

1.2实现代码

package sorting;

import java.util.Scanner;

//冒泡排序
public class BubbleSort {
    public static void sort(Comparable[] a) {
        //将a按升序排列
        int N=a.length;
        for (int p=N-1;p>=0;p--){
         for(int i=0;i<p;i++){
             if(!less(a[i],a[i+1])) exch(a,i,i+1);
         }
        }
    }
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    public static void exch(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    public static void show(Comparable[] a){
        //在单行中打印数组
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
    public static boolean isSorted(Comparable a[]){
        //测试数组元素是否有序
        for(int i=1;i<a.length;i++){
            if(less(a[i],a[i-1]))
                return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        String[] a=s.split("\\s+");
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

1.3特点

冒泡一种用时间换空间的排序方法。

2选择排序

2.1原理

2.2实现代码

package sorting;

import java.util.Scanner;

//选择排序
public class Selection {
    public static void sort(Comparable[] a) {
        //将a按升序排列
        int N=a.length;
        for (int i=0;i<N;i++){
            //将a[i]和a[i+1...N]中最小的元素交换
            int min=i;
            for (int j=i+1;j<N;j++){
                if(less(a[j],a[min])){
                    min=j;
                }
            }
            exch(a,i,min);
        }
    }
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    public static void exch(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    public static void show(Comparable[] a){
        //在单行中打印数组
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
    public static boolean isSorted(Comparable a[]){
        //测试数组元素是否有序
        for(int i=1;i<a.length;i++){
            if(less(a[i],a[i-1]))
                return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        String[] a=s.split("\\s+");
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

2.3特点

3插入排序

3.1原理

基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。

3.2实现代码

package sorting;

import java.util.Scanner;

//插入排序
public class Insertction {
    public static void sort(Comparable[] a) {
        //将a按升序排列
        int N=a.length;
        for(int i=1;i<N;i++){
            //将a[i]插入到a[i-1]、a[i-2]、a[i-3]...之中
            for(int j=i;j>0 && less(a[j],a[j-1]);j--){
                exch(a,j,j-1);
            }
        }
    }
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    public static void exch(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    public static void show(Comparable[] a){
        //在单行中打印数组
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
    public static boolean isSorted(Comparable a[]){
        //测试数组元素是否有序
        for(int i=1;i<a.length;i++){
            if(less(a[i],a[i-1]))
                return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        String[] a=s.split("\\s+");
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

3.3特点

插入排序所需的时间取决于输入中元素的初始顺序。对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。

4希尔排序

4.1原理

4.2代码实现

package sorting;

import java.util.Scanner;

//希尔排序
public class Shell {
    public static void sort(Comparable[] a) {
        //将a按升序排列
        int N=a.length;
        int h=1;
        while(h<N/3){
            h=3*h+1;//1,4,13,40,121,364,1093,...
        }
        while (h>=1){
            //将数组变为h有序
            for(int i=h;i<N;i++){
                //将a[i]插入到a[i-h]、a[i-2*h]、a[i-3*h]...之中
                for(int j=i;j>0 && less(a[j],a[j-h]);j-=h){
                    exch(a,j,j-h);
                }
            }
            h=h/3;
        }
    }
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    public static void exch(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    public static void show(Comparable[] a){
        //在单行中打印数组
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
    public static boolean isSorted(Comparable a[]){
        //测试数组元素是否有序
        for(int i=1;i<a.length;i++){
            if(less(a[i],a[i-1]))
                return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        String[] a=s.split("\\s+");
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

4.3特点

希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大。
代码量很小，而且不需要额外的内存空间。

5归并排序

5.1自顶向下的归并排序

5.1.1原理

分而治之的思想：如果能将两个子数组排序，就能通过归并两个子数组来将整个数组排序。要对子数组a[lo…hi]进行排序，先将它分为a[lo…mid]和a[mid+1…hi]两部分,分别通过递归调用将它们单独排序，最后将有序的子数组归并为最终的排序结果。

5.1.2代码实现

package sorting;

import java.util.Scanner;

//自顶向下归并排序
public class Merge {
    private static Comparable[] aux;//归并所需的辅助数组
    public static void sort(Comparable[] a){
        aux=new Comparable[a.length];//一次性分配空间，若放在merge方法中，需要每次创建数组
        sort(a,0,a.length-1);
    }
    public static void sort(Comparable[] a,int lo,int hi){
        //将数组a[lo...hi]排序
        if(hi<=lo) return;
        int mid=lo+(hi-lo)/2;
        sort(a,lo,mid);//将左半边排序
        sort(a,mid+1,hi);//将右半边排序
        merge(a,lo,mid,hi);//归并结果
    }
    public static void merge(Comparable[] a,int lo,int mid,int hi){
        //将a[lo...mid]和a[mid+1...hi]归并
        int i=lo,j=mid+1;
        for(int k=lo;k<=hi;k++){
            //将a[lo...hi]复制到aux[lo...hi]
            aux[k]=a[k];
        }
        for(int k=lo;k<=hi;k++){
            //归并回到a[lo...hi]
            if(i>mid) a[k]=aux[j++];//左半边用尽，取右半边元素
            else if(j>hi) a[k]=aux[i++];//右半边用尽，取左半边元素
            else if(less(aux[j],aux[i])) a[k]=aux[j++];//右半边的当前元素小于左半边的当前元素，取右半边元素
            else a[k]=aux[i++];//右半边的当前元素大于等于左半边的当前元素，取左半边元素
        }
    }
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    public static void show(Comparable[] a){
        //在单行中打印数组
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
    public static boolean isSorted(Comparable a[]){
        //测试数组元素是否有序
        for(int i=1;i<a.length;i++){
            if(less(a[i],a[i-1]))
                return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        String[] a=s.split("\\s+");
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

5.2自底向上的归并排序

5.2.1原理

先归并那些微型数组，然后再成对归并得到的这些子数组，如此这般，直到我们将整个数组归并在一起。

5.2.2代码实现

package sorting;

import java.util.Scanner;

//自底向上的归并排序
public class MergeBu {
    private static Comparable[] aux;//归并所需的辅助数组
    public static void sort(Comparable[] a){
        //进行lgN次两两归并
        int N=a.length;
        aux=new Comparable[N];//一次性分配空间，若放在merge方法中，需要每次创建数组
        for(int sz=1;sz<N;sz=sz+sz){
            //sz子数组大小
            for(int lo=0;lo<N-sz;lo+=sz+sz){
                //lo:子数组索引
                merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));
            }
        }
    }
    public static void merge(Comparable[] a,int lo,int mid,int hi){
        //将a[lo...mid]和a[mid+1...hi]归并
        int i=lo,j=mid+1;
        for(int k=lo;k<=hi;k++){
            //将a[lo...hi]复制到aux[lo...hi]
            aux[k]=a[k];
        }
        for(int k=lo;k<=hi;k++){
            //归并回到a[lo...hi]
            if(i>mid) a[k]=aux[j++];//左半边用尽，取右半边元素
            else if(j>hi) a[k]=aux[i++];//右半边用尽，取左半边元素
            else if(less(aux[j],aux[i])) a[k]=aux[j++];//右半边的当前元素小于左半边的当前元素，取右半边元素
            else a[k]=aux[i++];//右半边的当前元素大于等于左半边的当前元素，取左半边元素
        }
    }
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    public static void show(Comparable[] a){
        //在单行中打印数组
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
    public static boolean isSorted(Comparable a[]){
        //测试数组元素是否有序
        for(int i=1;i<a.length;i++){
            if(less(a[i],a[i-1]))
                return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        String[] a=s.split("\\s+");
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

5.3特点

归并排序所需要的时间和NlgN成正比，只需要比遍历整个数组多个对数因子的时间就能将一个庞大的数组排序。主要缺点是辅助数组所使用的额外空间和N的大小成正比。

6快速排序

6.1原理

一种分治的排序算法。将一个数组分成两个子数组，将两部分分别独立地排序。通过递归地调用切分来排序。

6.2代码实现

package sorting;

import edu.princeton.cs.algs4.StdRandom;
import java.util.Scanner;

//快速排序
public class Quick {
    public static void sort(Comparable[] a){
        StdRandom.shuffle(a);//消除对输入的依赖
        sort(a,0,a.length-1);
    }
    public static void sort(Comparable[] a,int lo,int hi){
        if(hi<=lo) return;
        int j=partition(a,lo,hi);
        sort(a,lo,j-1);//将左半部分a[lo..j-1]排序
        sort(a,j+1,hi);//将有半部分a[j+1,..hi]排序
    }
    private static int partition(Comparable[] a,int lo,int hi){
        //将数组切分为a[lo..i-1],a[i],a[i+1..hi]
        int i=lo,j=hi+1;//左右扫描指针
        Comparable v=a[lo];//切分元素
        while(true){
            //扫描左右，检查扫描是否结束并交换元素
            while (less(a[++i],v)) if(i==hi) break;
            while (less(v,a[--j])) if(j==lo) break;//这个边界检测条件是冗余的，因为切分元素a[lo]不可能比自己小
            if(i>=j) break;
            exch(a,i,j);
        }
        exch(a,lo,j);//将v=a[j]放入正确的位置
        return j;//a[lo..j-1]<=a[j]<=a[j+1..hi]达成
    }
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    public static void exch(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    public static void show(Comparable[] a){
        //在单行中打印数组
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
    public static boolean isSorted(Comparable a[]){
        //测试数组元素是否有序
        for(int i=1;i<a.length;i++){
            if(less(a[i],a[i-1]))
                return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        String[] a=s.split("\\s+");
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

6.3特点

7.基于堆的优先队列

7.1概念

优先队列是一种抽象数据类型，表示了一组值和对这些值的操作。优先队列最重要的操作是删除最大元素和插入元素。

堆的定义：当一个二叉树的每个节点都大于等于它的两个子节点时，它被称为堆有序。根节点是堆有序的二叉树的最大节点。

在一个堆中，位置k的结点的父节点的位置为[k/2]，而它的两个子节点的位置则分别为2k和2k+1。
由下至上的堆有序化（上浮）

    private void swim(int k){
        while (k>1 && less(k/2,k)){
            exch(k/2,k);
            k=k/2;
        }
    }

由上至下的堆有序化（下沉）

    private void sink(int k){
        while(2*k<=N){
            int j=2*k;//子结点
            if(j<N && less(j,j+1)) j++;//找到子结点较大的那个
            if(!less(k,j)) break;
            exch(k,j);
            k=j;
        }
    }

7.2代码实现

package sorting;

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;//基于堆的完全二叉树
    private int N=0;//存储于pq[1..N]中，pq[0]没有使用

    public MaxPQ(int maxN){
        pq=(Key[])new Comparable[maxN+1];
    }
    public boolean isEmpty(){
        return N==0;
    }
    public int size(){
        return N;
    }
    public void insert(Key v){
        pq[++N]=v;
        swim(N);
    }
    public Key delMax(){
        Key max=pq[1];//从根结点得到最大元素
        exch(1,N--);//将其和最后一个结点交换
        pq[N+1]=null;//防止越界
        sink(1);//恢复堆的有序性
        return max;
    }
    private void sink(int k){//由上至下的堆有序化（下沉）
        while(2*k<=N){
            int j=2*k;//子结点
            if(j<N && less(j,j+1)) j++;//找到子结点较大的那个
            if(!less(k,j)) break;
            exch(k,j);
            k=j;
        }
    }
    private void swim(int k){//由上至下的堆有序化（上浮）
        while (k>1 && less(k/2,k)){
            exch(k/2,k);
            k=k/2;
        }
    }
    private boolean less(int i,int j){
        return pq[i].compareTo(pq[j])<0;
    }
    private void exch(int i,int j){
        Key t=pq[i];
        pq[i]=pq[j];
        pq[j]=t;
    }
}

8堆排序

8.1原理

将优先队列变成一种排序算法：将所有元素插入一个查找最小元素的优先队列，然后再重复调用删除最小元素的操作将它们按顺序排序。
分为两个阶段：在堆的构造阶段中，将原始数组重新安排进一个堆中，然后在下沉阶段排序阶段，从堆中按递减的顺序取出所有元素并得到排序结果。

8.2代码实现

package sorting;

import java.util.Scanner;

//堆排序
public class Heap {
    public static void sort(Comparable[] pq) {
        //相当于将pq[0]~pq[n-1]编号为1~n，将1~n排序，即实现了pq[0]~pq[n-1]的排序
        int n = pq.length;
        //for循环构造堆有序
        for (int k = n/2; k >= 1; k--)
            sink(pq, k, n);
        //while循环将最大的元素a[1]和a[N]交换并修复了堆
        while (n > 1) {
            exch(pq, 1, n--);
            sink(pq, 1, n);
        }
    }
    private static void sink(Comparable[] pq, int k, int n) {//由上至下的堆有序化（下沉）
        while (2*k <= n) {
            int j = 2*k;//子节点
            if (j < n && less(pq, j, j+1)) j++;//找子节点较大的那个
            if (!less(pq, k, j)) break;
            exch(pq, k, j);
            k = j;
        }
    }
    private static void exch(Object[] pq, int i, int j) {
        Object swap = pq[i-1];//i-1是将元素编号转换为实际的数组元素
        pq[i-1] = pq[j-1];
        pq[j-1] = swap;
    }
    private static boolean less(Comparable[] pq, int i, int j) {
        return pq[i-1].compareTo(pq[j-1]) < 0;//i-1是将元素编号转换为实际的数组元素
    }
    public static void show(Comparable[] a){
        //在单行中打印数组
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        String[] a=s.split("\\s+");
        sort(a);
        show(a);
    }
}

9 桶排序、计数排序、基数排序

https://www.cnblogs.com/sun-haiyu/p/7859252.html

10 各种排序算法性能比较

排序方式	时间复杂度	空间复杂度	稳定性
冒泡排序	O(N^2)	O(1)	稳定
选择排序	O(N^2)	O(1)	不稳定
插入排序	O(N^2)	O(1)	稳定
归并排序	O(N*logN)	O(N)	稳定
快速排序	O(N*logN)	O(logN)	不稳定
希尔排序	O(N*logN)	O(1)	不稳定
堆排序	O(N*logN)	O(1)	不稳定
桶排序(计数排序、基数排序)	O(N)	O(M) (M为桶的数量)	稳定