尤其优化正是充实一个flag,平均复杂度为O(nlogn)

希尔排序的年月复杂度,最好的场馆下还是是正序时,可达到O(n),平均复杂度为O(nlogn)。

文档版本 开发工具 测试平台 工程名字 日期 作者 备注
V1.0 2016.04.06 lutianfei none
V1.1 2016.07.16 lutianfei 增加了归并排序说明
V2.0 2016.07.19 lutianfei 完善了排序算法的总结

算法思想:

  接纳跳跃式处理数组,使得数组粗粒度的落到实处宗旨平稳。在举行细粒度的拍卖,最终使得网络在跳越数为1时,达成基本铁钉铁铆的排序,以减弱插入排序的复杂度。


一言九鼎程序:

void shellSort(int *arr,int length){
    int i,j,k;
    int increment = length;
    while(increment>0){
        if(increment != 1)
            increment = increment/3+1;
        else
            break;
        for(i = increment; i<length; i++){
            if(arr[i] < arr[i-increment]){
                k = arr[i];
                for(j=i-increment; j>=0 && k < arr[j] ; j-=increment){
                    arr[j+increment] = arr[j];
                }
                arr[j+increment] = k;
            }
        }
    }
}
  • 排序另一种分法
    • 向外排水序:必要在上下存之间反复换来数据才能展开
    • 内排序:
      • 插入类排序
        • 直接插入排序
        • 希尔排序
      • 选择类排序
        • 粗略选拔排序
        • 堆排序
      • 沟通类排序
        • 冒泡排序
        • 立时排序
      • 归并类排序
        • 归并排序

凡事代码:

图片 1图片 2

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int arrtest1[10] = {3,4,7,8,0,9,1,2,6,5};
int arrtest2[10] = {0,1,2,3,4,5,6,7,8,9};
int arrtest3[10] = {9,8,7,6,5,4,3,2,1,0};
void copy(int *from,int *arr,int length);
void print(int *arr,int length);
void shellSort(int *arr,int length);
int main(){
    clock_t start,end;
    int Arr[10];
    int i;
    copy(arrtest1,Arr,10);
    print(Arr,10);
    shellSort(Arr,10);
    print(Arr,10);
    start = clock();
    for(i=0;i<100000;i++){
        copy(arrtest1,Arr,10);
        //print(Arr,10);
        shellSort(Arr,10);
        //print(Arr,10);
    }
    end = clock();
    printf("first test:%d\n",end-start);

    start = clock();
    for(i=0;i<100000;i++){
        copy(arrtest2,Arr,10);
        //print(Arr,10);
        shellSort(Arr,10);
        //print(Arr,10);
    }
    end = clock();
    printf("first test:%d\n",end-start);

    start = clock();
    for(i=0;i<100000;i++){
        copy(arrtest3,Arr,10);
        //print(Arr,10);
        shellSort(Arr,10);
        //print(Arr,10);
    }
    end = clock();
    printf("first test:%d\n",end-start);

    getchar();
    return 0;
}
void shellSort(int *arr,int length){
    int i,j,k;
    int increment = length;
    while(increment>0){
        if(increment != 1)
            increment = increment/3+1;
        else
            break;
        for(i = increment; i<length; i++){
            if(arr[i] < arr[i-increment]){
                k = arr[i];
                for(j=i-increment; j>=0 && k < arr[j] ; j-=increment){
                    arr[j+increment] = arr[j];
                }
                arr[j+increment] = k;
            }
        }
    }
}
void copy(int *from,int *arr,int length){
    int i;
    for(i=0;i<length;i++){
        arr[i] = from[i];
    }
}

void print(int *arr,int length){
    int i;
    for(i=0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
}

View Code

排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
简单选择排序 O(n^2) O(n^2) O(n^2) O(1) 稳定
直接插入排序 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序 O(nlogn)~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn)~O(n) 不稳定

运维示例:

图片 3

  • 测试工程表明
    • 下文都是用以下测试用例举行测试

    public static void main(String[] args) {
        int[] A = new int[] { 11, 2, 3, 22, 4, 1, 11, 10, 6, 5, 22, 13, 21 };
        int n = A.length;
        int[] A_sort = new int[n];
        System.out.println("排序前:");
        arrayPrint(A);

        System.out.println("排序后:");

        mSort(A,A_sort,0, n-1);
        // System.out.println(A);
        arrayPrint(A_sort);

        System.out.println("标准答案");
        Arrays.sort(A);

        arrayPrint(A);
    }

    /**
     * 
     * <p>@MethodName : arrayPrint</p>
     * <p>@Description: 打印数组至控制台</p>
     * @date          : 2016-7-6 ,下午4:51:43  
     * @param         : @param 待打印数组A  
     * @Version       : v1.0
     */
    public static void arrayPrint(int[] A) {
        System.out.print("[ ");
        for (int i = 0; i < A.length; i++) {
            System.out.print(A[i] + " ");
        }
        System.out.println("]");
        System.out.println();
    }

简单来讲排序算法

冒泡算法

  • 基本思路:两两相比较相邻记录的主要性字,纵然反序则调换,直到没有反序的笔录结束。

初级冒泡算法

/**
 * 
 * <p>@MethodName : bubbleSort0</p>
 * <p>@Description: 初级版冒泡排序</p>
 * @date          : 2016年7月19日 ,上午10:10:53  
 * @param         : @param A  
 * @Version       : vx.x
 */

public static void bubbleSort0(int[] A){
    for(int i=0;i < A.length-1;i++){
        for(int j=i+1;j<A.length;j++){
            if(A[i] > A[j]){
                swap(A,i,j);
            }
        }
    }
}

优化版冒泡排序

/**
 * 
 * <p>@MethodName : buubleSort1</p>
 * <p>@Description: 优化版冒泡排序算法</p>
 * @date          : 2016年7月19日 ,上午10:57:17  
 * @param         : @param A  带排序数组
 * @Version       : vx.x
 */
public static void bubbleSort1(int[] A){
    for(int i = 0;i<A.length;i++){
        for(int j=A.length-1;j>i;j--){ //j从后往前循环
            if(A[j-1] > A[j]){ //从下往上依次比较
                swap(A,j-1,j); 
            }
        }
    }
}

图片 4

冒泡排序的愈益优化

上述的优化冒泡排序算法的题材在于一旦数量在中等已经排序好,后续的相比较工作还会接二连三开始展览,造成时间浪费。进一步优化就是增多一个flag,标志是还是不是须求后续比较。

/**
 * 
 * <p>@MethodName : bubbleSort2</p>
 * <p>@Description: 进一步优化版冒泡排序算法</p>
 * @date          : 2016年7月19日 ,上午11:26:36  
 * @param         : @param A  
 * @Version       : vx.x
 */
public static void bubbleSort2(int [] A){
    boolean flag = true;
    for(int i=0; i<A.length && flag;i++){
        flag = false;
        for(int j=A.length-1;j>i;j--){
            if(A[j-1] > A[j]){
                swap(A,j-1,j);
                flag = true;
            }
        }
    }
}

冒泡排序复杂度分析

  • 最好状态下
    :数组本人有序,只供给展开n-三次比较,不供给交流,时间复杂度为O(n)
  • 最坏情状下
    :数组为逆序,此时亟需比较n*(n-1)/2,并作等数据级的笔录移动,时间复杂度为O(n^2)

挑选类排序

  • 基本思路:每一趟在n-i+1(i=1,2,…,n-1)
    个记录中精选关键字非常的小的记录作为一如既往系列的第i个记录

不难选取排序

  • 通过n-i次重庆大学字间的比较,从n-i+一个记录中选出第二字十分小的笔录,并和第i(1<=i<=n)个记录交流之。

/**
 * 
 * <p>@MethodName : selectSort</p>
 * <p>@Description: 简单选择排序</p>
 * @date          : 2016年7月19日 ,上午11:48:40  
 * @param         : @param A  
 * @Version       : vx.x
 */
public static void selectSort(int[] A){
    for(int i=0;i<A.length-1;i++){
        int min = i;

        for(int j=i+1;j<A.length;j++){
            if(A[min] > A[j]){
                min = j;
            }
        }

        if(i != min){
            swap(A,i,min);
        }
    }
}
简言之选拔排序复杂度分析
  • 粗略排序最大的风味:调换移动多少次数十一分少,最好状态下交流0次,最差请求沟通n-二遍;适用于数组个数不多,但各样数组成分较大的景况。

  • 时光复杂度:无论是最好最差境况,相比次数一样多,n(n-1)/2,总的时间复杂度O(n^2)

  • 总结选取排序质量上略优于冒泡排序。

插入类排序

间接插入排序算法

  • 将叁个记下插入到曾经排好序的有序表中,从而获得2个新的、记录数增1的有序表。

/**
 * 
 * <p>@MethodName : insertSort</p>
 * <p>@Description: 直接插入排序</p>
 * @date          : 2016年7月19日 ,下午3:05:31  
 * @param         : @param A  
 * @Version       : vx.x
 */
public static void insertSort(int[] A){
    for(int i=1;i<A.length;i++){ 
        //从1开始表示:假设A[0] 已经放好位置了,后面的数字就是插入到它左边还是右边的问题。

        if(A[i] < A[i-1]){ //发现A[i]比前面的有序数组的最后一个数小了

            int tmp = A[i];//缓存下A[i]
            int j;
            for(j=i-1; j>=0 && A[j] > tmp; j--){ //从后往前逐个排查哪个位置刚好适合A[i],最后一次j--可能会为负值,这是为了配合后面A[j+1]
                A[j+1] = A[j];
            }
            A[j+1] = tmp;
        }

    }
}
直接插入排序复杂度分析
  • 最好状态下:在自笔者有序的意况下,共比较了n-一回,没有活动的笔录,时间复杂度为O(n)。
  • 最坏情形下:在逆序情形下:比较了
    n(n-1)/三遍,而运动次数为(n+2)(n-2)/二次。
  • 平均相比较 移动 次数:n^五成,故直接插入排序的时刻复杂度为O(n^2)。
  • 直接插入排序法比冒泡和简易选择排序的性格要好有的。

核查排序算法

插入类排序

Hill排序算法

  • 主导平稳:小的关键字基本在前头,大的主要性字基本在前边,相当小十分大的着力在中间。
  • 跳跃分割策略:将偏离有个别“增量”的笔录组成二个子连串,这样才能保险在子体系内分别开始展览间接插入排序后收获的结果是着力板上钉钉而不是一些有序。

/**
 * 
 * <p>@MethodName : shellSort</p>
 * <p>@Description: 希尔排序算法</p>
 * @date          : 2016年7月19日 ,下午4:06:41  
 * @param         : @param A  
 * @Version       : vx.x
 */
public static void shellSort(int[] A){
    int inc = A.length; //希尔排序可以理解为将一个大数组按照间隔inc分为inc个小数组
                        //每个数组按照直接插入排序进行处理

    do{
        inc = inc/4 + 1;

        for(int i=inc;i<A.length;i++){
            if(A[i] < A[i-inc]){
                int tmp = A[i];
                int j=0;

                for(j=i-inc;j>=0 && tmp < A[j]; j-=inc){
                    A[j+inc] = A[j];
                }

                A[j+inc] = tmp;
            }
        }
    }
    while(inc>1);
}
希尔排序复杂度分析
  • 希尔排序的重点并不是无论分组后分别排序,而是将相隔有个别增量的数组组成四个子类别,落成跳跃式的位移。
  • 增量的选项实验证实当增量类别为delt[k]=2^(t-k+1)-1(
    0<=k<=t<=log2(n+1))时,效果较佳,但注意最后增量值必须等于1。
  • 那时候时刻复杂度为O(n^1.5)
  • 希尔排序因为是跳跃式记录,故不是三个安居乐业的排序算法。

挑选类排序

堆排序

  • 不难易行采纳排序的标题:没有把每一遍的可比结实保存下来,在后一趟的相比较中,有广大相比较在前一趟已经做过了。
福寿年高步骤
  • 倘若有数主任度为n,下标0~n-1
  • 先将数组根据大堆顶格式的完全二叉树拓展排序。
  • 以下两步循环n-二回后,可做到排序。

    • 将大顶堆的根节点最后一个节点交流地点。
    • 将多余的n-2个成分重新布局成2个大顶堆。
  • 注:大堆顶完全二叉树数学概念

    • K[i] >= K[2i+1] , i=0…n-1
    • K[i] >= K[2i+2] , i=0…n-1

图片 5
图片 6
图片 7

/**
 * 
 * <p>@MethodName : heapSort</p>
 * <p>@Description: 堆排序函数</p>
 * @date          : 2016年7月19日 ,下午5:29:24  
 * @param         : @param A
 * @param         : @param n  
 * @Version       : vx.x
 */
public static void heapSort(int[] A,int n){
    for(int i=(n-1)/2 ;i>=0;i--){
        //循环从最后一个拥有子节点的节点(A[(n-1)/2])处开始,这样循环可以实现从下到上,从左到右将较大数向上推,最终实现大顶堆。
        //循环到0结束因为根节点0,也有两个子节点要比较。
        heapAdjust(A,i,n-1);
    }

    for(int i=n-1;i>0;i--){
        //循环从n-1开始,因为每次要交换根节点A[0],与最后一个节点A[i-1]
        //循环到1结束,因为此时A[0],A[1]大小已知
        swap(A,0,i);
        heapAdjust(A,0,i-1);
    }
}


/**
 * 
 * <p>@MethodName : heapAdjust</p>
 * <p>@Description: 进行大顶堆排序</p>
 * @date          : 2016年7月19日 ,下午5:37:06  
 * @param         : @param A
 * @param         : @param s 二叉树根节点坐标
 * @param         : @param m  二叉树尾节点坐标
 * @Version       : vx.x
 */
public static void heapAdjust(int[] A, int s, int m){
    int tmp = A[s];
    for(int j=2*s+1;j<=m;j=j*2+1){
        if(j<m && A[j]<A[j+1]){ //比较左右两个子节点谁大,并记录大的坐标; j<m保证了j+1不会超界
            j++;
        }

        if(tmp > A[j]){ //将父节点A[s]与上面得到的较大子节点比较,为true说明已是大堆顶,退出for循环
            break;
        }
        else{ //否则将较大子节点的值赋给父节点,并将原父节点的下标s变为较大节点的下标j,实现了将较大数向上推,较小数向下抛
            A[s] = A[j];
            s=j;
        }
    }
    A[s] = tmp;//整个循环完成后,将最初父节点的值,复制到循环后相应的节点上。
}
堆排序复杂度分析
  • 营造大堆顶的小时复杂度为O(n)
  • 第i次取堆顶记录重建堆需求O(logi)的日子,取n-三回,故重建堆的日子复杂度为O(nlogn)
  • 任凭最好,最坏,平均时间复杂度均为O(nlogn)
  • 空间复杂度,只须要一个暂存单元
  • 由于记录的相比与交流是跳跃式进行,故是一种不稳定的排序方法
  • 是因为开头营造堆所供给的比较次数较多,不吻合带排序类别个数较少的气象。

归并排序

  • 原理:假诺初步种类含有n个记录,则足以当作是n个能有序的子系列,每种子种类的长短为1,然后两两归并,获得┎n/2┒(┎x┒表示十分大于x的微小整数)个长度为2或1的有序子连串;再两两归并,…,如此重复,直至获得3个长度为n的静止种类截至,这种排序方法称为2路归并排序。

递归达成归并排序

图片 8

/**
 * 
 * <p>@MethodName : mSort</p>
 * <p>@Description: 递归型归并排序算法</p>
 * @date          : 2016-7-6 ,下午4:27:19  
 * @param         : @param sR      :原始数组
 * @param         : @param tR1     :排序后数组
 * @param         : @param s    :数组起始下标
 * @param         : @param t    :数组结尾下标
 * @Version       : v1.0
 */

static void mSort(int[] sR,int[] tR1, int s , int t){
    int m; //将数组二等分坐标
    int[] tR2 = new int[sR.length]; //二分后数组的临时排序缓冲数组

    if(s==t){
        tR1[s]=sR[s];
    }
    else {
        m=(s+t)/2;               //将sR[s..t] 平分为 sR[s..m]和sR[m+1..t]
        mSort(sR, tR2, s, m);    //递归将sR[s..m]归并为有序的tR2[s..m]
        mSort(sR, tR2, m+1, t);  //递归将sR[m+1,t]归并为有序tR2[m+1..t]
        merge(tR2,tR1,s,m,t);    //将tR2[s..m]和tR2[m+1,t]归并到tR1[s..t]
    }
}


/**
 *
 * <p>@MethodName : merge</p>
 * <p>@Description: 将部分归并数组进行最后排序</p>
 * @date          : 2016-7-6 ,下午4:40:33  
 * @param         : @param sR :部分归并数组
 * @param         : @param tR :最终有序数组
 * @param         : @param i  :数组起始下标
 * @param         : @param m  :数组中间下标
 * @param         : @param n  :数组结尾下标
 * @Version       : vx.x
 */

static void merge(int sR[],int tR[] ,int i ,int m ,int n){
    int j,k,l;
    for(j=m+1,k=i;i<=m && j<=n;k++){
        if(sR[i] < sR[j]){
            tR[k] = sR[i++];
        }else {
            tR[k] = sR[j++];
        }
    }

    if(i<=m){
        for(l=0;l<=m-i;l++){
            tR[k+l]=sR[i+l];
        }
    }

    if(j<=n){
        for(l=0;l<=n-j;l++){
            tR[k+l]=sR[j+l];
        }
    }
}

非递归格局达成归并排序

  • 非递归的迭代方法,制止了递归时深度为log2^n的栈空间,所需空间只是利用申请归并一时用的t本田CR-V数组,由此空间复杂度为O(n),并且防止递归也在时刻质量上有一定升高。

/**
 * 
 * <p>@MethodName : mergeSort</p>
 * <p>@Description: 非递归方式的合并排序</p>
 * @param         : @param sR  带排序的数组
 * @date          : 2016-7-6 ,下午9:15:30  
 * @Version       : v1.0
 */

static int[] mergeSort(int[] sR){
    int m; //将数组二等分坐标
    int[] tR = new int[sR.length]; //二分后数组的临时排序缓冲数组

    int k=1; //子序列长度因子

    while(k < sR.length){

        MergePass(sR,tR,k,sR.length-1);
        k=k*2;

        MergePass(tR,sR,k,sR.length-1);
        k=k*2;            
    }

    return sR;
}



/**
 * 
 * <p>@MethodName : MergePass</p>
 * <p>@Description: 将sR数组中长度为s的相邻子序列两两归并到tR数组中</p>
 * @date          : 2016-7-6 ,下午9:20:15  
 * @param         : @param sR :原始数组
 * @param         : @param tR :排序后数组
 * @param         : @param s  :待排序子数组的长度
 * @param         : @param n  :原始数组长度
 * @Version       : v1.0
 */
static void MergePass(int sR[] , int tR[], int s , int n){
    int i = 0;

    while(i <= n-2*s+1){ //步进为2s的情况下:能循环的最大次数
        merge(sR, tR, i, i+s-1, i+2*s-1);
        i=i+2*s;
    }

    if(i<n-s+1){//将最后剩下的不够2s长度的子序列进行排序
        merge(sR, tR, i, i+s-1, n);
    }
    else{
        for(int j=i;j<=n;j++){
            tR[j] = sR[j];
        }
    }
}



/**
 * 
 * <p>@MethodName : merge</p>
 * <p>@Description: 将部分归并数组进行最后排序</p>
 * @date          : 2016-7-6 ,下午4:40:33  
 * @param         : @param sR :部分归并数组
 * @param         : @param tR :最终有序数组
 * @param         : @param i  :数组起始下标
 * @param         : @param m  :数组中间下标
 * @param         : @param n  :数组结尾下标
 * @Version       : vx.x
 */

static void merge(int sR[],int tR[] ,int i ,int m ,int n){
    int j,k,l;
    for(j=m+1,k=i;i<=m && j<=n;k++){
        if(sR[i] < sR[j]){
            tR[k] = sR[i++];
        }else {
            tR[k] = sR[j++];
        }
    }

    if(i<=m){
        for(l=0;l<=m-i;l++){
            tR[k+l]=sR[i+l];
        }
    }

    if(j<=n){
        for(l=0;l<=n-j;l++){
            tR[k+l]=sR[j+l];
        }
    }
}
归并排序复杂度分析
  • 任凭最好、最坏、平均来讲总的时间复杂度为O(nlogn)
  • 对于递归归并:由于供给与原始记录种类同样数量的储存空间存放归并结果及递归时深度为logn的栈空间,空间复杂度O(n+logn)
  • 非递归格局的集合排序:空间复杂度为O(n)
  • 归并排序为稳定的排序算法。

急速排序算法

  • 着力考虑:通过一趟排序将待排序记录分割成独立的两片段,在那之中部分笔录的机要字均比另一有些记录的重大字小,则足以分别对那两有的记录继续进行排序,以完成全体系列有序的目的。

/**
 *     
 * <p>@MethodName : quickSort</p>
 * <p>@Description: 进行快速排序</p>
 * @date          : 2016年7月18日 ,下午7:19:20  
 * @param         : @param A  
 * @return 
 * @Version       : vx.x
 */
 public static void quickSort(int[] A,int startIdx,int endIdx){
     int pivot;
     if(startIdx < endIdx){
         pivot = partition(A,startIdx,endIdx); //将待排序数组一分为二,返回枢轴值pivot

         quickSort(A,startIdx,pivot-1); //对于弟子表递归排序
         quickSort(A,pivot+1,endIdx);  //对高子表递归排序
     }
 }



 /**
  * 
  * <p>@MethodName : partition</p>
  * <p>@Description: 获取枢轴值位置</p>
  * @date          : 2016年7月18日 ,下午11:18:15  
  * @param         : @param A 待排序数组
  * @param         : @param startIdx 开始坐标
  * @param         : @param endIdx 结束坐标
  * @param         : @return  枢纽坐标位置
  * @Version       : vx.x
  */
 public static int partition(int[] A,int startIdx,int endIdx){
    int pivotkey;

    pivotkey = A[startIdx]; //这里用子表的第一个记录做枢轴记录

    while(startIdx < endIdx){

        while(startIdx < endIdx && A[endIdx] >= pivotkey){ //此时pivotkey=A[startIdx]
            endIdx--;
        }
        swap(A,startIdx,endIdx); 
        //pivotkey = A[endIdx]

        while(startIdx < endIdx && A[startIdx] <= pivotkey){
            startIdx++;
        }
        swap(A,startIdx,endIdx); //pivotkey=A[startIdx]
    }
    return startIdx;

}


 /**
  * 
  * <p>@MethodName : swap</p>
  * <p>@Description: 交换数组a,b位置的数据</p>
  * @date          : 2016年7月18日 ,下午11:37:53  
  * @param         : @param A
  * @param         : @param a
  * @param         : @param b  
  * @Version       : vx.x
  */
static void swap(int[] A , int a, int b){
    int temp = A[a];
    A[a] = A[b];
    A[b] = temp;
}
飞速排序时间复杂度分析
  • 最优与平均时间复杂度O(nlogn)
  • 最坏时间复杂度O(n^2)
  • 空中复杂度O(logn)
  • 神速排序是一种不平稳的排序方法

相关文章