原理:

这两种算法在查找中都较为常见,顺序查找就是从前向后查找匹配,平均查找长度为(1 + N) * N / 2 / N,最终为(N + 1)/2。二分查找是每次折半查找,其实相当于一个平衡二叉树,查找它的叶子的过程。平均查找长度就是约为log2(N + 1) - 1。它的前提必须是顺序存储结构,且是有序数据。开始时设置一个起点和终点,还有中间点,每次取中间点位置的数据与关键字比较,若大于关键字则把起点设置为中间点加一,若小于关键字则把终点设置为中间点减一,若相等则直接返回中间点坐标。

算法:

int low, mid, high;
low = 0, high = Array.length - 1;
while(low <= high){
    mid = (low + high)/2;
    if(Array[mid] > key)
        low = mid + 1;
    else if(Array[mid] == key)
        return mid;
    else
        high = mid - 1;
}//Bisection Search


Read More...

原理:

选择排序的方法比较简单,每次循环一次后,相应位置的数据就是已排序好的数据,每次即可确定相应位置的数据。进行N-1次后,数据有序。具体先是从第一个位置开始,遍历全部数据找出最值,然后记录位置下标,将第一个数据或最后一个数据与之交换。共进行N-1次,达到排序目的。

算法:

int pos;
for(int i = 0;i < Array.length;i++) {
    pos = i;
    for(int j = i + 1;j < Array.length;j++) {
        if(Array[j] < Array[pos])
            pos = j;
    }
    if(pos != i) {
        swap(Array[pos], Array[i]);
    }
}
Read More...

原理:

快速排序是排序中我比较喜欢的一个算法,效率高,十分常用。而且这个算法的思路也十分不错,每一次的遍历就可以排出一个确定其在数据中最终位置的数据,非常适合原始数据就比较无序的情况。以升序排列为例,整体思路是,

  1. 设置两个变量,一个在头,一个在尾,不妨设成start与end。先从数据中选出一个关键数据-pivot(通常把数据中第一个数据就设为关键数据),再从右向左找,end自减,碰到一个比它小的,这时就把关键数据缓存起来,然后把找到的数据放到原关键数据的位置。
  2. 再从新位置start开始向右找,start自增,直到碰到一个比关键数据大的,再把这个数据放到之前的end位置。
  3. 重复向左找和向右找的过程,直到start和end相同,这时就把关键数据放到这个位置,它的左边一定都是比它小的,而右面一定都是比它大的。
  4. 此时完成一个数据的定位,通过递归,再进行此时关键数据左半边的递归,和右半边的递归,最后把全部数据都定位,完成排序。
Read More...

原理:

交换排序也是排序算法的一种,它与插入排序不同的是,它是每次将两个数据进行交换,而不是分成两组,排序组与未排序组。经典的交换排序有快速排序(Quick Sort)和冒泡排序(Bubble Sort),这里先说冒泡排序。冒泡排序是每次排列都会将一个数据按升序或者降序排到最后或者最前面,所以每次排序都会使一个数在最大或者最小的位置。按升序来说,具体是每次让最起始数据与紧挨它后面的数据比较,大的话就交换位置,然后依次执行下去,最终一定会有一个最大的数据排到最后。循环最后, 当数据没有任何交换动作时,说明所有数据排列完毕,退出循环。整个过程像冒泡一样,所以叫冒泡排序。

下面的算法是先让最小的数据到数据的0号初始位置。

Read More...

原理:

希尔排序是直接插入排序的一种改进算法,但更为有效,大体想法就是先将整体数据变得更为有序,使得直接插入时效率更好,最后形成一个有序的整体。这里有一个步长的概念,假设它是dt。我们这里可以把它想成分组,每次都分出来dt个组,然后对每组进行直接插入排序,dt逐渐变小的,变小的方式不固定,通常是以一个数学函数的方式来变小,大多数的就是每次对dt折半,直到dt等于1结束,这就说明最后就变成一个组,而且他相对有序,一次直接插入算法就搞定了。

我们假设一组数据:2,3,5,7,8,9,1,4。按升序排列。

  1. 最开始步长就取长度的一半,4。那分组是怎样分的呢?因为4是步长,所以第一个数据2就和它位置加4的数据,也就是8为同一组。同理,(3, 9),(4, 1),(7, 4)各为一组,然后每组进行一次直接插入排序,所以数据就变成了2,3,1,4,8,9,5,7。
  2. 进行完一次之后就要调整dt的大小,应用一个数学函数,我们这里就把它定位折半,也就是除以2,那么dt就等于2,再以2为步长分组。(3,4,9,7),(2,1,8,5)各为一组,在进行直接插入排序,数据就变成了1,3,2,4,5,7,8,9。看,数据基本已经有序了。我们只需要再来最后一次就可以了。
  3. 继续调整dt大小,dt=dt/2,所以dt等于1,最外层循环终止,所以数据为一个大组,排序后为1,2,3,4,5,7,8。
Read More...

原理:

折半插入排序与直接插入排序有些相似,都有相同的查找后移位操作,不同的是,在寻找移位的位置时,折半插入是用二分法来进行查找,而不是把每个数都进行比较。直接插入排序是将数据分成有序和待排序的两组数据,这里就是用二分法查找有序数据中待排序数据的位置。二分法是,设置一个头坐标,设置一个尾坐标,再设置一个中间值,大小就等于头加尾和的一半,每次用被查找数与数据中中间值位置的数据比较,若小于中间值的数据则将尾坐标设置为中间值减1,反之将头坐标设置为中间值加1。具体二分法在后面查找算法中会提到,这里要注意的是,二分法只适用于已排序的数据。

算法:

int low, mid, high;
for(int i = 2;i < count;i++) {
    low = 1;
    high = i - 1;
    Array[0] = Array[i];
    while(low <= high) {
        mid = (low + high) / 2;
        if(Array[mid] > Array[0])
            high = mid - 1;
        else
            low = mid + 1; 
    }
    for(int j = i;j > high + 1;j--) {
        Array[j] = Array[j - 1];
    }
    Array[j] = Array[0];
}
Read More...

稳定性:

直接插入排序算法(Straight Insertion Sort Algorithm)是一种稳定的排序算法,何为稳定?就是假如被排序数据中有相同值的两个数据单元,在排序后他们的前后关系不改变就是稳定。有的算法就会改变,在后面的算法中将会遇到。

原理:

直接插入排序算法是插入排序算法最基本的一种,它是在每次循环中将未排序的第一个数据直接插入到已排序的数据中,然后依次调整已排序数据的位置,算法较为简单直接。为判断处理越界及不单独另申请内存空间,这里使用“哨兵”来处理。即让Array[0]的位置为哨兵,将每次暂存的数据放到这里,并且在判断越界时也十分巧妙,假设当前判断数据为最小(最大)数据,当他判断到最后一个位置时,它将于自己进行比较,这样必然会不满足条件而退出当前循环。从而省去了每次都要判断是否越界。

因此下例排序为1到N个元素排序,0号元素为哨兵。

算法:

for(int i = 2;i < 100; i++) {
    if(array[i] < array[i - 1]) {
        array[0] = array[i];
        for(int j = i; array[j - 1] > array[0]; j--) {
            array[j] = array[j - 1];
        }
        array[j] = array[0];
    }
}
Read More...