排序算法总结

Scroll Down

排序算法总结

希尔排序

综述

希尔排序是插入排序的一种高级形式,其缩短了比较的距离

普通的插入排序默认将一个数组中的元素逐个插入,逐个寻找插入的位置,其带来的时间的开销是不可忽略的,也会产生很多次的重复比较

希尔排序的引入

希尔排序是一种更高级的插入排序方式,其本质还是对直接插入排序的一种改进,是一种分组的直接插入排序。它将数据分成若干组,然后进行组内的插入排序,然后慢慢变成一整组之间的排序,减少了重复的比较次数,有效的提升了效率。而直接插入排序在一开始就有很多次的重复比较,因为其一直是一组在排序,元素比较的距离太近了。

希尔排序的介绍

如果数据越接近有序,时间效率越高,但是数组长度n越大,数组越无序的时候,直接插入的排序就有了比较多的缺点,希尔排序一定程度是解决了问题。

希尔排序的算法描述如下

  1. 将一个数据序列分程若干组,每组之间相隔一段距离(增量),在一个组之间进行直接插入算法排序
  2. 增量的初值通常为一个序列长度的一半,以后每次的增量减半,直到1为止,随着增量减小,序列越接近有序

图解算法

image20200624204711657.png

image20200624204610065.png

image20200624204906105.png

image20200624205020864.png

希尔排序的算法实现

//希尔排序
public static void sort(int[] array){
    //对delta进行循环
    for(int delta = array.length/2;delta>0;delta/=2){
        //对每一组进行排序
        for (int i=delta;i<array.length;i++){
            int temp = array[i],j;
            //分组逐个对比,找到组中插入的位置,并将前面的元素向后移动
            for (j = i-delta;j>=0 && temp<array[j];j-=delta){
                array[j+delta] = array[j];
            }
            //把temp放到应该在的位置上
            array[j+delta] = temp;
        }
    }
}

时间复杂度分析

对于希尔排序,需要排序logN趟,在每一趟中排序N

所以总的时间复杂度是O(NlogN)

快速排序

综述

快速排序是冒泡排序的一种高级形式,冒泡排序中存在重复的数据的移动,快速排序需要解决重复移动的问题

快速排序的介绍

快速排序的算法描述

在序列中选择一个元素作为基准值,每趟从数据两端开始交替进行

  1. 如果这个数小于基准值把这个数放到基准值的位置,把基准值放到那个数的位置,从前向后寻找
  2. 如果有一个数大于基准值,这两个数交换位置,从后向前寻找
  3. 重复算法,直到这个基准值的位置找到位置

此时,我们已经找到基准值的所在位置,我们基准值前面的元素都小于基准值,基准值后面的元素都大于基准值,整个序列被划分成两个小序列,递归执行快速排序这两个小序列

快速排序算法的图解

image20200624213714448.png

image20200624213830595.png

image20200624213911681.png

image20200624213933273.png

image20200624214053706.png

image20200624214151015.png

image20200624214256852.png

image20200624214324142.png

快速排序算法的实现

/**
 * 快速排序算法
 * @param keys 需要排序的数组
 * @param begin 开始位置的下表
 * @param end 结束位置的下标
 */
public static void quickSort![image20200624214033293.png](http://lucasgao.cn:80/upload/2020/06/image-20200624214033293-4cbd6976d3174de3b91db1149191ab8f.png)(int[] keys, int begin, int end){
    //递归算法的结束条件
    if (begin<0 || end>=keys.length || begin>=end)
        return;
    int i=begin,j=end;
    int vot = keys[i];  //将序列的第一个作为哨兵/基准值
    while (i!=j){
        //从后向前进行比较
        while(i<j && keys[j]>=vot)
            j--;
        //如果是 keys[j]<vot
        if (i<j)
            keys[i++]=keys[j];
        //从前向后进行比较
        while (j>i && keys[i]<=vot)
            i++;
        // 当 keys[i]>vot
        if (i<j)
            keys[j--] = keys[i];
    }
    //vot归位
    keys[i] = vot;
    //递归排序两个子序列
    quickSort(keys,begin,j-1);
    quickSort(keys,i+1,end);
}

快速排序算法的时间复杂度分析

快速排序算法需要排序logN个子序列,每个子序列的时间复杂度位N

所以总的时间复杂度为NlogN

堆排序

算法综述

堆排序算法是选择排序算法的一种更高级的版本,其关键是利用了堆的性质,提高了选择排序选择最大/最小值的速度

具体介绍

具体介绍在这里

http://lucasgao.cn/archives/%E5%A0%86%E6%8E%92%E5%BA%8F

算法实现

/**
 *  进行堆排序
 *  minheap 为真时升序,为假时降序
 */
public static void heapSort(int[] keys,boolean minheap)     //堆排序
{
    //从叶子节点上面一层开始创建最大/最小堆
    //根节点为最大/最小值
    for(int i=keys.length/2-1;i>=0;i--)             
        sift(keys,i,keys.length-1,minheap);
    //进行堆排序
    for(int i=keys.length-1;i>0;i--)
    {
        swap(keys,0,i);             //交换keys[0]和keys[i]的值
        sift(keys,0,i-1,minheap);   //向下调整,把此堆调整为最大/最小堆
    }
}
/**
 *  交换a处和b处的值
 */
public static void swap(int[] keys,int a,int b)
{
    int temp = keys[a];
    keys[a] = keys[b];
    keys[b] = temp;
}
 /**
 *  向下调整函数,传入一个需要向下调整的节点编号parent,孩子节点范围end,从parent开始向下调整
 *  keys 数组
 *  minheap 为真时创建最小堆,为假时创建最大堆
 *  向下调整函数基于parent的孩子都是最小/最大堆
 */
public static void sift(int[] keys,int parent,int end,boolean minheap )
{
    int child=2*parent+1;       //child是parent的左孩子
    int value=keys[parent];     //记录parent的值
    while(child<=end)           //保证child在范围内
    {
        if(child<end && (minheap?keys[child]>keys[child+1]:keys[child]<keys[child+1]))  
        //找出child中比较小的那一个
            child++;
        if(minheap?value>keys[child]:value>keys[child]) //如果父母比孩子大/小
        {
            keys[parent]=keys[child];       //将较小/大的孩子节点和父亲节点交换
            parent = child;                 //孩子和父母都进入下一层
            child = 2*parent+1;
        }
        else
            break;
    }
    keys[parent] = value;                   //将原来的parent值和最小子堆中最大/小的进行交换
}

时间复杂度分析

建立堆需要的时间复杂度为logN,选择n个数并调整的时间的时间复杂度为NlogN,所以堆排序的时间复杂度为NlogN

归并排序

归并排序算法描述

将一个长为n的序列分割成n个子序列,两两进行归并操作,将相邻的两个子序列合并成一个序列,这个序列满足排序的要求,然后继续两两归并,变成一个大序列

算法图解

image20200624223842406.png

image20200624223940648.png

image20200624224048240.png

image20200624224157651.png

image20200624224307743.png

算法实现

/**
 * 一次归并,把两个子序列归并成一个序列
 * @param x 子序列x, 原序列
 * @param y 子序列y, 现序列
 * @param begin1 子序列1开始的位置
 * @param begin2 子序列2开始的位置
 * @param n 子序列的长度n
 */
public static void merge(int[] x, int[] y, int begin1, int begin2, int n){
    int i=begin1,j=begin2,k=begin1;
    //x有可能不满n个
    while (i<begin1+n && j<begin2+n && j<x.length){
        //不断进行对比,按照大小顺序进行插入,直到一个子序列结束
        if (x[i]<x[j]){
            y[k++] = x[i++];
        }else {
            y[k++] = x[i++];
        }
    }
    //如果是子序列2结束了,把子序列1剩下的内容拷贝到y中
    while (i<begin1+n && i<x.length){
        y[k++] = x[i++];
    }
    //如果是子序列1结束了,把子序列2剩下的内容拷贝到y中
    while (j<begin2+n && j<x.length){
        y[k++] = x[j++];
    }
}

/**
 * 一趟归并,将序列中若干个子序列进行归并
 * @param x 原序列x
 * @param y 复制到的序列y
 * @param n n为子序列的长度
 */
public static void mergePass(int[] x, int[] y, int n){
    //进行数次归并
    for (int i=0;i<x.length;i+=2*n){
        merge(x,y,i,i+n,n);
    }
}

/**
 * 归并排序
 * @param x[]
 */
public static void mergeSort(int[] x){
    int[] y = new int[x.length];
    int n = 1;
    while (n<x.length){
        //将x序列归并到y
        mergePass(x,y,n);
        n*=2;
        //将y序列归并到x
        if (n<x.length){
            mergePass(y,x,n);
            n*=2;
        }
    }
}

时间复杂度分析

一趟归并的时间复杂度为N ,总共进行logN趟归并

总时间复杂度为NlogN