文档章节

排序算法总结

冷记忆
 冷记忆
发布于 2016/07/07 19:51
字数 8977
阅读 8
收藏 0

 

 

         查找算法之折半查找算法

Table of Contents

在查找算法中,主要分为两类:一类是静态查找表和动态查找表。所谓静态查找表就是只负责查找的表,主要完成的操作有两个:一个是查询某个特定的元素是否在表中;二是检索特定数据元素的属性。动态查找表就是在查询过程可以进行更新或者删除操作的表。在查找算法中,作为程序员来讲,最重要的就是折半查找算法了。这篇博客也是主要讨论折半查找算法的,折半查找算法运用的前提是数据元素必须是有序的(注意我这里的有序不是严格有序,只是从总体上是有序的)。折半查找算法有三个变种:折半查找算法、插值查找算法和斐波那契查找算法。

折半查找算法

折半查找算法又称二分查找,主要思想就是去数据的中间记录作为比较对象,如果待查找的数据与中间记录相等,那么查找成功;如果待查找的数据记录小于中间数据记录,那么就从左半区中查找;如果待查找的数据大于中间数据记录,那么就从右半区中进行查找。重复以上过程,如果查找成功就返回,否则就是查找失败。下面以一个实例说明折半查找算法的执行过程。

代码清单1-1:

/* @param a: 要查找的数组 */

/* @param n: 数组的长度 */

/* @param key: 待查找的关键字 */

 

int Binary_Search(int *a,int n,int key)

{

    int low,mid,high;

    low =1;                 /* 定义开始查找的最低下标 */

    high = n;               /* 定义开始查找的最高下标 */

 

    while(low <= high)

    {

        mid = (low+high)/2;

        if(a[mid] > key)

        {

            high = mid -1;

        }

        else if(a[mid] < key)

        {

            low = mid + 1;

        }

        else                /* 执行到这表示已经找到key */

            return mid;

    }

}

假如有一个数组{0,1,16,24,35,47,59,62,73,88,99},现在要查找62,折半查找算法的执行过程如下:

    1    程序开始运行,n=10,key=62,此时low=1,high=10;

    2    进入循坏,开始查找

    3    获取中间位置mid = (1+10)/2 = 5;对应的a[5] = 47 < key = 62;故执行第二个if的判断语句中,更新low的值,这里low=5+1=6;

    4    开始第二轮循坏,重新计算mid=(6+10) /2=8;再次比较a[8]=73 > key =62;故进入第一个if判断语句中,更新high的值,这里high=8-1=7;

    5    进入第三轮循坏,再计算mid=(6+7)/2=6;再次比较a[6]=59 < key=62;故更新low=mid+1=7

    6    此时low=7与high=7相等,继续循环,mid=(7+7)/2=7;比较a[7]=62=key=62,所以查找成功,返回mid=7;程序退出。

那么折半查找算法的最坏的查找次数是

 

次,那么最好的情况呢,由于是把中间那个数据做为比较对象,如果查找的数据就是中间那个数据,则需要查找的次数就是1了。综合来看,折半查找算法的平均时间复杂度是O(logn);

插值查找算法

考虑这么一种极端情况,如果有10万个数据,范围是1-100000,如果要查找的数据是5,那么按照上面的折半查找算法要查找的次数就比较多了。因为根据我们的思维,由于5是一个偏小的数,而中间那个数比5大得多,那么就应该选择偏小的数作为比较对象。在折半查找算法中,我们总是选择1/2作为下一个要比较的对象的下标,为什么不可以是其他的分数呢?比如1/3,1/4之类的。这里就是要讨论的插值查找算法了。

注意到折半查找算法中,mid=(low+high)/2 = low + (high - low)/2,这里的插值查找算法就是在/2上下功夫,经过许多算法科学家的研究最终确定了这个分数确定如下样子的时候比较高效:

mid = low + (key - a[low])/(a[high] - a[low])

这就是插值查找算法的核心了,有木有很简单的酱紫。做了这项优化后,虽然时间复杂度没有提到提高,但是在查找表比较长,关键字分布也比较均匀的情况下,使用插值查找算法的效率比使用折半查找算法更高。

代码清单1-2:

/*  插值查找算法 */

int Interpolation_Search(int *a,int n,int key)

{

    int low,mid,high;

    low = 1;

    high = n;

 

    while(low <= high)

    {

        mid = low + (key - a[low])/(a[high] - a[low]);

        if(a[mid] > key)

        {

            high = mid -1;

        }

        else if(a[mid] < key)

        {

            low = mid + 1;

        }

        else                /* 执行到这表示已经找到key */

            return mid;

    }

    return 0;

}

斐波那契查找算法

斐波那契查找算法主要利用了黄金分割的原理实现的,其中有一个斐波那契数列。一个斐波那契数列是像这样的:0,1,1,2,3,5,8,13,21,34,55,89…。很容易发现其规律是从第三项开始,下一项都是前两项之和。那么与查找有什么关系呢?实际上可以吧斐波那契查找算法理解为一种更优秀的插值查找算法,因为其选择比较的对象的分割点处于黄金分割点。使用斐波那契查找算法进行查找的过程一般是这样的:

    1    从斐波那契数列中找到要查找的数据的长度n位于数列的哪个位置,假定为k

    2    如果数列下标为k对应的值大于n,那么就把大于n的位置用n代替。这一步的主要作用就是如果要查找的数据位于大于n的位置,那么就可以直接返回n位置对应的值

    3    以黄金分割点对应的值作为比较的对象,循坏开始查找。找到了就直接返回。

斐波那契查找算法的代码如下:

代码清单1-3:

/* 斐波那契查找算法 */

int Fibonacci_Search(int *a,int n,int key)

{

    int low,mid,high,i,k=0;

    low =1;                 /* 从第2位(下标为1)开始存储数据 */

    high =n;

    while(n>F[k]-1)         /* 找到n在斐波那契数列中的位置 */

        k++;

    for(i=n;i<F[k]-1;i++)   /* 用a[n]填充剩余的位置 */

        a[i]=a[n];

 

    while(low <= high)

    {

        mid = low +F[k-1]-1;/* 黄金分割点就是这么算的 */

        if(a[mid] > key)

        {

            high = mid -1;

            k = k-1;

        }

        else if(a[mid] < key)

        {

            low = mid +1;

            k = k-2;

        }

        else

        {

            if(mid <=n)     /* 由于用数组的最后一个数进行了填充,所以mid的值可能超过n */

                return mid;

            else

                return n;

        }

    }

    return 0;

}

下面以{0,1,16,24,35,47,59,62,73,88,99}中查找59为例,说明程序的运行过程:

    1    程序开始,key=59,n=10

    2    根据斐波那契数列{0,1,1,2,3,5,8,13,21,34},由于F[6]=8< n=10 < F[7]=13,所以k等于7

    3    因为n=10 < F[7]=13,所以需要对a[11]和a[12]用a[10]进行填充

    4    进入循坏,开始查找

    5    计算mid = 1+F[7-1]-1=8,于是第一轮要进行比较的对象是a[8]=73;

    6    比较a[8]与59的大小,a[8]=73>key=59,所以进入第一个if判断语句,于是high = mid-1=8-1=7,k=7-1=6

    7    计算mid=1+F[6-1]-1=5,则第二轮要比较的对象是a[5]=47

    8    比较a[5]与59的大小,a[5]=47< key=59,所以进入第二个判断语句,于是low=mid+1=5+1=6,k=k-2=6-2=4

    9    计算mid=6+F[4-1]-1=7,于是第三轮要比较的对象是a[7]=62

    10    比较a[7]与59的大小,a[7]=62>key=59,则进入第一个if判断语句,于是high=mid-1=7-1=6,k=k-1=4-1=3

    11    计算mid=6+F[3-1]-1=6,于是第四轮要进行比较的对象是a[6]=59

    12    比较a[6]与59的大小,a[6]=59=key=59,则进入最后一个else语句,查找成功,返回mid=6

从上面的程序执行过程中可以看到,如果要查找的元素在要比较元素的左边,那么右边的元素都不会在查找了。这也是斐波那契查找算法角普通折半查找算法优秀的地方,在大量的数据中查找中性能是优于折半查找算法的。

小结

上述的三个查找算法都是基于有序的基础进行的,如果忽略了这个前提,其查找性能将会大打折扣,这一点是需要注意的。折半查找算法选择1/2作为比较元素的分割点,而插值查找算法则是使用更灵活的插值点作为分割点,而斐波那契查找算法则是充分利用斐波那契数列的特点进行查找的,其使用的是黄金分割点作为比较元素的分割点。这也是它们三者的不同之处。

附:测试函数

代码清单1-4:

int main()

{

    int i,result;

    int arr[MAXSIZE]={0,1,16,24,35,47,59,62,73,88,99};

 

    result = Binary_Search(arr,10,62);

    printf("折半查找result:%d\n",result);

    result = Interpolation_Search(arr,10,62);

    printf("插值查找算法result:%d\n",result);

 

    F[0]=0;

    F[1]=1;

    for(i=2;i<100;i++)

        F[i]=F[i-1]+F[i-2];

 

    result = Fibonacci_Search(arr,10,59);

    printf("斐波那契查找result:%d\n",result);

 

    return 0;

}

常用内部排序算法之一:归并排序

Table of Contents

前言

归并排序是所有常用内部排序算法中稳定性最好的,无论是平均时间复杂度、最坏时间复杂度还是最好时间复杂度,其时间复杂度都是O(nlogn)。由于这个特性,在需要考虑排序稳定性的情况下,归并排序是所有优化算法(直接插入排序、冒泡排序和简单选择排序)使用最多的。其实归并排序算法的思想很简单:假设初始序列含有n个记录,则可以看成是n个有序的子序列,每一个子序列的长度都是1,然后把这些子序列两两归并,得到$\lceil n/2 \rceil$($\lceil x \rceil$表示不小于$x$的最小整数)个长度为2或者1的有序子序列;再两两归并,……,如此重复,直至得到一个长度为n的有序序列为止。这种方法也被称为2路归并排序。

首先看代码的实现过程:

1

package com.rhwayfun.algorithm.sort;

 

/**

 * 归并排序

 * @author Administrator

 *

 */

public class MergeSort2 {

 

    public void mergeSort(int[] a){

        mSort(a,a,0,a.length - 1);

        for (int i = 0; i < a.length; i++) {

            System.out.println(a[i]);

        }

    }

 

    private void mSort(int[] b, int[] a, int i, int j) {

        int m = 0;

        int[] c = new int[a.length];

        if(i == j){//递归终止条件

            a[i] = b[i];

        }else {

promise的状态有()m = (i + j)/2;

            //将数组a分为a[i...m]并进行排序

            mSort(b,c,i,m);

            //数组a[m+1...j]部分进行排序

            mSort(b, c, m + 1, j);

            //将a[i...m]部分和a[m+1...j]部分的排序结果归并到a

            merge(c,a,i,m,j);

        }

    }

 

    private void merge(int[] b, int[] a, int i, int m, int t) {

        int j = 0,k = 0,l = 0;

        for(j = m+1,k = i;i <= m && j<=t;k++){

            //将b中记录由小到大归并到a中

            if(b[i] < b[j]){

                a[k] = b[i++];

            }else {

                a[k] = b[j++];

            }

        }

        //将剩余b[i...m]复制到a中

        if(i<=m){

            for(l=0;l<=m-i;l++){

                a[k+l]=b[i+l];

            }

        }

        //将剩余b[m+1...t]复制到数组a中

        if(j<=t){

            for(l=0;l<=t-j;l++){

                a[k+l]=b[j+l];

            }

        }

    }

    

    public static void main(String[] args) {

        new MergeSort2().mergeSort(new int[]{50,10,90,30,70,40,80,60,20});

    }

}

下面以序列{50,10,90,30,70,40,80,60,20}为例,说明归并排序的具体过程:

    1    初始时刻,mSort方法中的数组b和数组a都是{50,10,90,30,70,40,80,60,20}

    2    i = 0,j = 9,显然两者不相等,将数组b分为b[i…m]和b[m+1…j],此时m = 5,也就是数组b 正中间下标

    3    然后递归调用mSort函数,继续将b[0…5]和b[6…9]拆成两组,直到每组只有一个元素

    4    两次递归调用mSort函数之后,b[0…5]和b[6…9]已经排好序了,最后将这两组排好序的数组继续归并成最终排好序的数组,这个过程调用的是merge函数,该函数的主要目的就是将最好的两组进行归并排序

    5    将排好序的数组返回给原数组a,排序结束

归并排序小结

由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为$log_2n$的栈空间,因此归并排序的空间复杂度是$O(n+logn)$。

归并排序的总的时间复杂度是$O(nlogn)$,同时这也是最好、最坏、平均的时间复杂度。需要注意的是,归并排序的是一种稳定的排序算法,但是归并排序是比较占用内存的。

常用内部排序算法之二:快速排序

Table of Contents

前言

快速排序可以说是内部排序算法中的高手,之所以称为快速排序,是因为快速排序算法从整体性能上讲是排序冠军。快速排序算法的思想是:通过一趟快速排序将待排序的记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的记录的关键字小,则可分别对这两部分记录继续进行排序,达到整个记录有序。实现快速排序算法的核心是partition函数,这个函数的主要目的先选取当中的一个关键字(称为枢轴),然后尽可能将他放在一个位置,使得它左边的值都比它小,右边的值比它大

快速排序算法实现

1

package com.rhwayfun.algorithm.sort;

 

public class QuickSort3 {

 

    public void quickSort(int[] a){

        qSort(a,0,a.length - 1);

        //打印输出

        for (int i = 0; i < a.length; i++) {

            System.out.println(a[i]);

        }

    }

 

    private void qSort(int[] a, int low, int high) {

        int pivot = 0;

        if(low < high){

            //将数组a一分为二

            pivot = partition(a,low,high);

            //对第一部分进行递归排序

            qSort(a,low,pivot);

            //对第二部分进行递归排序

            qSort(a,pivot + 1,high);

        }

    }

 

    private int partition(int[] a, int low, int high) {

        //用第一个元素作为枢轴记录

        int pivotkey = a[low];

        while(low < high){

            //将比枢轴记录小的交换到低端

            while(low < high && a[high] >= pivotkey){

                high--;

            }

            swap(a,low,high);

            //将比枢轴记录大的交换到高端

            while(low < high && a[low] <= pivotkey){

                low++;

            }

            swap(a,low,high);

        }

        //返回枢轴所在的位置

        return low;

    }

 

    private void swap(int[] a, int low, int high) {

        int temp = a[low];

        a[low] = a[high];

        a[high] = temp;

    }

    

    public static void main(String[] args) {

        new QuickSort3().quickSort(new int[]{50,10,90,30,70,40,80,60,20});

    }

}

快速排序算法的最优时间复杂度是$O(nlogn)$,在如下的情况下是最优的:对于一组具有n个关键字的记录,partition函数每次都划分得很均匀,也就是每次调用partition函数之后,比枢轴小的关键字和比枢轴大的关键字的数量基本相等。这样下次调用partition函数的时候所用的时间是上次调用partition函数的两倍加上比较元素的时间,所以这是最优的情况。

在最坏的情况指的就是每次调用partition函数,只得到一个比上一次划分少一个记录的子序列(因为只要调用partition函数,必须至少会有一次关键字的交换)。由于只减少了一个关键字,所以后面还需要进行n-1次(总共有n个关键字)递归调用partition函数。所以到最后总共需要比较的次数是$\sum_{i=1}^{n-1} = n-1 + n-2 + … + 1 = \frac{n(n-1)}{2}$,所以最终的时间复杂度是$O(n^2)$。

在平均的情况下,枢轴的关键字应该在$k$位置($1 \le k \le n$)。所以最优情况下的时间复杂度是$O(nlogn)$。

那么快速排序算法的空间复杂度又是如何呢?最优和平均情况下空间复杂度都是$O(logn)$,在最坏情况就是$n-1$次调用,所以空间复杂度是$O(n)$。

快速排序算法的优化

优化一:优化枢轴的选取位置

可以发现我们上面的算法中,枢轴的选取是在第一个位置的,这种选取枢轴位置的最大弊端就是很可能在调用partition函数的时候,只更换了两个元素的位置,而其他位置的元素并没有发生变化,这就是上面分析中提到的最坏的情况,发现导致这种情况的根源在于选取的枢轴的大小要么太大要么太小(因为太大或者太小,high或low的值只能减小一个位置或者增加一个位置),那么优化的思路就是让枢轴既不会太大又不会太小。所以可以采用三数取中法:这种方法就是取三个关键字先进行排序,将中间的数作为枢轴,一般是取左端、右端和中间的三个数。这样排序之后就能基本保证枢轴既不会太大又不会太小。所以我们只需要修改partition函数如下:

1

private int partition2(int[] a, int low, int high) {

        //用第一个元素作为枢轴记录

        int pivotkey = 0;

        //计算数组中间的下标

        int m = low + (high - low)/2;

        if(a[low] > a[high]){

            swap(a, low, high);

        }

        if(a[m] > a[high]){

            swap(a, m, high);

        }

        if(a[low] > a[m]){

            swap(a, low, m);

        }

        pivotkey = a[low];

        while(low < high){

            //将比枢轴记录小的交换到低端

            while(low < high && a[high] >= pivotkey){

                high--;

            }

            swap(a,low,high);

            //将比枢轴记录大的交换到高端

            while(low < high && a[low] <= pivotkey){

                low++;

            }

            swap(a,low,high);

        }

        //返回枢轴所在的位置

        return low;

    }

优化二:优化不必要的交换

经过上面的优化,我们选取枢轴关键字基本是适中大小的,分析枢轴的位置变化过程,从最后一个位置到第一个位置,再到中间那个位置。其实枢轴的目标就是中间那个位置,所以在枢轴到达中间位置的很多交换其实是不必要的。基于这个思路可以继续优化partition函数如下:

1

private int partition3(int[] a, int low, int high) {

        //用第一个元素作为枢轴记录

        int pivotkey = 0;

        //计算数组中间的下标

        int m = low + (high - low)/2;

        if(a[low] > a[high]){

            swap(a, low, high);

        }

        if(a[m] > a[high]){

            swap(a, m, high);

        }

        if(a[low] > a[m]){

            swap(a, low, m);

        }

        pivotkey = a[low];

        //把枢轴元素备份到一个临时变量中

        int temp = pivotkey;

        while(low < high){

            //将比枢轴记录小的交换到低端

            while(low < high && a[high] >= pivotkey){

                high--;

            }

            //采用替换而不是交换的方式操作

            a[low] = a[high];

            //将比枢轴记录大的交换到高端

            while(low < high && a[low] <= pivotkey){

                low++;

            }

            //采用替换而不是交换的方式操作

            a[high] = a[low];

        }

        //将枢轴的值替换回给a[low]

        a[low] = temp;

        //返回枢轴所在的位置

        return low;

    }

优化三:优化数据量较小时的排序

在数据量较小的时候使用简单排序算法反而更简单,更高效,正如排序数组{2,1,3}的时候,使用简单排序算法比如直接插入排序只要两次比较久搞定了,使用快速排序的话还要划分,明显效率低一些。所以我们可以对partition函数进行小数组的优化,有资料认为当数组的长度不大于7的时候算是小数组,也有认为是50,这个其实不是最重要的,这个时候就使用直接插入排序算法就很好用。所以基于这个思路优化代码如下:

1

private void qSort(int[] a, int low, int high) {

        int pivot = 0;

        if(low < high && (high - low) > MAX_LENGTH_SORT){

            //MAX_LENGTH_SORT暂且定为50

            //将数组a一分为二

            pivot = partition3(a,low,high);

            //对第一部分进行递归排序

            qSort(a,low,pivot);

            //对第二部分进行递归排序

            qSort(a,pivot + 1,high);

        }else{

            //小数组的时候使用直接插入排序

            insertSort(a);

        }

    }

优化四:优化递归操作

递归对性能较大,如果递归的层次很多的话将会造成栈溢出,因此如果能够能够减少递归次数的话将会对函数的性能提高不少。下面对qSort函数进行代码优化如下:

1

private void qSort2(int[] a, int low, int high) {

        int pivot = 0;

        if(low < high && (high - low) > MAX_LENGTH_SORT){

            while(low < high){

                //将数组a一分为二

                pivot = partition3(a,low,high);

                //对第一部分进行递归排序

                qSort2(a,low,pivot);

                //对第二部分进行尾递归,这里之所以可以将pivot+1赋给low,是因为一/次递归结束

                //之后,low的值就没有用处了。下一次递归调用的执行的就是qSort(a,pivot + 1,high)

                low = pivot +1;

            }

        }else{

            //小数组的时候使用直接插入排序

            insertSort(a);

        }

    }

经过以上的优化,快速排序算法可以算得上是当之无愧的排序冠军,快速排序算法也是名副其实。

常用内部排序算法之三:堆排序

Table of Contents

前言

堆排序是以堆为原型的排序。堆首先是一棵二叉树,具有以下两个性质:每个节点的值大于或者等于其左右孩子结点的值,称为大顶堆;或者每个节点的值都小于或者等于其左右孩子结点的值,称为小顶堆。从这个定义中可以发现,堆得根节点要么是最大值要么是最小值。实现堆排序的基本思想是:将待排序的序列构造成一个大顶堆或者小顶堆。此时整个堆满足根节点是最大值或者最小值。将根节点移走,并与堆数组的最后一个值进行交换,这样的话最后一个值就是最大值或者最小值了。然后将剩余n-1(假设原来总共有n个元素)未排序的序列重新构造成一个最大堆或者最小堆,再与除原来最大值之外的最后一个元素进行交换,得到次小值。如此反复进行,就得到一个排序的序列。

堆排序算法的Java实现

1

package com.rhwayfun.algorithm.sort;

 

public class HeapSort2 {

 

    public void heapSort(int[] a){

        for(int i = a.length/2-1; i >= 0; i--){

            //建立一个最大堆

            heapAdjust(a,i,a.length - 1);

        }

        for (int i = a.length - 1; i > 0; i--) {

            //将堆顶元素与当前未经排序的最后一个记录交换

            swap(a,0,i);

            //将数组a中下标从0到i-1的子序列重新调整为最大堆

            heapAdjust(a, 0, i - 1);

        }

        

        for (int i = 0; i < a.length; i++) {

            System.out.println(a[i]);

        }

    }

 

    private void swap(int[] a, int i, int j) {

        int temp = a[i];

        a[i] = a[j];

        a[j] = temp;

    }

 

    private void heapAdjust(int[] a, int s, int m) {

        int temp = 0,j=0;

        //把堆顶元素保存在临时变量中

        temp = a[s];

        //由于s可能是0,所以需要+1。此外,如果当前结点的序号是s,那么其左孩子是2*s+1(+1是因为s可能是0)

        for(j = 2*s+1; j <= m; j = 2*j+1){

            //找出左右孩子较大的结点的下标

            if(j < m && a[j] < a[j+1]){

                ++j;

            }

            if(temp >= a[j]){

                break;

            }

            //把较大的孩子结点的赋给当前结点

            a[s] = a[j];

            //把更大孩子结点的下标赋给s

            s = j;

        }

        //把原来s下标位置的值赋给新的下标为s的值,这样就完成了当前结点与更大孩子结点值的交换

        a[s] = temp;

    }

    

    public static void main(String[] args) {

        new HeapSort2().heapSort(new int[]{90,70,80,60,10,40,50,30,20});

    }

}

可以发现在建立最大堆的时候,$i$是从$a.length/2$开始的,为什么要从这个位置开始呢?比如有一个数组${90,70,80,60,10,40,50,30,20}$,初始情况是这样的:

 

一共有9个元素,那么$a.length/2-1$的值是3,也就是第4个元素,执行for循环,i的值从3->2->1->0变化,可以发现这几个下标的结点都是有孩子结点的元素,所以第一个for循环就很好理解了:其实就是从下往上、从右到左,将每个非终端结点当做根节点,将其和子树调整成最大堆,所以下标3->2->1->0的变化,也就是60,80,70,90结点的调整过程。

堆排序算法的时间复杂度

可以发现堆排序的主要时间主要花在建堆和重建堆时的反复筛选上。在初始建堆的时候,由于只涉及两个节点的交换操作,所以建堆的时间复杂度是$O(n)$。在正式排序的时候,第i次取堆顶的元素并重建堆需要花去$O(logi)$的时间,需要n-1次取堆顶记录,所以排序的过程的时间复杂度是$O(nlogn)$。而且这是最好、最坏和平均的时间复杂度,但是由于记录的交换与比较是跳跃式的,所以与归并排序不同,堆排序是一种不稳定的排序算法。

由于初始建堆的比较次数比较多,所以堆排序不适合记录数较少的情况(使用简单排序算法是一种不错的选择,没必要大材小用了)。

常用内部排序算法之四:简单选择排序、插入排序和冒泡排序

Table of Contents

前言

之所以把这三类算法放在一块,是因为除此之外的算法都是在这三类算法的基础上进行优化的。简单选择排序的思想是每一趟$n-i+1(i=1,2,…,n-1)$个记录中选择最小的记录作为有序序列的第$i$个记录。直接插入排序的思想是将一个记录插入到已经排好序的有序序列中,从而得到一个新的、记录数增加1的有序表。冒泡排序的算法思想是不断在交换,通过交换完成最终的排序,每一趟的交换就会把最大的记录取出来,下一趟则会把第二大的记录取出来,这样每进行一趟交换就把一个记录取出来的过程称为冒泡。

简单选择排序算法

简单选择的排序的算法思想是:通过$n-i$次关键字间的比较,从$n-i+1$个记录中选出关键字最小的记录,并和第$i(1\le i \le n)$个记录交换之。其算法代码如下:

1

package com.rhwayfun.algorithm.sort;

 

public class SelectSort {

 

    public void selectSort(int[] a){

        int i,j,min;

        for (i = 0; i < a.length; i++) {

            //假设第一个位置的值是最小值

            min = i;

            for(j = i + 1; j < a.length; j++){

                if(a[min] > a[j]){

                    min = j;

                }

            }

            //如果min不等于i,说明找到最小值的下标

            if(min != i){

                swap(a,i,min);

            }

        }

        

        for(i = 0; i < a.length; i++){

            System.out.println(a[i]);

        }

    }

 

    private void swap(int[] a, int i, int min) {

        int temp = a[i];

        a[i] = a[min];

        a[min] = temp;

    }

    

    public static void main(String[] args) {

        new SelectSort().selectSort(new int[]{9,1,5,8,3,7,4,6,2});

    }

}

观察代码可以发现,第$i$趟排序需要比较$n-i$次关键字的比较,所以总共需要比较$\sum_{i=1}^{n-1}(n-i)=n-1+n-2+…+1=\frac{n(n-1)}{2}$次。最好的情况下,交换0次,最差的情况是交换$n-1$次,所以最终的时间复杂度是$O(n^2)$。

直接插入排序算法

直接插入排序算法的思想是:将一个记录插入到已经排序的有序表中,从而得到一个新的、记录数增加1的有序表。其处理过程是,在排序刚开始的时候,把第一个元素当做是排序的记录,当依次插入后面的元素的时候,就获得其插入的位置,然后形成一个新的有序表。其算法代码如下:

1

package com.rhwayfun.algorithm.sort;

 

public class InsertSort2 {

 

    public void insertSort(int[] a) {

        int i,j,temp;

        for(i = 1; i < a.length; i++){

            if(a[i] < a[i-1]){

                temp = a[i];

                for(j = i - 1; j >= 0 && a[j] > temp; j--){

                    a[j+1] = a[j];

                }

                a[j+1] = temp;

            }

        }

        

        for(i = 0;i < a.length; i++){

            System.out.println(a[i]);

        }

    }

    

    public static void main(String[] args) {

        new InsertSort2().insertSort(new int[]{9,1,5,8,3,7,4,6,2});

    }

}

从空间上分析,直接插入排序算法只需要一个辅助空间。

从时间复杂度上分析,最好的情况是排序的记录本身是有序的,所以时间复杂度是$O(n)$;在最坏的情况,待排序的记录是逆序的,那么此时的时间复杂度是$O(\frac{n^2}{4})$。所以虽然量级仍然是$n^2$,但是直接插入排序算法的时间复杂度是优于冒泡排序算法和简单选择排序的。

冒泡排序

冒泡排序的基本思想是两两比较相邻记录的关键字,如果反序就交换,直到没有反序的关键字为止。下面是一种实现思路:

1

package com.rhwayfun.algorithm.sort;

 

public class BubbleSort3 {

 

    public void bubbleSort(int[] a){

        int i,j;

        for(i = 0; i < a.length; i++){

            for(j = i + 1; j < a.length; j++){

                if(a[i] > a[j]){

                    swap(a,i,j);

                }

            }

        }

        

        for(i = 0; i < a.length; i++){

            System.out.println(a[i]);

        }

    }

    

    private void swap(int[] a, int i, int j) {

        int temp = a[i];

        a[i] = a[j];

        a[j] = temp;

    }

    

    public static void main(String[] args) {

        new BubbleSort3().bubbleSort(new int[]{9,1,5,8,3,7,4,6,2});

    }

}

这种版本也是我第一时间写出来的,但是可以发现一个问题,在排好第一个和第二个为止之后,数字3反而被排到了最后面。下面是针对这种情况的改良版代码:

1

public void bubbleSort2(int[] a){

        int i,j;

        for(i = 0; i < a.length; i++){

            for(j = a.length - 2; j >= i; j--){

                if(a[j] > a[j + 1]){

                    swap(a,j,j+1);

                }

            }

        }

        

        for(i = 0; i < a.length; i++){

            System.out.println(a[i]);

        }

    }

这里的改进主要把第二个for循环由从前往后比较改成由后往前进行比较了,这样的好处是可以把本来较小的元素放在尽可能前一点的位置,这种差异性在数据量较大的时候能够体现出来。以上改良版的冒泡排序使用于基本无序的序列,如果是基本有序的序列再使用上述的算法进行排序就会出现一个问题:那就是可能在进行完前几次的冒泡之后就已经是有序的了,那么后面的冒泡都是多余的。下面得代码是针对这种情况进行的优化:

1

public void bubbleSort3(int[] a){

        int i,j;

        boolean flag = true;

        for(i = 0; i < a.length && flag; i++){

            flag = false;

            for(j = a.length - 2; j >= i; j--){

                if(a[j] > a[j + 1]){//如果不进行数据交换,说明是有序的

                    swap(a,j,j+1);

                    flag = true;

                }

            }

        }

        

        for(i = 0; i < a.length; i++){

            System.out.println(a[i]);

        }

    }

如果在面试中要求写出冒泡排序算法的代码,写最后一种情况就可以了。

下面分析冒泡排序算法的时间复杂度:在最坏的情况就是待排序的记录是逆序的,此时的时间复杂度是$O(n^2)$;最好的情况是,排序表本身就是有序的,那么在这种情况下,时间复杂度是$O(n)$。

常用内部排序算法之五:希尔排序

Table of Contents

前言

在前面介绍常用内部排序算法的文章中,我们知道在简单排序算法中,直接插入排序算法的时间复杂度是要优于冒泡排序和简单选择排序的。而这里要讲的希尔排序则是优于直接插入排序的。而且希尔排序打破了原来简单排序中时间复杂度不能超过$O(n^2)$的神话。这也是希尔排序伟大的地方,而且希尔排序不同于之前三种简单排序,希尔排序是以一个科学家的名字进行命名的。

希尔排序的原理

由于希尔排序是在直接插入排序的基础上进行改进的,所以为了更好理解希尔排序,需要再次将直接插入排序请出来。我们知道直接插入排序的基本思想是将一个记录插入到有序表中,构成一个新的有序表。而且直接插入排序的使用情况是基本有序、记录少。在实际的情况中,这两个条件是有点苛刻的,很多情况下都是无序在记录数比较大。这种情况下再使用直接插入排序无疑是影响效率的。基于此,希尔提出了把大记录数的列表分割为一组组更少的记录列表,这个过程的实现采用的跳跃分割策略。所谓跳跃分割策略,就是将相距某个增量的记录组成一个子序列,这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序

希尔排序的实现算法与分析

下面是希尔排序具体的实现代码:

1

package com.rhwayfun.algorithm.sort;

 

public class ShellSort2 {

 

    public void shellSort(int[] a) {

        //定义一个增长序列,就是分割数组的增量

        int inc = a.length,i,j,k;

        do{

            inc = inc / 3 + 1;

            for (i = inc; i < a.length; i++) {

                if(a[i] < a[i - inc]){

                    //将a[i]插入有序表中

                    k = a[i];

                    //记录后移

                    for (j = i - inc; j >= 0 && k < a[j]; j-=inc) {

                        a[j + inc] = a[j];

                    }

                    //把需要插入的值插入到那个位置,这里就是j+inc

                    a[j + inc] = k;

                }

            }

        }while(inc > 1);//循环的终止条件是增量变为1的时候

        

        for (i = 0;i < a.length; i++) {

            System.out.println(a[i]);

        }

    }

    

    public static void main(String[] args) {

        new ShellSort2().shellSort(new int[]{0,9,1,5,8,3,7,4,6,2});

        

    }

}

上面有几个难以理解的地方。第一点是为什么增量的选取是inc=a.length/3+1。因为目前增量的选取还没有一个定论,但是有研究表明当增量序列为$dlta[k]=2^{t-k+1}-1$$(0 \lt k\lt t \lt \lfloor log_2{(n+1)} \rfloor)$的时候,可以获得不错的效率。第二点,第二个循环是干嘛的。实际上就是把排在序列前面的更大的记录往后挪,然后循坏之后的那个赋值语句就是把要插入的那个值放入原先被移走的那个数的位置。还有一点是为什么循坏的终止条件是增量为1的时候,而不是其他值的时候呢?假设现在增量变为了1,可以发现在从增量为5到增量为1,这个过程已经基本使得整个序列是有序的,当增量变为1的时候,可交换的元素的个数大为减少,所以增量为1是循环结束的条件(其实从另一个角度看,增量必然是一个正整数,而1是最小的正整数)。

然后,我们综合看一下希尔排序与直接插入排序的代码实现:

1

public void insertSort(int[] a) {

        int i,j,temp;

        for(i = 1; i < a.length; i++){

            if(a[i] < a[i-1]){

                temp = a[i];

                for(j = i - 1; j >= 0 && a[j] > temp; j--){

                    a[j+1] = a[j];

                }

                a[j+1] = temp;

            }

        }

        

        for(i = 0;i < a.length; i++){

            System.out.println(a[i]);

        }

    }

可以发现大部分是相同的代码,只不过希尔排序采用了跳跃式的分割数组的策略,在i与j那里改成了增量序列,所以大大提高了排序的整体性能。那么希尔排序的时间复杂度是多少呢?答案是$O(n^{3/2})$,明显是优于$O(n^2)$的时间复杂度的,这也是希尔排序伟大的地方。

© 著作权归作者所有

上一篇: 时间管理
下一篇: java面试基础
冷记忆
粉丝 0
博文 16
码字总数 36699
作品 0
南昌
私信 提问

暂无文章

高并发场景下的缓存有哪些常见的问题?

一、缓存一致性问题 当数据时效性要求很高时,需要保证缓存中的数据与数据库中的保持一致,而且需要保证缓存节点和副本中的数据也保持一致,不能出现差异现象。 这就比较依赖缓存的过期和更新...

别打我会飞
25分钟前
1
0
List list = new ArrayList()为何父类引用指向子类对象(多态)

态:要有继承,方法的重写,父类引用指向子类对象 疑问一:父类引用指向子类对象 与指向父类对象 Animal cat = new Cat(); //向上转型。 父类引用指向子类对象,该引用不能再访问子类新增加的...

architect刘源源
25分钟前
2
0
分而治之-快速排序

快速排序的思想: 快速排序首先在数组中确定1个枢纽项(比如数组中的第一个元素),将大于该枢纽项的元素放到右侧,小于该枢纽项的元素放到左侧,这样枢纽项将数组划分成两部分。接着继续对划...

万山红遍
今天
5
0
Qt编写自定义控件9-导航按钮控件

前言 导航按钮控件,主要用于各种漂亮精美的导航条,我们经常在web中看到导航条都非常精美,都是html+css+js实现的,还自带动画过度效果,Qt提供的qss其实也是无敌的,支持基本上所有的CSS2属...

飞扬青云
今天
4
0
Python开发工具:pyJasper

原文:https://www.oschina.net/p/pyjasper 前言 pyJasper是 JasperReports 网络服务器的 Python 客户端。 pyJasper 是一组 Python 基础工具,可以用来处理 JasperReports 报表 。因为 Jasper...

A_裙232550246
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部