首页 > 代码库 > 《算法导论》习题2.3-4 插入排序的递归版本

《算法导论》习题2.3-4 插入排序的递归版本

伪代码:

RECURSIVE-INSERT-SORT (A, n)   if n>1     RECURSIVE-INSERT-SORT (A ,n-1)     InsertLastNumber (A,n)InsertLastNumber (A,n)  temp = A[n]  i=n-1  while i>0 && A[i]>temp    A[i+1] = A[i]    i -=1  A[i+1]=temp

Java实现:

public class RecursiveInsertSort {    public static void sort(double A[] , int n)    {        if(n>1)        {                sort(A,n-1);            insert(A,n);        }        return ;    }    public static void insert(double A[],int n)    {        double temp = A[n-1];        int i = n-2;        while(i>=0 && A[i]>temp)        {            A[i+1] = A[i];            i--;        }        A[i+1]=temp;    }    public static void main(String[] args) {        // TODO Auto-generated method stub        double [] A = {1.3, 5 ,2, 6.9, 2.0,7.8,4.3};        RecursiveInsertSort.sort(A,A.length);        for(double a:A)            System.out.print(a+" ");    }}

 

《算法导论》习题2.3-4 插入排序的递归版本